poly2.c
Go to the documentation of this file.
1 /*<html><pre> -<a href="qh-poly.htm"
2  >-------------------------------</a><a name="TOP">-</a>
3 
4  poly2.c
5  implements polygons and simplices
6 
7  see qh-poly.htm, poly.h and libqhull.h
8 
9  frequently used code is in poly.c
10 
11  Copyright (c) 1993-2015 The Geometry Center.
12  $Id: //main/2015/qhull/src/libqhull/poly2.c#11 $$Change: 2069 $
13  $DateTime: 2016/01/18 22:05:03 $$Author: bbarber $
14 */
15 
16 #include "qhull_a.h"
17 
18 /*======== functions in alphabetical order ==========*/
19 
20 /*-<a href="qh-poly.htm#TOC"
21  >-------------------------------</a><a name="addhash">-</a>
22 
23  qh_addhash( newelem, hashtable, hashsize, hash )
24  add newelem to linear hash table at hash if not already there
25 */
26 void qh_addhash(void* newelem, setT *hashtable, int hashsize, int hash) {
27  int scan;
28  void *elem;
29 
30  for (scan= (int)hash; (elem= SETelem_(hashtable, scan));
31  scan= (++scan >= hashsize ? 0 : scan)) {
32  if (elem == newelem)
33  break;
34  }
35  /* loop terminates because qh_HASHfactor >= 1.1 by qh_initbuffers */
36  if (!elem)
37  SETelem_(hashtable, scan)= newelem;
38 } /* addhash */
39 
40 /*-<a href="qh-poly.htm#TOC"
41  >-------------------------------</a><a name="check_bestdist">-</a>
42 
43  qh_check_bestdist()
44  check that all points are within max_outside of the nearest facet
45  if qh.ONLYgood,
46  ignores !good facets
47 
48  see:
49  qh_check_maxout(), qh_outerinner()
50 
51  notes:
52  only called from qh_check_points()
53  seldom used since qh.MERGING is almost always set
54  if notverified>0 at end of routine
55  some points were well inside the hull. If the hull contains
56  a lens-shaped component, these points were not verified. Use
57  options 'Qi Tv' to verify all points. (Exhaustive check also verifies)
58 
59  design:
60  determine facet for each point (if any)
61  for each point
62  start with the assigned facet or with the first facet
63  find the best facet for the point and check all coplanar facets
64  error if point is outside of facet
65 */
66 void qh_check_bestdist(void) {
67  boolT waserror= False, unassigned;
68  facetT *facet, *bestfacet, *errfacet1= NULL, *errfacet2= NULL;
69  facetT *facetlist;
70  realT dist, maxoutside, maxdist= -REALmax;
71  pointT *point;
72  int numpart= 0, facet_i, facet_n, notgood= 0, notverified= 0;
73  setT *facets;
74 
75  trace1((qh ferr, 1020, "qh_check_bestdist: check points below nearest facet. Facet_list f%d\n",
76  qh facet_list->id));
77  maxoutside= qh_maxouter();
78  maxoutside += qh DISTround;
79  /* one more qh.DISTround for check computation */
80  trace1((qh ferr, 1021, "qh_check_bestdist: check that all points are within %2.2g of best facet\n", maxoutside));
81  facets= qh_pointfacet(/*qh.facet_list*/);
82  if (!qh_QUICKhelp && qh PRINTprecision)
83  qh_fprintf(qh ferr, 8091, "\n\
84 qhull output completed. Verifying that %d points are\n\
85 below %2.2g of the nearest %sfacet.\n",
86  qh_setsize(facets), maxoutside, (qh ONLYgood ? "good " : ""));
87  FOREACHfacet_i_(facets) { /* for each point with facet assignment */
88  if (facet)
89  unassigned= False;
90  else {
91  unassigned= True;
92  facet= qh facet_list;
93  }
94  point= qh_point(facet_i);
95  if (point == qh GOODpointp)
96  continue;
97  qh_distplane(point, facet, &dist);
98  numpart++;
99  bestfacet= qh_findbesthorizon(!qh_IScheckmax, point, facet, qh_NOupper, &dist, &numpart);
100  /* occurs after statistics reported */
101  maximize_(maxdist, dist);
102  if (dist > maxoutside) {
103  if (qh ONLYgood && !bestfacet->good
104  && !((bestfacet= qh_findgooddist(point, bestfacet, &dist, &facetlist))
105  && dist > maxoutside))
106  notgood++;
107  else {
108  waserror= True;
109  qh_fprintf(qh ferr, 6109, "qhull precision error: point p%d is outside facet f%d, distance= %6.8g maxoutside= %6.8g\n",
110  facet_i, bestfacet->id, dist, maxoutside);
111  if (errfacet1 != bestfacet) {
112  errfacet2= errfacet1;
113  errfacet1= bestfacet;
114  }
115  }
116  }else if (unassigned && dist < -qh MAXcoplanar)
117  notverified++;
118  }
119  qh_settempfree(&facets);
120  if (notverified && !qh DELAUNAY && !qh_QUICKhelp && qh PRINTprecision)
121  qh_fprintf(qh ferr, 8092, "\n%d points were well inside the hull. If the hull contains\n\
122 a lens-shaped component, these points were not verified. Use\n\
123 options 'Qci Tv' to verify all points.\n", notverified);
124  if (maxdist > qh outside_err) {
125  qh_fprintf(qh ferr, 6110, "qhull precision error (qh_check_bestdist): a coplanar point is %6.2g from convex hull. The maximum value(qh.outside_err) is %6.2g\n",
126  maxdist, qh outside_err);
127  qh_errexit2(qh_ERRprec, errfacet1, errfacet2);
128  }else if (waserror && qh outside_err > REALmax/2)
129  qh_errexit2(qh_ERRprec, errfacet1, errfacet2);
130  /* else if waserror, the error was logged to qh.ferr but does not effect the output */
131  trace0((qh ferr, 20, "qh_check_bestdist: max distance outside %2.2g\n", maxdist));
132 } /* check_bestdist */
133 
134 /*-<a href="qh-poly.htm#TOC"
135  >-------------------------------</a><a name="check_dupridge">-</a>
136 
137  qh_check_dupridge(facet1, dist1, facet2, dist2)
138  Check duplicate ridge between facet1 and facet2 for wide merge
139  dist1 is the maximum distance of facet1's vertices to facet2
140  dist2 is the maximum distance of facet2's vertices to facet1
141 
142  Returns
143  Level 1 log of the duplicate ridge with the minimum distance between vertices
144  Throws error if the merge will increase the maximum facet width by qh_WIDEduplicate (100x)
145 
146  called from:
147  qh_forcedmerges()
148 */
149 #ifndef qh_NOmerge
150 void qh_check_dupridge(facetT *facet1, realT dist1, facetT *facet2, realT dist2) {
151  vertexT *vertex, **vertexp, *vertexA, **vertexAp;
152  realT dist, innerplane, mergedist, outerplane, prevdist, ratio;
153  realT minvertex= REALmax;
154 
155  mergedist= fmin_(dist1, dist2);
156  qh_outerinner(NULL, &outerplane, &innerplane); /* ratio from qh_printsummary */
157  prevdist= fmax_(outerplane, innerplane);
158  maximize_(prevdist, qh ONEmerge + qh DISTround);
159  maximize_(prevdist, qh MINoutside + qh DISTround);
160  ratio= mergedist/prevdist;
161  FOREACHvertex_(facet1->vertices) { /* The duplicate ridge is between facet1 and facet2, so either facet can be tested */
162  FOREACHvertexA_(facet1->vertices) {
163  if (vertex > vertexA){ /* Test each pair once */
164  dist= qh_pointdist(vertex->point, vertexA->point, qh hull_dim);
165  minimize_(minvertex, dist);
166  }
167  }
168  }
169  trace0((qh ferr, 16, "qh_check_dupridge: duplicate ridge between f%d and f%d due to nearly-coincident vertices (%2.2g), dist %2.2g, reverse dist %2.2g, ratio %2.2g while processing p%d\n",
170  facet1->id, facet2->id, minvertex, dist1, dist2, ratio, qh furthest_id));
171  if (ratio > qh_WIDEduplicate) {
172  qh_fprintf(qh ferr, 6271, "qhull precision error (qh_check_dupridge): wide merge (%.0f times wider) due to duplicate ridge with nearly coincident points (%2.2g) between f%d and f%d, merge dist %2.2g, while processing p%d\n- Ignore error with option 'Q12'\n- To be fixed in a later version of Qhull\n",
173  ratio, minvertex, facet1->id, facet2->id, mergedist, qh furthest_id);
174  if (qh DELAUNAY)
175  qh_fprintf(qh ferr, 8145, "- A bounding box for the input sites may alleviate this error.\n");
176  if(minvertex > qh_WIDEduplicate*prevdist)
177  qh_fprintf(qh ferr, 8146, "- Vertex distance %2.2g is greater than %d times maximum distance %2.2g\n Please report to bradb@shore.net with steps to reproduce and all output\n",
178  minvertex, qh_WIDEduplicate, prevdist);
179  if (!qh NOwide)
180  qh_errexit2(qh_ERRqhull, facet1, facet2);
181  }
182 } /* check_dupridge */
183 #endif
184 
185 /*-<a href="qh-poly.htm#TOC"
186  >-------------------------------</a><a name="check_maxout">-</a>
187 
188  qh_check_maxout()
189  updates qh.max_outside by checking all points against bestfacet
190  if qh.ONLYgood, ignores !good facets
191 
192  returns:
193  updates facet->maxoutside via qh_findbesthorizon()
194  sets qh.maxoutdone
195  if printing qh.min_vertex (qh_outerinner),
196  it is updated to the current vertices
197  removes inside/coplanar points from coplanarset as needed
198 
199  notes:
200  defines coplanar as min_vertex instead of MAXcoplanar
201  may not need to check near-inside points because of qh.MAXcoplanar
202  and qh.KEEPnearinside (before it was -DISTround)
203 
204  see also:
205  qh_check_bestdist()
206 
207  design:
208  if qh.min_vertex is needed
209  for all neighbors of all vertices
210  test distance from vertex to neighbor
211  determine facet for each point (if any)
212  for each point with an assigned facet
213  find the best facet for the point and check all coplanar facets
214  (updates outer planes)
215  remove near-inside points from coplanar sets
216 */
217 #ifndef qh_NOmerge
218 void qh_check_maxout(void) {
219  facetT *facet, *bestfacet, *neighbor, **neighborp, *facetlist;
220  realT dist, maxoutside, minvertex, old_maxoutside;
221  pointT *point;
222  int numpart= 0, facet_i, facet_n, notgood= 0;
223  setT *facets, *vertices;
224  vertexT *vertex;
225 
226  trace1((qh ferr, 1022, "qh_check_maxout: check and update maxoutside for each facet.\n"));
227  maxoutside= minvertex= 0;
228  if (qh VERTEXneighbors
229  && (qh PRINTsummary || qh KEEPinside || qh KEEPcoplanar
230  || qh TRACElevel || qh PRINTstatistics
231  || qh PRINTout[0] == qh_PRINTsummary || qh PRINTout[0] == qh_PRINTnone)) {
232  trace1((qh ferr, 1023, "qh_check_maxout: determine actual maxoutside and minvertex\n"));
233  vertices= qh_pointvertex(/*qh.facet_list*/);
234  FORALLvertices {
235  FOREACHneighbor_(vertex) {
236  zinc_(Zdistvertex); /* distance also computed by main loop below */
237  qh_distplane(vertex->point, neighbor, &dist);
238  minimize_(minvertex, dist);
239  if (-dist > qh TRACEdist || dist > qh TRACEdist
240  || neighbor == qh tracefacet || vertex == qh tracevertex)
241  qh_fprintf(qh ferr, 8093, "qh_check_maxout: p%d(v%d) is %.2g from f%d\n",
242  qh_pointid(vertex->point), vertex->id, dist, neighbor->id);
243  }
244  }
245  if (qh MERGING) {
246  wmin_(Wminvertex, qh min_vertex);
247  }
248  qh min_vertex= minvertex;
249  qh_settempfree(&vertices);
250  }
251  facets= qh_pointfacet(/*qh.facet_list*/);
252  do {
253  old_maxoutside= fmax_(qh max_outside, maxoutside);
254  FOREACHfacet_i_(facets) { /* for each point with facet assignment */
255  if (facet) {
256  point= qh_point(facet_i);
257  if (point == qh GOODpointp)
258  continue;
259  zzinc_(Ztotcheck);
260  qh_distplane(point, facet, &dist);
261  numpart++;
262  bestfacet= qh_findbesthorizon(qh_IScheckmax, point, facet, !qh_NOupper, &dist, &numpart);
263  if (bestfacet && dist > maxoutside) {
264  if (qh ONLYgood && !bestfacet->good
265  && !((bestfacet= qh_findgooddist(point, bestfacet, &dist, &facetlist))
266  && dist > maxoutside))
267  notgood++;
268  else
269  maxoutside= dist;
270  }
271  if (dist > qh TRACEdist || (bestfacet && bestfacet == qh tracefacet))
272  qh_fprintf(qh ferr, 8094, "qh_check_maxout: p%d is %.2g above f%d\n",
273  qh_pointid(point), dist, (bestfacet ? bestfacet->id : UINT_MAX));
274  }
275  }
276  }while
277  (maxoutside > 2*old_maxoutside);
278  /* if qh.maxoutside increases substantially, qh_SEARCHdist is not valid
279  e.g., RBOX 5000 s Z1 G1e-13 t1001200614 | qhull */
280  zzadd_(Zcheckpart, numpart);
281  qh_settempfree(&facets);
282  wval_(Wmaxout)= maxoutside - qh max_outside;
283  wmax_(Wmaxoutside, qh max_outside);
284  qh max_outside= maxoutside;
285  qh_nearcoplanar(/*qh.facet_list*/);
286  qh maxoutdone= True;
287  trace1((qh ferr, 1024, "qh_check_maxout: maxoutside %2.2g, min_vertex %2.2g, outside of not good %d\n",
288  maxoutside, qh min_vertex, notgood));
289 } /* check_maxout */
290 #else /* qh_NOmerge */
291 void qh_check_maxout(void) {
292 }
293 #endif
294 
295 /*-<a href="qh-poly.htm#TOC"
296  >-------------------------------</a><a name="check_output">-</a>
297 
298  qh_check_output()
299  performs the checks at the end of qhull algorithm
300  Maybe called after voronoi output. Will recompute otherwise centrums are Voronoi centers instead
301 */
302 void qh_check_output(void) {
303  int i;
304 
305  if (qh STOPcone)
306  return;
307  if (qh VERIFYoutput | qh IStracing | qh CHECKfrequently) {
308  qh_checkpolygon(qh facet_list);
309  qh_checkflipped_all(qh facet_list);
310  qh_checkconvex(qh facet_list, qh_ALGORITHMfault);
311  }else if (!qh MERGING && qh_newstats(qhstat precision, &i)) {
312  qh_checkflipped_all(qh facet_list);
313  qh_checkconvex(qh facet_list, qh_ALGORITHMfault);
314  }
315 } /* check_output */
316 
317 
318 
319 /*-<a href="qh-poly.htm#TOC"
320  >-------------------------------</a><a name="check_point">-</a>
321 
322  qh_check_point( point, facet, maxoutside, maxdist, errfacet1, errfacet2 )
323  check that point is less than maxoutside from facet
324 */
325 void qh_check_point(pointT *point, facetT *facet, realT *maxoutside, realT *maxdist, facetT **errfacet1, facetT **errfacet2) {
326  realT dist;
327 
328  /* occurs after statistics reported */
329  qh_distplane(point, facet, &dist);
330  if (dist > *maxoutside) {
331  if (*errfacet1 != facet) {
332  *errfacet2= *errfacet1;
333  *errfacet1= facet;
334  }
335  qh_fprintf(qh ferr, 6111, "qhull precision error: point p%d is outside facet f%d, distance= %6.8g maxoutside= %6.8g\n",
336  qh_pointid(point), facet->id, dist, *maxoutside);
337  }
338  maximize_(*maxdist, dist);
339 } /* qh_check_point */
340 
341 
342 /*-<a href="qh-poly.htm#TOC"
343  >-------------------------------</a><a name="check_points">-</a>
344 
345  qh_check_points()
346  checks that all points are inside all facets
347 
348  notes:
349  if many points and qh_check_maxout not called (i.e., !qh.MERGING),
350  calls qh_findbesthorizon (seldom done).
351  ignores flipped facets
352  maxoutside includes 2 qh.DISTrounds
353  one qh.DISTround for the computed distances in qh_check_points
354  qh_printafacet and qh_printsummary needs only one qh.DISTround
355  the computation for qh.VERIFYdirect does not account for qh.other_points
356 
357  design:
358  if many points
359  use qh_check_bestdist()
360  else
361  for all facets
362  for all points
363  check that point is inside facet
364 */
365 void qh_check_points(void) {
366  facetT *facet, *errfacet1= NULL, *errfacet2= NULL;
367  realT total, maxoutside, maxdist= -REALmax;
368  pointT *point, **pointp, *pointtemp;
369  boolT testouter;
370 
371  maxoutside= qh_maxouter();
372  maxoutside += qh DISTround;
373  /* one more qh.DISTround for check computation */
374  trace1((qh ferr, 1025, "qh_check_points: check all points below %2.2g of all facet planes\n",
375  maxoutside));
376  if (qh num_good) /* miss counts other_points and !good facets */
377  total= (float)qh num_good * (float)qh num_points;
378  else
379  total= (float)qh num_facets * (float)qh num_points;
380  if (total >= qh_VERIFYdirect && !qh maxoutdone) {
381  if (!qh_QUICKhelp && qh SKIPcheckmax && qh MERGING)
382  qh_fprintf(qh ferr, 7075, "qhull input warning: merging without checking outer planes('Q5' or 'Po').\n\
383 Verify may report that a point is outside of a facet.\n");
384  qh_check_bestdist();
385  }else {
386  if (qh_MAXoutside && qh maxoutdone)
387  testouter= True;
388  else
389  testouter= False;
390  if (!qh_QUICKhelp) {
391  if (qh MERGEexact)
392  qh_fprintf(qh ferr, 7076, "qhull input warning: exact merge ('Qx'). Verify may report that a point\n\
393 is outside of a facet. See qh-optq.htm#Qx\n");
394  else if (qh SKIPcheckmax || qh NOnearinside)
395  qh_fprintf(qh ferr, 7077, "qhull input warning: no outer plane check ('Q5') or no processing of\n\
396 near-inside points ('Q8'). Verify may report that a point is outside\n\
397 of a facet.\n");
398  }
399  if (qh PRINTprecision) {
400  if (testouter)
401  qh_fprintf(qh ferr, 8098, "\n\
402 Output completed. Verifying that all points are below outer planes of\n\
403 all %sfacets. Will make %2.0f distance computations.\n",
404  (qh ONLYgood ? "good " : ""), total);
405  else
406  qh_fprintf(qh ferr, 8099, "\n\
407 Output completed. Verifying that all points are below %2.2g of\n\
408 all %sfacets. Will make %2.0f distance computations.\n",
409  maxoutside, (qh ONLYgood ? "good " : ""), total);
410  }
411  FORALLfacets {
412  if (!facet->good && qh ONLYgood)
413  continue;
414  if (facet->flipped)
415  continue;
416  if (!facet->normal) {
417  qh_fprintf(qh ferr, 7061, "qhull warning (qh_check_points): missing normal for facet f%d\n", facet->id);
418  continue;
419  }
420  if (testouter) {
421 #if qh_MAXoutside
422  maxoutside= facet->maxoutside + 2* qh DISTround;
423  /* one DISTround to actual point and another to computed point */
424 #endif
425  }
426  FORALLpoints {
427  if (point != qh GOODpointp)
428  qh_check_point(point, facet, &maxoutside, &maxdist, &errfacet1, &errfacet2);
429  }
430  FOREACHpoint_(qh other_points) {
431  if (point != qh GOODpointp)
432  qh_check_point(point, facet, &maxoutside, &maxdist, &errfacet1, &errfacet2);
433  }
434  }
435  if (maxdist > qh outside_err) {
436  qh_fprintf(qh ferr, 6112, "qhull precision error (qh_check_points): a coplanar point is %6.2g from convex hull. The maximum value(qh.outside_err) is %6.2g\n",
437  maxdist, qh outside_err );
438  qh_errexit2( qh_ERRprec, errfacet1, errfacet2 );
439  }else if (errfacet1 && qh outside_err > REALmax/2)
440  qh_errexit2( qh_ERRprec, errfacet1, errfacet2 );
441  /* else if errfacet1, the error was logged to qh.ferr but does not effect the output */
442  trace0((qh ferr, 21, "qh_check_points: max distance outside %2.2g\n", maxdist));
443  }
444 } /* check_points */
445 
446 
447 /*-<a href="qh-poly.htm#TOC"
448  >-------------------------------</a><a name="checkconvex">-</a>
449 
450  qh_checkconvex( facetlist, fault )
451  check that each ridge in facetlist is convex
452  fault = qh_DATAfault if reporting errors
453  = qh_ALGORITHMfault otherwise
454 
455  returns:
456  counts Zconcaveridges and Zcoplanarridges
457  errors if concaveridge or if merging an coplanar ridge
458 
459  note:
460  if not merging,
461  tests vertices for neighboring simplicial facets
462  else if ZEROcentrum,
463  tests vertices for neighboring simplicial facets
464  else
465  tests centrums of neighboring facets
466 
467  design:
468  for all facets
469  report flipped facets
470  if ZEROcentrum and simplicial neighbors
471  test vertices for neighboring simplicial facets
472  else
473  test centrum against all neighbors
474 */
475 void qh_checkconvex(facetT *facetlist, int fault) {
476  facetT *facet, *neighbor, **neighborp, *errfacet1=NULL, *errfacet2=NULL;
477  vertexT *vertex;
478  realT dist;
479  pointT *centrum;
480  boolT waserror= False, centrum_warning= False, tempcentrum= False, allsimplicial;
481  int neighbor_i;
482 
483  trace1((qh ferr, 1026, "qh_checkconvex: check all ridges are convex\n"));
484  if (!qh RERUN) {
485  zzval_(Zconcaveridges)= 0;
486  zzval_(Zcoplanarridges)= 0;
487  }
488  FORALLfacet_(facetlist) {
489  if (facet->flipped) {
490  qh_precision("flipped facet");
491  qh_fprintf(qh ferr, 6113, "qhull precision error: f%d is flipped(interior point is outside)\n",
492  facet->id);
493  errfacet1= facet;
494  waserror= True;
495  continue;
496  }
497  if (qh MERGING && (!qh ZEROcentrum || !facet->simplicial || facet->tricoplanar))
498  allsimplicial= False;
499  else {
500  allsimplicial= True;
501  neighbor_i= 0;
502  FOREACHneighbor_(facet) {
503  vertex= SETelemt_(facet->vertices, neighbor_i++, vertexT);
504  if (!neighbor->simplicial || neighbor->tricoplanar) {
505  allsimplicial= False;
506  continue;
507  }
508  qh_distplane(vertex->point, neighbor, &dist);
509  if (dist > -qh DISTround) {
510  if (fault == qh_DATAfault) {
511  qh_precision("coplanar or concave ridge");
512  qh_fprintf(qh ferr, 6114, "qhull precision error: initial simplex is not convex. Distance=%.2g\n", dist);
513  qh_errexit(qh_ERRsingular, NULL, NULL);
514  }
515  if (dist > qh DISTround) {
516  zzinc_(Zconcaveridges);
517  qh_precision("concave ridge");
518  qh_fprintf(qh ferr, 6115, "qhull precision error: f%d is concave to f%d, since p%d(v%d) is %6.4g above\n",
519  facet->id, neighbor->id, qh_pointid(vertex->point), vertex->id, dist);
520  errfacet1= facet;
521  errfacet2= neighbor;
522  waserror= True;
523  }else if (qh ZEROcentrum) {
524  if (dist > 0) { /* qh_checkzero checks that dist < - qh DISTround */
525  zzinc_(Zcoplanarridges);
526  qh_precision("coplanar ridge");
527  qh_fprintf(qh ferr, 6116, "qhull precision error: f%d is clearly not convex to f%d, since p%d(v%d) is %6.4g above\n",
528  facet->id, neighbor->id, qh_pointid(vertex->point), vertex->id, dist);
529  errfacet1= facet;
530  errfacet2= neighbor;
531  waserror= True;
532  }
533  }else {
534  zzinc_(Zcoplanarridges);
535  qh_precision("coplanar ridge");
536  trace0((qh ferr, 22, "qhull precision error: f%d may be coplanar to f%d, since p%d(v%d) is within %6.4g during p%d\n",
537  facet->id, neighbor->id, qh_pointid(vertex->point), vertex->id, dist, qh furthest_id));
538  }
539  }
540  }
541  }
542  if (!allsimplicial) {
543  if (qh CENTERtype == qh_AScentrum) {
544  if (!facet->center)
545  facet->center= qh_getcentrum(facet);
546  centrum= facet->center;
547  }else {
548  if (!centrum_warning && (!facet->simplicial || facet->tricoplanar)) {
549  centrum_warning= True;
550  qh_fprintf(qh ferr, 7062, "qhull warning: recomputing centrums for convexity test. This may lead to false, precision errors.\n");
551  }
552  centrum= qh_getcentrum(facet);
553  tempcentrum= True;
554  }
555  FOREACHneighbor_(facet) {
556  if (qh ZEROcentrum && facet->simplicial && neighbor->simplicial)
557  continue;
558  if (facet->tricoplanar || neighbor->tricoplanar)
559  continue;
560  zzinc_(Zdistconvex);
561  qh_distplane(centrum, neighbor, &dist);
562  if (dist > qh DISTround) {
563  zzinc_(Zconcaveridges);
564  qh_precision("concave ridge");
565  qh_fprintf(qh ferr, 6117, "qhull precision error: f%d is concave to f%d. Centrum of f%d is %6.4g above f%d\n",
566  facet->id, neighbor->id, facet->id, dist, neighbor->id);
567  errfacet1= facet;
568  errfacet2= neighbor;
569  waserror= True;
570  }else if (dist >= 0.0) { /* if arithmetic always rounds the same,
571  can test against centrum radius instead */
572  zzinc_(Zcoplanarridges);
573  qh_precision("coplanar ridge");
574  qh_fprintf(qh ferr, 6118, "qhull precision error: f%d is coplanar or concave to f%d. Centrum of f%d is %6.4g above f%d\n",
575  facet->id, neighbor->id, facet->id, dist, neighbor->id);
576  errfacet1= facet;
577  errfacet2= neighbor;
578  waserror= True;
579  }
580  }
581  if (tempcentrum)
582  qh_memfree(centrum, qh normal_size);
583  }
584  }
585  if (waserror && !qh FORCEoutput)
586  qh_errexit2(qh_ERRprec, errfacet1, errfacet2);
587 } /* checkconvex */
588 
589 
590 /*-<a href="qh-poly.htm#TOC"
591  >-------------------------------</a><a name="checkfacet">-</a>
592 
593  qh_checkfacet( facet, newmerge, waserror )
594  checks for consistency errors in facet
595  newmerge set if from merge.c
596 
597  returns:
598  sets waserror if any error occurs
599 
600  checks:
601  vertex ids are inverse sorted
602  unless newmerge, at least hull_dim neighbors and vertices (exactly if simplicial)
603  if non-simplicial, at least as many ridges as neighbors
604  neighbors are not duplicated
605  ridges are not duplicated
606  in 3-d, ridges=verticies
607  (qh.hull_dim-1) ridge vertices
608  neighbors are reciprocated
609  ridge neighbors are facet neighbors and a ridge for every neighbor
610  simplicial neighbors match facetintersect
611  vertex intersection matches vertices of common ridges
612  vertex neighbors and facet vertices agree
613  all ridges have distinct vertex sets
614 
615  notes:
616  uses neighbor->seen
617 
618  design:
619  check sets
620  check vertices
621  check sizes of neighbors and vertices
622  check for qh_MERGEridge and qh_DUPLICATEridge flags
623  check neighbor set
624  check ridge set
625  check ridges, neighbors, and vertices
626 */
627 void qh_checkfacet(facetT *facet, boolT newmerge, boolT *waserrorp) {
628  facetT *neighbor, **neighborp, *errother=NULL;
629  ridgeT *ridge, **ridgep, *errridge= NULL, *ridge2;
630  vertexT *vertex, **vertexp;
631  unsigned previousid= INT_MAX;
632  int numneighbors, numvertices, numridges=0, numRvertices=0;
633  boolT waserror= False;
634  int skipA, skipB, ridge_i, ridge_n, i;
635  setT *intersection;
636 
637  if (facet->visible) {
638  qh_fprintf(qh ferr, 6119, "qhull internal error (qh_checkfacet): facet f%d is on the visible_list\n",
639  facet->id);
640  qh_errexit(qh_ERRqhull, facet, NULL);
641  }
642  if (!facet->normal) {
643  qh_fprintf(qh ferr, 6120, "qhull internal error (qh_checkfacet): facet f%d does not have a normal\n",
644  facet->id);
645  waserror= True;
646  }
647  qh_setcheck(facet->vertices, "vertices for f", facet->id);
648  qh_setcheck(facet->ridges, "ridges for f", facet->id);
649  qh_setcheck(facet->outsideset, "outsideset for f", facet->id);
650  qh_setcheck(facet->coplanarset, "coplanarset for f", facet->id);
651  qh_setcheck(facet->neighbors, "neighbors for f", facet->id);
652  FOREACHvertex_(facet->vertices) {
653  if (vertex->deleted) {
654  qh_fprintf(qh ferr, 6121, "qhull internal error (qh_checkfacet): deleted vertex v%d in f%d\n", vertex->id, facet->id);
655  qh_errprint("ERRONEOUS", NULL, NULL, NULL, vertex);
656  waserror= True;
657  }
658  if (vertex->id >= previousid) {
659  qh_fprintf(qh ferr, 6122, "qhull internal error (qh_checkfacet): vertices of f%d are not in descending id order at v%d\n", facet->id, vertex->id);
660  waserror= True;
661  break;
662  }
663  previousid= vertex->id;
664  }
665  numneighbors= qh_setsize(facet->neighbors);
666  numvertices= qh_setsize(facet->vertices);
667  numridges= qh_setsize(facet->ridges);
668  if (facet->simplicial) {
669  if (numvertices+numneighbors != 2*qh hull_dim
670  && !facet->degenerate && !facet->redundant) {
671  qh_fprintf(qh ferr, 6123, "qhull internal error (qh_checkfacet): for simplicial facet f%d, #vertices %d + #neighbors %d != 2*qh hull_dim\n",
672  facet->id, numvertices, numneighbors);
673  qh_setprint(qh ferr, "", facet->neighbors);
674  waserror= True;
675  }
676  }else { /* non-simplicial */
677  if (!newmerge
678  &&(numvertices < qh hull_dim || numneighbors < qh hull_dim)
679  && !facet->degenerate && !facet->redundant) {
680  qh_fprintf(qh ferr, 6124, "qhull internal error (qh_checkfacet): for facet f%d, #vertices %d or #neighbors %d < qh hull_dim\n",
681  facet->id, numvertices, numneighbors);
682  waserror= True;
683  }
684  /* in 3-d, can get a vertex twice in an edge list, e.g., RBOX 1000 s W1e-13 t995849315 D2 | QHULL d Tc Tv TP624 TW1e-13 T4 */
685  if (numridges < numneighbors
686  ||(qh hull_dim == 3 && numvertices > numridges && !qh NEWfacets)
687  ||(qh hull_dim == 2 && numridges + numvertices + numneighbors != 6)) {
688  if (!facet->degenerate && !facet->redundant) {
689  qh_fprintf(qh ferr, 6125, "qhull internal error (qh_checkfacet): for facet f%d, #ridges %d < #neighbors %d or(3-d) > #vertices %d or(2-d) not all 2\n",
690  facet->id, numridges, numneighbors, numvertices);
691  waserror= True;
692  }
693  }
694  }
695  FOREACHneighbor_(facet) {
696  if (neighbor == qh_MERGEridge || neighbor == qh_DUPLICATEridge) {
697  qh_fprintf(qh ferr, 6126, "qhull internal error (qh_checkfacet): facet f%d still has a MERGE or DUP neighbor\n", facet->id);
698  qh_errexit(qh_ERRqhull, facet, NULL);
699  }
700  neighbor->seen= True;
701  }
702  FOREACHneighbor_(facet) {
703  if (!qh_setin(neighbor->neighbors, facet)) {
704  qh_fprintf(qh ferr, 6127, "qhull internal error (qh_checkfacet): facet f%d has neighbor f%d, but f%d does not have neighbor f%d\n",
705  facet->id, neighbor->id, neighbor->id, facet->id);
706  errother= neighbor;
707  waserror= True;
708  }
709  if (!neighbor->seen) {
710  qh_fprintf(qh ferr, 6128, "qhull internal error (qh_checkfacet): facet f%d has a duplicate neighbor f%d\n",
711  facet->id, neighbor->id);
712  errother= neighbor;
713  waserror= True;
714  }
715  neighbor->seen= False;
716  }
717  FOREACHridge_(facet->ridges) {
718  qh_setcheck(ridge->vertices, "vertices for r", ridge->id);
719  ridge->seen= False;
720  }
721  FOREACHridge_(facet->ridges) {
722  if (ridge->seen) {
723  qh_fprintf(qh ferr, 6129, "qhull internal error (qh_checkfacet): facet f%d has a duplicate ridge r%d\n",
724  facet->id, ridge->id);
725  errridge= ridge;
726  waserror= True;
727  }
728  ridge->seen= True;
729  numRvertices= qh_setsize(ridge->vertices);
730  if (numRvertices != qh hull_dim - 1) {
731  qh_fprintf(qh ferr, 6130, "qhull internal error (qh_checkfacet): ridge between f%d and f%d has %d vertices\n",
732  ridge->top->id, ridge->bottom->id, numRvertices);
733  errridge= ridge;
734  waserror= True;
735  }
736  neighbor= otherfacet_(ridge, facet);
737  neighbor->seen= True;
738  if (!qh_setin(facet->neighbors, neighbor)) {
739  qh_fprintf(qh ferr, 6131, "qhull internal error (qh_checkfacet): for facet f%d, neighbor f%d of ridge r%d not in facet\n",
740  facet->id, neighbor->id, ridge->id);
741  errridge= ridge;
742  waserror= True;
743  }
744  }
745  if (!facet->simplicial) {
746  FOREACHneighbor_(facet) {
747  if (!neighbor->seen) {
748  qh_fprintf(qh ferr, 6132, "qhull internal error (qh_checkfacet): facet f%d does not have a ridge for neighbor f%d\n",
749  facet->id, neighbor->id);
750  errother= neighbor;
751  waserror= True;
752  }
753  intersection= qh_vertexintersect_new(facet->vertices, neighbor->vertices);
754  qh_settemppush(intersection);
755  FOREACHvertex_(facet->vertices) {
756  vertex->seen= False;
757  vertex->seen2= False;
758  }
759  FOREACHvertex_(intersection)
760  vertex->seen= True;
761  FOREACHridge_(facet->ridges) {
762  if (neighbor != otherfacet_(ridge, facet))
763  continue;
764  FOREACHvertex_(ridge->vertices) {
765  if (!vertex->seen) {
766  qh_fprintf(qh ferr, 6133, "qhull internal error (qh_checkfacet): vertex v%d in r%d not in f%d intersect f%d\n",
767  vertex->id, ridge->id, facet->id, neighbor->id);
768  qh_errexit(qh_ERRqhull, facet, ridge);
769  }
770  vertex->seen2= True;
771  }
772  }
773  if (!newmerge) {
774  FOREACHvertex_(intersection) {
775  if (!vertex->seen2) {
776  if (qh IStracing >=3 || !qh MERGING) {
777  qh_fprintf(qh ferr, 6134, "qhull precision error (qh_checkfacet): vertex v%d in f%d intersect f%d but\n\
778  not in a ridge. This is ok under merging. Last point was p%d\n",
779  vertex->id, facet->id, neighbor->id, qh furthest_id);
780  if (!qh FORCEoutput && !qh MERGING) {
781  qh_errprint("ERRONEOUS", facet, neighbor, NULL, vertex);
782  if (!qh MERGING)
783  qh_errexit(qh_ERRqhull, NULL, NULL);
784  }
785  }
786  }
787  }
788  }
789  qh_settempfree(&intersection);
790  }
791  }else { /* simplicial */
792  FOREACHneighbor_(facet) {
793  if (neighbor->simplicial) {
794  skipA= SETindex_(facet->neighbors, neighbor);
795  skipB= qh_setindex(neighbor->neighbors, facet);
796  if (skipA<0 || skipB<0 || !qh_setequal_skip(facet->vertices, skipA, neighbor->vertices, skipB)) {
797  qh_fprintf(qh ferr, 6135, "qhull internal error (qh_checkfacet): facet f%d skip %d and neighbor f%d skip %d do not match \n",
798  facet->id, skipA, neighbor->id, skipB);
799  errother= neighbor;
800  waserror= True;
801  }
802  }
803  }
804  }
805  if (qh hull_dim < 5 && (qh IStracing > 2 || qh CHECKfrequently)) {
806  FOREACHridge_i_(facet->ridges) { /* expensive */
807  for (i=ridge_i+1; i < ridge_n; i++) {
808  ridge2= SETelemt_(facet->ridges, i, ridgeT);
809  if (qh_setequal(ridge->vertices, ridge2->vertices)) {
810  qh_fprintf(qh ferr, 6227, "Qhull internal error (qh_checkfacet): ridges r%d and r%d have the same vertices\n",
811  ridge->id, ridge2->id);
812  errridge= ridge;
813  waserror= True;
814  }
815  }
816  }
817  }
818  if (waserror) {
819  qh_errprint("ERRONEOUS", facet, errother, errridge, NULL);
820  *waserrorp= True;
821  }
822 } /* checkfacet */
823 
824 
825 /*-<a href="qh-poly.htm#TOC"
826  >-------------------------------</a><a name="checkflipped_all">-</a>
827 
828  qh_checkflipped_all( facetlist )
829  checks orientation of facets in list against interior point
830 */
831 void qh_checkflipped_all(facetT *facetlist) {
832  facetT *facet;
833  boolT waserror= False;
834  realT dist;
835 
836  if (facetlist == qh facet_list)
837  zzval_(Zflippedfacets)= 0;
838  FORALLfacet_(facetlist) {
839  if (facet->normal && !qh_checkflipped(facet, &dist, !qh_ALL)) {
840  qh_fprintf(qh ferr, 6136, "qhull precision error: facet f%d is flipped, distance= %6.12g\n",
841  facet->id, dist);
842  if (!qh FORCEoutput) {
843  qh_errprint("ERRONEOUS", facet, NULL, NULL, NULL);
844  waserror= True;
845  }
846  }
847  }
848  if (waserror) {
849  qh_fprintf(qh ferr, 8101, "\n\
850 A flipped facet occurs when its distance to the interior point is\n\
851 greater than %2.2g, the maximum roundoff error.\n", -qh DISTround);
852  qh_errexit(qh_ERRprec, NULL, NULL);
853  }
854 } /* checkflipped_all */
855 
856 /*-<a href="qh-poly.htm#TOC"
857  >-------------------------------</a><a name="checkpolygon">-</a>
858 
859  qh_checkpolygon( facetlist )
860  checks the correctness of the structure
861 
862  notes:
863  call with either qh.facet_list or qh.newfacet_list
864  checks num_facets and num_vertices if qh.facet_list
865 
866  design:
867  for each facet
868  checks facet and outside set
869  initializes vertexlist
870  for each facet
871  checks vertex set
872  if checking all facets(qh.facetlist)
873  check facet count
874  if qh.VERTEXneighbors
875  check vertex neighbors and count
876  check vertex count
877 */
878 void qh_checkpolygon(facetT *facetlist) {
879  facetT *facet;
880  vertexT *vertex, **vertexp, *vertexlist;
881  int numfacets= 0, numvertices= 0, numridges= 0;
882  int totvneighbors= 0, totvertices= 0;
883  boolT waserror= False, nextseen= False, visibleseen= False;
884 
885  trace1((qh ferr, 1027, "qh_checkpolygon: check all facets from f%d\n", facetlist->id));
886  if (facetlist != qh facet_list || qh ONLYgood)
887  nextseen= True;
888  FORALLfacet_(facetlist) {
889  if (facet == qh visible_list)
890  visibleseen= True;
891  if (!facet->visible) {
892  if (!nextseen) {
893  if (facet == qh facet_next)
894  nextseen= True;
895  else if (qh_setsize(facet->outsideset)) {
896  if (!qh NARROWhull
897 #if !qh_COMPUTEfurthest
898  || facet->furthestdist >= qh MINoutside
899 #endif
900  ) {
901  qh_fprintf(qh ferr, 6137, "qhull internal error (qh_checkpolygon): f%d has outside points before qh facet_next\n",
902  facet->id);
903  qh_errexit(qh_ERRqhull, facet, NULL);
904  }
905  }
906  }
907  numfacets++;
908  qh_checkfacet(facet, False, &waserror);
909  }
910  }
911  if (qh visible_list && !visibleseen && facetlist == qh facet_list) {
912  qh_fprintf(qh ferr, 6138, "qhull internal error (qh_checkpolygon): visible list f%d no longer on facet list\n", qh visible_list->id);
913  qh_printlists();
914  qh_errexit(qh_ERRqhull, qh visible_list, NULL);
915  }
916  if (facetlist == qh facet_list)
917  vertexlist= qh vertex_list;
918  else if (facetlist == qh newfacet_list)
919  vertexlist= qh newvertex_list;
920  else
921  vertexlist= NULL;
922  FORALLvertex_(vertexlist) {
923  vertex->seen= False;
924  vertex->visitid= 0;
925  }
926  FORALLfacet_(facetlist) {
927  if (facet->visible)
928  continue;
929  if (facet->simplicial)
930  numridges += qh hull_dim;
931  else
932  numridges += qh_setsize(facet->ridges);
933  FOREACHvertex_(facet->vertices) {
934  vertex->visitid++;
935  if (!vertex->seen) {
936  vertex->seen= True;
937  numvertices++;
938  if (qh_pointid(vertex->point) == qh_IDunknown) {
939  qh_fprintf(qh ferr, 6139, "qhull internal error (qh_checkpolygon): unknown point %p for vertex v%d first_point %p\n",
940  vertex->point, vertex->id, qh first_point);
941  waserror= True;
942  }
943  }
944  }
945  }
946  qh vertex_visit += (unsigned int)numfacets;
947  if (facetlist == qh facet_list) {
948  if (numfacets != qh num_facets - qh num_visible) {
949  qh_fprintf(qh ferr, 6140, "qhull internal error (qh_checkpolygon): actual number of facets is %d, cumulative facet count is %d - %d visible facets\n",
950  numfacets, qh num_facets, qh num_visible);
951  waserror= True;
952  }
953  qh vertex_visit++;
954  if (qh VERTEXneighbors) {
955  FORALLvertices {
956  qh_setcheck(vertex->neighbors, "neighbors for v", vertex->id);
957  if (vertex->deleted)
958  continue;
959  totvneighbors += qh_setsize(vertex->neighbors);
960  }
961  FORALLfacet_(facetlist)
962  totvertices += qh_setsize(facet->vertices);
963  if (totvneighbors != totvertices) {
964  qh_fprintf(qh ferr, 6141, "qhull internal error (qh_checkpolygon): vertex neighbors inconsistent. Totvneighbors %d, totvertices %d\n",
965  totvneighbors, totvertices);
966  waserror= True;
967  }
968  }
969  if (numvertices != qh num_vertices - qh_setsize(qh del_vertices)) {
970  qh_fprintf(qh ferr, 6142, "qhull internal error (qh_checkpolygon): actual number of vertices is %d, cumulative vertex count is %d\n",
971  numvertices, qh num_vertices - qh_setsize(qh del_vertices));
972  waserror= True;
973  }
974  if (qh hull_dim == 2 && numvertices != numfacets) {
975  qh_fprintf(qh ferr, 6143, "qhull internal error (qh_checkpolygon): #vertices %d != #facets %d\n",
976  numvertices, numfacets);
977  waserror= True;
978  }
979  if (qh hull_dim == 3 && numvertices + numfacets - numridges/2 != 2) {
980  qh_fprintf(qh ferr, 7063, "qhull warning: #vertices %d + #facets %d - #edges %d != 2\n\
981  A vertex appears twice in a edge list. May occur during merging.",
982  numvertices, numfacets, numridges/2);
983  /* occurs if lots of merging and a vertex ends up twice in an edge list. e.g., RBOX 1000 s W1e-13 t995849315 D2 | QHULL d Tc Tv */
984  }
985  }
986  if (waserror)
987  qh_errexit(qh_ERRqhull, NULL, NULL);
988 } /* checkpolygon */
989 
990 
991 /*-<a href="qh-poly.htm#TOC"
992  >-------------------------------</a><a name="checkvertex">-</a>
993 
994  qh_checkvertex( vertex )
995  check vertex for consistency
996  checks vertex->neighbors
997 
998  notes:
999  neighbors checked efficiently in checkpolygon
1000 */
1001 void qh_checkvertex(vertexT *vertex) {
1002  boolT waserror= False;
1003  facetT *neighbor, **neighborp, *errfacet=NULL;
1004 
1005  if (qh_pointid(vertex->point) == qh_IDunknown) {
1006  qh_fprintf(qh ferr, 6144, "qhull internal error (qh_checkvertex): unknown point id %p\n", vertex->point);
1007  waserror= True;
1008  }
1009  if (vertex->id >= qh vertex_id) {
1010  qh_fprintf(qh ferr, 6145, "qhull internal error (qh_checkvertex): unknown vertex id %d\n", vertex->id);
1011  waserror= True;
1012  }
1013  if (!waserror && !vertex->deleted) {
1014  if (qh_setsize(vertex->neighbors)) {
1015  FOREACHneighbor_(vertex) {
1016  if (!qh_setin(neighbor->vertices, vertex)) {
1017  qh_fprintf(qh ferr, 6146, "qhull internal error (qh_checkvertex): neighbor f%d does not contain v%d\n", neighbor->id, vertex->id);
1018  errfacet= neighbor;
1019  waserror= True;
1020  }
1021  }
1022  }
1023  }
1024  if (waserror) {
1025  qh_errprint("ERRONEOUS", NULL, NULL, NULL, vertex);
1026  qh_errexit(qh_ERRqhull, errfacet, NULL);
1027  }
1028 } /* checkvertex */
1029 
1030 /*-<a href="qh-poly.htm#TOC"
1031  >-------------------------------</a><a name="clearcenters">-</a>
1032 
1033  qh_clearcenters( type )
1034  clear old data from facet->center
1035 
1036  notes:
1037  sets new centertype
1038  nop if CENTERtype is the same
1039 */
1040 void qh_clearcenters(qh_CENTER type) {
1041  facetT *facet;
1042 
1043  if (qh CENTERtype != type) {
1044  FORALLfacets {
1045  if (facet->tricoplanar && !facet->keepcentrum)
1046  facet->center= NULL; /* center is owned by the ->keepcentrum facet */
1047  else if (qh CENTERtype == qh_ASvoronoi){
1048  if (facet->center) {
1049  qh_memfree(facet->center, qh center_size);
1050  facet->center= NULL;
1051  }
1052  }else /* qh.CENTERtype == qh_AScentrum */ {
1053  if (facet->center) {
1054  qh_memfree(facet->center, qh normal_size);
1055  facet->center= NULL;
1056  }
1057  }
1058  }
1059  qh CENTERtype= type;
1060  }
1061  trace2((qh ferr, 2043, "qh_clearcenters: switched to center type %d\n", type));
1062 } /* clearcenters */
1063 
1064 /*-<a href="qh-poly.htm#TOC"
1065  >-------------------------------</a><a name="createsimplex">-</a>
1066 
1067  qh_createsimplex( vertices )
1068  creates a simplex from a set of vertices
1069 
1070  returns:
1071  initializes qh.facet_list to the simplex
1072  initializes qh.newfacet_list, .facet_tail
1073  initializes qh.vertex_list, .newvertex_list, .vertex_tail
1074 
1075  design:
1076  initializes lists
1077  for each vertex
1078  create a new facet
1079  for each new facet
1080  create its neighbor set
1081 */
1082 void qh_createsimplex(setT *vertices) {
1083  facetT *facet= NULL, *newfacet;
1084  boolT toporient= True;
1085  int vertex_i, vertex_n, nth;
1086  setT *newfacets= qh_settemp(qh hull_dim+1);
1087  vertexT *vertex;
1088 
1089  qh facet_list= qh newfacet_list= qh facet_tail= qh_newfacet();
1090  qh num_facets= qh num_vertices= qh num_visible= 0;
1091  qh vertex_list= qh newvertex_list= qh vertex_tail= qh_newvertex(NULL);
1092  FOREACHvertex_i_(vertices) {
1093  newfacet= qh_newfacet();
1094  newfacet->vertices= qh_setnew_delnthsorted(vertices, vertex_n,
1095  vertex_i, 0);
1096  newfacet->toporient= (unsigned char)toporient;
1097  qh_appendfacet(newfacet);
1098  newfacet->newfacet= True;
1099  qh_appendvertex(vertex);
1100  qh_setappend(&newfacets, newfacet);
1101  toporient ^= True;
1102  }
1103  FORALLnew_facets {
1104  nth= 0;
1105  FORALLfacet_(qh newfacet_list) {
1106  if (facet != newfacet)
1107  SETelem_(newfacet->neighbors, nth++)= facet;
1108  }
1109  qh_settruncate(newfacet->neighbors, qh hull_dim);
1110  }
1111  qh_settempfree(&newfacets);
1112  trace1((qh ferr, 1028, "qh_createsimplex: created simplex\n"));
1113 } /* createsimplex */
1114 
1115 /*-<a href="qh-poly.htm#TOC"
1116  >-------------------------------</a><a name="delridge">-</a>
1117 
1118  qh_delridge( ridge )
1119  deletes ridge from data structures it belongs to
1120  frees up its memory
1121 
1122  notes:
1123  in merge.c, caller sets vertex->delridge for each vertex
1124  ridges also freed in qh_freeqhull
1125 */
1126 void qh_delridge(ridgeT *ridge) {
1127  void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
1128 
1129  qh_setdel(ridge->top->ridges, ridge);
1130  qh_setdel(ridge->bottom->ridges, ridge);
1131  qh_setfree(&(ridge->vertices));
1132  qh_memfree_(ridge, (int)sizeof(ridgeT), freelistp);
1133 } /* delridge */
1134 
1135 
1136 /*-<a href="qh-poly.htm#TOC"
1137  >-------------------------------</a><a name="delvertex">-</a>
1138 
1139  qh_delvertex( vertex )
1140  deletes a vertex and frees its memory
1141 
1142  notes:
1143  assumes vertex->adjacencies have been updated if needed
1144  unlinks from vertex_list
1145 */
1146 void qh_delvertex(vertexT *vertex) {
1147 
1148  if (vertex == qh tracevertex)
1149  qh tracevertex= NULL;
1150  qh_removevertex(vertex);
1151  qh_setfree(&vertex->neighbors);
1152  qh_memfree(vertex, (int)sizeof(vertexT));
1153 } /* delvertex */
1154 
1155 
1156 /*-<a href="qh-poly.htm#TOC"
1157  >-------------------------------</a><a name="facet3vertex">-</a>
1158 
1159  qh_facet3vertex( )
1160  return temporary set of 3-d vertices in qh_ORIENTclock order
1161 
1162  design:
1163  if simplicial facet
1164  build set from facet->vertices with facet->toporient
1165  else
1166  for each ridge in order
1167  build set from ridge's vertices
1168 */
1169 setT *qh_facet3vertex(facetT *facet) {
1170  ridgeT *ridge, *firstridge;
1171  vertexT *vertex;
1172  int cntvertices, cntprojected=0;
1173  setT *vertices;
1174 
1175  cntvertices= qh_setsize(facet->vertices);
1176  vertices= qh_settemp(cntvertices);
1177  if (facet->simplicial) {
1178  if (cntvertices != 3) {
1179  qh_fprintf(qh ferr, 6147, "qhull internal error (qh_facet3vertex): only %d vertices for simplicial facet f%d\n",
1180  cntvertices, facet->id);
1181  qh_errexit(qh_ERRqhull, facet, NULL);
1182  }
1183  qh_setappend(&vertices, SETfirst_(facet->vertices));
1184  if (facet->toporient ^ qh_ORIENTclock)
1185  qh_setappend(&vertices, SETsecond_(facet->vertices));
1186  else
1187  qh_setaddnth(&vertices, 0, SETsecond_(facet->vertices));
1188  qh_setappend(&vertices, SETelem_(facet->vertices, 2));
1189  }else {
1190  ridge= firstridge= SETfirstt_(facet->ridges, ridgeT); /* no infinite */
1191  while ((ridge= qh_nextridge3d(ridge, facet, &vertex))) {
1192  qh_setappend(&vertices, vertex);
1193  if (++cntprojected > cntvertices || ridge == firstridge)
1194  break;
1195  }
1196  if (!ridge || cntprojected != cntvertices) {
1197  qh_fprintf(qh ferr, 6148, "qhull internal error (qh_facet3vertex): ridges for facet %d don't match up. got at least %d\n",
1198  facet->id, cntprojected);
1199  qh_errexit(qh_ERRqhull, facet, ridge);
1200  }
1201  }
1202  return vertices;
1203 } /* facet3vertex */
1204 
1205 /*-<a href="qh-poly.htm#TOC"
1206  >-------------------------------</a><a name="findbestfacet">-</a>
1207 
1208  qh_findbestfacet( point, bestoutside, bestdist, isoutside )
1209  find facet that is furthest below a point
1210 
1211  for Delaunay triangulations,
1212  Use qh_setdelaunay() to lift point to paraboloid and scale by 'Qbb' if needed
1213  Do not use options 'Qbk', 'QBk', or 'QbB' since they scale the coordinates.
1214 
1215  returns:
1216  if bestoutside is set (e.g., qh_ALL)
1217  returns best facet that is not upperdelaunay
1218  if Delaunay and inside, point is outside circumsphere of bestfacet
1219  else
1220  returns first facet below point
1221  if point is inside, returns nearest, !upperdelaunay facet
1222  distance to facet
1223  isoutside set if outside of facet
1224 
1225  notes:
1226  For tricoplanar facets, this finds one of the tricoplanar facets closest
1227  to the point. For Delaunay triangulations, the point may be inside a
1228  different tricoplanar facet. See <a href="../html/qh-code.htm#findfacet">locate a facet with qh_findbestfacet()</a>
1229 
1230  If inside, qh_findbestfacet performs an exhaustive search
1231  this may be too conservative. Sometimes it is clearly required.
1232 
1233  qh_findbestfacet is not used by qhull.
1234  uses qh.visit_id and qh.coplanarset
1235 
1236  see:
1237  <a href="geom.c#findbest">qh_findbest</a>
1238 */
1239 facetT *qh_findbestfacet(pointT *point, boolT bestoutside,
1240  realT *bestdist, boolT *isoutside) {
1241  facetT *bestfacet= NULL;
1242  int numpart, totpart= 0;
1243 
1244  bestfacet= qh_findbest(point, qh facet_list,
1245  bestoutside, !qh_ISnewfacets, bestoutside /* qh_NOupper */,
1246  bestdist, isoutside, &totpart);
1247  if (*bestdist < -qh DISTround) {
1248  bestfacet= qh_findfacet_all(point, bestdist, isoutside, &numpart);
1249  totpart += numpart;
1250  if ((isoutside && *isoutside && bestoutside)
1251  || (isoutside && !*isoutside && bestfacet->upperdelaunay)) {
1252  bestfacet= qh_findbest(point, bestfacet,
1253  bestoutside, False, bestoutside,
1254  bestdist, isoutside, &totpart);
1255  totpart += numpart;
1256  }
1257  }
1258  trace3((qh ferr, 3014, "qh_findbestfacet: f%d dist %2.2g isoutside %d totpart %d\n",
1259  bestfacet->id, *bestdist, (isoutside ? *isoutside : UINT_MAX), totpart));
1260  return bestfacet;
1261 } /* findbestfacet */
1262 
1263 /*-<a href="qh-poly.htm#TOC"
1264  >-------------------------------</a><a name="findbestlower">-</a>
1265 
1266  qh_findbestlower( facet, point, bestdist, numpart )
1267  returns best non-upper, non-flipped neighbor of facet for point
1268  if needed, searches vertex neighbors
1269 
1270  returns:
1271  returns bestdist and updates numpart
1272 
1273  notes:
1274  if Delaunay and inside, point is outside of circumsphere of bestfacet
1275  called by qh_findbest() for points above an upperdelaunay facet
1276 
1277 */
1278 facetT *qh_findbestlower(facetT *upperfacet, pointT *point, realT *bestdistp, int *numpart) {
1279  facetT *neighbor, **neighborp, *bestfacet= NULL;
1280  realT bestdist= -REALmax/2 /* avoid underflow */;
1281  realT dist;
1282  vertexT *vertex;
1283  boolT isoutside= False; /* not used */
1284 
1285  zinc_(Zbestlower);
1286  FOREACHneighbor_(upperfacet) {
1287  if (neighbor->upperdelaunay || neighbor->flipped)
1288  continue;
1289  (*numpart)++;
1290  qh_distplane(point, neighbor, &dist);
1291  if (dist > bestdist) {
1292  bestfacet= neighbor;
1293  bestdist= dist;
1294  }
1295  }
1296  if (!bestfacet) {
1297  zinc_(Zbestlowerv);
1298  /* rarely called, numpart does not count nearvertex computations */
1299  vertex= qh_nearvertex(upperfacet, point, &dist);
1300  qh_vertexneighbors();
1301  FOREACHneighbor_(vertex) {
1302  if (neighbor->upperdelaunay || neighbor->flipped)
1303  continue;
1304  (*numpart)++;
1305  qh_distplane(point, neighbor, &dist);
1306  if (dist > bestdist) {
1307  bestfacet= neighbor;
1308  bestdist= dist;
1309  }
1310  }
1311  }
1312  if (!bestfacet) {
1313  zinc_(Zbestlowerall); /* invoked once per point in outsideset */
1314  zmax_(Zbestloweralln, qh num_facets);
1315  /* [dec'15] Previously reported as QH6228 */
1316  trace3((qh ferr, 3025, "qh_findbestlower: all neighbors of facet %d are flipped or upper Delaunay. Search all facets\n",
1317  upperfacet->id));
1318  /* rarely called */
1319  bestfacet= qh_findfacet_all(point, &bestdist, &isoutside, numpart);
1320  }
1321  *bestdistp= bestdist;
1322  trace3((qh ferr, 3015, "qh_findbestlower: f%d dist %2.2g for f%d p%d\n",
1323  bestfacet->id, bestdist, upperfacet->id, qh_pointid(point)));
1324  return bestfacet;
1325 } /* findbestlower */
1326 
1327 /*-<a href="qh-poly.htm#TOC"
1328  >-------------------------------</a><a name="findfacet_all">-</a>
1329 
1330  qh_findfacet_all( point, bestdist, isoutside, numpart )
1331  exhaustive search for facet below a point
1332 
1333  for Delaunay triangulations,
1334  Use qh_setdelaunay() to lift point to paraboloid and scale by 'Qbb' if needed
1335  Do not use options 'Qbk', 'QBk', or 'QbB' since they scale the coordinates.
1336 
1337  returns:
1338  returns first facet below point
1339  if point is inside,
1340  returns nearest facet
1341  distance to facet
1342  isoutside if point is outside of the hull
1343  number of distance tests
1344 
1345  notes:
1346  primarily for library users, rarely used by Qhull
1347 */
1348 facetT *qh_findfacet_all(pointT *point, realT *bestdist, boolT *isoutside,
1349  int *numpart) {
1350  facetT *bestfacet= NULL, *facet;
1351  realT dist;
1352  int totpart= 0;
1353 
1354  *bestdist= -REALmax;
1355  *isoutside= False;
1356  FORALLfacets {
1357  if (facet->flipped || !facet->normal)
1358  continue;
1359  totpart++;
1360  qh_distplane(point, facet, &dist);
1361  if (dist > *bestdist) {
1362  *bestdist= dist;
1363  bestfacet= facet;
1364  if (dist > qh MINoutside) {
1365  *isoutside= True;
1366  break;
1367  }
1368  }
1369  }
1370  *numpart= totpart;
1371  trace3((qh ferr, 3016, "qh_findfacet_all: f%d dist %2.2g isoutside %d totpart %d\n",
1372  getid_(bestfacet), *bestdist, *isoutside, totpart));
1373  return bestfacet;
1374 } /* findfacet_all */
1375 
1376 /*-<a href="qh-poly.htm#TOC"
1377  >-------------------------------</a><a name="findgood">-</a>
1378 
1379  qh_findgood( facetlist, goodhorizon )
1380  identify good facets for qh.PRINTgood
1381  if qh.GOODvertex>0
1382  facet includes point as vertex
1383  if !match, returns goodhorizon
1384  inactive if qh.MERGING
1385  if qh.GOODpoint
1386  facet is visible or coplanar (>0) or not visible (<0)
1387  if qh.GOODthreshold
1388  facet->normal matches threshold
1389  if !goodhorizon and !match,
1390  selects facet with closest angle
1391  sets GOODclosest
1392 
1393  returns:
1394  number of new, good facets found
1395  determines facet->good
1396  may update qh.GOODclosest
1397 
1398  notes:
1399  qh_findgood_all further reduces the good region
1400 
1401  design:
1402  count good facets
1403  mark good facets for qh.GOODpoint
1404  mark good facets for qh.GOODthreshold
1405  if necessary
1406  update qh.GOODclosest
1407 */
1408 int qh_findgood(facetT *facetlist, int goodhorizon) {
1409  facetT *facet, *bestfacet= NULL;
1410  realT angle, bestangle= REALmax, dist;
1411  int numgood=0;
1412 
1413  FORALLfacet_(facetlist) {
1414  if (facet->good)
1415  numgood++;
1416  }
1417  if (qh GOODvertex>0 && !qh MERGING) {
1418  FORALLfacet_(facetlist) {
1419  if (!qh_isvertex(qh GOODvertexp, facet->vertices)) {
1420  facet->good= False;
1421  numgood--;
1422  }
1423  }
1424  }
1425  if (qh GOODpoint && numgood) {
1426  FORALLfacet_(facetlist) {
1427  if (facet->good && facet->normal) {
1428  zinc_(Zdistgood);
1429  qh_distplane(qh GOODpointp, facet, &dist);
1430  if ((qh GOODpoint > 0) ^ (dist > 0.0)) {
1431  facet->good= False;
1432  numgood--;
1433  }
1434  }
1435  }
1436  }
1437  if (qh GOODthreshold && (numgood || goodhorizon || qh GOODclosest)) {
1438  FORALLfacet_(facetlist) {
1439  if (facet->good && facet->normal) {
1440  if (!qh_inthresholds(facet->normal, &angle)) {
1441  facet->good= False;
1442  numgood--;
1443  if (angle < bestangle) {
1444  bestangle= angle;
1445  bestfacet= facet;
1446  }
1447  }
1448  }
1449  }
1450  if (!numgood && (!goodhorizon || qh GOODclosest)) {
1451  if (qh GOODclosest) {
1452  if (qh GOODclosest->visible)
1453  qh GOODclosest= NULL;
1454  else {
1455  qh_inthresholds(qh GOODclosest->normal, &angle);
1456  if (angle < bestangle)
1457  bestfacet= qh GOODclosest;
1458  }
1459  }
1460  if (bestfacet && bestfacet != qh GOODclosest) {
1461  if (qh GOODclosest)
1462  qh GOODclosest->good= False;
1463  qh GOODclosest= bestfacet;
1464  bestfacet->good= True;
1465  numgood++;
1466  trace2((qh ferr, 2044, "qh_findgood: f%d is closest(%2.2g) to thresholds\n",
1467  bestfacet->id, bestangle));
1468  return numgood;
1469  }
1470  }else if (qh GOODclosest) { /* numgood > 0 */
1471  qh GOODclosest->good= False;
1472  qh GOODclosest= NULL;
1473  }
1474  }
1475  zadd_(Zgoodfacet, numgood);
1476  trace2((qh ferr, 2045, "qh_findgood: found %d good facets with %d good horizon\n",
1477  numgood, goodhorizon));
1478  if (!numgood && qh GOODvertex>0 && !qh MERGING)
1479  return goodhorizon;
1480  return numgood;
1481 } /* findgood */
1482 
1483 /*-<a href="qh-poly.htm#TOC"
1484  >-------------------------------</a><a name="findgood_all">-</a>
1485 
1486  qh_findgood_all( facetlist )
1487  apply other constraints for good facets (used by qh.PRINTgood)
1488  if qh.GOODvertex
1489  facet includes (>0) or doesn't include (<0) point as vertex
1490  if last good facet and ONLYgood, prints warning and continues
1491  if qh.SPLITthresholds
1492  facet->normal matches threshold, or if none, the closest one
1493  calls qh_findgood
1494  nop if good not used
1495 
1496  returns:
1497  clears facet->good if not good
1498  sets qh.num_good
1499 
1500  notes:
1501  this is like qh_findgood but more restrictive
1502 
1503  design:
1504  uses qh_findgood to mark good facets
1505  marks facets for qh.GOODvertex
1506  marks facets for qh.SPLITthreholds
1507 */
1508 void qh_findgood_all(facetT *facetlist) {
1509  facetT *facet, *bestfacet=NULL;
1510  realT angle, bestangle= REALmax;
1511  int numgood=0, startgood;
1512 
1513  if (!qh GOODvertex && !qh GOODthreshold && !qh GOODpoint
1514  && !qh SPLITthresholds)
1515  return;
1516  if (!qh ONLYgood)
1517  qh_findgood(qh facet_list, 0);
1518  FORALLfacet_(facetlist) {
1519  if (facet->good)
1520  numgood++;
1521  }
1522  if (qh GOODvertex <0 || (qh GOODvertex > 0 && qh MERGING)) {
1523  FORALLfacet_(facetlist) {
1524  if (facet->good && ((qh GOODvertex > 0) ^ !!qh_isvertex(qh GOODvertexp, facet->vertices))) {
1525  if (!--numgood) {
1526  if (qh ONLYgood) {
1527  qh_fprintf(qh ferr, 7064, "qhull warning: good vertex p%d does not match last good facet f%d. Ignored.\n",
1528  qh_pointid(qh GOODvertexp), facet->id);
1529  return;
1530  }else if (qh GOODvertex > 0)
1531  qh_fprintf(qh ferr, 7065, "qhull warning: point p%d is not a vertex('QV%d').\n",
1532  qh GOODvertex-1, qh GOODvertex-1);
1533  else
1534  qh_fprintf(qh ferr, 7066, "qhull warning: point p%d is a vertex for every facet('QV-%d').\n",
1535  -qh GOODvertex - 1, -qh GOODvertex - 1);
1536  }
1537  facet->good= False;
1538  }
1539  }
1540  }
1541  startgood= numgood;
1542  if (qh SPLITthresholds) {
1543  FORALLfacet_(facetlist) {
1544  if (facet->good) {
1545  if (!qh_inthresholds(facet->normal, &angle)) {
1546  facet->good= False;
1547  numgood--;
1548  if (angle < bestangle) {
1549  bestangle= angle;
1550  bestfacet= facet;
1551  }
1552  }
1553  }
1554  }
1555  if (!numgood && bestfacet) {
1556  bestfacet->good= True;
1557  numgood++;
1558  trace0((qh ferr, 23, "qh_findgood_all: f%d is closest(%2.2g) to thresholds\n",
1559  bestfacet->id, bestangle));
1560  return;
1561  }
1562  }
1563  qh num_good= numgood;
1564  trace0((qh ferr, 24, "qh_findgood_all: %d good facets remain out of %d facets\n",
1565  numgood, startgood));
1566 } /* findgood_all */
1567 
1568 /*-<a href="qh-poly.htm#TOC"
1569  >-------------------------------</a><a name="furthestnext">-</a>
1570 
1571  qh_furthestnext()
1572  set qh.facet_next to facet with furthest of all furthest points
1573  searches all facets on qh.facet_list
1574 
1575  notes:
1576  this may help avoid precision problems
1577 */
1578 void qh_furthestnext(void /* qh.facet_list */) {
1579  facetT *facet, *bestfacet= NULL;
1580  realT dist, bestdist= -REALmax;
1581 
1582  FORALLfacets {
1583  if (facet->outsideset) {
1584 #if qh_COMPUTEfurthest
1585  pointT *furthest;
1586  furthest= (pointT*)qh_setlast(facet->outsideset);
1587  zinc_(Zcomputefurthest);
1588  qh_distplane(furthest, facet, &dist);
1589 #else
1590  dist= facet->furthestdist;
1591 #endif
1592  if (dist > bestdist) {
1593  bestfacet= facet;
1594  bestdist= dist;
1595  }
1596  }
1597  }
1598  if (bestfacet) {
1599  qh_removefacet(bestfacet);
1600  qh_prependfacet(bestfacet, &qh facet_next);
1601  trace1((qh ferr, 1029, "qh_furthestnext: made f%d next facet(dist %.2g)\n",
1602  bestfacet->id, bestdist));
1603  }
1604 } /* furthestnext */
1605 
1606 /*-<a href="qh-poly.htm#TOC"
1607  >-------------------------------</a><a name="furthestout">-</a>
1608 
1609  qh_furthestout( facet )
1610  make furthest outside point the last point of outsideset
1611 
1612  returns:
1613  updates facet->outsideset
1614  clears facet->notfurthest
1615  sets facet->furthestdist
1616 
1617  design:
1618  determine best point of outsideset
1619  make it the last point of outsideset
1620 */
1621 void qh_furthestout(facetT *facet) {
1622  pointT *point, **pointp, *bestpoint= NULL;
1623  realT dist, bestdist= -REALmax;
1624 
1625  FOREACHpoint_(facet->outsideset) {
1626  qh_distplane(point, facet, &dist);
1627  zinc_(Zcomputefurthest);
1628  if (dist > bestdist) {
1629  bestpoint= point;
1630  bestdist= dist;
1631  }
1632  }
1633  if (bestpoint) {
1634  qh_setdel(facet->outsideset, point);
1635  qh_setappend(&facet->outsideset, point);
1636 #if !qh_COMPUTEfurthest
1637  facet->furthestdist= bestdist;
1638 #endif
1639  }
1640  facet->notfurthest= False;
1641  trace3((qh ferr, 3017, "qh_furthestout: p%d is furthest outside point of f%d\n",
1642  qh_pointid(point), facet->id));
1643 } /* furthestout */
1644 
1645 
1646 /*-<a href="qh-qhull.htm#TOC"
1647  >-------------------------------</a><a name="infiniteloop">-</a>
1648 
1649  qh_infiniteloop( facet )
1650  report infinite loop error due to facet
1651 */
1652 void qh_infiniteloop(facetT *facet) {
1653 
1654  qh_fprintf(qh ferr, 6149, "qhull internal error (qh_infiniteloop): potential infinite loop detected\n");
1655  qh_errexit(qh_ERRqhull, facet, NULL);
1656 } /* qh_infiniteloop */
1657 
1658 /*-<a href="qh-poly.htm#TOC"
1659  >-------------------------------</a><a name="initbuild">-</a>
1660 
1661  qh_initbuild()
1662  initialize hull and outside sets with point array
1663  qh.FIRSTpoint/qh.NUMpoints is point array
1664  if qh.GOODpoint
1665  adds qh.GOODpoint to initial hull
1666 
1667  returns:
1668  qh_facetlist with initial hull
1669  points partioned into outside sets, coplanar sets, or inside
1670  initializes qh.GOODpointp, qh.GOODvertexp,
1671 
1672  design:
1673  initialize global variables used during qh_buildhull
1674  determine precision constants and points with max/min coordinate values
1675  if qh.SCALElast, scale last coordinate(for 'd')
1676  build initial simplex
1677  partition input points into facets of initial simplex
1678  set up lists
1679  if qh.ONLYgood
1680  check consistency
1681  add qh.GOODvertex if defined
1682 */
1683 void qh_initbuild( void) {
1684  setT *maxpoints, *vertices;
1685  facetT *facet;
1686  int i, numpart;
1687  realT dist;
1688  boolT isoutside;
1689 
1690  qh furthest_id= qh_IDunknown;
1691  qh lastreport= 0;
1692  qh facet_id= qh vertex_id= qh ridge_id= 0;
1693  qh visit_id= qh vertex_visit= 0;
1694  qh maxoutdone= False;
1695 
1696  if (qh GOODpoint > 0)
1697  qh GOODpointp= qh_point(qh GOODpoint-1);
1698  else if (qh GOODpoint < 0)
1699  qh GOODpointp= qh_point(-qh GOODpoint-1);
1700  if (qh GOODvertex > 0)
1701  qh GOODvertexp= qh_point(qh GOODvertex-1);
1702  else if (qh GOODvertex < 0)
1703  qh GOODvertexp= qh_point(-qh GOODvertex-1);
1704  if ((qh GOODpoint
1705  && (qh GOODpointp < qh first_point /* also catches !GOODpointp */
1706  || qh GOODpointp > qh_point(qh num_points-1)))
1707  || (qh GOODvertex
1708  && (qh GOODvertexp < qh first_point /* also catches !GOODvertexp */
1709  || qh GOODvertexp > qh_point(qh num_points-1)))) {
1710  qh_fprintf(qh ferr, 6150, "qhull input error: either QGn or QVn point is > p%d\n",
1711  qh num_points-1);
1712  qh_errexit(qh_ERRinput, NULL, NULL);
1713  }
1714  maxpoints= qh_maxmin(qh first_point, qh num_points, qh hull_dim);
1715  if (qh SCALElast)
1716  qh_scalelast(qh first_point, qh num_points, qh hull_dim,
1717  qh MINlastcoord, qh MAXlastcoord, qh MAXwidth);
1718  qh_detroundoff();
1719  if (qh DELAUNAY && qh upper_threshold[qh hull_dim-1] > REALmax/2
1720  && qh lower_threshold[qh hull_dim-1] < -REALmax/2) {
1721  for (i=qh_PRINTEND; i--; ) {
1722  if (qh PRINTout[i] == qh_PRINTgeom && qh DROPdim < 0
1723  && !qh GOODthreshold && !qh SPLITthresholds)
1724  break; /* in this case, don't set upper_threshold */
1725  }
1726  if (i < 0) {
1727  if (qh UPPERdelaunay) { /* matches qh.upperdelaunay in qh_setfacetplane */
1728  qh lower_threshold[qh hull_dim-1]= qh ANGLEround * qh_ZEROdelaunay;
1729  qh GOODthreshold= True;
1730  }else {
1731  qh upper_threshold[qh hull_dim-1]= -qh ANGLEround * qh_ZEROdelaunay;
1732  if (!qh GOODthreshold)
1733  qh SPLITthresholds= True; /* build upper-convex hull even if Qg */
1734  /* qh_initqhull_globals errors if Qg without Pdk/etc. */
1735  }
1736  }
1737  }
1738  vertices= qh_initialvertices(qh hull_dim, maxpoints, qh first_point, qh num_points);
1739  qh_initialhull(vertices); /* initial qh facet_list */
1740  qh_partitionall(vertices, qh first_point, qh num_points);
1741  if (qh PRINToptions1st || qh TRACElevel || qh IStracing) {
1742  if (qh TRACElevel || qh IStracing)
1743  qh_fprintf(qh ferr, 8103, "\nTrace level %d for %s | %s\n",
1744  qh IStracing ? qh IStracing : qh TRACElevel, qh rbox_command, qh qhull_command);
1745  qh_fprintf(qh ferr, 8104, "Options selected for Qhull %s:\n%s\n", qh_version, qh qhull_options);
1746  }
1747  qh_resetlists(False, qh_RESETvisible /*qh.visible_list newvertex_list newfacet_list */);
1748  qh facet_next= qh facet_list;
1749  qh_furthestnext(/* qh.facet_list */);
1750  if (qh PREmerge) {
1751  qh cos_max= qh premerge_cos;
1752  qh centrum_radius= qh premerge_centrum;
1753  }
1754  if (qh ONLYgood) {
1755  if (qh GOODvertex > 0 && qh MERGING) {
1756  qh_fprintf(qh ferr, 6151, "qhull input error: 'Qg QVn' (only good vertex) does not work with merging.\nUse 'QJ' to joggle the input or 'Q0' to turn off merging.\n");
1757  qh_errexit(qh_ERRinput, NULL, NULL);
1758  }
1759  if (!(qh GOODthreshold || qh GOODpoint
1760  || (!qh MERGEexact && !qh PREmerge && qh GOODvertexp))) {
1761  qh_fprintf(qh ferr, 6152, "qhull input error: 'Qg' (ONLYgood) needs a good threshold('Pd0D0'), a\n\
1762 good point(QGn or QG-n), or a good vertex with 'QJ' or 'Q0' (QVn).\n");
1763  qh_errexit(qh_ERRinput, NULL, NULL);
1764  }
1765  if (qh GOODvertex > 0 && !qh MERGING /* matches qh_partitionall */
1766  && !qh_isvertex(qh GOODvertexp, vertices)) {
1767  facet= qh_findbestnew(qh GOODvertexp, qh facet_list,
1768  &dist, !qh_ALL, &isoutside, &numpart);
1769  zadd_(Zdistgood, numpart);
1770  if (!isoutside) {
1771  qh_fprintf(qh ferr, 6153, "qhull input error: point for QV%d is inside initial simplex. It can not be made a vertex.\n",
1772  qh_pointid(qh GOODvertexp));
1773  qh_errexit(qh_ERRinput, NULL, NULL);
1774  }
1775  if (!qh_addpoint(qh GOODvertexp, facet, False)) {
1776  qh_settempfree(&vertices);
1777  qh_settempfree(&maxpoints);
1778  return;
1779  }
1780  }
1781  qh_findgood(qh facet_list, 0);
1782  }
1783  qh_settempfree(&vertices);
1784  qh_settempfree(&maxpoints);
1785  trace1((qh ferr, 1030, "qh_initbuild: initial hull created and points partitioned\n"));
1786 } /* initbuild */
1787 
1788 /*-<a href="qh-poly.htm#TOC"
1789  >-------------------------------</a><a name="initialhull">-</a>
1790 
1791  qh_initialhull( vertices )
1792  constructs the initial hull as a DIM3 simplex of vertices
1793 
1794  design:
1795  creates a simplex (initializes lists)
1796  determines orientation of simplex
1797  sets hyperplanes for facets
1798  doubles checks orientation (in case of axis-parallel facets with Gaussian elimination)
1799  checks for flipped facets and qh.NARROWhull
1800  checks the result
1801 */
1802 void qh_initialhull(setT *vertices) {
1803  facetT *facet, *firstfacet, *neighbor, **neighborp;
1804  realT dist, angle, minangle= REALmax;
1805 #ifndef qh_NOtrace
1806  int k;
1807 #endif
1808 
1809  qh_createsimplex(vertices); /* qh.facet_list */
1810  qh_resetlists(False, qh_RESETvisible);
1811  qh facet_next= qh facet_list; /* advance facet when processed */
1812  qh interior_point= qh_getcenter(vertices);
1813  firstfacet= qh facet_list;
1814  qh_setfacetplane(firstfacet);
1815  zinc_(Znumvisibility); /* needs to be in printsummary */
1816  qh_distplane(qh interior_point, firstfacet, &dist);
1817  if (dist > 0) {
1818  FORALLfacets
1819  facet->toporient ^= (unsigned char)True;
1820  }
1821  FORALLfacets
1822  qh_setfacetplane(facet);
1823  FORALLfacets {
1824  if (!qh_checkflipped(facet, NULL, qh_ALL)) {/* due to axis-parallel facet */
1825  trace1((qh ferr, 1031, "qh_initialhull: initial orientation incorrect. Correct all facets\n"));
1826  facet->flipped= False;
1827  FORALLfacets {
1828  facet->toporient ^= (unsigned char)True;
1829  qh_orientoutside(facet);
1830  }
1831  break;
1832  }
1833  }
1834  FORALLfacets {
1835  if (!qh_checkflipped(facet, NULL, !qh_ALL)) { /* can happen with 'R0.1' */
1836  if (qh DELAUNAY && ! qh ATinfinity) {
1837  if (qh UPPERdelaunay)
1838  qh_fprintf(qh ferr, 6240, "Qhull precision error: Initial simplex is cocircular or cospherical. Option 'Qs' searches all points. Can not compute the upper Delaunay triangulation or upper Voronoi diagram of cocircular/cospherical points.\n");
1839  else
1840  qh_fprintf(qh ferr, 6239, "Qhull precision error: Initial simplex is cocircular or cospherical. Use option 'Qz' for the Delaunay triangulation or Voronoi diagram of cocircular/cospherical points. Option 'Qz' adds a point \"at infinity\". Use option 'Qs' to search all points for the initial simplex.\n");
1841  qh_errexit(qh_ERRinput, NULL, NULL);
1842  }
1843  qh_precision("initial simplex is flat");
1844  qh_fprintf(qh ferr, 6154, "Qhull precision error: Initial simplex is flat (facet %d is coplanar with the interior point)\n",
1845  facet->id);
1846  qh_errexit(qh_ERRsingular, NULL, NULL); /* calls qh_printhelp_singular */
1847  }
1848  FOREACHneighbor_(facet) {
1849  angle= qh_getangle(facet->normal, neighbor->normal);
1850  minimize_( minangle, angle);
1851  }
1852  }
1853  if (minangle < qh_MAXnarrow && !qh NOnarrow) {
1854  realT diff= 1.0 + minangle;
1855 
1856  qh NARROWhull= True;
1857  qh_option("_narrow-hull", NULL, &diff);
1858  if (minangle < qh_WARNnarrow && !qh RERUN && qh PRINTprecision)
1859  qh_printhelp_narrowhull(qh ferr, minangle);
1860  }
1861  zzval_(Zprocessed)= qh hull_dim+1;
1862  qh_checkpolygon(qh facet_list);
1863  qh_checkconvex(qh facet_list, qh_DATAfault);
1864 #ifndef qh_NOtrace
1865  if (qh IStracing >= 1) {
1866  qh_fprintf(qh ferr, 8105, "qh_initialhull: simplex constructed, interior point:");
1867  for (k=0; k < qh hull_dim; k++)
1868  qh_fprintf(qh ferr, 8106, " %6.4g", qh interior_point[k]);
1869  qh_fprintf(qh ferr, 8107, "\n");
1870  }
1871 #endif
1872 } /* initialhull */
1873 
1874 /*-<a href="qh-poly.htm#TOC"
1875  >-------------------------------</a><a name="initialvertices">-</a>
1876 
1877  qh_initialvertices( dim, maxpoints, points, numpoints )
1878  determines a non-singular set of initial vertices
1879  maxpoints may include duplicate points
1880 
1881  returns:
1882  temporary set of dim+1 vertices in descending order by vertex id
1883  if qh.RANDOMoutside && !qh.ALLpoints
1884  picks random points
1885  if dim >= qh_INITIALmax,
1886  uses min/max x and max points with non-zero determinants
1887 
1888  notes:
1889  unless qh.ALLpoints,
1890  uses maxpoints as long as determinate is non-zero
1891 */
1892 setT *qh_initialvertices(int dim, setT *maxpoints, pointT *points, int numpoints) {
1893  pointT *point, **pointp;
1894  setT *vertices, *simplex, *tested;
1895  realT randr;
1896  int idx, point_i, point_n, k;
1897  boolT nearzero= False;
1898 
1899  vertices= qh_settemp(dim + 1);
1900  simplex= qh_settemp(dim+1);
1901  if (qh ALLpoints)
1902  qh_maxsimplex(dim, NULL, points, numpoints, &simplex);
1903  else if (qh RANDOMoutside) {
1904  while (qh_setsize(simplex) != dim+1) {
1905  randr= qh_RANDOMint;
1906  randr= randr/(qh_RANDOMmax+1);
1907  idx= (int)floor(qh num_points * randr);
1908  while (qh_setin(simplex, qh_point(idx))) {
1909  idx++; /* in case qh_RANDOMint always returns the same value */
1910  idx= idx < qh num_points ? idx : 0;
1911  }
1912  qh_setappend(&simplex, qh_point(idx));
1913  }
1914  }else if (qh hull_dim >= qh_INITIALmax) {
1915  tested= qh_settemp(dim+1);
1916  qh_setappend(&simplex, SETfirst_(maxpoints)); /* max and min X coord */
1917  qh_setappend(&simplex, SETsecond_(maxpoints));
1918  qh_maxsimplex(fmin_(qh_INITIALsearch, dim), maxpoints, points, numpoints, &simplex);
1919  k= qh_setsize(simplex);
1920  FOREACHpoint_i_(maxpoints) {
1921  if (point_i & 0x1) { /* first pick up max. coord. points */
1922  if (!qh_setin(simplex, point) && !qh_setin(tested, point)){
1923  qh_detsimplex(point, simplex, k, &nearzero);
1924  if (nearzero)
1925  qh_setappend(&tested, point);
1926  else {
1927  qh_setappend(&simplex, point);
1928  if (++k == dim) /* use search for last point */
1929  break;
1930  }
1931  }
1932  }
1933  }
1934  while (k != dim && (point= (pointT*)qh_setdellast(maxpoints))) {
1935  if (!qh_setin(simplex, point) && !qh_setin(tested, point)){
1936  qh_detsimplex(point, simplex, k, &nearzero);
1937  if (nearzero)
1938  qh_setappend(&tested, point);
1939  else {
1940  qh_setappend(&simplex, point);
1941  k++;
1942  }
1943  }
1944  }
1945  idx= 0;
1946  while (k != dim && (point= qh_point(idx++))) {
1947  if (!qh_setin(simplex, point) && !qh_setin(tested, point)){
1948  qh_detsimplex(point, simplex, k, &nearzero);
1949  if (!nearzero){
1950  qh_setappend(&simplex, point);
1951  k++;
1952  }
1953  }
1954  }
1955  qh_settempfree(&tested);
1956  qh_maxsimplex(dim, maxpoints, points, numpoints, &simplex);
1957  }else
1958  qh_maxsimplex(dim, maxpoints, points, numpoints, &simplex);
1959  FOREACHpoint_(simplex)
1960  qh_setaddnth(&vertices, 0, qh_newvertex(point)); /* descending order */
1961  qh_settempfree(&simplex);
1962  return vertices;
1963 } /* initialvertices */
1964 
1965 
1966 /*-<a href="qh-poly.htm#TOC"
1967  >-------------------------------</a><a name="isvertex">-</a>
1968 
1969  qh_isvertex( point, vertices )
1970  returns vertex if point is in vertex set, else returns NULL
1971 
1972  notes:
1973  for qh.GOODvertex
1974 */
1975 vertexT *qh_isvertex(pointT *point, setT *vertices) {
1976  vertexT *vertex, **vertexp;
1977 
1978  FOREACHvertex_(vertices) {
1979  if (vertex->point == point)
1980  return vertex;
1981  }
1982  return NULL;
1983 } /* isvertex */
1984 
1985 /*-<a href="qh-poly.htm#TOC"
1986  >-------------------------------</a><a name="makenewfacets">-</a>
1987 
1988  qh_makenewfacets( point )
1989  make new facets from point and qh.visible_list
1990 
1991  returns:
1992  qh.newfacet_list= list of new facets with hyperplanes and ->newfacet
1993  qh.newvertex_list= list of vertices in new facets with ->newlist set
1994 
1995  if (qh.ONLYgood)
1996  newfacets reference horizon facets, but not vice versa
1997  ridges reference non-simplicial horizon ridges, but not vice versa
1998  does not change existing facets
1999  else
2000  sets qh.NEWfacets
2001  new facets attached to horizon facets and ridges
2002  for visible facets,
2003  visible->r.replace is corresponding new facet
2004 
2005  see also:
2006  qh_makenewplanes() -- make hyperplanes for facets
2007  qh_attachnewfacets() -- attachnewfacets if not done here(qh ONLYgood)
2008  qh_matchnewfacets() -- match up neighbors
2009  qh_updatevertices() -- update vertex neighbors and delvertices
2010  qh_deletevisible() -- delete visible facets
2011  qh_checkpolygon() --check the result
2012  qh_triangulate() -- triangulate a non-simplicial facet
2013 
2014  design:
2015  for each visible facet
2016  make new facets to its horizon facets
2017  update its f.replace
2018  clear its neighbor set
2019 */
2020 vertexT *qh_makenewfacets(pointT *point /*visible_list*/) {
2021  facetT *visible, *newfacet= NULL, *newfacet2= NULL, *neighbor, **neighborp;
2022  vertexT *apex;
2023  int numnew=0;
2024 
2025  qh newfacet_list= qh facet_tail;
2026  qh newvertex_list= qh vertex_tail;
2027  apex= qh_newvertex(point);
2028  qh_appendvertex(apex);
2029  qh visit_id++;
2030  if (!qh ONLYgood)
2031  qh NEWfacets= True;
2032  FORALLvisible_facets {
2033  FOREACHneighbor_(visible)
2034  neighbor->seen= False;
2035  if (visible->ridges) {
2036  visible->visitid= qh visit_id;
2037  newfacet2= qh_makenew_nonsimplicial(visible, apex, &numnew);
2038  }
2039  if (visible->simplicial)
2040  newfacet= qh_makenew_simplicial(visible, apex, &numnew);
2041  if (!qh ONLYgood) {
2042  if (newfacet2) /* newfacet is null if all ridges defined */
2043  newfacet= newfacet2;
2044  if (newfacet)
2045  visible->f.replace= newfacet;
2046  else
2047  zinc_(Zinsidevisible);
2048  SETfirst_(visible->neighbors)= NULL;
2049  }
2050  }
2051  trace1((qh ferr, 1032, "qh_makenewfacets: created %d new facets from point p%d to horizon\n",
2052  numnew, qh_pointid(point)));
2053  if (qh IStracing >= 4)
2054  qh_printfacetlist(qh newfacet_list, NULL, qh_ALL);
2055  return apex;
2056 } /* makenewfacets */
2057 
2058 /*-<a href="qh-poly.htm#TOC"
2059  >-------------------------------</a><a name="matchduplicates">-</a>
2060 
2061  qh_matchduplicates( atfacet, atskip, hashsize, hashcount )
2062  match duplicate ridges in qh.hash_table for atfacet/atskip
2063  duplicates marked with ->dupridge and qh_DUPLICATEridge
2064 
2065  returns:
2066  picks match with worst merge (min distance apart)
2067  updates hashcount
2068 
2069  see also:
2070  qh_matchneighbor
2071 
2072  notes:
2073 
2074  design:
2075  compute hash value for atfacet and atskip
2076  repeat twice -- once to make best matches, once to match the rest
2077  for each possible facet in qh.hash_table
2078  if it is a matching facet and pass 2
2079  make match
2080  unless tricoplanar, mark match for merging (qh_MERGEridge)
2081  [e.g., tricoplanar RBOX s 1000 t993602376 | QHULL C-1e-3 d Qbb FA Qt]
2082  if it is a matching facet and pass 1
2083  test if this is a better match
2084  if pass 1,
2085  make best match (it will not be merged)
2086 */
2087 #ifndef qh_NOmerge
2088 void qh_matchduplicates(facetT *atfacet, int atskip, int hashsize, int *hashcount) {
2089  boolT same, ismatch;
2090  int hash, scan;
2091  facetT *facet, *newfacet, *maxmatch= NULL, *maxmatch2= NULL, *nextfacet;
2092  int skip, newskip, nextskip= 0, maxskip= 0, maxskip2= 0, makematch;
2093  realT maxdist= -REALmax, mindist, dist2, low, high;
2094 
2095  hash= qh_gethash(hashsize, atfacet->vertices, qh hull_dim, 1,
2096  SETelem_(atfacet->vertices, atskip));
2097  trace2((qh ferr, 2046, "qh_matchduplicates: find duplicate matches for f%d skip %d hash %d hashcount %d\n",
2098  atfacet->id, atskip, hash, *hashcount));
2099  for (makematch= 0; makematch < 2; makematch++) {
2100  qh visit_id++;
2101  for (newfacet= atfacet, newskip= atskip; newfacet; newfacet= nextfacet, newskip= nextskip) {
2102  zinc_(Zhashlookup);
2103  nextfacet= NULL;
2104  newfacet->visitid= qh visit_id;
2105  for (scan= hash; (facet= SETelemt_(qh hash_table, scan, facetT));
2106  scan= (++scan >= hashsize ? 0 : scan)) {
2107  if (!facet->dupridge || facet->visitid == qh visit_id)
2108  continue;
2109  zinc_(Zhashtests);
2110  if (qh_matchvertices(1, newfacet->vertices, newskip, facet->vertices, &skip, &same)) {
2111  ismatch= (same == (boolT)(newfacet->toporient ^ facet->toporient));
2112  if (SETelemt_(facet->neighbors, skip, facetT) != qh_DUPLICATEridge) {
2113  if (!makematch) {
2114  qh_fprintf(qh ferr, 6155, "qhull internal error (qh_matchduplicates): missing dupridge at f%d skip %d for new f%d skip %d hash %d\n",
2115  facet->id, skip, newfacet->id, newskip, hash);
2116  qh_errexit2(qh_ERRqhull, facet, newfacet);
2117  }
2118  }else if (ismatch && makematch) {
2119  if (SETelemt_(newfacet->neighbors, newskip, facetT) == qh_DUPLICATEridge) {
2120  SETelem_(facet->neighbors, skip)= newfacet;
2121  if (newfacet->tricoplanar)
2122  SETelem_(newfacet->neighbors, newskip)= facet;
2123  else
2124  SETelem_(newfacet->neighbors, newskip)= qh_MERGEridge;
2125  *hashcount -= 2; /* removed two unmatched facets */
2126  trace4((qh ferr, 4059, "qh_matchduplicates: duplicate f%d skip %d matched with new f%d skip %d merge\n",
2127  facet->id, skip, newfacet->id, newskip));
2128  }
2129  }else if (ismatch) {
2130  mindist= qh_getdistance(facet, newfacet, &low, &high);
2131  dist2= qh_getdistance(newfacet, facet, &low, &high);
2132  minimize_(mindist, dist2);
2133  if (mindist > maxdist) {
2134  maxdist= mindist;
2135  maxmatch= facet;
2136  maxskip= skip;
2137  maxmatch2= newfacet;
2138  maxskip2= newskip;
2139  }
2140  trace3((qh ferr, 3018, "qh_matchduplicates: duplicate f%d skip %d new f%d skip %d at dist %2.2g, max is now f%d f%d\n",
2141  facet->id, skip, newfacet->id, newskip, mindist,
2142  maxmatch->id, maxmatch2->id));
2143  }else { /* !ismatch */
2144  nextfacet= facet;
2145  nextskip= skip;
2146  }
2147  }
2148  if (makematch && !facet
2149  && SETelemt_(facet->neighbors, skip, facetT) == qh_DUPLICATEridge) {
2150  qh_fprintf(qh ferr, 6156, "qhull internal error (qh_matchduplicates): no MERGEridge match for duplicate f%d skip %d at hash %d\n",
2151  newfacet->id, newskip, hash);
2152  qh_errexit(qh_ERRqhull, newfacet, NULL);
2153  }
2154  }
2155  } /* end of for each new facet at hash */
2156  if (!makematch) {
2157  if (!maxmatch) {
2158  qh_fprintf(qh ferr, 6157, "qhull internal error (qh_matchduplicates): no maximum match at duplicate f%d skip %d at hash %d\n",
2159  atfacet->id, atskip, hash);
2160  qh_errexit(qh_ERRqhull, atfacet, NULL);
2161  }
2162  SETelem_(maxmatch->neighbors, maxskip)= maxmatch2; /* maxmatch!=0 by QH6157 */
2163  SETelem_(maxmatch2->neighbors, maxskip2)= maxmatch;
2164  *hashcount -= 2; /* removed two unmatched facets */
2165  zzinc_(Zmultiridge);
2166  trace0((qh ferr, 25, "qh_matchduplicates: duplicate f%d skip %d matched with new f%d skip %d keep\n",
2167  maxmatch->id, maxskip, maxmatch2->id, maxskip2));
2168  qh_precision("ridge with multiple neighbors");
2169  if (qh IStracing >= 4)
2170  qh_errprint("DUPLICATED/MATCH", maxmatch, maxmatch2, NULL, NULL);
2171  }
2172  }
2173 } /* matchduplicates */
2174 
2175 /*-<a href="qh-poly.htm#TOC"
2176  >-------------------------------</a><a name="nearcoplanar">-</a>
2177 
2178  qh_nearcoplanar()
2179  for all facets, remove near-inside points from facet->coplanarset</li>
2180  coplanar points defined by innerplane from qh_outerinner()
2181 
2182  returns:
2183  if qh KEEPcoplanar && !qh KEEPinside
2184  facet->coplanarset only contains coplanar points
2185  if qh.JOGGLEmax
2186  drops inner plane by another qh.JOGGLEmax diagonal since a
2187  vertex could shift out while a coplanar point shifts in
2188 
2189  notes:
2190  used for qh.PREmerge and qh.JOGGLEmax
2191  must agree with computation of qh.NEARcoplanar in qh_detroundoff()
2192  design:
2193  if not keeping coplanar or inside points
2194  free all coplanar sets
2195  else if not keeping both coplanar and inside points
2196  remove !coplanar or !inside points from coplanar sets
2197 */
2198 void qh_nearcoplanar(void /* qh.facet_list */) {
2199  facetT *facet;
2200  pointT *point, **pointp;
2201  int numpart;
2202  realT dist, innerplane;
2203 
2204  if (!qh KEEPcoplanar && !qh KEEPinside) {
2205  FORALLfacets {
2206  if (facet->coplanarset)
2207  qh_setfree( &facet->coplanarset);
2208  }
2209  }else if (!qh KEEPcoplanar || !qh KEEPinside) {
2210  qh_outerinner(NULL, NULL, &innerplane);
2211  if (qh JOGGLEmax < REALmax/2)
2212  innerplane -= qh JOGGLEmax * sqrt((realT)qh hull_dim);
2213  numpart= 0;
2214  FORALLfacets {
2215  if (facet->coplanarset) {
2216  FOREACHpoint_(facet->coplanarset) {
2217  numpart++;
2218  qh_distplane(point, facet, &dist);
2219  if (dist < innerplane) {
2220  if (!qh KEEPinside)
2221  SETref_(point)= NULL;
2222  }else if (!qh KEEPcoplanar)
2223  SETref_(point)= NULL;
2224  }
2225  qh_setcompact(facet->coplanarset);
2226  }
2227  }
2228  zzadd_(Zcheckpart, numpart);
2229  }
2230 } /* nearcoplanar */
2231 
2232 /*-<a href="qh-poly.htm#TOC"
2233  >-------------------------------</a><a name="nearvertex">-</a>
2234 
2235  qh_nearvertex( facet, point, bestdist )
2236  return nearest vertex in facet to point
2237 
2238  returns:
2239  vertex and its distance
2240 
2241  notes:
2242  if qh.DELAUNAY
2243  distance is measured in the input set
2244  searches neighboring tricoplanar facets (requires vertexneighbors)
2245  Slow implementation. Recomputes vertex set for each point.
2246  The vertex set could be stored in the qh.keepcentrum facet.
2247 */
2248 vertexT *qh_nearvertex(facetT *facet, pointT *point, realT *bestdistp) {
2249  realT bestdist= REALmax, dist;
2250  vertexT *bestvertex= NULL, *vertex, **vertexp, *apex;
2251  coordT *center;
2252  facetT *neighbor, **neighborp;
2253  setT *vertices;
2254  int dim= qh hull_dim;
2255 
2256  if (qh DELAUNAY)
2257  dim--;
2258  if (facet->tricoplanar) {
2259  if (!qh VERTEXneighbors || !facet->center) {
2260  qh_fprintf(qh ferr, 6158, "qhull internal error (qh_nearvertex): qh.VERTEXneighbors and facet->center required for tricoplanar facets\n");
2261  qh_errexit(qh_ERRqhull, facet, NULL);
2262  }
2263  vertices= qh_settemp(qh TEMPsize);
2264  apex= SETfirstt_(facet->vertices, vertexT);
2265  center= facet->center;
2266  FOREACHneighbor_(apex) {
2267  if (neighbor->center == center) {
2268  FOREACHvertex_(neighbor->vertices)
2269  qh_setappend(&vertices, vertex);
2270  }
2271  }
2272  }else
2273  vertices= facet->vertices;
2274  FOREACHvertex_(vertices) {
2275  dist= qh_pointdist(vertex->point, point, -dim);
2276  if (dist < bestdist) {
2277  bestdist= dist;
2278  bestvertex= vertex;
2279  }
2280  }
2281  if (facet->tricoplanar)
2282  qh_settempfree(&vertices);
2283  *bestdistp= sqrt(bestdist);
2284  if (!bestvertex) {
2285  qh_fprintf(qh ferr, 6261, "qhull internal error (qh_nearvertex): did not find bestvertex for f%d p%d\n", facet->id, qh_pointid(point));
2286  qh_errexit(qh_ERRqhull, facet, NULL);
2287  }
2288  trace3((qh ferr, 3019, "qh_nearvertex: v%d dist %2.2g for f%d p%d\n",
2289  bestvertex->id, *bestdistp, facet->id, qh_pointid(point))); /* bestvertex!=0 by QH2161 */
2290  return bestvertex;
2291 } /* nearvertex */
2292 
2293 /*-<a href="qh-poly.htm#TOC"
2294  >-------------------------------</a><a name="newhashtable">-</a>
2295 
2296  qh_newhashtable( newsize )
2297  returns size of qh.hash_table of at least newsize slots
2298 
2299  notes:
2300  assumes qh.hash_table is NULL
2301  qh_HASHfactor determines the number of extra slots
2302  size is not divisible by 2, 3, or 5
2303 */
2304 int qh_newhashtable(int newsize) {
2305  int size;
2306 
2307  size= ((newsize+1)*qh_HASHfactor) | 0x1; /* odd number */
2308  while (True) {
2309  if (newsize<0 || size<0) {
2310  qh_fprintf(qhmem.ferr, 6236, "qhull error (qh_newhashtable): negative request (%d) or size (%d). Did int overflow due to high-D?\n", newsize, size); /* WARN64 */
2311  qh_errexit(qhmem_ERRmem, NULL, NULL);
2312  }
2313  if ((size%3) && (size%5))
2314  break;
2315  size += 2;
2316  /* loop terminates because there is an infinite number of primes */
2317  }
2318  qh hash_table= qh_setnew(size);
2319  qh_setzero(qh hash_table, 0, size);
2320  return size;
2321 } /* newhashtable */
2322 
2323 /*-<a href="qh-poly.htm#TOC"
2324  >-------------------------------</a><a name="newvertex">-</a>
2325 
2326  qh_newvertex( point )
2327  returns a new vertex for point
2328 */
2329 vertexT *qh_newvertex(pointT *point) {
2330  vertexT *vertex;
2331 
2332  zinc_(Ztotvertices);
2333  vertex= (vertexT *)qh_memalloc((int)sizeof(vertexT));
2334  memset((char *) vertex, (size_t)0, sizeof(vertexT));
2335  if (qh vertex_id == UINT_MAX) {
2336  qh_memfree(vertex, (int)sizeof(vertexT));
2337  qh_fprintf(qh ferr, 6159, "qhull error: more than 2^32 vertices. vertexT.id field overflows. Vertices would not be sorted correctly.\n");
2338  qh_errexit(qh_ERRqhull, NULL, NULL);
2339  }
2340  if (qh vertex_id == qh tracevertex_id)
2341  qh tracevertex= vertex;
2342  vertex->id= qh vertex_id++;
2343  vertex->point= point;
2344  trace4((qh ferr, 4060, "qh_newvertex: vertex p%d(v%d) created\n", qh_pointid(vertex->point),
2345  vertex->id));
2346  return(vertex);
2347 } /* newvertex */
2348 
2349 /*-<a href="qh-poly.htm#TOC"
2350  >-------------------------------</a><a name="nextridge3d">-</a>
2351 
2352  qh_nextridge3d( atridge, facet, vertex )
2353  return next ridge and vertex for a 3d facet
2354  returns NULL on error
2355  [for QhullFacet::nextRidge3d] Does not call qh_errexit nor access qh_qh.
2356 
2357  notes:
2358  in qh_ORIENTclock order
2359  this is a O(n^2) implementation to trace all ridges
2360  be sure to stop on any 2nd visit
2361  same as QhullRidge::nextRidge3d
2362  does not use qh_qh or qh_errexit [QhullFacet.cpp]
2363 
2364  design:
2365  for each ridge
2366  exit if it is the ridge after atridge
2367 */
2368 ridgeT *qh_nextridge3d(ridgeT *atridge, facetT *facet, vertexT **vertexp) {
2369  vertexT *atvertex, *vertex, *othervertex;
2370  ridgeT *ridge, **ridgep;
2371 
2372  if ((atridge->top == facet) ^ qh_ORIENTclock)
2373  atvertex= SETsecondt_(atridge->vertices, vertexT);
2374  else
2375  atvertex= SETfirstt_(atridge->vertices, vertexT);
2376  FOREACHridge_(facet->ridges) {
2377  if (ridge == atridge)
2378  continue;
2379  if ((ridge->top == facet) ^ qh_ORIENTclock) {
2380  othervertex= SETsecondt_(ridge->vertices, vertexT);
2381  vertex= SETfirstt_(ridge->vertices, vertexT);
2382  }else {
2383  vertex= SETsecondt_(ridge->vertices, vertexT);
2384  othervertex= SETfirstt_(ridge->vertices, vertexT);
2385  }
2386  if (vertex == atvertex) {
2387  if (vertexp)
2388  *vertexp= othervertex;
2389  return ridge;
2390  }
2391  }
2392  return NULL;
2393 } /* nextridge3d */
2394 #else /* qh_NOmerge */
2395 void qh_matchduplicates(facetT *atfacet, int atskip, int hashsize, int *hashcount) {
2396 }
2397 ridgeT *qh_nextridge3d(ridgeT *atridge, facetT *facet, vertexT **vertexp) {
2398 
2399  return NULL;
2400 }
2401 #endif /* qh_NOmerge */
2402 
2403 /*-<a href="qh-poly.htm#TOC"
2404  >-------------------------------</a><a name="outcoplanar">-</a>
2405 
2406  qh_outcoplanar()
2407  move points from all facets' outsidesets to their coplanarsets
2408 
2409  notes:
2410  for post-processing under qh.NARROWhull
2411 
2412  design:
2413  for each facet
2414  for each outside point for facet
2415  partition point into coplanar set
2416 */
2417 void qh_outcoplanar(void /* facet_list */) {
2418  pointT *point, **pointp;
2419  facetT *facet;
2420  realT dist;
2421 
2422  trace1((qh ferr, 1033, "qh_outcoplanar: move outsideset to coplanarset for qh NARROWhull\n"));
2423  FORALLfacets {
2424  FOREACHpoint_(facet->outsideset) {
2425  qh num_outside--;
2426  if (qh KEEPcoplanar || qh KEEPnearinside) {
2427  qh_distplane(point, facet, &dist);
2428  zinc_(Zpartition);
2429  qh_partitioncoplanar(point, facet, &dist);
2430  }
2431  }
2432  qh_setfree(&facet->outsideset);
2433  }
2434 } /* outcoplanar */
2435 
2436 /*-<a href="qh-poly.htm#TOC"
2437  >-------------------------------</a><a name="point">-</a>
2438 
2439  qh_point( id )
2440  return point for a point id, or NULL if unknown
2441 
2442  alternative code:
2443  return((pointT *)((unsigned long)qh.first_point
2444  + (unsigned long)((id)*qh.normal_size)));
2445 */
2446 pointT *qh_point(int id) {
2447 
2448  if (id < 0)
2449  return NULL;
2450  if (id < qh num_points)
2451  return qh first_point + id * qh hull_dim;
2452  id -= qh num_points;
2453  if (id < qh_setsize(qh other_points))
2454  return SETelemt_(qh other_points, id, pointT);
2455  return NULL;
2456 } /* point */
2457 
2458 /*-<a href="qh-poly.htm#TOC"
2459  >-------------------------------</a><a name="point_add">-</a>
2460 
2461  qh_point_add( set, point, elem )
2462  stores elem at set[point.id]
2463 
2464  returns:
2465  access function for qh_pointfacet and qh_pointvertex
2466 
2467  notes:
2468  checks point.id
2469 */
2470 void qh_point_add(setT *set, pointT *point, void *elem) {
2471  int id, size;
2472 
2473  SETreturnsize_(set, size);
2474  if ((id= qh_pointid(point)) < 0)
2475  qh_fprintf(qh ferr, 7067, "qhull internal warning (point_add): unknown point %p id %d\n",
2476  point, id);
2477  else if (id >= size) {
2478  qh_fprintf(qh ferr, 6160, "qhull internal errror(point_add): point p%d is out of bounds(%d)\n",
2479  id, size);
2480  qh_errexit(qh_ERRqhull, NULL, NULL);
2481  }else
2482  SETelem_(set, id)= elem;
2483 } /* point_add */
2484 
2485 
2486 /*-<a href="qh-poly.htm#TOC"
2487  >-------------------------------</a><a name="pointfacet">-</a>
2488 
2489  qh_pointfacet()
2490  return temporary set of facet for each point
2491  the set is indexed by point id
2492 
2493  notes:
2494  vertices assigned to one of the facets
2495  coplanarset assigned to the facet
2496  outside set assigned to the facet
2497  NULL if no facet for point (inside)
2498  includes qh.GOODpointp
2499 
2500  access:
2501  FOREACHfacet_i_(facets) { ... }
2502  SETelem_(facets, i)
2503 
2504  design:
2505  for each facet
2506  add each vertex
2507  add each coplanar point
2508  add each outside point
2509 */
2510 setT *qh_pointfacet(void /*qh.facet_list*/) {
2511  int numpoints= qh num_points + qh_setsize(qh other_points);
2512  setT *facets;
2513  facetT *facet;
2514  vertexT *vertex, **vertexp;
2515  pointT *point, **pointp;
2516 
2517  facets= qh_settemp(numpoints);
2518  qh_setzero(facets, 0, numpoints);
2519  qh vertex_visit++;
2520  FORALLfacets {
2521  FOREACHvertex_(facet->vertices) {
2522  if (vertex->visitid != qh vertex_visit) {
2523  vertex->visitid= qh vertex_visit;
2524  qh_point_add(facets, vertex->point, facet);
2525  }
2526  }
2527  FOREACHpoint_(facet->coplanarset)
2528  qh_point_add(facets, point, facet);
2529  FOREACHpoint_(facet->outsideset)
2530  qh_point_add(facets, point, facet);
2531  }
2532  return facets;
2533 } /* pointfacet */
2534 
2535 /*-<a href="qh-poly.htm#TOC"
2536  >-------------------------------</a><a name="pointvertex">-</a>
2537 
2538  qh_pointvertex( )
2539  return temporary set of vertices indexed by point id
2540  entry is NULL if no vertex for a point
2541  this will include qh.GOODpointp
2542 
2543  access:
2544  FOREACHvertex_i_(vertices) { ... }
2545  SETelem_(vertices, i)
2546 */
2547 setT *qh_pointvertex(void /*qh.facet_list*/) {
2548  int numpoints= qh num_points + qh_setsize(qh other_points);
2549  setT *vertices;
2550  vertexT *vertex;
2551 
2552  vertices= qh_settemp(numpoints);
2553  qh_setzero(vertices, 0, numpoints);
2554  FORALLvertices
2555  qh_point_add(vertices, vertex->point, vertex);
2556  return vertices;
2557 } /* pointvertex */
2558 
2559 
2560 /*-<a href="qh-poly.htm#TOC"
2561  >-------------------------------</a><a name="prependfacet">-</a>
2562 
2563  qh_prependfacet( facet, facetlist )
2564  prepend facet to the start of a facetlist
2565 
2566  returns:
2567  increments qh.numfacets
2568  updates facetlist, qh.facet_list, facet_next
2569 
2570  notes:
2571  be careful of prepending since it can lose a pointer.
2572  e.g., can lose _next by deleting and then prepending before _next
2573 */
2574 void qh_prependfacet(facetT *facet, facetT **facetlist) {
2575  facetT *prevfacet, *list;
2576 
2577 
2578  trace4((qh ferr, 4061, "qh_prependfacet: prepend f%d before f%d\n",
2579  facet->id, getid_(*facetlist)));
2580  if (!*facetlist)
2581  (*facetlist)= qh facet_tail;
2582  list= *facetlist;
2583  prevfacet= list->previous;
2584  facet->previous= prevfacet;
2585  if (prevfacet)
2586  prevfacet->next= facet;
2587  list->previous= facet;
2588  facet->next= *facetlist;
2589  if (qh facet_list == list) /* this may change *facetlist */
2590  qh facet_list= facet;
2591  if (qh facet_next == list)
2592  qh facet_next= facet;
2593  *facetlist= facet;
2594  qh num_facets++;
2595 } /* prependfacet */
2596 
2597 
2598 /*-<a href="qh-poly.htm#TOC"
2599  >-------------------------------</a><a name="printhashtable">-</a>
2600 
2601  qh_printhashtable( fp )
2602  print hash table to fp
2603 
2604  notes:
2605  not in I/O to avoid bringing io.c in
2606 
2607  design:
2608  for each hash entry
2609  if defined
2610  if unmatched or will merge (NULL, qh_MERGEridge, qh_DUPLICATEridge)
2611  print entry and neighbors
2612 */
2613 void qh_printhashtable(FILE *fp) {
2614  facetT *facet, *neighbor;
2615  int id, facet_i, facet_n, neighbor_i= 0, neighbor_n= 0;
2616  vertexT *vertex, **vertexp;
2617 
2618  FOREACHfacet_i_(qh hash_table) {
2619  if (facet) {
2620  FOREACHneighbor_i_(facet) {
2621  if (!neighbor || neighbor == qh_MERGEridge || neighbor == qh_DUPLICATEridge)
2622  break;
2623  }
2624  if (neighbor_i == neighbor_n)
2625  continue;
2626  qh_fprintf(fp, 9283, "hash %d f%d ", facet_i, facet->id);
2627  FOREACHvertex_(facet->vertices)
2628  qh_fprintf(fp, 9284, "v%d ", vertex->id);
2629  qh_fprintf(fp, 9285, "\n neighbors:");
2630  FOREACHneighbor_i_(facet) {
2631  if (neighbor == qh_MERGEridge)
2632  id= -3;
2633  else if (neighbor == qh_DUPLICATEridge)
2634  id= -2;
2635  else
2636  id= getid_(neighbor);
2637  qh_fprintf(fp, 9286, " %d", id);
2638  }
2639  qh_fprintf(fp, 9287, "\n");
2640  }
2641  }
2642 } /* printhashtable */
2643 
2644 
2645 /*-<a href="qh-poly.htm#TOC"
2646  >-------------------------------</a><a name="printlists">-</a>
2647 
2648  qh_printlists( fp )
2649  print out facet and vertex list for debugging (without 'f/v' tags)
2650 */
2651 void qh_printlists(void) {
2652  facetT *facet;
2653  vertexT *vertex;
2654  int count= 0;
2655 
2656  qh_fprintf(qh ferr, 8108, "qh_printlists: facets:");
2657  FORALLfacets {
2658  if (++count % 100 == 0)
2659  qh_fprintf(qh ferr, 8109, "\n ");
2660  qh_fprintf(qh ferr, 8110, " %d", facet->id);
2661  }
2662  qh_fprintf(qh ferr, 8111, "\n new facets %d visible facets %d next facet for qh_addpoint %d\n vertices(new %d):",
2663  getid_(qh newfacet_list), getid_(qh visible_list), getid_(qh facet_next),
2664  getid_(qh newvertex_list));
2665  count = 0;
2666  FORALLvertices {
2667  if (++count % 100 == 0)
2668  qh_fprintf(qh ferr, 8112, "\n ");
2669  qh_fprintf(qh ferr, 8113, " %d", vertex->id);
2670  }
2671  qh_fprintf(qh ferr, 8114, "\n");
2672 } /* printlists */
2673 
2674 /*-<a href="qh-poly.htm#TOC"
2675  >-------------------------------</a><a name="resetlists">-</a>
2676 
2677  qh_resetlists( stats, qh_RESETvisible )
2678  reset newvertex_list, newfacet_list, visible_list
2679  if stats,
2680  maintains statistics
2681 
2682  returns:
2683  visible_list is empty if qh_deletevisible was called
2684 */
2685 void qh_resetlists(boolT stats, boolT resetVisible /*qh.newvertex_list newfacet_list visible_list*/) {
2686  vertexT *vertex;
2687  facetT *newfacet, *visible;
2688  int totnew=0, totver=0;
2689 
2690  if (stats) {
2691  FORALLvertex_(qh newvertex_list)
2692  totver++;
2693  FORALLnew_facets
2694  totnew++;
2695  zadd_(Zvisvertextot, totver);
2696  zmax_(Zvisvertexmax, totver);
2697  zadd_(Znewfacettot, totnew);
2698  zmax_(Znewfacetmax, totnew);
2699  }
2700  FORALLvertex_(qh newvertex_list)
2701  vertex->newlist= False;
2702  qh newvertex_list= NULL;
2703  FORALLnew_facets
2704  newfacet->newfacet= False;
2705  qh newfacet_list= NULL;
2706  if (resetVisible) {
2707  FORALLvisible_facets {
2708  visible->f.replace= NULL;
2709  visible->visible= False;
2710  }
2711  qh num_visible= 0;
2712  }
2713  qh visible_list= NULL; /* may still have visible facets via qh_triangulate */
2714  qh NEWfacets= False;
2715 } /* resetlists */
2716 
2717 /*-<a href="qh-poly.htm#TOC"
2718  >-------------------------------</a><a name="setvoronoi_all">-</a>
2719 
2720  qh_setvoronoi_all()
2721  compute Voronoi centers for all facets
2722  includes upperDelaunay facets if qh.UPPERdelaunay ('Qu')
2723 
2724  returns:
2725  facet->center is the Voronoi center
2726 
2727  notes:
2728  this is unused/untested code
2729  please email bradb@shore.net if this works ok for you
2730 
2731  use:
2732  FORALLvertices {...} to locate the vertex for a point.
2733  FOREACHneighbor_(vertex) {...} to visit the Voronoi centers for a Voronoi cell.
2734 */
2735 void qh_setvoronoi_all(void) {
2736  facetT *facet;
2737 
2738  qh_clearcenters(qh_ASvoronoi);
2739  qh_vertexneighbors();
2740 
2741  FORALLfacets {
2742  if (!facet->normal || !facet->upperdelaunay || qh UPPERdelaunay) {
2743  if (!facet->center)
2744  facet->center= qh_facetcenter(facet->vertices);
2745  }
2746  }
2747 } /* setvoronoi_all */
2748 
2749 #ifndef qh_NOmerge
2750 
2751 /*-<a href="qh-poly.htm#TOC"
2752  >-------------------------------</a><a name="triangulate">-</a>
2753 
2754  qh_triangulate()
2755  triangulate non-simplicial facets on qh.facet_list,
2756  if qh VORONOI, sets Voronoi centers of non-simplicial facets
2757  nop if hasTriangulation
2758 
2759  returns:
2760  all facets simplicial
2761  each tricoplanar facet has ->f.triowner == owner of ->center,normal,etc.
2762 
2763  notes:
2764  call after qh_check_output since may switch to Voronoi centers
2765  Output may overwrite ->f.triowner with ->f.area
2766 */
2767 void qh_triangulate(void /*qh.facet_list*/) {
2768  facetT *facet, *nextfacet, *owner;
2769  int onlygood= qh ONLYgood;
2770  facetT *neighbor, *visible= NULL, *facet1, *facet2, *new_facet_list= NULL;
2771  facetT *orig_neighbor= NULL, *otherfacet;
2772  vertexT *new_vertex_list= NULL;
2773  mergeT *merge;
2774  mergeType mergetype;
2775  int neighbor_i, neighbor_n;
2776 
2777  if (qh hasTriangulation)
2778  return;
2779  trace1((qh ferr, 1034, "qh_triangulate: triangulate non-simplicial facets\n"));
2780  if (qh hull_dim == 2)
2781  return;
2782  if (qh VORONOI) { /* otherwise lose Voronoi centers [could rebuild vertex set from tricoplanar] */
2783  qh_clearcenters(qh_ASvoronoi);
2784  qh_vertexneighbors();
2785  }
2786  qh ONLYgood= False; /* for makenew_nonsimplicial */
2787  qh visit_id++;
2788  qh NEWfacets= True;
2789  qh degen_mergeset= qh_settemp(qh TEMPsize);
2790  qh newvertex_list= qh vertex_tail;
2791  for (facet= qh facet_list; facet && facet->next; facet= nextfacet) { /* non-simplicial facets moved to end */
2792  nextfacet= facet->next;
2793  if (facet->visible || facet->simplicial)
2794  continue;
2795  /* triangulate all non-simplicial facets, otherwise merging does not work, e.g., RBOX c P-0.1 P+0.1 P+0.1 D3 | QHULL d Qt Tv */
2796  if (!new_facet_list)
2797  new_facet_list= facet; /* will be moved to end */
2798  qh_triangulate_facet(facet, &new_vertex_list);
2799  }
2800  trace2((qh ferr, 2047, "qh_triangulate: delete null facets from f%d -- apex same as second vertex\n", getid_(new_facet_list)));
2801  for (facet= new_facet_list; facet && facet->next; facet= nextfacet) { /* null facets moved to end */
2802  nextfacet= facet->next;
2803  if (facet->visible)
2804  continue;
2805  if (facet->ridges) {
2806  if (qh_setsize(facet->ridges) > 0) {
2807  qh_fprintf(qh ferr, 6161, "qhull error (qh_triangulate): ridges still defined for f%d\n", facet->id);
2808  qh_errexit(qh_ERRqhull, facet, NULL);
2809  }
2810  qh_setfree(&facet->ridges);
2811  }
2812  if (SETfirst_(facet->vertices) == SETsecond_(facet->vertices)) {
2813  zinc_(Ztrinull);
2814  qh_triangulate_null(facet);
2815  }
2816  }
2817  trace2((qh ferr, 2048, "qh_triangulate: delete %d or more mirror facets -- same vertices and neighbors\n", qh_setsize(qh degen_mergeset)));
2818  qh visible_list= qh facet_tail;
2819  while ((merge= (mergeT*)qh_setdellast(qh degen_mergeset))) {
2820  facet1= merge->facet1;
2821  facet2= merge->facet2;
2822  mergetype= merge->type;
2823  qh_memfree(merge, (int)sizeof(mergeT));
2824  if (mergetype == MRGmirror) {
2825  zinc_(Ztrimirror);
2826  qh_triangulate_mirror(facet1, facet2);
2827  }
2828  }
2829  qh_settempfree(&qh degen_mergeset);
2830  trace2((qh ferr, 2049, "qh_triangulate: update neighbor lists for vertices from v%d\n", getid_(new_vertex_list)));
2831  qh newvertex_list= new_vertex_list; /* all vertices of new facets */
2832  qh visible_list= NULL;
2833  qh_updatevertices(/*qh.newvertex_list, empty newfacet_list and visible_list*/);
2834  qh_resetlists(False, !qh_RESETvisible /*qh.newvertex_list, empty newfacet_list and visible_list*/);
2835 
2836  trace2((qh ferr, 2050, "qh_triangulate: identify degenerate tricoplanar facets from f%d\n", getid_(new_facet_list)));
2837  trace2((qh ferr, 2051, "qh_triangulate: and replace facet->f.triowner with tricoplanar facets that own center, normal, etc.\n"));
2838  FORALLfacet_(new_facet_list) {
2839  if (facet->tricoplanar && !facet->visible) {
2840  FOREACHneighbor_i_(facet) {
2841  if (neighbor_i == 0) { /* first iteration */
2842  if (neighbor->tricoplanar)
2843  orig_neighbor= neighbor->f.triowner;
2844  else
2845  orig_neighbor= neighbor;
2846  }else {
2847  if (neighbor->tricoplanar)
2848  otherfacet= neighbor->f.triowner;
2849  else
2850  otherfacet= neighbor;
2851  if (orig_neighbor == otherfacet) {
2852  zinc_(Ztridegen);
2853  facet->degenerate= True;
2854  break;
2855  }
2856  }
2857  }
2858  }
2859  }
2860 
2861  trace2((qh ferr, 2052, "qh_triangulate: delete visible facets -- non-simplicial, null, and mirrored facets\n"));
2862  owner= NULL;
2863  visible= NULL;
2864  for (facet= new_facet_list; facet && facet->next; facet= nextfacet) { /* may delete facet */
2865  nextfacet= facet->next;
2866  if (facet->visible) {
2867  if (facet->tricoplanar) { /* a null or mirrored facet */
2868  qh_delfacet(facet);
2869  qh num_visible--;
2870  }else { /* a non-simplicial facet followed by its tricoplanars */
2871  if (visible && !owner) {
2872  /* RBOX 200 s D5 t1001471447 | QHULL Qt C-0.01 Qx Qc Tv Qt -- f4483 had 6 vertices/neighbors and 8 ridges */
2873  trace2((qh ferr, 2053, "qh_triangulate: all tricoplanar facets degenerate for non-simplicial facet f%d\n",
2874  visible->id));
2875  qh_delfacet(visible);
2876  qh num_visible--;
2877  }
2878  visible= facet;
2879  owner= NULL;
2880  }
2881  }else if (facet->tricoplanar) {
2882  if (facet->f.triowner != visible || visible==NULL) {
2883  qh_fprintf(qh ferr, 6162, "qhull error (qh_triangulate): tricoplanar facet f%d not owned by its visible, non-simplicial facet f%d\n", facet->id, getid_(visible));
2884  qh_errexit2(qh_ERRqhull, facet, visible);
2885  }
2886  if (owner)
2887  facet->f.triowner= owner;
2888  else if (!facet->degenerate) {
2889  owner= facet;
2890  nextfacet= visible->next; /* rescan tricoplanar facets with owner, visible!=0 by QH6162 */
2891  facet->keepcentrum= True; /* one facet owns ->normal, etc. */
2892  facet->coplanarset= visible->coplanarset;
2893  facet->outsideset= visible->outsideset;
2894  visible->coplanarset= NULL;
2895  visible->outsideset= NULL;
2896  if (!qh TRInormals) { /* center and normal copied to tricoplanar facets */
2897  visible->center= NULL;
2898  visible->normal= NULL;
2899  }
2900  qh_delfacet(visible);
2901  qh num_visible--;
2902  }
2903  }
2904  }
2905  if (visible && !owner) {
2906  trace2((qh ferr, 2054, "qh_triangulate: all tricoplanar facets degenerate for last non-simplicial facet f%d\n",
2907  visible->id));
2908  qh_delfacet(visible);
2909  qh num_visible--;
2910  }
2911  qh NEWfacets= False;
2912  qh ONLYgood= onlygood; /* restore value */
2913  if (qh CHECKfrequently)
2914  qh_checkpolygon(qh facet_list);
2915  qh hasTriangulation= True;
2916 } /* triangulate */
2917 
2918 
2919 /*-<a href="qh-poly.htm#TOC"
2920  >-------------------------------</a><a name="triangulate_facet">-</a>
2921 
2922  qh_triangulate_facet(qh, facetA, &firstVertex )
2923  triangulate a non-simplicial facet
2924  if qh.CENTERtype=qh_ASvoronoi, sets its Voronoi center
2925  returns:
2926  qh.newfacet_list == simplicial facets
2927  facet->tricoplanar set and ->keepcentrum false
2928  facet->degenerate set if duplicated apex
2929  facet->f.trivisible set to facetA
2930  facet->center copied from facetA (created if qh_ASvoronoi)
2931  qh_eachvoronoi, qh_detvridge, qh_detvridge3 assume centers copied
2932  facet->normal,offset,maxoutside copied from facetA
2933 
2934  notes:
2935  only called by qh_triangulate
2936  qh_makenew_nonsimplicial uses neighbor->seen for the same
2937  if qh.TRInormals, newfacet->normal will need qh_free
2938  if qh.TRInormals and qh_AScentrum, newfacet->center will need qh_free
2939  keepcentrum is also set on Zwidefacet in qh_mergefacet
2940  freed by qh_clearcenters
2941 
2942  see also:
2943  qh_addpoint() -- add a point
2944  qh_makenewfacets() -- construct a cone of facets for a new vertex
2945 
2946  design:
2947  if qh_ASvoronoi,
2948  compute Voronoi center (facet->center)
2949  select first vertex (highest ID to preserve ID ordering of ->vertices)
2950  triangulate from vertex to ridges
2951  copy facet->center, normal, offset
2952  update vertex neighbors
2953 */
2954 void qh_triangulate_facet(facetT *facetA, vertexT **first_vertex) {
2955  facetT *newfacet;
2956  facetT *neighbor, **neighborp;
2957  vertexT *apex;
2958  int numnew=0;
2959 
2960  trace3((qh ferr, 3020, "qh_triangulate_facet: triangulate facet f%d\n", facetA->id));
2961 
2962  if (qh IStracing >= 4)
2963  qh_printfacet(qh ferr, facetA);
2964  FOREACHneighbor_(facetA) {
2965  neighbor->seen= False;
2966  neighbor->coplanar= False;
2967  }
2968  if (qh CENTERtype == qh_ASvoronoi && !facetA->center /* matches upperdelaunay in qh_setfacetplane() */
2969  && fabs_(facetA->normal[qh hull_dim -1]) >= qh ANGLEround * qh_ZEROdelaunay) {
2970  facetA->center= qh_facetcenter(facetA->vertices);
2971  }
2972  qh_willdelete(facetA, NULL);
2973  qh newfacet_list= qh facet_tail;
2974  facetA->visitid= qh visit_id;
2975  apex= SETfirstt_(facetA->vertices, vertexT);
2976  qh_makenew_nonsimplicial(facetA, apex, &numnew);
2977  SETfirst_(facetA->neighbors)= NULL;
2978  FORALLnew_facets {
2979  newfacet->tricoplanar= True;
2980  newfacet->f.trivisible= facetA;
2981  newfacet->degenerate= False;
2982  newfacet->upperdelaunay= facetA->upperdelaunay;
2983  newfacet->good= facetA->good;
2984  if (qh TRInormals) { /* 'Q11' triangulate duplicates ->normal and ->center */
2985  newfacet->keepcentrum= True;
2986  if(facetA->normal){
2987  newfacet->normal= qh_memalloc(qh normal_size);
2988  memcpy((char *)newfacet->normal, facetA->normal, qh normal_size);
2989  }
2990  if (qh CENTERtype == qh_AScentrum)
2991  newfacet->center= qh_getcentrum(newfacet);
2992  else if (qh CENTERtype == qh_ASvoronoi && facetA->center){
2993  newfacet->center= qh_memalloc(qh center_size);
2994  memcpy((char *)newfacet->center, facetA->center, qh center_size);
2995  }
2996  }else {
2997  newfacet->keepcentrum= False;
2998  /* one facet will have keepcentrum=True at end of qh_triangulate */
2999  newfacet->normal= facetA->normal;
3000  newfacet->center= facetA->center;
3001  }
3002  newfacet->offset= facetA->offset;
3003 #if qh_MAXoutside
3004  newfacet->maxoutside= facetA->maxoutside;
3005 #endif
3006  }
3007  qh_matchnewfacets(/*qh.newfacet_list*/);
3008  zinc_(Ztricoplanar);
3009  zadd_(Ztricoplanartot, numnew);
3010  zmax_(Ztricoplanarmax, numnew);
3011  qh visible_list= NULL;
3012  if (!(*first_vertex))
3013  (*first_vertex)= qh newvertex_list;
3014  qh newvertex_list= NULL;
3015  qh_updatevertices(/*qh.newfacet_list, qh.empty visible_list and qh.newvertex_list*/);
3016  qh_resetlists(False, !qh_RESETvisible /*qh.newfacet_list, qh.empty visible_list and qh.newvertex_list*/);
3017 } /* triangulate_facet */
3018 
3019 /*-<a href="qh-poly.htm#TOC"
3020  >-------------------------------</a><a name="triangulate_link">-</a>
3021 
3022  qh_triangulate_link(oldfacetA, facetA, oldfacetB, facetB)
3023  relink facetA to facetB via oldfacets
3024  returns:
3025  adds mirror facets to qh degen_mergeset (4-d and up only)
3026  design:
3027  if they are already neighbors, the opposing neighbors become MRGmirror facets
3028 */
3029 void qh_triangulate_link(facetT *oldfacetA, facetT *facetA, facetT *oldfacetB, facetT *facetB) {
3030  int errmirror= False;
3031 
3032  trace3((qh ferr, 3021, "qh_triangulate_link: relink old facets f%d and f%d between neighbors f%d and f%d\n",
3033  oldfacetA->id, oldfacetB->id, facetA->id, facetB->id));
3034  if (qh_setin(facetA->neighbors, facetB)) {
3035  if (!qh_setin(facetB->neighbors, facetA))
3036  errmirror= True;
3037  else
3038  qh_appendmergeset(facetA, facetB, MRGmirror, NULL);
3039  }else if (qh_setin(facetB->neighbors, facetA))
3040  errmirror= True;
3041  if (errmirror) {
3042  qh_fprintf(qh ferr, 6163, "qhull error (qh_triangulate_link): mirror facets f%d and f%d do not match for old facets f%d and f%d\n",
3043  facetA->id, facetB->id, oldfacetA->id, oldfacetB->id);
3044  qh_errexit2(qh_ERRqhull, facetA, facetB);
3045  }
3046  qh_setreplace(facetB->neighbors, oldfacetB, facetA);
3047  qh_setreplace(facetA->neighbors, oldfacetA, facetB);
3048 } /* triangulate_link */
3049 
3050 /*-<a href="qh-poly.htm#TOC"
3051  >-------------------------------</a><a name="triangulate_mirror">-</a>
3052 
3053  qh_triangulate_mirror(facetA, facetB)
3054  delete mirrored facets from qh_triangulate_null() and qh_triangulate_mirror
3055  a mirrored facet shares the same vertices of a logical ridge
3056  design:
3057  since a null facet duplicates the first two vertices, the opposing neighbors absorb the null facet
3058  if they are already neighbors, the opposing neighbors become MRGmirror facets
3059 */
3060 void qh_triangulate_mirror(facetT *facetA, facetT *facetB) {
3061  facetT *neighbor, *neighborB;
3062  int neighbor_i, neighbor_n;
3063 
3064  trace3((qh ferr, 3022, "qh_triangulate_mirror: delete mirrored facets f%d and f%d\n",
3065  facetA->id, facetB->id));
3066  FOREACHneighbor_i_(facetA) {
3067  neighborB= SETelemt_(facetB->neighbors, neighbor_i, facetT);
3068  if (neighbor == neighborB)
3069  continue; /* occurs twice */
3070  qh_triangulate_link(facetA, neighbor, facetB, neighborB);
3071  }
3072  qh_willdelete(facetA, NULL);
3073  qh_willdelete(facetB, NULL);
3074 } /* triangulate_mirror */
3075 
3076 /*-<a href="qh-poly.htm#TOC"
3077  >-------------------------------</a><a name="triangulate_null">-</a>
3078 
3079  qh_triangulate_null(facetA)
3080  remove null facetA from qh_triangulate_facet()
3081  a null facet has vertex #1 (apex) == vertex #2
3082  returns:
3083  adds facetA to ->visible for deletion after qh_updatevertices
3084  qh degen_mergeset contains mirror facets (4-d and up only)
3085  design:
3086  since a null facet duplicates the first two vertices, the opposing neighbors absorb the null facet
3087  if they are already neighbors, the opposing neighbors become MRGmirror facets
3088 */
3089 void qh_triangulate_null(facetT *facetA) {
3090  facetT *neighbor, *otherfacet;
3091 
3092  trace3((qh ferr, 3023, "qh_triangulate_null: delete null facet f%d\n", facetA->id));
3093  neighbor= SETfirstt_(facetA->neighbors, facetT);
3094  otherfacet= SETsecondt_(facetA->neighbors, facetT);
3095  qh_triangulate_link(facetA, neighbor, facetA, otherfacet);
3096  qh_willdelete(facetA, NULL);
3097 } /* triangulate_null */
3098 
3099 #else /* qh_NOmerge */
3100 void qh_triangulate(void) {
3101 }
3102 #endif /* qh_NOmerge */
3103 
3104  /*-<a href="qh-poly.htm#TOC"
3105  >-------------------------------</a><a name="vertexintersect">-</a>
3106 
3107  qh_vertexintersect( vertexsetA, vertexsetB )
3108  intersects two vertex sets (inverse id ordered)
3109  vertexsetA is a temporary set at the top of qhmem.tempstack
3110 
3111  returns:
3112  replaces vertexsetA with the intersection
3113 
3114  notes:
3115  could overwrite vertexsetA if currently too slow
3116 */
3117 void qh_vertexintersect(setT **vertexsetA,setT *vertexsetB) {
3118  setT *intersection;
3119 
3120  intersection= qh_vertexintersect_new(*vertexsetA, vertexsetB);
3121  qh_settempfree(vertexsetA);
3122  *vertexsetA= intersection;
3123  qh_settemppush(intersection);
3124 } /* vertexintersect */
3125 
3126 /*-<a href="qh-poly.htm#TOC"
3127  >-------------------------------</a><a name="vertexintersect_new">-</a>
3128 
3129  qh_vertexintersect_new( )
3130  intersects two vertex sets (inverse id ordered)
3131 
3132  returns:
3133  a new set
3134 */
3135 setT *qh_vertexintersect_new(setT *vertexsetA,setT *vertexsetB) {
3136  setT *intersection= qh_setnew(qh hull_dim - 1);
3137  vertexT **vertexA= SETaddr_(vertexsetA, vertexT);
3138  vertexT **vertexB= SETaddr_(vertexsetB, vertexT);
3139 
3140  while (*vertexA && *vertexB) {
3141  if (*vertexA == *vertexB) {
3142  qh_setappend(&intersection, *vertexA);
3143  vertexA++; vertexB++;
3144  }else {
3145  if ((*vertexA)->id > (*vertexB)->id)
3146  vertexA++;
3147  else
3148  vertexB++;
3149  }
3150  }
3151  return intersection;
3152 } /* vertexintersect_new */
3153 
3154 /*-<a href="qh-poly.htm#TOC"
3155  >-------------------------------</a><a name="vertexneighbors">-</a>
3156 
3157  qh_vertexneighbors()
3158  for each vertex in qh.facet_list,
3159  determine its neighboring facets
3160 
3161  returns:
3162  sets qh.VERTEXneighbors
3163  nop if qh.VERTEXneighbors already set
3164  qh_addpoint() will maintain them
3165 
3166  notes:
3167  assumes all vertex->neighbors are NULL
3168 
3169  design:
3170  for each facet
3171  for each vertex
3172  append facet to vertex->neighbors
3173 */
3174 void qh_vertexneighbors(void /*qh.facet_list*/) {
3175  facetT *facet;
3176  vertexT *vertex, **vertexp;
3177 
3178  if (qh VERTEXneighbors)
3179  return;
3180  trace1((qh ferr, 1035, "qh_vertexneighbors: determing neighboring facets for each vertex\n"));
3181  qh vertex_visit++;
3182  FORALLfacets {
3183  if (facet->visible)
3184  continue;
3185  FOREACHvertex_(facet->vertices) {
3186  if (vertex->visitid != qh vertex_visit) {
3187  vertex->visitid= qh vertex_visit;
3188  vertex->neighbors= qh_setnew(qh hull_dim);
3189  }
3190  qh_setappend(&vertex->neighbors, facet);
3191  }
3192  }
3193  qh VERTEXneighbors= True;
3194 } /* vertexneighbors */
3195 
3196 /*-<a href="qh-poly.htm#TOC"
3197  >-------------------------------</a><a name="vertexsubset">-</a>
3198 
3199  qh_vertexsubset( vertexsetA, vertexsetB )
3200  returns True if vertexsetA is a subset of vertexsetB
3201  assumes vertexsets are sorted
3202 
3203  note:
3204  empty set is a subset of any other set
3205 */
3206 boolT qh_vertexsubset(setT *vertexsetA, setT *vertexsetB) {
3207  vertexT **vertexA= (vertexT **) SETaddr_(vertexsetA, vertexT);
3208  vertexT **vertexB= (vertexT **) SETaddr_(vertexsetB, vertexT);
3209 
3210  while (True) {
3211  if (!*vertexA)
3212  return True;
3213  if (!*vertexB)
3214  return False;
3215  if ((*vertexA)->id > (*vertexB)->id)
3216  return False;
3217  if (*vertexA == *vertexB)
3218  vertexA++;
3219  vertexB++;
3220  }
3221  return False; /* avoid warnings */
3222 } /* vertexsubset */
trace2
#define trace2(args)
Definition: qhull_a.h:82
qh_checkflipped
boolT qh_checkflipped(facetT *facet, realT *distp, boolT allerror)
Definition: poly.c:218
qh_ERRprec
#define qh_ERRprec
Definition: libqhull.h:196
qh_createsimplex
void qh_createsimplex(setT *vertices)
Definition: poly2.c:1082
qh_IScheckmax
#define qh_IScheckmax
Definition: libqhull.h:182
qh_MAXoutside
#define qh_MAXoutside
Definition: user.h:547
qh_newfacet
facetT * qh_newfacet(void)
Definition: poly.c:985
facetT::newfacet
flagT newfacet
Definition: libqhull.h:320
qh_ERRqhull
#define qh_ERRqhull
Definition: libqhull.h:198
qh_findfacet_all
facetT * qh_findfacet_all(pointT *point, realT *bestdist, boolT *isoutside, int *numpart)
Definition: poly2.c:1348
FORALLfacets
#define FORALLfacets
Definition: libqhull.h:840
mergeT::facet2
facetT * facet2
Definition: merge.h:93
facetT::notfurthest
flagT notfurthest
Definition: libqhull.h:329
zinc_
#define zinc_(id)
Definition: stat.h:386
qh_delridge
void qh_delridge(ridgeT *ridge)
Definition: poly2.c:1126
boolT
#define boolT
Definition: libqhull.h:121
qh_settruncate
void qh_settruncate(setT *set, int size)
Definition: qset.c:1275
qh_newvertex
vertexT * qh_newvertex(pointT *point)
Definition: poly2.c:2329
facetT::neighbors
setT * neighbors
Definition: libqhull.h:299
qh_triangulate
void qh_triangulate(void)
Definition: poly2.c:2767
qh_RANDOMmax
#define qh_RANDOMmax
Definition: user.h:282
fmax_
#define fmax_(a, b)
Definition: geom.h:35
setT
Definition: qset.h:83
qh_initialhull
void qh_initialhull(setT *vertices)
Definition: poly2.c:1802
qh_getcenter
pointT * qh_getcenter(setT *vertices)
Definition: geom.c:669
ridgeT::top
facetT * top
Definition: libqhull.h:374
otherfacet_
#define otherfacet_(ridge, facet)
Definition: libqhull.h:813
facetT::center
coordT * center
Definition: libqhull.h:286
qh_INITIALmax
#define qh_INITIALmax
Definition: user.h:420
FOREACHvertex_
#define FOREACHvertex_(vertices)
Definition: libqhull.h:950
qh_removefacet
void qh_removefacet(facetT *facet)
Definition: poly.c:1084
qh_partitionall
void qh_partitionall(setT *vertices, pointT *points, int numpoints)
Definition: libqhull.c:777
qh_nextridge3d
ridgeT * qh_nextridge3d(ridgeT *atridge, facetT *facet, vertexT **vertexp)
Definition: poly2.c:2368
qh_vertexsubset
boolT qh_vertexsubset(setT *vertexsetA, setT *vertexsetB)
Definition: poly2.c:3206
trace1
#define trace1(args)
Definition: qhull_a.h:81
qh_setcompact
void qh_setcompact(setT *set)
Definition: qset.c:276
qhmem
qhmemT qhmem
Definition: mem.c:62
qh_pointfacet
setT * qh_pointfacet(void)
Definition: poly2.c:2510
qh_setreplace
void qh_setreplace(setT *set, void *oldelem, void *newelem)
Definition: qset.c:1080
zadd_
#define zadd_(id, val)
Definition: stat.h:400
Wmaxout
Definition: stat.h:162
SETfirstt_
#define SETfirstt_(set, type)
Definition: qset.h:371
Ztrinull
Definition: stat.h:261
qh_printhelp_narrowhull
void qh_printhelp_narrowhull(FILE *fp, realT minangle)
Definition: user.c:423
qh_setcheck
void qh_setcheck(setT *set, const char *tname, unsigned id)
Definition: qset.c:234
qh_prependfacet
void qh_prependfacet(facetT *facet, facetT **facetlist)
Definition: poly2.c:2574
fmin_
#define fmin_(a, b)
Definition: geom.h:43
qh_vertexneighbors
void qh_vertexneighbors(void)
Definition: poly2.c:3174
pointT
#define pointT
Definition: libqhull.h:96
FORALLvertex_
#define FORALLvertex_(vertexlist)
Definition: poly.h:101
qh_vertexintersect_new
setT * qh_vertexintersect_new(setT *vertexsetA, setT *vertexsetB)
Definition: poly2.c:3135
qh_MAXnarrow
#define qh_MAXnarrow
Definition: user.h:845
qh_point
pointT * qh_point(int id)
Definition: poly2.c:2446
vertexT::deleted
flagT deleted
Definition: libqhull.h:407
getid_
#define getid_(p)
Definition: libqhull.h:823
qh_findbestnew
facetT * qh_findbestnew(pointT *point, facetT *startfacet, realT *dist, boolT bestoutside, boolT *isoutside, int *numpart)
Definition: geom.c:412
qh_fprintf
void qh_fprintf(FILE *fp, int msgcode, const char *fmt,...)
Definition: userprintf.c:42
qh_removevertex
void qh_removevertex(vertexT *vertex)
Definition: poly.c:1115
qh_precision
void qh_precision(const char *reason)
Definition: libqhull.c:1180
qh_version
const char qh_version[]
Definition: global.c:50
facetT::previous
facetT * previous
Definition: libqhull.h:293
qh_check_points
void qh_check_points(void)
Definition: poly2.c:365
qh_RESETvisible
#define qh_RESETvisible
Definition: libqhull.h:184
qh_findbestlower
facetT * qh_findbestlower(facetT *upperfacet, pointT *point, realT *bestdistp, int *numpart)
Definition: poly2.c:1278
qh_printfacetlist
void qh_printfacetlist(facetT *facetlist, setT *facets, boolT printall)
Definition: user.c:325
FORALLfacet_
#define FORALLfacet_(facetlist)
Definition: poly.h:77
qh_check_maxout
void qh_check_maxout(void)
Definition: poly2.c:218
facetT::coplanarset
setT * coplanarset
Definition: libqhull.h:305
doxygen_xml_parser.type
type
Definition: doxygen_xml_parser.py:881
SETref_
#define SETref_(elem)
Definition: qset.h:319
qh_delvertex
void qh_delvertex(vertexT *vertex)
Definition: poly2.c:1146
qh_facet3vertex
setT * qh_facet3vertex(facetT *facet)
Definition: poly2.c:1169
qh_MERGEridge
#define qh_MERGEridge
Definition: poly.h:57
zzadd_
#define zzadd_(id, val)
Definition: stat.h:397
qh_setindex
int qh_setindex(setT *set, void *atelem)
Definition: qset.c:821
qh_pointid
int qh_pointid(pointT *point)
Definition: poly.c:1053
qhmem_ERRmem
#define qhmem_ERRmem
Definition: mem.h:62
facetT::ridges
setT * ridges
Definition: libqhull.h:297
FOREACHvertexA_
#define FOREACHvertexA_(vertices)
Definition: poly.h:192
qh_VERIFYdirect
#define qh_VERIFYdirect
Definition: user.h:400
qh_RANDOMint
#define qh_RANDOMint
Definition: user.h:283
qh_HASHfactor
#define qh_HASHfactor
Definition: user.h:389
qh_initialvertices
setT * qh_initialvertices(int dim, setT *maxpoints, pointT *points, int numpoints)
Definition: poly2.c:1892
mergeT::type
mergeType type
Definition: merge.h:94
qhstat
#define qhstat
Definition: stat.h:500
qh_triangulate_link
void qh_triangulate_link(facetT *oldfacetA, facetT *facetA, facetT *oldfacetB, facetT *facetB)
Definition: poly2.c:3029
FORALLnew_facets
#define FORALLnew_facets
Definition: poly.h:89
qh_DUPLICATEridge
#define qh_DUPLICATEridge
Definition: poly.h:46
dim
int dim
qh_triangulate_mirror
void qh_triangulate_mirror(facetT *facetA, facetT *facetB)
Definition: poly2.c:3060
qh_appendfacet
void qh_appendfacet(facetT *facet)
Definition: poly.c:38
qh_check_output
void qh_check_output(void)
Definition: poly2.c:302
REALmax
#define REALmax
Definition: user.h:155
qh_QUICKhelp
#define qh_QUICKhelp
Definition: user.h:643
ridgeT::bottom
facetT * bottom
Definition: libqhull.h:375
facetT::visitid
unsigned visitid
Definition: libqhull.h:309
qh_addhash
void qh_addhash(void *newelem, setT *hashtable, int hashsize, int hash)
Definition: poly2.c:26
qh_setin
int qh_setin(setT *set, void *setelem)
Definition: qset.c:795
facetT::vertices
setT * vertices
Definition: libqhull.h:295
qh_check_point
void qh_check_point(pointT *point, facetT *facet, realT *maxoutside, realT *maxdist, facetT **errfacet1, facetT **errfacet2)
Definition: poly2.c:325
qh_printfacet
void qh_printfacet(FILE *fp, facetT *facet)
Definition: io.c:1944
qh_resetlists
void qh_resetlists(boolT stats, boolT resetVisible)
Definition: poly2.c:2685
qh_addpoint
boolT qh_addpoint(pointT *furthest, facetT *facet, boolT checkdist)
Definition: libqhull.c:168
qh_printhashtable
void qh_printhashtable(FILE *fp)
Definition: poly2.c:2613
qh_checkconvex
void qh_checkconvex(facetT *facetlist, int fault)
Definition: poly2.c:475
mergeType
mergeType
Definition: merge.h:56
qh_delfacet
void qh_delfacet(facetT *facet)
Definition: poly.c:247
qh_furthestnext
void qh_furthestnext(void)
Definition: poly2.c:1578
qh_inthresholds
boolT qh_inthresholds(coordT *normal, realT *angle)
Definition: geom2.c:811
qh_getangle
realT qh_getangle(pointT *vect1, pointT *vect2)
Definition: geom.c:644
vertexT::neighbors
setT * neighbors
Definition: libqhull.h:400
coordT
#define coordT
Definition: libqhull.h:80
qh_findgooddist
facetT * qh_findgooddist(pointT *point, facetT *facetA, realT *distp, facetT **facetlist)
Definition: geom2.c:630
True
#define True
Definition: libqhull.h:129
qh_nearcoplanar
void qh_nearcoplanar(void)
Definition: poly2.c:2198
qh_findbest
facetT * qh_findbest(pointT *point, facetT *startfacet, boolT bestoutside, boolT isnewfacets, boolT noupper, realT *dist, boolT *isoutside, int *numpart)
Definition: geom.c:140
qh_ERRinput
#define qh_ERRinput
Definition: libqhull.h:194
facetT::trivisible
facetT * trivisible
Definition: libqhull.h:283
facetT::simplicial
flagT simplicial
Definition: libqhull.h:324
qh_matchvertices
boolT qh_matchvertices(int firstindex, setT *verticesA, int skipA, setT *verticesB, int *skipB, boolT *same)
Definition: poly.c:952
facetT::outsideset
setT * outsideset
Definition: libqhull.h:302
facetT::dupridge
flagT dupridge
Definition: libqhull.h:336
zzval_
#define zzval_(id)
Definition: stat.h:413
mergeT
Definition: merge.h:90
qh_makenew_nonsimplicial
facetT * qh_makenew_nonsimplicial(facetT *visible, vertexT *apex, int *numnew)
Definition: poly.c:563
qh_ZEROdelaunay
#define qh_ZEROdelaunay
Definition: user.h:876
qh
#define qh
Definition: libqhull.h:457
wval_
#define wval_(id)
Definition: stat.h:417
qh_findgood_all
void qh_findgood_all(facetT *facetlist)
Definition: poly2.c:1508
qh_pointvertex
setT * qh_pointvertex(void)
Definition: poly2.c:2547
qh_setlast
void * qh_setlast(setT *set)
Definition: qset.c:895
qh_settempfree
void qh_settempfree(setT **set)
Definition: qset.c:1174
FOREACHvertex_i_
#define FOREACHvertex_i_(vertices)
Definition: libqhull.h:1028
FOREACHridge_
#define FOREACHridge_(ridges)
Definition: libqhull.h:936
facetT::redundant
flagT redundant
Definition: libqhull.h:347
qh_triangulate_facet
void qh_triangulate_facet(facetT *facetA, vertexT **first_vertex)
Definition: poly2.c:2954
facetT::upperdelaunay
flagT upperdelaunay
Definition: libqhull.h:328
vertexT::point
pointT * point
Definition: libqhull.h:399
qh_DATAfault
#define qh_DATAfault
Definition: poly.h:35
qh_findbesthorizon
facetT * qh_findbesthorizon(boolT ischeckmax, pointT *point, facetT *startfacet, boolT noupper, realT *bestdist, int *numpart)
Definition: geom.c:281
facetT::flipped
flagT flipped
Definition: libqhull.h:327
FOREACHfacet_i_
#define FOREACHfacet_i_(facets)
Definition: libqhull.h:965
qh_getcentrum
pointT * qh_getcentrum(facetT *facet)
Definition: geom.c:700
vertexT::newlist
flagT newlist
Definition: libqhull.h:408
qh_appendmergeset
void qh_appendmergeset(facetT *facet, facetT *neighbor, mergeType mergetype, realT *angle)
Definition: merge.c:320
qh_setvoronoi_all
void qh_setvoronoi_all(void)
Definition: poly2.c:2735
qh_checkvertex
void qh_checkvertex(vertexT *vertex)
Definition: poly2.c:1001
qh_checkflipped_all
void qh_checkflipped_all(facetT *facetlist)
Definition: poly2.c:831
maximize_
#define maximize_(maxval, val)
Definition: geom.h:51
qh_errexit2
void qh_errexit2(int exitcode, facetT *facet, facetT *otherfacet)
Definition: libqhull.c:521
qh_setprint
void qh_setprint(FILE *fp, const char *string, setT *set)
Definition: qset.c:1049
qh_detsimplex
realT qh_detsimplex(pointT *apex, setT *points, int dim, boolT *nearzero)
Definition: geom2.c:304
ridgeT::id
unsigned id
Definition: libqhull.h:376
qh_option
void qh_option(const char *option, int *i, realT *r)
Definition: global.c:2115
qh_vertexintersect
void qh_vertexintersect(setT **vertexsetA, setT *vertexsetB)
Definition: poly2.c:3117
qh_check_dupridge
void qh_check_dupridge(facetT *facet1, realT dist1, facetT *facet2, realT dist2)
Definition: poly2.c:150
qh_setnew_delnthsorted
setT * qh_setnew_delnthsorted(setT *set, int size, int nth, int prepend)
Definition: qset.c:967
qh_clearcenters
void qh_clearcenters(qh_CENTER type)
Definition: poly2.c:1040
qh_nearvertex
vertexT * qh_nearvertex(facetT *facet, pointT *point, realT *bestdistp)
Definition: poly2.c:2248
vertexT::seen
flagT seen
Definition: libqhull.h:404
qh_initbuild
void qh_initbuild(void)
Definition: poly2.c:1683
facetT::maxoutside
coordT maxoutside
Definition: libqhull.h:267
qh_makenew_simplicial
facetT * qh_makenew_simplicial(facetT *visible, vertexT *apex, int *numnew)
Definition: poly.c:660
qh_NOupper
#define qh_NOupper
Definition: libqhull.h:181
vertexT::id
unsigned id
Definition: libqhull.h:402
qh_point_add
void qh_point_add(setT *set, pointT *point, void *elem)
Definition: poly2.c:2470
qh_settemppush
void qh_settemppush(setT *set)
Definition: qset.c:1247
qh_newhashtable
int qh_newhashtable(int newsize)
Definition: poly2.c:2304
qhull_a.h
qh_setzero
void qh_setzero(setT *set, int idx, int size)
Definition: qset.c:1327
SETreturnsize_
#define SETreturnsize_(set, size)
Definition: qset.h:408
qh_orientoutside
boolT qh_orientoutside(facetT *facet)
Definition: geom2.c:1244
qh_check_bestdist
void qh_check_bestdist(void)
Definition: poly2.c:66
qh_setfree
void qh_setfree(setT **setp)
Definition: qset.c:716
qh_pointdist
coordT qh_pointdist(pointT *point1, pointT *point2, int dim)
Definition: geom2.c:1320
qh_setaddnth
void qh_setaddnth(setT **setp, int nth, void *newelem)
Definition: qset.c:61
FOREACHneighbor_
#define FOREACHneighbor_(facet)
Definition: libqhull.h:908
SETelemt_
#define SETelemt_(set, n, type)
Definition: qset.h:342
qh_ORIENTclock
#define qh_ORIENTclock
Definition: user.h:297
SETindex_
#define SETindex_(set, elem)
Definition: qset.h:308
facetT::keepcentrum
flagT keepcentrum
Definition: libqhull.h:344
qh_checkfacet
void qh_checkfacet(facetT *facet, boolT newmerge, boolT *waserrorp)
Definition: poly2.c:627
facetT::next
facetT * next
Definition: libqhull.h:294
qh_setappend
void qh_setappend(setT **setp, void *newelem)
Definition: qset.c:131
qh_INITIALsearch
#define qh_INITIALsearch
Definition: user.h:408
facetT::visible
flagT visible
Definition: libqhull.h:321
qh_ISnewfacets
#define qh_ISnewfacets
Definition: libqhull.h:183
vertexT::seen2
flagT seen2
Definition: libqhull.h:405
FORALLvertices
#define FORALLvertices
Definition: libqhull.h:877
qh_triangulate_null
void qh_triangulate_null(facetT *facetA)
Definition: poly2.c:3089
qh_memfree_
#define qh_memfree_(object, insize, freelistp)
Definition: mem.h:193
qh_isvertex
vertexT * qh_isvertex(pointT *point, setT *vertices)
Definition: poly2.c:1975
qh_COMPUTEfurthest
#define qh_COMPUTEfurthest
Definition: user.h:523
facetT::furthestdist
coordT furthestdist
Definition: libqhull.h:264
qh_setdellast
void * qh_setdellast(setT *set)
Definition: qset.c:384
wmin_
#define wmin_(id, val)
Definition: stat.h:446
facetT::replace
facetT * replace
Definition: libqhull.h:278
qh_furthestout
void qh_furthestout(facetT *facet)
Definition: poly2.c:1621
qh_memfree
void qh_memfree(void *object, int insize)
Definition: mem.c:245
qh_appendvertex
void qh_appendvertex(vertexT *vertex)
Definition: poly.c:72
qh_maxouter
realT qh_maxouter(void)
Definition: geom2.c:1066
mergeT::facet1
facetT * facet1
Definition: merge.h:92
qh_partitioncoplanar
void qh_partitioncoplanar(pointT *point, facetT *facet, realT *dist)
Definition: libqhull.c:896
SETelem_
#define SETelem_(set, n)
Definition: qset.h:331
FORALLpoints
#define FORALLpoints
Definition: libqhull.h:851
qh_outerinner
void qh_outerinner(facetT *facet, realT *outerplane, realT *innerplane)
Definition: geom2.c:1279
facetT::seen
flagT seen
Definition: libqhull.h:325
facetT::offset
coordT offset
Definition: libqhull.h:273
facetT::good
flagT good
Definition: libqhull.h:332
qh_setdel
void * qh_setdel(setT *set, void *oldelem)
Definition: qset.c:344
ridgeT::vertices
setT * vertices
Definition: libqhull.h:372
ridgeT::seen
flagT seen
Definition: libqhull.h:377
qh_newstats
boolT qh_newstats(int idx, int *nextindex)
Definition: stat.c:520
qh_ALGORITHMfault
#define qh_ALGORITHMfault
Definition: poly.h:27
vertexT::visitid
unsigned visitid
Definition: libqhull.h:403
qh_matchduplicates
void qh_matchduplicates(facetT *atfacet, int atskip, int hashsize, int *hashcount)
Definition: poly2.c:2088
qh_errexit
void qh_errexit(int exitcode, facetT *facet, ridgeT *ridge)
Definition: user.c:213
qh_matchnewfacets
void qh_matchnewfacets(void)
Definition: poly.c:841
qh_setequal_skip
int qh_setequal_skip(setT *setA, int skipA, setT *setB, int skipB)
Definition: qset.c:677
zmax_
#define zmax_(id, val)
Definition: stat.h:431
qh_scalelast
void qh_scalelast(coordT *points, int numpoints, int dim, coordT low, coordT high, coordT newhigh)
Definition: geom2.c:1675
qhmemT::ferr
FILE * ferr
Definition: mem.h:130
qh_WARNnarrow
#define qh_WARNnarrow
Definition: user.h:857
trace0
#define trace0(args)
Definition: qhull_a.h:80
trace4
#define trace4(args)
Definition: qhull_a.h:84
qh_settemp
setT * qh_settemp(int setsize)
Definition: qset.c:1146
FOREACHridge_i_
#define FOREACHridge_i_(ridges)
Definition: libqhull.h:1013
wmax_
#define wmax_(id, val)
Definition: stat.h:432
FORALLvisible_facets
#define FORALLvisible_facets
Definition: poly.h:113
qh_infiniteloop
void qh_infiniteloop(facetT *facet)
Definition: poly2.c:1652
qh_findbestfacet
facetT * qh_findbestfacet(pointT *point, boolT bestoutside, realT *bestdist, boolT *isoutside)
Definition: poly2.c:1239
qh_makenewfacets
vertexT * qh_makenewfacets(pointT *point)
Definition: poly2.c:2020
False
#define False
Definition: libqhull.h:128
qh_maxmin
setT * qh_maxmin(pointT *points, int numpoints, int dimension)
Definition: geom2.c:979
zzinc_
#define zzinc_(id)
Definition: stat.h:384
facetT::triowner
facetT * triowner
Definition: libqhull.h:284
qh_updatevertices
void qh_updatevertices(void)
Definition: poly.c:1155
qh_ALL
#define qh_ALL
Definition: libqhull.h:180
qh_detroundoff
void qh_detroundoff(void)
Definition: geom2.c:192
qh_checkpolygon
void qh_checkpolygon(facetT *facetlist)
Definition: poly2.c:878
qh_findgood
int qh_findgood(facetT *facetlist, int goodhorizon)
Definition: poly2.c:1408
facetT::toporient
flagT toporient
Definition: libqhull.h:322
qh_setequal
int qh_setequal(setT *setA, setT *setB)
Definition: qset.c:587
qh_memalloc
void * qh_memalloc(int insize)
Definition: mem.c:115
qh_distplane
void qh_distplane(pointT *point, facetT *facet, realT *dist)
Definition: geom.c:36
qh_CENTER
qh_CENTER
Definition: libqhull.h:141
qh_setsize
int qh_setsize(setT *set)
Definition: qset.c:1111
qh_setnew
setT * qh_setnew(int setsize)
Definition: qset.c:924
qh_printlists
void qh_printlists(void)
Definition: poly2.c:2651
facetT::id
unsigned id
Definition: libqhull.h:311
vertexT
struct vertexT vertexT
Definition: libqhull.h:218
qh_getdistance
realT qh_getdistance(facetT *facet, facetT *neighbor, realT *mindist, realT *maxdist)
Definition: geom.c:728
qh_errprint
void qh_errprint(const char *string, facetT *atfacet, facetT *otherfacet, ridgeT *atridge, vertexT *atvertex)
Definition: user.c:277
SETaddr_
#define SETaddr_(set, type)
Definition: qset.h:396
FOREACHpoint_
#define FOREACHpoint_(points)
Definition: libqhull.h:922
qh_WIDEduplicate
#define qh_WIDEduplicate
Definition: user.h:829
fabs_
#define fabs_(a)
Definition: geom.h:27
realT
#define realT
Definition: user.h:154
FOREACHneighbor_i_
#define FOREACHneighbor_i_(facet)
Definition: libqhull.h:983
facetT::coplanar
flagT coplanar
Definition: libqhull.h:340
facetT::normal
coordT * normal
Definition: libqhull.h:274
qh_outcoplanar
void qh_outcoplanar(void)
Definition: poly2.c:2417
qh_ERRsingular
#define qh_ERRsingular
Definition: libqhull.h:195
trace3
#define trace3(args)
Definition: qhull_a.h:83
qh_maxsimplex
void qh_maxsimplex(int dim, setT *maxpoints, pointT *points, int numpoints, setT **simplex)
Definition: geom2.c:1098
qh_willdelete
void qh_willdelete(facetT *facet, facetT *replace)
Definition: merge.c:3610
SETfirst_
#define SETfirst_(set)
Definition: qset.h:362
facetT::f
union facetT::@20 f
SETsecond_
#define SETsecond_(set)
Definition: qset.h:380
FOREACHpoint_i_
#define FOREACHpoint_i_(points)
Definition: libqhull.h:998
qh_gethash
int qh_gethash(int hashsize, setT *set, int size, int firstindex, void *skipelem)
Definition: poly.c:405
minimize_
#define minimize_(minval, val)
Definition: geom.h:59
facetT::tricoplanar
flagT tricoplanar
Definition: libqhull.h:314
SETsecondt_
#define SETsecondt_(set, type)
Definition: qset.h:388
qh_facetcenter
pointT * qh_facetcenter(setT *vertices)
Definition: geom2.c:591
qh_setfacetplane
void qh_setfacetplane(facetT *facet)
Definition: geom.c:929
facetT::degenerate
flagT degenerate
Definition: libqhull.h:346

hpp-fcl
Author(s):
autogenerated on Fri Jun 2 2023 02:39:01