merge.c
Go to the documentation of this file.
1 /*<html><pre> -<a href="qh-merge.htm#TOC"
2  >-------------------------------</a><a name="TOP">-</a>
3 
4  merge.c
5  merges non-convex facets
6 
7  see qh-merge.htm and merge.h
8 
9  other modules call qh_premerge() and qh_postmerge()
10 
11  the user may call qh_postmerge() to perform additional merges.
12 
13  To remove deleted facets and vertices (qhull() in libqhull.c):
14  qh_partitionvisible(!qh_ALL, &numoutside); // visible_list, newfacet_list
15  qh_deletevisible(); // qh.visible_list
16  qh_resetlists(False, qh_RESETvisible); // qh.visible_list newvertex_list newfacet_list
17 
18  assumes qh.CENTERtype= centrum
19 
20  merges occur in qh_mergefacet and in qh_mergecycle
21  vertex->neighbors not set until the first merge occurs
22 
23  Copyright (c) 1993-2015 C.B. Barber.
24  $Id: //main/2015/qhull/src/libqhull/merge.c#4 $$Change: 2064 $
25  $DateTime: 2016/01/18 12:36:08 $$Author: bbarber $
26 */
27 
28 #include "qhull_a.h"
29 
30 #ifndef qh_NOmerge
31 
32 /*===== functions(alphabetical after premerge and postmerge) ======*/
33 
34 /*-<a href="qh-merge.htm#TOC"
35  >-------------------------------</a><a name="premerge">-</a>
36 
37  qh_premerge( apex, maxcentrum )
38  pre-merge nonconvex facets in qh.newfacet_list for apex
39  maxcentrum defines coplanar and concave (qh_test_appendmerge)
40 
41  returns:
42  deleted facets added to qh.visible_list with facet->visible set
43 
44  notes:
45  uses globals, qh.MERGEexact, qh.PREmerge
46 
47  design:
48  mark duplicate ridges in qh.newfacet_list
49  merge facet cycles in qh.newfacet_list
50  merge duplicate ridges and concave facets in qh.newfacet_list
51  check merged facet cycles for degenerate and redundant facets
52  merge degenerate and redundant facets
53  collect coplanar and concave facets
54  merge concave, coplanar, degenerate, and redundant facets
55 */
56 void qh_premerge(vertexT *apex, realT maxcentrum, realT maxangle) {
57  boolT othermerge= False;
58  facetT *newfacet;
59 
60  if (qh ZEROcentrum && qh_checkzero(!qh_ALL))
61  return;
62  trace2((qh ferr, 2008, "qh_premerge: premerge centrum %2.2g angle %2.2g for apex v%d facetlist f%d\n",
63  maxcentrum, maxangle, apex->id, getid_(qh newfacet_list)));
64  if (qh IStracing >= 4 && qh num_facets < 50)
65  qh_printlists();
66  qh centrum_radius= maxcentrum;
67  qh cos_max= maxangle;
68  qh degen_mergeset= qh_settemp(qh TEMPsize);
69  qh facet_mergeset= qh_settemp(qh TEMPsize);
70  if (qh hull_dim >=3) {
71  qh_mark_dupridges(qh newfacet_list); /* facet_mergeset */
72  qh_mergecycle_all(qh newfacet_list, &othermerge);
73  qh_forcedmerges(&othermerge /* qh.facet_mergeset */);
74  FORALLnew_facets { /* test samecycle merges */
75  if (!newfacet->simplicial && !newfacet->mergeridge)
76  qh_degen_redundant_neighbors(newfacet, NULL);
77  }
78  if (qh_merge_degenredundant())
79  othermerge= True;
80  }else /* qh.hull_dim == 2 */
81  qh_mergecycle_all(qh newfacet_list, &othermerge);
82  qh_flippedmerges(qh newfacet_list, &othermerge);
83  if (!qh MERGEexact || zzval_(Ztotmerge)) {
84  zinc_(Zpremergetot);
85  qh POSTmerging= False;
86  qh_getmergeset_initial(qh newfacet_list);
87  qh_all_merges(othermerge, False);
88  }
89  qh_settempfree(&qh facet_mergeset);
90  qh_settempfree(&qh degen_mergeset);
91 } /* premerge */
92 
93 /*-<a href="qh-merge.htm#TOC"
94  >-------------------------------</a><a name="postmerge">-</a>
95 
96  qh_postmerge( reason, maxcentrum, maxangle, vneighbors )
97  post-merge nonconvex facets as defined by maxcentrum and maxangle
98  'reason' is for reporting progress
99  if vneighbors,
100  calls qh_test_vneighbors at end of qh_all_merge
101  if firstmerge,
102  calls qh_reducevertices before qh_getmergeset
103 
104  returns:
105  if first call (qh.visible_list != qh.facet_list),
106  builds qh.facet_newlist, qh.newvertex_list
107  deleted facets added to qh.visible_list with facet->visible
108  qh.visible_list == qh.facet_list
109 
110  notes:
111 
112 
113  design:
114  if first call
115  set qh.visible_list and qh.newfacet_list to qh.facet_list
116  add all facets to qh.newfacet_list
117  mark non-simplicial facets, facet->newmerge
118  set qh.newvertext_list to qh.vertex_list
119  add all vertices to qh.newvertex_list
120  if a pre-merge occured
121  set vertex->delridge {will retest the ridge}
122  if qh.MERGEexact
123  call qh_reducevertices()
124  if no pre-merging
125  merge flipped facets
126  determine non-convex facets
127  merge all non-convex facets
128 */
129 void qh_postmerge(const char *reason, realT maxcentrum, realT maxangle,
130  boolT vneighbors) {
131  facetT *newfacet;
132  boolT othermerges= False;
133  vertexT *vertex;
134 
135  if (qh REPORTfreq || qh IStracing) {
136  qh_buildtracing(NULL, NULL);
137  qh_printsummary(qh ferr);
138  if (qh PRINTstatistics)
139  qh_printallstatistics(qh ferr, "reason");
140  qh_fprintf(qh ferr, 8062, "\n%s with 'C%.2g' and 'A%.2g'\n",
141  reason, maxcentrum, maxangle);
142  }
143  trace2((qh ferr, 2009, "qh_postmerge: postmerge. test vneighbors? %d\n",
144  vneighbors));
145  qh centrum_radius= maxcentrum;
146  qh cos_max= maxangle;
147  qh POSTmerging= True;
148  qh degen_mergeset= qh_settemp(qh TEMPsize);
149  qh facet_mergeset= qh_settemp(qh TEMPsize);
150  if (qh visible_list != qh facet_list) { /* first call */
151  qh NEWfacets= True;
152  qh visible_list= qh newfacet_list= qh facet_list;
153  FORALLnew_facets {
154  newfacet->newfacet= True;
155  if (!newfacet->simplicial)
156  newfacet->newmerge= True;
157  zinc_(Zpostfacets);
158  }
159  qh newvertex_list= qh vertex_list;
160  FORALLvertices
161  vertex->newlist= True;
162  if (qh VERTEXneighbors) { /* a merge has occurred */
163  FORALLvertices
164  vertex->delridge= True; /* test for redundant, needed? */
165  if (qh MERGEexact) {
166  if (qh hull_dim <= qh_DIMreduceBuild)
167  qh_reducevertices(); /* was skipped during pre-merging */
168  }
169  }
170  if (!qh PREmerge && !qh MERGEexact)
171  qh_flippedmerges(qh newfacet_list, &othermerges);
172  }
173  qh_getmergeset_initial(qh newfacet_list);
174  qh_all_merges(False, vneighbors);
175  qh_settempfree(&qh facet_mergeset);
176  qh_settempfree(&qh degen_mergeset);
177 } /* post_merge */
178 
179 /*-<a href="qh-merge.htm#TOC"
180  >-------------------------------</a><a name="all_merges">-</a>
181 
182  qh_all_merges( othermerge, vneighbors )
183  merge all non-convex facets
184 
185  set othermerge if already merged facets (for qh_reducevertices)
186  if vneighbors
187  tests vertex neighbors for convexity at end
188  qh.facet_mergeset lists the non-convex ridges in qh_newfacet_list
189  qh.degen_mergeset is defined
190  if qh.MERGEexact && !qh.POSTmerging,
191  does not merge coplanar facets
192 
193  returns:
194  deleted facets added to qh.visible_list with facet->visible
195  deleted vertices added qh.delvertex_list with vertex->delvertex
196 
197  notes:
198  unless !qh.MERGEindependent,
199  merges facets in independent sets
200  uses qh.newfacet_list as argument since merges call qh_removefacet()
201 
202  design:
203  while merges occur
204  for each merge in qh.facet_mergeset
205  unless one of the facets was already merged in this pass
206  merge the facets
207  test merged facets for additional merges
208  add merges to qh.facet_mergeset
209  if vertices record neighboring facets
210  rename redundant vertices
211  update qh.facet_mergeset
212  if vneighbors ??
213  tests vertex neighbors for convexity at end
214 */
215 void qh_all_merges(boolT othermerge, boolT vneighbors) {
216  facetT *facet1, *facet2;
217  mergeT *merge;
218  boolT wasmerge= True, isreduce;
219  void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
220  vertexT *vertex;
221  mergeType mergetype;
222  int numcoplanar=0, numconcave=0, numdegenredun= 0, numnewmerges= 0;
223 
224  trace2((qh ferr, 2010, "qh_all_merges: starting to merge facets beginning from f%d\n",
225  getid_(qh newfacet_list)));
226  while (True) {
227  wasmerge= False;
228  while (qh_setsize(qh facet_mergeset)) {
229  while ((merge= (mergeT*)qh_setdellast(qh facet_mergeset))) {
230  facet1= merge->facet1;
231  facet2= merge->facet2;
232  mergetype= merge->type;
233  qh_memfree_(merge, (int)sizeof(mergeT), freelistp);
234  if (facet1->visible || facet2->visible) /*deleted facet*/
235  continue;
236  if ((facet1->newfacet && !facet1->tested)
237  || (facet2->newfacet && !facet2->tested)) {
238  if (qh MERGEindependent && mergetype <= MRGanglecoplanar)
239  continue; /* perform independent sets of merges */
240  }
241  qh_merge_nonconvex(facet1, facet2, mergetype);
242  numdegenredun += qh_merge_degenredundant();
243  numnewmerges++;
244  wasmerge= True;
245  if (mergetype == MRGconcave)
246  numconcave++;
247  else /* MRGcoplanar or MRGanglecoplanar */
248  numcoplanar++;
249  } /* while setdellast */
250  if (qh POSTmerging && qh hull_dim <= qh_DIMreduceBuild
251  && numnewmerges > qh_MAXnewmerges) {
252  numnewmerges= 0;
253  qh_reducevertices(); /* otherwise large post merges too slow */
254  }
255  qh_getmergeset(qh newfacet_list); /* facet_mergeset */
256  } /* while mergeset */
257  if (qh VERTEXneighbors) {
258  isreduce= False;
259  if (qh hull_dim >=4 && qh POSTmerging) {
260  FORALLvertices
261  vertex->delridge= True;
262  isreduce= True;
263  }
264  if ((wasmerge || othermerge) && (!qh MERGEexact || qh POSTmerging)
265  && qh hull_dim <= qh_DIMreduceBuild) {
266  othermerge= False;
267  isreduce= True;
268  }
269  if (isreduce) {
270  if (qh_reducevertices()) {
271  qh_getmergeset(qh newfacet_list); /* facet_mergeset */
272  continue;
273  }
274  }
275  }
276  if (vneighbors && qh_test_vneighbors(/* qh.newfacet_list */))
277  continue;
278  break;
279  } /* while (True) */
280  if (qh CHECKfrequently && !qh MERGEexact) {
281  qh old_randomdist= qh RANDOMdist;
282  qh RANDOMdist= False;
283  qh_checkconvex(qh newfacet_list, qh_ALGORITHMfault);
284  /* qh_checkconnect(); [this is slow and it changes the facet order] */
285  qh RANDOMdist= qh old_randomdist;
286  }
287  trace1((qh ferr, 1009, "qh_all_merges: merged %d coplanar facets %d concave facets and %d degen or redundant facets.\n",
288  numcoplanar, numconcave, numdegenredun));
289  if (qh IStracing >= 4 && qh num_facets < 50)
290  qh_printlists();
291 } /* all_merges */
292 
293 
294 /*-<a href="qh-merge.htm#TOC"
295  >-------------------------------</a><a name="appendmergeset">-</a>
296 
297  qh_appendmergeset( facet, neighbor, mergetype, angle )
298  appends an entry to qh.facet_mergeset or qh.degen_mergeset
299 
300  angle ignored if NULL or !qh.ANGLEmerge
301 
302  returns:
303  merge appended to facet_mergeset or degen_mergeset
304  sets ->degenerate or ->redundant if degen_mergeset
305 
306  see:
307  qh_test_appendmerge()
308 
309  design:
310  allocate merge entry
311  if regular merge
312  append to qh.facet_mergeset
313  else if degenerate merge and qh.facet_mergeset is all degenerate
314  append to qh.degen_mergeset
315  else if degenerate merge
316  prepend to qh.degen_mergeset
317  else if redundant merge
318  append to qh.degen_mergeset
319 */
320 void qh_appendmergeset(facetT *facet, facetT *neighbor, mergeType mergetype, realT *angle) {
321  mergeT *merge, *lastmerge;
322  void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
323 
324  if (facet->redundant)
325  return;
326  if (facet->degenerate && mergetype == MRGdegen)
327  return;
328  qh_memalloc_((int)sizeof(mergeT), freelistp, merge, mergeT);
329  merge->facet1= facet;
330  merge->facet2= neighbor;
331  merge->type= mergetype;
332  if (angle && qh ANGLEmerge)
333  merge->angle= *angle;
334  if (mergetype < MRGdegen)
335  qh_setappend(&(qh facet_mergeset), merge);
336  else if (mergetype == MRGdegen) {
337  facet->degenerate= True;
338  if (!(lastmerge= (mergeT*)qh_setlast(qh degen_mergeset))
339  || lastmerge->type == MRGdegen)
340  qh_setappend(&(qh degen_mergeset), merge);
341  else
342  qh_setaddnth(&(qh degen_mergeset), 0, merge);
343  }else if (mergetype == MRGredundant) {
344  facet->redundant= True;
345  qh_setappend(&(qh degen_mergeset), merge);
346  }else /* mergetype == MRGmirror */ {
347  if (facet->redundant || neighbor->redundant) {
348  qh_fprintf(qh ferr, 6092, "qhull error (qh_appendmergeset): facet f%d or f%d is already a mirrored facet\n",
349  facet->id, neighbor->id);
350  qh_errexit2(qh_ERRqhull, facet, neighbor);
351  }
352  if (!qh_setequal(facet->vertices, neighbor->vertices)) {
353  qh_fprintf(qh ferr, 6093, "qhull error (qh_appendmergeset): mirrored facets f%d and f%d do not have the same vertices\n",
354  facet->id, neighbor->id);
355  qh_errexit2(qh_ERRqhull, facet, neighbor);
356  }
357  facet->redundant= True;
358  neighbor->redundant= True;
359  qh_setappend(&(qh degen_mergeset), merge);
360  }
361 } /* appendmergeset */
362 
363 
364 /*-<a href="qh-merge.htm#TOC"
365  >-------------------------------</a><a name="basevertices">-</a>
366 
367  qh_basevertices( samecycle )
368  return temporary set of base vertices for samecycle
369  samecycle is first facet in the cycle
370  assumes apex is SETfirst_( samecycle->vertices )
371 
372  returns:
373  vertices(settemp)
374  all ->seen are cleared
375 
376  notes:
377  uses qh_vertex_visit;
378 
379  design:
380  for each facet in samecycle
381  for each unseen vertex in facet->vertices
382  append to result
383 */
384 setT *qh_basevertices(facetT *samecycle) {
385  facetT *same;
386  vertexT *apex, *vertex, **vertexp;
387  setT *vertices= qh_settemp(qh TEMPsize);
388 
389  apex= SETfirstt_(samecycle->vertices, vertexT);
390  apex->visitid= ++qh vertex_visit;
391  FORALLsame_cycle_(samecycle) {
392  if (same->mergeridge)
393  continue;
394  FOREACHvertex_(same->vertices) {
395  if (vertex->visitid != qh vertex_visit) {
396  qh_setappend(&vertices, vertex);
397  vertex->visitid= qh vertex_visit;
398  vertex->seen= False;
399  }
400  }
401  }
402  trace4((qh ferr, 4019, "qh_basevertices: found %d vertices\n",
403  qh_setsize(vertices)));
404  return vertices;
405 } /* basevertices */
406 
407 /*-<a href="qh-merge.htm#TOC"
408  >-------------------------------</a><a name="checkconnect">-</a>
409 
410  qh_checkconnect()
411  check that new facets are connected
412  new facets are on qh.newfacet_list
413 
414  notes:
415  this is slow and it changes the order of the facets
416  uses qh.visit_id
417 
418  design:
419  move first new facet to end of qh.facet_list
420  for all newly appended facets
421  append unvisited neighbors to end of qh.facet_list
422  for all new facets
423  report error if unvisited
424 */
425 void qh_checkconnect(void /* qh.newfacet_list */) {
426  facetT *facet, *newfacet, *errfacet= NULL, *neighbor, **neighborp;
427 
428  facet= qh newfacet_list;
429  qh_removefacet(facet);
430  qh_appendfacet(facet);
431  facet->visitid= ++qh visit_id;
432  FORALLfacet_(facet) {
433  FOREACHneighbor_(facet) {
434  if (neighbor->visitid != qh visit_id) {
435  qh_removefacet(neighbor);
436  qh_appendfacet(neighbor);
437  neighbor->visitid= qh visit_id;
438  }
439  }
440  }
441  FORALLnew_facets {
442  if (newfacet->visitid == qh visit_id)
443  break;
444  qh_fprintf(qh ferr, 6094, "qhull error: f%d is not attached to the new facets\n",
445  newfacet->id);
446  errfacet= newfacet;
447  }
448  if (errfacet)
449  qh_errexit(qh_ERRqhull, errfacet, NULL);
450 } /* checkconnect */
451 
452 /*-<a href="qh-merge.htm#TOC"
453  >-------------------------------</a><a name="checkzero">-</a>
454 
455  qh_checkzero( testall )
456  check that facets are clearly convex for qh.DISTround with qh.MERGEexact
457 
458  if testall,
459  test all facets for qh.MERGEexact post-merging
460  else
461  test qh.newfacet_list
462 
463  if qh.MERGEexact,
464  allows coplanar ridges
465  skips convexity test while qh.ZEROall_ok
466 
467  returns:
468  True if all facets !flipped, !dupridge, normal
469  if all horizon facets are simplicial
470  if all vertices are clearly below neighbor
471  if all opposite vertices of horizon are below
472  clears qh.ZEROall_ok if any problems or coplanar facets
473 
474  notes:
475  uses qh.vertex_visit
476  horizon facets may define multiple new facets
477 
478  design:
479  for all facets in qh.newfacet_list or qh.facet_list
480  check for flagged faults (flipped, etc.)
481  for all facets in qh.newfacet_list or qh.facet_list
482  for each neighbor of facet
483  skip horizon facets for qh.newfacet_list
484  test the opposite vertex
485  if qh.newfacet_list
486  test the other vertices in the facet's horizon facet
487 */
488 boolT qh_checkzero(boolT testall) {
489  facetT *facet, *neighbor, **neighborp;
490  facetT *horizon, *facetlist;
491  int neighbor_i;
492  vertexT *vertex, **vertexp;
493  realT dist;
494 
495  if (testall)
496  facetlist= qh facet_list;
497  else {
498  facetlist= qh newfacet_list;
499  FORALLfacet_(facetlist) {
500  horizon= SETfirstt_(facet->neighbors, facetT);
501  if (!horizon->simplicial)
502  goto LABELproblem;
503  if (facet->flipped || facet->dupridge || !facet->normal)
504  goto LABELproblem;
505  }
506  if (qh MERGEexact && qh ZEROall_ok) {
507  trace2((qh ferr, 2011, "qh_checkzero: skip convexity check until first pre-merge\n"));
508  return True;
509  }
510  }
511  FORALLfacet_(facetlist) {
512  qh vertex_visit++;
513  neighbor_i= 0;
514  horizon= NULL;
515  FOREACHneighbor_(facet) {
516  if (!neighbor_i && !testall) {
517  horizon= neighbor;
518  neighbor_i++;
519  continue; /* horizon facet tested in qh_findhorizon */
520  }
521  vertex= SETelemt_(facet->vertices, neighbor_i++, vertexT);
522  vertex->visitid= qh vertex_visit;
523  zzinc_(Zdistzero);
524  qh_distplane(vertex->point, neighbor, &dist);
525  if (dist >= -qh DISTround) {
526  qh ZEROall_ok= False;
527  if (!qh MERGEexact || testall || dist > qh DISTround)
528  goto LABELnonconvex;
529  }
530  }
531  if (!testall && horizon) {
532  FOREACHvertex_(horizon->vertices) {
533  if (vertex->visitid != qh vertex_visit) {
534  zzinc_(Zdistzero);
535  qh_distplane(vertex->point, facet, &dist);
536  if (dist >= -qh DISTround) {
537  qh ZEROall_ok= False;
538  if (!qh MERGEexact || dist > qh DISTround)
539  goto LABELnonconvex;
540  }
541  break;
542  }
543  }
544  }
545  }
546  trace2((qh ferr, 2012, "qh_checkzero: testall %d, facets are %s\n", testall,
547  (qh MERGEexact && !testall) ?
548  "not concave, flipped, or duplicate ridged" : "clearly convex"));
549  return True;
550 
551  LABELproblem:
552  qh ZEROall_ok= False;
553  trace2((qh ferr, 2013, "qh_checkzero: facet f%d needs pre-merging\n",
554  facet->id));
555  return False;
556 
557  LABELnonconvex:
558  trace2((qh ferr, 2014, "qh_checkzero: facet f%d and f%d are not clearly convex. v%d dist %.2g\n",
559  facet->id, neighbor->id, vertex->id, dist));
560  return False;
561 } /* checkzero */
562 
563 /*-<a href="qh-merge.htm#TOC"
564  >-------------------------------</a><a name="compareangle">-</a>
565 
566  qh_compareangle( angle1, angle2 )
567  used by qsort() to order merges by angle
568 */
569 int qh_compareangle(const void *p1, const void *p2) {
570  const mergeT *a= *((mergeT *const*)p1), *b= *((mergeT *const*)p2);
571 
572  return((a->angle > b->angle) ? 1 : -1);
573 } /* compareangle */
574 
575 /*-<a href="qh-merge.htm#TOC"
576  >-------------------------------</a><a name="comparemerge">-</a>
577 
578  qh_comparemerge( merge1, merge2 )
579  used by qsort() to order merges
580 */
581 int qh_comparemerge(const void *p1, const void *p2) {
582  const mergeT *a= *((mergeT *const*)p1), *b= *((mergeT *const*)p2);
583 
584  return(a->type - b->type);
585 } /* comparemerge */
586 
587 /*-<a href="qh-merge.htm#TOC"
588  >-------------------------------</a><a name="comparevisit">-</a>
589 
590  qh_comparevisit( vertex1, vertex2 )
591  used by qsort() to order vertices by their visitid
592 */
593 int qh_comparevisit(const void *p1, const void *p2) {
594  const vertexT *a= *((vertexT *const*)p1), *b= *((vertexT *const*)p2);
595 
596  return(a->visitid - b->visitid);
597 } /* comparevisit */
598 
599 /*-<a href="qh-merge.htm#TOC"
600  >-------------------------------</a><a name="copynonconvex">-</a>
601 
602  qh_copynonconvex( atridge )
603  set non-convex flag on other ridges (if any) between same neighbors
604 
605  notes:
606  may be faster if use smaller ridge set
607 
608  design:
609  for each ridge of atridge's top facet
610  if ridge shares the same neighbor
611  set nonconvex flag
612 */
613 void qh_copynonconvex(ridgeT *atridge) {
614  facetT *facet, *otherfacet;
615  ridgeT *ridge, **ridgep;
616 
617  facet= atridge->top;
618  otherfacet= atridge->bottom;
619  FOREACHridge_(facet->ridges) {
620  if (otherfacet == otherfacet_(ridge, facet) && ridge != atridge) {
621  ridge->nonconvex= True;
622  trace4((qh ferr, 4020, "qh_copynonconvex: moved nonconvex flag from r%d to r%d\n",
623  atridge->id, ridge->id));
624  break;
625  }
626  }
627 } /* copynonconvex */
628 
629 /*-<a href="qh-merge.htm#TOC"
630  >-------------------------------</a><a name="degen_redundant_facet">-</a>
631 
632  qh_degen_redundant_facet( facet )
633  check facet for degen. or redundancy
634 
635  notes:
636  bumps vertex_visit
637  called if a facet was redundant but no longer is (qh_merge_degenredundant)
638  qh_appendmergeset() only appends first reference to facet (i.e., redundant)
639 
640  see:
641  qh_degen_redundant_neighbors()
642 
643  design:
644  test for redundant neighbor
645  test for degenerate facet
646 */
647 void qh_degen_redundant_facet(facetT *facet) {
648  vertexT *vertex, **vertexp;
649  facetT *neighbor, **neighborp;
650 
651  trace4((qh ferr, 4021, "qh_degen_redundant_facet: test facet f%d for degen/redundant\n",
652  facet->id));
653  FOREACHneighbor_(facet) {
654  qh vertex_visit++;
655  FOREACHvertex_(neighbor->vertices)
656  vertex->visitid= qh vertex_visit;
657  FOREACHvertex_(facet->vertices) {
658  if (vertex->visitid != qh vertex_visit)
659  break;
660  }
661  if (!vertex) {
662  qh_appendmergeset(facet, neighbor, MRGredundant, NULL);
663  trace2((qh ferr, 2015, "qh_degen_redundant_facet: f%d is contained in f%d. merge\n", facet->id, neighbor->id));
664  return;
665  }
666  }
667  if (qh_setsize(facet->neighbors) < qh hull_dim) {
668  qh_appendmergeset(facet, facet, MRGdegen, NULL);
669  trace2((qh ferr, 2016, "qh_degen_redundant_neighbors: f%d is degenerate.\n", facet->id));
670  }
671 } /* degen_redundant_facet */
672 
673 
674 /*-<a href="qh-merge.htm#TOC"
675  >-------------------------------</a><a name="degen_redundant_neighbors">-</a>
676 
677  qh_degen_redundant_neighbors( facet, delfacet, )
678  append degenerate and redundant neighbors to facet_mergeset
679  if delfacet,
680  only checks neighbors of both delfacet and facet
681  also checks current facet for degeneracy
682 
683  notes:
684  bumps vertex_visit
685  called for each qh_mergefacet() and qh_mergecycle()
686  merge and statistics occur in merge_nonconvex
687  qh_appendmergeset() only appends first reference to facet (i.e., redundant)
688  it appends redundant facets after degenerate ones
689 
690  a degenerate facet has fewer than hull_dim neighbors
691  a redundant facet's vertices is a subset of its neighbor's vertices
692  tests for redundant merges first (appendmergeset is nop for others)
693  in a merge, only needs to test neighbors of merged facet
694 
695  see:
696  qh_merge_degenredundant() and qh_degen_redundant_facet()
697 
698  design:
699  test for degenerate facet
700  test for redundant neighbor
701  test for degenerate neighbor
702 */
703 void qh_degen_redundant_neighbors(facetT *facet, facetT *delfacet) {
704  vertexT *vertex, **vertexp;
705  facetT *neighbor, **neighborp;
706  int size;
707 
708  trace4((qh ferr, 4022, "qh_degen_redundant_neighbors: test neighbors of f%d with delfacet f%d\n",
709  facet->id, getid_(delfacet)));
710  if ((size= qh_setsize(facet->neighbors)) < qh hull_dim) {
711  qh_appendmergeset(facet, facet, MRGdegen, NULL);
712  trace2((qh ferr, 2017, "qh_degen_redundant_neighbors: f%d is degenerate with %d neighbors.\n", facet->id, size));
713  }
714  if (!delfacet)
715  delfacet= facet;
716  qh vertex_visit++;
717  FOREACHvertex_(facet->vertices)
718  vertex->visitid= qh vertex_visit;
719  FOREACHneighbor_(delfacet) {
720  /* uses early out instead of checking vertex count */
721  if (neighbor == facet)
722  continue;
723  FOREACHvertex_(neighbor->vertices) {
724  if (vertex->visitid != qh vertex_visit)
725  break;
726  }
727  if (!vertex) {
728  qh_appendmergeset(neighbor, facet, MRGredundant, NULL);
729  trace2((qh ferr, 2018, "qh_degen_redundant_neighbors: f%d is contained in f%d. merge\n", neighbor->id, facet->id));
730  }
731  }
732  FOREACHneighbor_(delfacet) { /* redundant merges occur first */
733  if (neighbor == facet)
734  continue;
735  if ((size= qh_setsize(neighbor->neighbors)) < qh hull_dim) {
736  qh_appendmergeset(neighbor, neighbor, MRGdegen, NULL);
737  trace2((qh ferr, 2019, "qh_degen_redundant_neighbors: f%d is degenerate with %d neighbors. Neighbor of f%d.\n", neighbor->id, size, facet->id));
738  }
739  }
740 } /* degen_redundant_neighbors */
741 
742 
743 /*-<a href="qh-merge.htm#TOC"
744  >-------------------------------</a><a name="find_newvertex">-</a>
745 
746  qh_find_newvertex( oldvertex, vertices, ridges )
747  locate new vertex for renaming old vertex
748  vertices is a set of possible new vertices
749  vertices sorted by number of deleted ridges
750 
751  returns:
752  newvertex or NULL
753  each ridge includes both vertex and oldvertex
754  vertices sorted by number of deleted ridges
755 
756  notes:
757  modifies vertex->visitid
758  new vertex is in one of the ridges
759  renaming will not cause a duplicate ridge
760  renaming will minimize the number of deleted ridges
761  newvertex may not be adjacent in the dual (though unlikely)
762 
763  design:
764  for each vertex in vertices
765  set vertex->visitid to number of references in ridges
766  remove unvisited vertices
767  set qh.vertex_visit above all possible values
768  sort vertices by number of references in ridges
769  add each ridge to qh.hash_table
770  for each vertex in vertices
771  look for a vertex that would not cause a duplicate ridge after a rename
772 */
773 vertexT *qh_find_newvertex(vertexT *oldvertex, setT *vertices, setT *ridges) {
774  vertexT *vertex, **vertexp;
775  setT *newridges;
776  ridgeT *ridge, **ridgep;
777  int size, hashsize;
778  int hash;
779 
780 #ifndef qh_NOtrace
781  if (qh IStracing >= 4) {
782  qh_fprintf(qh ferr, 8063, "qh_find_newvertex: find new vertex for v%d from ",
783  oldvertex->id);
784  FOREACHvertex_(vertices)
785  qh_fprintf(qh ferr, 8064, "v%d ", vertex->id);
786  FOREACHridge_(ridges)
787  qh_fprintf(qh ferr, 8065, "r%d ", ridge->id);
788  qh_fprintf(qh ferr, 8066, "\n");
789  }
790 #endif
791  FOREACHvertex_(vertices)
792  vertex->visitid= 0;
793  FOREACHridge_(ridges) {
794  FOREACHvertex_(ridge->vertices)
795  vertex->visitid++;
796  }
797  FOREACHvertex_(vertices) {
798  if (!vertex->visitid) {
799  qh_setdelnth(vertices, SETindex_(vertices,vertex));
800  vertexp--; /* repeat since deleted this vertex */
801  }
802  }
803  qh vertex_visit += (unsigned int)qh_setsize(ridges);
804  if (!qh_setsize(vertices)) {
805  trace4((qh ferr, 4023, "qh_find_newvertex: vertices not in ridges for v%d\n",
806  oldvertex->id));
807  return NULL;
808  }
809  qsort(SETaddr_(vertices, vertexT), (size_t)qh_setsize(vertices),
810  sizeof(vertexT *), qh_comparevisit);
811  /* can now use qh vertex_visit */
812  if (qh PRINTstatistics) {
813  size= qh_setsize(vertices);
814  zinc_(Zintersect);
815  zadd_(Zintersecttot, size);
816  zmax_(Zintersectmax, size);
817  }
818  hashsize= qh_newhashtable(qh_setsize(ridges));
819  FOREACHridge_(ridges)
820  qh_hashridge(qh hash_table, hashsize, ridge, oldvertex);
821  FOREACHvertex_(vertices) {
822  newridges= qh_vertexridges(vertex);
823  FOREACHridge_(newridges) {
824  if (qh_hashridge_find(qh hash_table, hashsize, ridge, vertex, oldvertex, &hash)) {
825  zinc_(Zdupridge);
826  break;
827  }
828  }
829  qh_settempfree(&newridges);
830  if (!ridge)
831  break; /* found a rename */
832  }
833  if (vertex) {
834  /* counted in qh_renamevertex */
835  trace2((qh ferr, 2020, "qh_find_newvertex: found v%d for old v%d from %d vertices and %d ridges.\n",
836  vertex->id, oldvertex->id, qh_setsize(vertices), qh_setsize(ridges)));
837  }else {
838  zinc_(Zfindfail);
839  trace0((qh ferr, 14, "qh_find_newvertex: no vertex for renaming v%d(all duplicated ridges) during p%d\n",
840  oldvertex->id, qh furthest_id));
841  }
842  qh_setfree(&qh hash_table);
843  return vertex;
844 } /* find_newvertex */
845 
846 /*-<a href="qh-merge.htm#TOC"
847  >-------------------------------</a><a name="findbest_test">-</a>
848 
849  qh_findbest_test( testcentrum, facet, neighbor, bestfacet, dist, mindist, maxdist )
850  test neighbor of facet for qh_findbestneighbor()
851  if testcentrum,
852  tests centrum (assumes it is defined)
853  else
854  tests vertices
855 
856  returns:
857  if a better facet (i.e., vertices/centrum of facet closer to neighbor)
858  updates bestfacet, dist, mindist, and maxdist
859 */
860 void qh_findbest_test(boolT testcentrum, facetT *facet, facetT *neighbor,
861  facetT **bestfacet, realT *distp, realT *mindistp, realT *maxdistp) {
862  realT dist, mindist, maxdist;
863 
864  if (testcentrum) {
865  zzinc_(Zbestdist);
866  qh_distplane(facet->center, neighbor, &dist);
867  dist *= qh hull_dim; /* estimate furthest vertex */
868  if (dist < 0) {
869  maxdist= 0;
870  mindist= dist;
871  dist= -dist;
872  }else {
873  mindist= 0;
874  maxdist= dist;
875  }
876  }else
877  dist= qh_getdistance(facet, neighbor, &mindist, &maxdist);
878  if (dist < *distp) {
879  *bestfacet= neighbor;
880  *mindistp= mindist;
881  *maxdistp= maxdist;
882  *distp= dist;
883  }
884 } /* findbest_test */
885 
886 /*-<a href="qh-merge.htm#TOC"
887  >-------------------------------</a><a name="findbestneighbor">-</a>
888 
889  qh_findbestneighbor( facet, dist, mindist, maxdist )
890  finds best neighbor (least dist) of a facet for merging
891 
892  returns:
893  returns min and max distances and their max absolute value
894 
895  notes:
896  error if qh_ASvoronoi
897  avoids merging old into new
898  assumes ridge->nonconvex only set on one ridge between a pair of facets
899  could use an early out predicate but not worth it
900 
901  design:
902  if a large facet
903  will test centrum
904  else
905  will test vertices
906  if a large facet
907  test nonconvex neighbors for best merge
908  else
909  test all neighbors for the best merge
910  if testing centrum
911  get distance information
912 */
913 facetT *qh_findbestneighbor(facetT *facet, realT *distp, realT *mindistp, realT *maxdistp) {
914  facetT *neighbor, **neighborp, *bestfacet= NULL;
915  ridgeT *ridge, **ridgep;
916  boolT nonconvex= True, testcentrum= False;
917  int size= qh_setsize(facet->vertices);
918 
919  if(qh CENTERtype==qh_ASvoronoi){
920  qh_fprintf(qh ferr, 6272, "qhull error: cannot call qh_findbestneighor for f%d while qh.CENTERtype is qh_ASvoronoi\n", facet->id);
921  qh_errexit(qh_ERRqhull, facet, NULL);
922  }
923  *distp= REALmax;
924  if (size > qh_BESTcentrum2 * qh hull_dim + qh_BESTcentrum) {
925  testcentrum= True;
926  zinc_(Zbestcentrum);
927  if (!facet->center)
928  facet->center= qh_getcentrum(facet);
929  }
930  if (size > qh hull_dim + qh_BESTnonconvex) {
931  FOREACHridge_(facet->ridges) {
932  if (ridge->nonconvex) {
933  neighbor= otherfacet_(ridge, facet);
934  qh_findbest_test(testcentrum, facet, neighbor,
935  &bestfacet, distp, mindistp, maxdistp);
936  }
937  }
938  }
939  if (!bestfacet) {
940  nonconvex= False;
941  FOREACHneighbor_(facet)
942  qh_findbest_test(testcentrum, facet, neighbor,
943  &bestfacet, distp, mindistp, maxdistp);
944  }
945  if (!bestfacet) {
946  qh_fprintf(qh ferr, 6095, "qhull internal error (qh_findbestneighbor): no neighbors for f%d\n", facet->id);
947 
948  qh_errexit(qh_ERRqhull, facet, NULL);
949  }
950  if (testcentrum)
951  qh_getdistance(facet, bestfacet, mindistp, maxdistp);
952  trace3((qh ferr, 3002, "qh_findbestneighbor: f%d is best neighbor for f%d testcentrum? %d nonconvex? %d dist %2.2g min %2.2g max %2.2g\n",
953  bestfacet->id, facet->id, testcentrum, nonconvex, *distp, *mindistp, *maxdistp));
954  return(bestfacet);
955 } /* findbestneighbor */
956 
957 
958 /*-<a href="qh-merge.htm#TOC"
959  >-------------------------------</a><a name="flippedmerges">-</a>
960 
961  qh_flippedmerges( facetlist, wasmerge )
962  merge flipped facets into best neighbor
963  assumes qh.facet_mergeset at top of temporary stack
964 
965  returns:
966  no flipped facets on facetlist
967  sets wasmerge if merge occurred
968  degen/redundant merges passed through
969 
970  notes:
971  othermerges not needed since qh.facet_mergeset is empty before & after
972  keep it in case of change
973 
974  design:
975  append flipped facets to qh.facetmergeset
976  for each flipped merge
977  find best neighbor
978  merge facet into neighbor
979  merge degenerate and redundant facets
980  remove flipped merges from qh.facet_mergeset
981 */
982 void qh_flippedmerges(facetT *facetlist, boolT *wasmerge) {
983  facetT *facet, *neighbor, *facet1;
984  realT dist, mindist, maxdist;
985  mergeT *merge, **mergep;
986  setT *othermerges;
987  int nummerge=0;
988 
989  trace4((qh ferr, 4024, "qh_flippedmerges: begin\n"));
990  FORALLfacet_(facetlist) {
991  if (facet->flipped && !facet->visible)
992  qh_appendmergeset(facet, facet, MRGflip, NULL);
993  }
994  othermerges= qh_settemppop(); /* was facet_mergeset */
995  qh facet_mergeset= qh_settemp(qh TEMPsize);
996  qh_settemppush(othermerges);
997  FOREACHmerge_(othermerges) {
998  facet1= merge->facet1;
999  if (merge->type != MRGflip || facet1->visible)
1000  continue;
1001  if (qh TRACEmerge-1 == zzval_(Ztotmerge))
1002  qhmem.IStracing= qh IStracing= qh TRACElevel;
1003  neighbor= qh_findbestneighbor(facet1, &dist, &mindist, &maxdist);
1004  trace0((qh ferr, 15, "qh_flippedmerges: merge flipped f%d into f%d dist %2.2g during p%d\n",
1005  facet1->id, neighbor->id, dist, qh furthest_id));
1006  qh_mergefacet(facet1, neighbor, &mindist, &maxdist, !qh_MERGEapex);
1007  nummerge++;
1008  if (qh PRINTstatistics) {
1009  zinc_(Zflipped);
1010  wadd_(Wflippedtot, dist);
1011  wmax_(Wflippedmax, dist);
1012  }
1013  qh_merge_degenredundant();
1014  }
1015  FOREACHmerge_(othermerges) {
1016  if (merge->facet1->visible || merge->facet2->visible)
1017  qh_memfree(merge, (int)sizeof(mergeT));
1018  else
1019  qh_setappend(&qh facet_mergeset, merge);
1020  }
1021  qh_settempfree(&othermerges);
1022  if (nummerge)
1023  *wasmerge= True;
1024  trace1((qh ferr, 1010, "qh_flippedmerges: merged %d flipped facets into a good neighbor\n", nummerge));
1025 } /* flippedmerges */
1026 
1027 
1028 /*-<a href="qh-merge.htm#TOC"
1029  >-------------------------------</a><a name="forcedmerges">-</a>
1030 
1031  qh_forcedmerges( wasmerge )
1032  merge duplicated ridges
1033 
1034  returns:
1035  removes all duplicate ridges on facet_mergeset
1036  wasmerge set if merge
1037  qh.facet_mergeset may include non-forced merges(none for now)
1038  qh.degen_mergeset includes degen/redun merges
1039 
1040  notes:
1041  duplicate ridges occur when the horizon is pinched,
1042  i.e. a subridge occurs in more than two horizon ridges.
1043  could rename vertices that pinch the horizon
1044  assumes qh_merge_degenredundant() has not be called
1045  othermerges isn't needed since facet_mergeset is empty afterwards
1046  keep it in case of change
1047 
1048  design:
1049  for each duplicate ridge
1050  find current facets by chasing f.replace links
1051  check for wide merge due to duplicate ridge
1052  determine best direction for facet
1053  merge one facet into the other
1054  remove duplicate ridges from qh.facet_mergeset
1055 */
1056 void qh_forcedmerges(boolT *wasmerge) {
1057  facetT *facet1, *facet2;
1058  mergeT *merge, **mergep;
1059  realT dist1, dist2, mindist1, mindist2, maxdist1, maxdist2;
1060  setT *othermerges;
1061  int nummerge=0, numflip=0;
1062 
1063  if (qh TRACEmerge-1 == zzval_(Ztotmerge))
1064  qhmem.IStracing= qh IStracing= qh TRACElevel;
1065  trace4((qh ferr, 4025, "qh_forcedmerges: begin\n"));
1066  othermerges= qh_settemppop(); /* was facet_mergeset */
1067  qh facet_mergeset= qh_settemp(qh TEMPsize);
1068  qh_settemppush(othermerges);
1069  FOREACHmerge_(othermerges) {
1070  if (merge->type != MRGridge)
1071  continue;
1072  if (qh TRACEmerge-1 == zzval_(Ztotmerge))
1073  qhmem.IStracing= qh IStracing= qh TRACElevel;
1074  facet1= merge->facet1;
1075  facet2= merge->facet2;
1076  while (facet1->visible) /* must exist, no qh_merge_degenredunant */
1077  facet1= facet1->f.replace; /* previously merged facet */
1078  while (facet2->visible)
1079  facet2= facet2->f.replace; /* previously merged facet */
1080  if (facet1 == facet2)
1081  continue;
1082  if (!qh_setin(facet2->neighbors, facet1)) {
1083  qh_fprintf(qh ferr, 6096, "qhull internal error (qh_forcedmerges): f%d and f%d had a duplicate ridge but as f%d and f%d they are no longer neighbors\n",
1084  merge->facet1->id, merge->facet2->id, facet1->id, facet2->id);
1085  qh_errexit2(qh_ERRqhull, facet1, facet2);
1086  }
1087  dist1= qh_getdistance(facet1, facet2, &mindist1, &maxdist1);
1088  dist2= qh_getdistance(facet2, facet1, &mindist2, &maxdist2);
1089  qh_check_dupridge(facet1, dist1, facet2, dist2);
1090  if (dist1 < dist2)
1091  qh_mergefacet(facet1, facet2, &mindist1, &maxdist1, !qh_MERGEapex);
1092  else {
1093  qh_mergefacet(facet2, facet1, &mindist2, &maxdist2, !qh_MERGEapex);
1094  dist1= dist2;
1095  facet1= facet2;
1096  }
1097  if (facet1->flipped) {
1098  zinc_(Zmergeflipdup);
1099  numflip++;
1100  }else
1101  nummerge++;
1102  if (qh PRINTstatistics) {
1103  zinc_(Zduplicate);
1104  wadd_(Wduplicatetot, dist1);
1105  wmax_(Wduplicatemax, dist1);
1106  }
1107  }
1108  FOREACHmerge_(othermerges) {
1109  if (merge->type == MRGridge)
1110  qh_memfree(merge, (int)sizeof(mergeT));
1111  else
1112  qh_setappend(&qh facet_mergeset, merge);
1113  }
1114  qh_settempfree(&othermerges);
1115  if (nummerge)
1116  *wasmerge= True;
1117  trace1((qh ferr, 1011, "qh_forcedmerges: merged %d facets and %d flipped facets across duplicated ridges\n",
1118  nummerge, numflip));
1119 } /* forcedmerges */
1120 
1121 
1122 /*-<a href="qh-merge.htm#TOC"
1123  >-------------------------------</a><a name="getmergeset">-</a>
1124 
1125  qh_getmergeset( facetlist )
1126  determines nonconvex facets on facetlist
1127  tests !tested ridges and nonconvex ridges of !tested facets
1128 
1129  returns:
1130  returns sorted qh.facet_mergeset of facet-neighbor pairs to be merged
1131  all ridges tested
1132 
1133  notes:
1134  assumes no nonconvex ridges with both facets tested
1135  uses facet->tested/ridge->tested to prevent duplicate tests
1136  can not limit tests to modified ridges since the centrum changed
1137  uses qh.visit_id
1138 
1139  see:
1140  qh_getmergeset_initial()
1141 
1142  design:
1143  for each facet on facetlist
1144  for each ridge of facet
1145  if untested ridge
1146  test ridge for convexity
1147  if non-convex
1148  append ridge to qh.facet_mergeset
1149  sort qh.facet_mergeset by angle
1150 */
1151 void qh_getmergeset(facetT *facetlist) {
1152  facetT *facet, *neighbor, **neighborp;
1153  ridgeT *ridge, **ridgep;
1154  int nummerges;
1155 
1156  nummerges= qh_setsize(qh facet_mergeset);
1157  trace4((qh ferr, 4026, "qh_getmergeset: started.\n"));
1158  qh visit_id++;
1159  FORALLfacet_(facetlist) {
1160  if (facet->tested)
1161  continue;
1162  facet->visitid= qh visit_id;
1163  facet->tested= True; /* must be non-simplicial due to merge */
1164  FOREACHneighbor_(facet)
1165  neighbor->seen= False;
1166  FOREACHridge_(facet->ridges) {
1167  if (ridge->tested && !ridge->nonconvex)
1168  continue;
1169  /* if tested & nonconvex, need to append merge */
1170  neighbor= otherfacet_(ridge, facet);
1171  if (neighbor->seen) {
1172  ridge->tested= True;
1173  ridge->nonconvex= False;
1174  }else if (neighbor->visitid != qh visit_id) {
1175  ridge->tested= True;
1176  ridge->nonconvex= False;
1177  neighbor->seen= True; /* only one ridge is marked nonconvex */
1178  if (qh_test_appendmerge(facet, neighbor))
1179  ridge->nonconvex= True;
1180  }
1181  }
1182  }
1183  nummerges= qh_setsize(qh facet_mergeset);
1184  if (qh ANGLEmerge)
1185  qsort(SETaddr_(qh facet_mergeset, mergeT), (size_t)nummerges, sizeof(mergeT *), qh_compareangle);
1186  else
1187  qsort(SETaddr_(qh facet_mergeset, mergeT), (size_t)nummerges, sizeof(mergeT *), qh_comparemerge);
1188  if (qh POSTmerging) {
1189  zadd_(Zmergesettot2, nummerges);
1190  }else {
1191  zadd_(Zmergesettot, nummerges);
1192  zmax_(Zmergesetmax, nummerges);
1193  }
1194  trace2((qh ferr, 2021, "qh_getmergeset: %d merges found\n", nummerges));
1195 } /* getmergeset */
1196 
1197 
1198 /*-<a href="qh-merge.htm#TOC"
1199  >-------------------------------</a><a name="getmergeset_initial">-</a>
1200 
1201  qh_getmergeset_initial( facetlist )
1202  determine initial qh.facet_mergeset for facets
1203  tests all facet/neighbor pairs on facetlist
1204 
1205  returns:
1206  sorted qh.facet_mergeset with nonconvex ridges
1207  sets facet->tested, ridge->tested, and ridge->nonconvex
1208 
1209  notes:
1210  uses visit_id, assumes ridge->nonconvex is False
1211 
1212  see:
1213  qh_getmergeset()
1214 
1215  design:
1216  for each facet on facetlist
1217  for each untested neighbor of facet
1218  test facet and neighbor for convexity
1219  if non-convex
1220  append merge to qh.facet_mergeset
1221  mark one of the ridges as nonconvex
1222  sort qh.facet_mergeset by angle
1223 */
1224 void qh_getmergeset_initial(facetT *facetlist) {
1225  facetT *facet, *neighbor, **neighborp;
1226  ridgeT *ridge, **ridgep;
1227  int nummerges;
1228 
1229  qh visit_id++;
1230  FORALLfacet_(facetlist) {
1231  facet->visitid= qh visit_id;
1232  facet->tested= True;
1233  FOREACHneighbor_(facet) {
1234  if (neighbor->visitid != qh visit_id) {
1235  if (qh_test_appendmerge(facet, neighbor)) {
1236  FOREACHridge_(neighbor->ridges) {
1237  if (facet == otherfacet_(ridge, neighbor)) {
1238  ridge->nonconvex= True;
1239  break; /* only one ridge is marked nonconvex */
1240  }
1241  }
1242  }
1243  }
1244  }
1245  FOREACHridge_(facet->ridges)
1246  ridge->tested= True;
1247  }
1248  nummerges= qh_setsize(qh facet_mergeset);
1249  if (qh ANGLEmerge)
1250  qsort(SETaddr_(qh facet_mergeset, mergeT), (size_t)nummerges, sizeof(mergeT *), qh_compareangle);
1251  else
1252  qsort(SETaddr_(qh facet_mergeset, mergeT), (size_t)nummerges, sizeof(mergeT *), qh_comparemerge);
1253  if (qh POSTmerging) {
1254  zadd_(Zmergeinittot2, nummerges);
1255  }else {
1256  zadd_(Zmergeinittot, nummerges);
1257  zmax_(Zmergeinitmax, nummerges);
1258  }
1259  trace2((qh ferr, 2022, "qh_getmergeset_initial: %d merges found\n", nummerges));
1260 } /* getmergeset_initial */
1261 
1262 
1263 /*-<a href="qh-merge.htm#TOC"
1264  >-------------------------------</a><a name="hashridge">-</a>
1265 
1266  qh_hashridge( hashtable, hashsize, ridge, oldvertex )
1267  add ridge to hashtable without oldvertex
1268 
1269  notes:
1270  assumes hashtable is large enough
1271 
1272  design:
1273  determine hash value for ridge without oldvertex
1274  find next empty slot for ridge
1275 */
1276 void qh_hashridge(setT *hashtable, int hashsize, ridgeT *ridge, vertexT *oldvertex) {
1277  int hash;
1278  ridgeT *ridgeA;
1279 
1280  hash= qh_gethash(hashsize, ridge->vertices, qh hull_dim-1, 0, oldvertex);
1281  while (True) {
1282  if (!(ridgeA= SETelemt_(hashtable, hash, ridgeT))) {
1283  SETelem_(hashtable, hash)= ridge;
1284  break;
1285  }else if (ridgeA == ridge)
1286  break;
1287  if (++hash == hashsize)
1288  hash= 0;
1289  }
1290 } /* hashridge */
1291 
1292 
1293 /*-<a href="qh-merge.htm#TOC"
1294  >-------------------------------</a><a name="hashridge_find">-</a>
1295 
1296  qh_hashridge_find( hashtable, hashsize, ridge, vertex, oldvertex, hashslot )
1297  returns matching ridge without oldvertex in hashtable
1298  for ridge without vertex
1299  if oldvertex is NULL
1300  matches with any one skip
1301 
1302  returns:
1303  matching ridge or NULL
1304  if no match,
1305  if ridge already in table
1306  hashslot= -1
1307  else
1308  hashslot= next NULL index
1309 
1310  notes:
1311  assumes hashtable is large enough
1312  can't match ridge to itself
1313 
1314  design:
1315  get hash value for ridge without vertex
1316  for each hashslot
1317  return match if ridge matches ridgeA without oldvertex
1318 */
1319 ridgeT *qh_hashridge_find(setT *hashtable, int hashsize, ridgeT *ridge,
1320  vertexT *vertex, vertexT *oldvertex, int *hashslot) {
1321  int hash;
1322  ridgeT *ridgeA;
1323 
1324  *hashslot= 0;
1325  zinc_(Zhashridge);
1326  hash= qh_gethash(hashsize, ridge->vertices, qh hull_dim-1, 0, vertex);
1327  while ((ridgeA= SETelemt_(hashtable, hash, ridgeT))) {
1328  if (ridgeA == ridge)
1329  *hashslot= -1;
1330  else {
1331  zinc_(Zhashridgetest);
1332  if (qh_setequal_except(ridge->vertices, vertex, ridgeA->vertices, oldvertex))
1333  return ridgeA;
1334  }
1335  if (++hash == hashsize)
1336  hash= 0;
1337  }
1338  if (!*hashslot)
1339  *hashslot= hash;
1340  return NULL;
1341 } /* hashridge_find */
1342 
1343 
1344 /*-<a href="qh-merge.htm#TOC"
1345  >-------------------------------</a><a name="makeridges">-</a>
1346 
1347  qh_makeridges( facet )
1348  creates explicit ridges between simplicial facets
1349 
1350  returns:
1351  facet with ridges and without qh_MERGEridge
1352  ->simplicial is False
1353 
1354  notes:
1355  allows qh_MERGEridge flag
1356  uses existing ridges
1357  duplicate neighbors ok if ridges already exist (qh_mergecycle_ridges)
1358 
1359  see:
1360  qh_mergecycle_ridges()
1361 
1362  design:
1363  look for qh_MERGEridge neighbors
1364  mark neighbors that already have ridges
1365  for each unprocessed neighbor of facet
1366  create a ridge for neighbor and facet
1367  if any qh_MERGEridge neighbors
1368  delete qh_MERGEridge flags (already handled by qh_mark_dupridges)
1369 */
1370 void qh_makeridges(facetT *facet) {
1371  facetT *neighbor, **neighborp;
1372  ridgeT *ridge, **ridgep;
1373  int neighbor_i, neighbor_n;
1374  boolT toporient, mergeridge= False;
1375 
1376  if (!facet->simplicial)
1377  return;
1378  trace4((qh ferr, 4027, "qh_makeridges: make ridges for f%d\n", facet->id));
1379  facet->simplicial= False;
1380  FOREACHneighbor_(facet) {
1381  if (neighbor == qh_MERGEridge)
1382  mergeridge= True;
1383  else
1384  neighbor->seen= False;
1385  }
1386  FOREACHridge_(facet->ridges)
1387  otherfacet_(ridge, facet)->seen= True;
1388  FOREACHneighbor_i_(facet) {
1389  if (neighbor == qh_MERGEridge)
1390  continue; /* fixed by qh_mark_dupridges */
1391  else if (!neighbor->seen) { /* no current ridges */
1392  ridge= qh_newridge();
1393  ridge->vertices= qh_setnew_delnthsorted(facet->vertices, qh hull_dim,
1394  neighbor_i, 0);
1395  toporient= facet->toporient ^ (neighbor_i & 0x1);
1396  if (toporient) {
1397  ridge->top= facet;
1398  ridge->bottom= neighbor;
1399  }else {
1400  ridge->top= neighbor;
1401  ridge->bottom= facet;
1402  }
1403 #if 0 /* this also works */
1404  flip= (facet->toporient ^ neighbor->toporient)^(skip1 & 0x1) ^ (skip2 & 0x1);
1405  if (facet->toporient ^ (skip1 & 0x1) ^ flip) {
1406  ridge->top= neighbor;
1407  ridge->bottom= facet;
1408  }else {
1409  ridge->top= facet;
1410  ridge->bottom= neighbor;
1411  }
1412 #endif
1413  qh_setappend(&(facet->ridges), ridge);
1414  qh_setappend(&(neighbor->ridges), ridge);
1415  }
1416  }
1417  if (mergeridge) {
1418  while (qh_setdel(facet->neighbors, qh_MERGEridge))
1419  ; /* delete each one */
1420  }
1421 } /* makeridges */
1422 
1423 
1424 /*-<a href="qh-merge.htm#TOC"
1425  >-------------------------------</a><a name="mark_dupridges">-</a>
1426 
1427  qh_mark_dupridges( facetlist )
1428  add duplicated ridges to qh.facet_mergeset
1429  facet->dupridge is true
1430 
1431  returns:
1432  duplicate ridges on qh.facet_mergeset
1433  ->mergeridge/->mergeridge2 set
1434  duplicate ridges marked by qh_MERGEridge and both sides facet->dupridge
1435  no MERGEridges in neighbor sets
1436 
1437  notes:
1438  duplicate ridges occur when the horizon is pinched,
1439  i.e. a subridge occurs in more than two horizon ridges.
1440  could rename vertices that pinch the horizon (thus removing subridge)
1441  uses qh.visit_id
1442 
1443  design:
1444  for all facets on facetlist
1445  if facet contains a duplicate ridge
1446  for each neighbor of facet
1447  if neighbor marked qh_MERGEridge (one side of the merge)
1448  set facet->mergeridge
1449  else
1450  if neighbor contains a duplicate ridge
1451  and the back link is qh_MERGEridge
1452  append duplicate ridge to qh.facet_mergeset
1453  for each duplicate ridge
1454  make ridge sets in preparation for merging
1455  remove qh_MERGEridge from neighbor set
1456  for each duplicate ridge
1457  restore the missing neighbor from the neighbor set that was qh_MERGEridge
1458  add the missing ridge for this neighbor
1459 */
1460 void qh_mark_dupridges(facetT *facetlist) {
1461  facetT *facet, *neighbor, **neighborp;
1462  int nummerge=0;
1463  mergeT *merge, **mergep;
1464 
1465 
1466  trace4((qh ferr, 4028, "qh_mark_dupridges: identify duplicate ridges\n"));
1467  FORALLfacet_(facetlist) {
1468  if (facet->dupridge) {
1469  FOREACHneighbor_(facet) {
1470  if (neighbor == qh_MERGEridge) {
1471  facet->mergeridge= True;
1472  continue;
1473  }
1474  if (neighbor->dupridge
1475  && !qh_setin(neighbor->neighbors, facet)) { /* qh_MERGEridge */
1476  qh_appendmergeset(facet, neighbor, MRGridge, NULL);
1477  facet->mergeridge2= True;
1478  facet->mergeridge= True;
1479  nummerge++;
1480  }
1481  }
1482  }
1483  }
1484  if (!nummerge)
1485  return;
1486  FORALLfacet_(facetlist) { /* gets rid of qh_MERGEridge */
1487  if (facet->mergeridge && !facet->mergeridge2)
1488  qh_makeridges(facet);
1489  }
1490  FOREACHmerge_(qh facet_mergeset) { /* restore the missing neighbors */
1491  if (merge->type == MRGridge) {
1492  qh_setappend(&merge->facet2->neighbors, merge->facet1);
1493  qh_makeridges(merge->facet1); /* and the missing ridges */
1494  }
1495  }
1496  trace1((qh ferr, 1012, "qh_mark_dupridges: found %d duplicated ridges\n",
1497  nummerge));
1498 } /* mark_dupridges */
1499 
1500 /*-<a href="qh-merge.htm#TOC"
1501  >-------------------------------</a><a name="maydropneighbor">-</a>
1502 
1503  qh_maydropneighbor( facet )
1504  drop neighbor relationship if no ridge between facet and neighbor
1505 
1506  returns:
1507  neighbor sets updated
1508  appends degenerate facets to qh.facet_mergeset
1509 
1510  notes:
1511  won't cause redundant facets since vertex inclusion is the same
1512  may drop vertex and neighbor if no ridge
1513  uses qh.visit_id
1514 
1515  design:
1516  visit all neighbors with ridges
1517  for each unvisited neighbor of facet
1518  delete neighbor and facet from the neighbor sets
1519  if neighbor becomes degenerate
1520  append neighbor to qh.degen_mergeset
1521  if facet is degenerate
1522  append facet to qh.degen_mergeset
1523 */
1524 void qh_maydropneighbor(facetT *facet) {
1525  ridgeT *ridge, **ridgep;
1526  realT angledegen= qh_ANGLEdegen;
1527  facetT *neighbor, **neighborp;
1528 
1529  qh visit_id++;
1530  trace4((qh ferr, 4029, "qh_maydropneighbor: test f%d for no ridges to a neighbor\n",
1531  facet->id));
1532  FOREACHridge_(facet->ridges) {
1533  ridge->top->visitid= qh visit_id;
1534  ridge->bottom->visitid= qh visit_id;
1535  }
1536  FOREACHneighbor_(facet) {
1537  if (neighbor->visitid != qh visit_id) {
1538  trace0((qh ferr, 17, "qh_maydropneighbor: facets f%d and f%d are no longer neighbors during p%d\n",
1539  facet->id, neighbor->id, qh furthest_id));
1540  zinc_(Zdropneighbor);
1541  qh_setdel(facet->neighbors, neighbor);
1542  neighborp--; /* repeat, deleted a neighbor */
1543  qh_setdel(neighbor->neighbors, facet);
1544  if (qh_setsize(neighbor->neighbors) < qh hull_dim) {
1545  zinc_(Zdropdegen);
1546  qh_appendmergeset(neighbor, neighbor, MRGdegen, &angledegen);
1547  trace2((qh ferr, 2023, "qh_maydropneighbors: f%d is degenerate.\n", neighbor->id));
1548  }
1549  }
1550  }
1551  if (qh_setsize(facet->neighbors) < qh hull_dim) {
1552  zinc_(Zdropdegen);
1553  qh_appendmergeset(facet, facet, MRGdegen, &angledegen);
1554  trace2((qh ferr, 2024, "qh_maydropneighbors: f%d is degenerate.\n", facet->id));
1555  }
1556 } /* maydropneighbor */
1557 
1558 
1559 /*-<a href="qh-merge.htm#TOC"
1560  >-------------------------------</a><a name="merge_degenredundant">-</a>
1561 
1562  qh_merge_degenredundant()
1563  merge all degenerate and redundant facets
1564  qh.degen_mergeset contains merges from qh_degen_redundant_neighbors()
1565 
1566  returns:
1567  number of merges performed
1568  resets facet->degenerate/redundant
1569  if deleted (visible) facet has no neighbors
1570  sets ->f.replace to NULL
1571 
1572  notes:
1573  redundant merges happen before degenerate ones
1574  merging and renaming vertices can result in degen/redundant facets
1575 
1576  design:
1577  for each merge on qh.degen_mergeset
1578  if redundant merge
1579  if non-redundant facet merged into redundant facet
1580  recheck facet for redundancy
1581  else
1582  merge redundant facet into other facet
1583 */
1584 int qh_merge_degenredundant(void) {
1585  int size;
1586  mergeT *merge;
1587  facetT *bestneighbor, *facet1, *facet2;
1588  realT dist, mindist, maxdist;
1589  vertexT *vertex, **vertexp;
1590  int nummerges= 0;
1591  mergeType mergetype;
1592 
1593  while ((merge= (mergeT*)qh_setdellast(qh degen_mergeset))) {
1594  facet1= merge->facet1;
1595  facet2= merge->facet2;
1596  mergetype= merge->type;
1597  qh_memfree(merge, (int)sizeof(mergeT));
1598  if (facet1->visible)
1599  continue;
1600  facet1->degenerate= False;
1601  facet1->redundant= False;
1602  if (qh TRACEmerge-1 == zzval_(Ztotmerge))
1603  qhmem.IStracing= qh IStracing= qh TRACElevel;
1604  if (mergetype == MRGredundant) {
1605  zinc_(Zneighbor);
1606  while (facet2->visible) {
1607  if (!facet2->f.replace) {
1608  qh_fprintf(qh ferr, 6097, "qhull internal error (qh_merge_degenredunant): f%d redundant but f%d has no replacement\n",
1609  facet1->id, facet2->id);
1610  qh_errexit2(qh_ERRqhull, facet1, facet2);
1611  }
1612  facet2= facet2->f.replace;
1613  }
1614  if (facet1 == facet2) {
1615  qh_degen_redundant_facet(facet1); /* in case of others */
1616  continue;
1617  }
1618  trace2((qh ferr, 2025, "qh_merge_degenredundant: facet f%d is contained in f%d, will merge\n",
1619  facet1->id, facet2->id));
1620  qh_mergefacet(facet1, facet2, NULL, NULL, !qh_MERGEapex);
1621  /* merge distance is already accounted for */
1622  nummerges++;
1623  }else { /* mergetype == MRGdegen, other merges may have fixed */
1624  if (!(size= qh_setsize(facet1->neighbors))) {
1625  zinc_(Zdelfacetdup);
1626  trace2((qh ferr, 2026, "qh_merge_degenredundant: facet f%d has no neighbors. Deleted\n", facet1->id));
1627  qh_willdelete(facet1, NULL);
1628  FOREACHvertex_(facet1->vertices) {
1629  qh_setdel(vertex->neighbors, facet1);
1630  if (!SETfirst_(vertex->neighbors)) {
1631  zinc_(Zdegenvertex);
1632  trace2((qh ferr, 2027, "qh_merge_degenredundant: deleted v%d because f%d has no neighbors\n",
1633  vertex->id, facet1->id));
1634  vertex->deleted= True;
1635  qh_setappend(&qh del_vertices, vertex);
1636  }
1637  }
1638  nummerges++;
1639  }else if (size < qh hull_dim) {
1640  bestneighbor= qh_findbestneighbor(facet1, &dist, &mindist, &maxdist);
1641  trace2((qh ferr, 2028, "qh_merge_degenredundant: facet f%d has %d neighbors, merge into f%d dist %2.2g\n",
1642  facet1->id, size, bestneighbor->id, dist));
1643  qh_mergefacet(facet1, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
1644  nummerges++;
1645  if (qh PRINTstatistics) {
1646  zinc_(Zdegen);
1647  wadd_(Wdegentot, dist);
1648  wmax_(Wdegenmax, dist);
1649  }
1650  } /* else, another merge fixed the degeneracy and redundancy tested */
1651  }
1652  }
1653  return nummerges;
1654 } /* merge_degenredundant */
1655 
1656 /*-<a href="qh-merge.htm#TOC"
1657  >-------------------------------</a><a name="merge_nonconvex">-</a>
1658 
1659  qh_merge_nonconvex( facet1, facet2, mergetype )
1660  remove non-convex ridge between facet1 into facet2
1661  mergetype gives why the facet's are non-convex
1662 
1663  returns:
1664  merges one of the facets into the best neighbor
1665 
1666  design:
1667  if one of the facets is a new facet
1668  prefer merging new facet into old facet
1669  find best neighbors for both facets
1670  merge the nearest facet into its best neighbor
1671  update the statistics
1672 */
1673 void qh_merge_nonconvex(facetT *facet1, facetT *facet2, mergeType mergetype) {
1674  facetT *bestfacet, *bestneighbor, *neighbor;
1675  realT dist, dist2, mindist, mindist2, maxdist, maxdist2;
1676 
1677  if (qh TRACEmerge-1 == zzval_(Ztotmerge))
1678  qhmem.IStracing= qh IStracing= qh TRACElevel;
1679  trace3((qh ferr, 3003, "qh_merge_nonconvex: merge #%d for f%d and f%d type %d\n",
1680  zzval_(Ztotmerge) + 1, facet1->id, facet2->id, mergetype));
1681  /* concave or coplanar */
1682  if (!facet1->newfacet) {
1683  bestfacet= facet2; /* avoid merging old facet if new is ok */
1684  facet2= facet1;
1685  facet1= bestfacet;
1686  }else
1687  bestfacet= facet1;
1688  bestneighbor= qh_findbestneighbor(bestfacet, &dist, &mindist, &maxdist);
1689  neighbor= qh_findbestneighbor(facet2, &dist2, &mindist2, &maxdist2);
1690  if (dist < dist2) {
1691  qh_mergefacet(bestfacet, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
1692  }else if (qh AVOIDold && !facet2->newfacet
1693  && ((mindist >= -qh MAXcoplanar && maxdist <= qh max_outside)
1694  || dist * 1.5 < dist2)) {
1695  zinc_(Zavoidold);
1696  wadd_(Wavoidoldtot, dist);
1697  wmax_(Wavoidoldmax, dist);
1698  trace2((qh ferr, 2029, "qh_merge_nonconvex: avoid merging old facet f%d dist %2.2g. Use f%d dist %2.2g instead\n",
1699  facet2->id, dist2, facet1->id, dist2));
1700  qh_mergefacet(bestfacet, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
1701  }else {
1702  qh_mergefacet(facet2, neighbor, &mindist2, &maxdist2, !qh_MERGEapex);
1703  dist= dist2;
1704  }
1705  if (qh PRINTstatistics) {
1706  if (mergetype == MRGanglecoplanar) {
1707  zinc_(Zacoplanar);
1708  wadd_(Wacoplanartot, dist);
1709  wmax_(Wacoplanarmax, dist);
1710  }else if (mergetype == MRGconcave) {
1711  zinc_(Zconcave);
1712  wadd_(Wconcavetot, dist);
1713  wmax_(Wconcavemax, dist);
1714  }else { /* MRGcoplanar */
1715  zinc_(Zcoplanar);
1716  wadd_(Wcoplanartot, dist);
1717  wmax_(Wcoplanarmax, dist);
1718  }
1719  }
1720 } /* merge_nonconvex */
1721 
1722 /*-<a href="qh-merge.htm#TOC"
1723  >-------------------------------</a><a name="mergecycle">-</a>
1724 
1725  qh_mergecycle( samecycle, newfacet )
1726  merge a cycle of facets starting at samecycle into a newfacet
1727  newfacet is a horizon facet with ->normal
1728  samecycle facets are simplicial from an apex
1729 
1730  returns:
1731  initializes vertex neighbors on first merge
1732  samecycle deleted (placed on qh.visible_list)
1733  newfacet at end of qh.facet_list
1734  deleted vertices on qh.del_vertices
1735 
1736  see:
1737  qh_mergefacet()
1738  called by qh_mergecycle_all() for multiple, same cycle facets
1739 
1740  design:
1741  make vertex neighbors if necessary
1742  make ridges for newfacet
1743  merge neighbor sets of samecycle into newfacet
1744  merge ridges of samecycle into newfacet
1745  merge vertex neighbors of samecycle into newfacet
1746  make apex of samecycle the apex of newfacet
1747  if newfacet wasn't a new facet
1748  add its vertices to qh.newvertex_list
1749  delete samecycle facets a make newfacet a newfacet
1750 */
1751 void qh_mergecycle(facetT *samecycle, facetT *newfacet) {
1752  int traceonce= False, tracerestore= 0;
1753  vertexT *apex;
1754 #ifndef qh_NOtrace
1755  facetT *same;
1756 #endif
1757 
1758  if (newfacet->tricoplanar) {
1759  if (!qh TRInormals) {
1760  qh_fprintf(qh ferr, 6224, "Qhull internal error (qh_mergecycle): does not work for tricoplanar facets. Use option 'Q11'\n");
1761  qh_errexit(qh_ERRqhull, newfacet, NULL);
1762  }
1763  newfacet->tricoplanar= False;
1764  newfacet->keepcentrum= False;
1765  }
1766  if (!qh VERTEXneighbors)
1767  qh_vertexneighbors();
1768  zzinc_(Ztotmerge);
1769  if (qh REPORTfreq2 && qh POSTmerging) {
1770  if (zzval_(Ztotmerge) > qh mergereport + qh REPORTfreq2)
1771  qh_tracemerging();
1772  }
1773 #ifndef qh_NOtrace
1774  if (qh TRACEmerge == zzval_(Ztotmerge))
1775  qhmem.IStracing= qh IStracing= qh TRACElevel;
1776  trace2((qh ferr, 2030, "qh_mergecycle: merge #%d for facets from cycle f%d into coplanar horizon f%d\n",
1777  zzval_(Ztotmerge), samecycle->id, newfacet->id));
1778  if (newfacet == qh tracefacet) {
1779  tracerestore= qh IStracing;
1780  qh IStracing= 4;
1781  qh_fprintf(qh ferr, 8068, "qh_mergecycle: ========= trace merge %d of samecycle %d into trace f%d, furthest is p%d\n",
1782  zzval_(Ztotmerge), samecycle->id, newfacet->id, qh furthest_id);
1783  traceonce= True;
1784  }
1785  if (qh IStracing >=4) {
1786  qh_fprintf(qh ferr, 8069, " same cycle:");
1787  FORALLsame_cycle_(samecycle)
1788  qh_fprintf(qh ferr, 8070, " f%d", same->id);
1789  qh_fprintf(qh ferr, 8071, "\n");
1790  }
1791  if (qh IStracing >=4)
1792  qh_errprint("MERGING CYCLE", samecycle, newfacet, NULL, NULL);
1793 #endif /* !qh_NOtrace */
1794  apex= SETfirstt_(samecycle->vertices, vertexT);
1795  qh_makeridges(newfacet);
1796  qh_mergecycle_neighbors(samecycle, newfacet);
1797  qh_mergecycle_ridges(samecycle, newfacet);
1798  qh_mergecycle_vneighbors(samecycle, newfacet);
1799  if (SETfirstt_(newfacet->vertices, vertexT) != apex)
1800  qh_setaddnth(&newfacet->vertices, 0, apex); /* apex has last id */
1801  if (!newfacet->newfacet)
1802  qh_newvertices(newfacet->vertices);
1803  qh_mergecycle_facets(samecycle, newfacet);
1804  qh_tracemerge(samecycle, newfacet);
1805  /* check for degen_redundant_neighbors after qh_forcedmerges() */
1806  if (traceonce) {
1807  qh_fprintf(qh ferr, 8072, "qh_mergecycle: end of trace facet\n");
1808  qh IStracing= tracerestore;
1809  }
1810 } /* mergecycle */
1811 
1812 /*-<a href="qh-merge.htm#TOC"
1813  >-------------------------------</a><a name="mergecycle_all">-</a>
1814 
1815  qh_mergecycle_all( facetlist, wasmerge )
1816  merge all samecycles of coplanar facets into horizon
1817  don't merge facets with ->mergeridge (these already have ->normal)
1818  all facets are simplicial from apex
1819  all facet->cycledone == False
1820 
1821  returns:
1822  all newfacets merged into coplanar horizon facets
1823  deleted vertices on qh.del_vertices
1824  sets wasmerge if any merge
1825 
1826  see:
1827  calls qh_mergecycle for multiple, same cycle facets
1828 
1829  design:
1830  for each facet on facetlist
1831  skip facets with duplicate ridges and normals
1832  check that facet is in a samecycle (->mergehorizon)
1833  if facet only member of samecycle
1834  sets vertex->delridge for all vertices except apex
1835  merge facet into horizon
1836  else
1837  mark all facets in samecycle
1838  remove facets with duplicate ridges from samecycle
1839  merge samecycle into horizon (deletes facets from facetlist)
1840 */
1841 void qh_mergecycle_all(facetT *facetlist, boolT *wasmerge) {
1842  facetT *facet, *same, *prev, *horizon;
1843  facetT *samecycle= NULL, *nextfacet, *nextsame;
1844  vertexT *apex, *vertex, **vertexp;
1845  int cycles=0, total=0, facets, nummerge;
1846 
1847  trace2((qh ferr, 2031, "qh_mergecycle_all: begin\n"));
1848  for (facet= facetlist; facet && (nextfacet= facet->next); facet= nextfacet) {
1849  if (facet->normal)
1850  continue;
1851  if (!facet->mergehorizon) {
1852  qh_fprintf(qh ferr, 6225, "Qhull internal error (qh_mergecycle_all): f%d without normal\n", facet->id);
1853  qh_errexit(qh_ERRqhull, facet, NULL);
1854  }
1855  horizon= SETfirstt_(facet->neighbors, facetT);
1856  if (facet->f.samecycle == facet) {
1857  zinc_(Zonehorizon);
1858  /* merge distance done in qh_findhorizon */
1859  apex= SETfirstt_(facet->vertices, vertexT);
1860  FOREACHvertex_(facet->vertices) {
1861  if (vertex != apex)
1862  vertex->delridge= True;
1863  }
1864  horizon->f.newcycle= NULL;
1865  qh_mergefacet(facet, horizon, NULL, NULL, qh_MERGEapex);
1866  }else {
1867  samecycle= facet;
1868  facets= 0;
1869  prev= facet;
1870  for (same= facet->f.samecycle; same; /* FORALLsame_cycle_(facet) */
1871  same= (same == facet ? NULL :nextsame)) { /* ends at facet */
1872  nextsame= same->f.samecycle;
1873  if (same->cycledone || same->visible)
1874  qh_infiniteloop(same);
1875  same->cycledone= True;
1876  if (same->normal) {
1877  prev->f.samecycle= same->f.samecycle; /* unlink ->mergeridge */
1878  same->f.samecycle= NULL;
1879  }else {
1880  prev= same;
1881  facets++;
1882  }
1883  }
1884  while (nextfacet && nextfacet->cycledone) /* will delete samecycle */
1885  nextfacet= nextfacet->next;
1886  horizon->f.newcycle= NULL;
1887  qh_mergecycle(samecycle, horizon);
1888  nummerge= horizon->nummerge + facets;
1889  if (nummerge > qh_MAXnummerge)
1890  horizon->nummerge= qh_MAXnummerge;
1891  else
1892  horizon->nummerge= (short unsigned int)nummerge;
1893  zzinc_(Zcyclehorizon);
1894  total += facets;
1895  zzadd_(Zcyclefacettot, facets);
1896  zmax_(Zcyclefacetmax, facets);
1897  }
1898  cycles++;
1899  }
1900  if (cycles)
1901  *wasmerge= True;
1902  trace1((qh ferr, 1013, "qh_mergecycle_all: merged %d same cycles or facets into coplanar horizons\n", cycles));
1903 } /* mergecycle_all */
1904 
1905 /*-<a href="qh-merge.htm#TOC"
1906  >-------------------------------</a><a name="mergecycle_facets">-</a>
1907 
1908  qh_mergecycle_facets( samecycle, newfacet )
1909  finish merge of samecycle into newfacet
1910 
1911  returns:
1912  samecycle prepended to visible_list for later deletion and partitioning
1913  each facet->f.replace == newfacet
1914 
1915  newfacet moved to end of qh.facet_list
1916  makes newfacet a newfacet (get's facet1->id if it was old)
1917  sets newfacet->newmerge
1918  clears newfacet->center (unless merging into a large facet)
1919  clears newfacet->tested and ridge->tested for facet1
1920 
1921  adds neighboring facets to facet_mergeset if redundant or degenerate
1922 
1923  design:
1924  make newfacet a new facet and set its flags
1925  move samecycle facets to qh.visible_list for later deletion
1926  unless newfacet is large
1927  remove its centrum
1928 */
1929 void qh_mergecycle_facets(facetT *samecycle, facetT *newfacet) {
1930  facetT *same, *next;
1931 
1932  trace4((qh ferr, 4030, "qh_mergecycle_facets: make newfacet new and samecycle deleted\n"));
1933  qh_removefacet(newfacet); /* append as a newfacet to end of qh facet_list */
1934  qh_appendfacet(newfacet);
1935  newfacet->newfacet= True;
1936  newfacet->simplicial= False;
1937  newfacet->newmerge= True;
1938 
1939  for (same= samecycle->f.samecycle; same; same= (same == samecycle ? NULL : next)) {
1940  next= same->f.samecycle; /* reused by willdelete */
1941  qh_willdelete(same, newfacet);
1942  }
1943  if (newfacet->center
1944  && qh_setsize(newfacet->vertices) <= qh hull_dim + qh_MAXnewcentrum) {
1945  qh_memfree(newfacet->center, qh normal_size);
1946  newfacet->center= NULL;
1947  }
1948  trace3((qh ferr, 3004, "qh_mergecycle_facets: merged facets from cycle f%d into f%d\n",
1949  samecycle->id, newfacet->id));
1950 } /* mergecycle_facets */
1951 
1952 /*-<a href="qh-merge.htm#TOC"
1953  >-------------------------------</a><a name="mergecycle_neighbors">-</a>
1954 
1955  qh_mergecycle_neighbors( samecycle, newfacet )
1956  add neighbors for samecycle facets to newfacet
1957 
1958  returns:
1959  newfacet with updated neighbors and vice-versa
1960  newfacet has ridges
1961  all neighbors of newfacet marked with qh.visit_id
1962  samecycle facets marked with qh.visit_id-1
1963  ridges updated for simplicial neighbors of samecycle with a ridge
1964 
1965  notes:
1966  assumes newfacet not in samecycle
1967  usually, samecycle facets are new, simplicial facets without internal ridges
1968  not so if horizon facet is coplanar to two different samecycles
1969 
1970  see:
1971  qh_mergeneighbors()
1972 
1973  design:
1974  check samecycle
1975  delete neighbors from newfacet that are also in samecycle
1976  for each neighbor of a facet in samecycle
1977  if neighbor is simplicial
1978  if first visit
1979  move the neighbor relation to newfacet
1980  update facet links for its ridges
1981  else
1982  make ridges for neighbor
1983  remove samecycle reference
1984  else
1985  update neighbor sets
1986 */
1987 void qh_mergecycle_neighbors(facetT *samecycle, facetT *newfacet) {
1988  facetT *same, *neighbor, **neighborp;
1989  int delneighbors= 0, newneighbors= 0;
1990  unsigned int samevisitid;
1991  ridgeT *ridge, **ridgep;
1992 
1993  samevisitid= ++qh visit_id;
1994  FORALLsame_cycle_(samecycle) {
1995  if (same->visitid == samevisitid || same->visible)
1996  qh_infiniteloop(samecycle);
1997  same->visitid= samevisitid;
1998  }
1999  newfacet->visitid= ++qh visit_id;
2000  trace4((qh ferr, 4031, "qh_mergecycle_neighbors: delete shared neighbors from newfacet\n"));
2001  FOREACHneighbor_(newfacet) {
2002  if (neighbor->visitid == samevisitid) {
2003  SETref_(neighbor)= NULL; /* samecycle neighbors deleted */
2004  delneighbors++;
2005  }else
2006  neighbor->visitid= qh visit_id;
2007  }
2008  qh_setcompact(newfacet->neighbors);
2009 
2010  trace4((qh ferr, 4032, "qh_mergecycle_neighbors: update neighbors\n"));
2011  FORALLsame_cycle_(samecycle) {
2012  FOREACHneighbor_(same) {
2013  if (neighbor->visitid == samevisitid)
2014  continue;
2015  if (neighbor->simplicial) {
2016  if (neighbor->visitid != qh visit_id) {
2017  qh_setappend(&newfacet->neighbors, neighbor);
2018  qh_setreplace(neighbor->neighbors, same, newfacet);
2019  newneighbors++;
2020  neighbor->visitid= qh visit_id;
2021  FOREACHridge_(neighbor->ridges) { /* update ridge in case of qh_makeridges */
2022  if (ridge->top == same) {
2023  ridge->top= newfacet;
2024  break;
2025  }else if (ridge->bottom == same) {
2026  ridge->bottom= newfacet;
2027  break;
2028  }
2029  }
2030  }else {
2031  qh_makeridges(neighbor);
2032  qh_setdel(neighbor->neighbors, same);
2033  /* same can't be horizon facet for neighbor */
2034  }
2035  }else { /* non-simplicial neighbor */
2036  qh_setdel(neighbor->neighbors, same);
2037  if (neighbor->visitid != qh visit_id) {
2038  qh_setappend(&neighbor->neighbors, newfacet);
2039  qh_setappend(&newfacet->neighbors, neighbor);
2040  neighbor->visitid= qh visit_id;
2041  newneighbors++;
2042  }
2043  }
2044  }
2045  }
2046  trace2((qh ferr, 2032, "qh_mergecycle_neighbors: deleted %d neighbors and added %d\n",
2047  delneighbors, newneighbors));
2048 } /* mergecycle_neighbors */
2049 
2050 /*-<a href="qh-merge.htm#TOC"
2051  >-------------------------------</a><a name="mergecycle_ridges">-</a>
2052 
2053  qh_mergecycle_ridges( samecycle, newfacet )
2054  add ridges/neighbors for facets in samecycle to newfacet
2055  all new/old neighbors of newfacet marked with qh.visit_id
2056  facets in samecycle marked with qh.visit_id-1
2057  newfacet marked with qh.visit_id
2058 
2059  returns:
2060  newfacet has merged ridges
2061 
2062  notes:
2063  ridge already updated for simplicial neighbors of samecycle with a ridge
2064 
2065  see:
2066  qh_mergeridges()
2067  qh_makeridges()
2068 
2069  design:
2070  remove ridges between newfacet and samecycle
2071  for each facet in samecycle
2072  for each ridge in facet
2073  update facet pointers in ridge
2074  skip ridges processed in qh_mergecycle_neighors
2075  free ridges between newfacet and samecycle
2076  free ridges between facets of samecycle (on 2nd visit)
2077  append remaining ridges to newfacet
2078  if simpilicial facet
2079  for each neighbor of facet
2080  if simplicial facet
2081  and not samecycle facet or newfacet
2082  make ridge between neighbor and newfacet
2083 */
2084 void qh_mergecycle_ridges(facetT *samecycle, facetT *newfacet) {
2085  facetT *same, *neighbor= NULL;
2086  int numold=0, numnew=0;
2087  int neighbor_i, neighbor_n;
2088  unsigned int samevisitid;
2089  ridgeT *ridge, **ridgep;
2090  boolT toporient;
2091  void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
2092 
2093  trace4((qh ferr, 4033, "qh_mergecycle_ridges: delete shared ridges from newfacet\n"));
2094  samevisitid= qh visit_id -1;
2095  FOREACHridge_(newfacet->ridges) {
2096  neighbor= otherfacet_(ridge, newfacet);
2097  if (neighbor->visitid == samevisitid)
2098  SETref_(ridge)= NULL; /* ridge free'd below */
2099  }
2100  qh_setcompact(newfacet->ridges);
2101 
2102  trace4((qh ferr, 4034, "qh_mergecycle_ridges: add ridges to newfacet\n"));
2103  FORALLsame_cycle_(samecycle) {
2104  FOREACHridge_(same->ridges) {
2105  if (ridge->top == same) {
2106  ridge->top= newfacet;
2107  neighbor= ridge->bottom;
2108  }else if (ridge->bottom == same) {
2109  ridge->bottom= newfacet;
2110  neighbor= ridge->top;
2111  }else if (ridge->top == newfacet || ridge->bottom == newfacet) {
2112  qh_setappend(&newfacet->ridges, ridge);
2113  numold++; /* already set by qh_mergecycle_neighbors */
2114  continue;
2115  }else {
2116  qh_fprintf(qh ferr, 6098, "qhull internal error (qh_mergecycle_ridges): bad ridge r%d\n", ridge->id);
2117  qh_errexit(qh_ERRqhull, NULL, ridge);
2118  }
2119  if (neighbor == newfacet) {
2120  qh_setfree(&(ridge->vertices));
2121  qh_memfree_(ridge, (int)sizeof(ridgeT), freelistp);
2122  numold++;
2123  }else if (neighbor->visitid == samevisitid) {
2124  qh_setdel(neighbor->ridges, ridge);
2125  qh_setfree(&(ridge->vertices));
2126  qh_memfree_(ridge, (int)sizeof(ridgeT), freelistp);
2127  numold++;
2128  }else {
2129  qh_setappend(&newfacet->ridges, ridge);
2130  numold++;
2131  }
2132  }
2133  if (same->ridges)
2134  qh_settruncate(same->ridges, 0);
2135  if (!same->simplicial)
2136  continue;
2137  FOREACHneighbor_i_(same) { /* note: !newfact->simplicial */
2138  if (neighbor->visitid != samevisitid && neighbor->simplicial) {
2139  ridge= qh_newridge();
2140  ridge->vertices= qh_setnew_delnthsorted(same->vertices, qh hull_dim,
2141  neighbor_i, 0);
2142  toporient= same->toporient ^ (neighbor_i & 0x1);
2143  if (toporient) {
2144  ridge->top= newfacet;
2145  ridge->bottom= neighbor;
2146  }else {
2147  ridge->top= neighbor;
2148  ridge->bottom= newfacet;
2149  }
2150  qh_setappend(&(newfacet->ridges), ridge);
2151  qh_setappend(&(neighbor->ridges), ridge);
2152  numnew++;
2153  }
2154  }
2155  }
2156 
2157  trace2((qh ferr, 2033, "qh_mergecycle_ridges: found %d old ridges and %d new ones\n",
2158  numold, numnew));
2159 } /* mergecycle_ridges */
2160 
2161 /*-<a href="qh-merge.htm#TOC"
2162  >-------------------------------</a><a name="mergecycle_vneighbors">-</a>
2163 
2164  qh_mergecycle_vneighbors( samecycle, newfacet )
2165  create vertex neighbors for newfacet from vertices of facets in samecycle
2166  samecycle marked with visitid == qh.visit_id - 1
2167 
2168  returns:
2169  newfacet vertices with updated neighbors
2170  marks newfacet with qh.visit_id-1
2171  deletes vertices that are merged away
2172  sets delridge on all vertices (faster here than in mergecycle_ridges)
2173 
2174  see:
2175  qh_mergevertex_neighbors()
2176 
2177  design:
2178  for each vertex of samecycle facet
2179  set vertex->delridge
2180  delete samecycle facets from vertex neighbors
2181  append newfacet to vertex neighbors
2182  if vertex only in newfacet
2183  delete it from newfacet
2184  add it to qh.del_vertices for later deletion
2185 */
2186 void qh_mergecycle_vneighbors(facetT *samecycle, facetT *newfacet) {
2187  facetT *neighbor, **neighborp;
2188  unsigned int mergeid;
2189  vertexT *vertex, **vertexp, *apex;
2190  setT *vertices;
2191 
2192  trace4((qh ferr, 4035, "qh_mergecycle_vneighbors: update vertex neighbors for newfacet\n"));
2193  mergeid= qh visit_id - 1;
2194  newfacet->visitid= mergeid;
2195  vertices= qh_basevertices(samecycle); /* temp */
2196  apex= SETfirstt_(samecycle->vertices, vertexT);
2197  qh_setappend(&vertices, apex);
2198  FOREACHvertex_(vertices) {
2199  vertex->delridge= True;
2200  FOREACHneighbor_(vertex) {
2201  if (neighbor->visitid == mergeid)
2202  SETref_(neighbor)= NULL;
2203  }
2204  qh_setcompact(vertex->neighbors);
2205  qh_setappend(&vertex->neighbors, newfacet);
2206  if (!SETsecond_(vertex->neighbors)) {
2207  zinc_(Zcyclevertex);
2208  trace2((qh ferr, 2034, "qh_mergecycle_vneighbors: deleted v%d when merging cycle f%d into f%d\n",
2209  vertex->id, samecycle->id, newfacet->id));
2210  qh_setdelsorted(newfacet->vertices, vertex);
2211  vertex->deleted= True;
2212  qh_setappend(&qh del_vertices, vertex);
2213  }
2214  }
2215  qh_settempfree(&vertices);
2216  trace3((qh ferr, 3005, "qh_mergecycle_vneighbors: merged vertices from cycle f%d into f%d\n",
2217  samecycle->id, newfacet->id));
2218 } /* mergecycle_vneighbors */
2219 
2220 /*-<a href="qh-merge.htm#TOC"
2221  >-------------------------------</a><a name="mergefacet">-</a>
2222 
2223  qh_mergefacet( facet1, facet2, mindist, maxdist, mergeapex )
2224  merges facet1 into facet2
2225  mergeapex==qh_MERGEapex if merging new facet into coplanar horizon
2226 
2227  returns:
2228  qh.max_outside and qh.min_vertex updated
2229  initializes vertex neighbors on first merge
2230 
2231  returns:
2232  facet2 contains facet1's vertices, neighbors, and ridges
2233  facet2 moved to end of qh.facet_list
2234  makes facet2 a newfacet
2235  sets facet2->newmerge set
2236  clears facet2->center (unless merging into a large facet)
2237  clears facet2->tested and ridge->tested for facet1
2238 
2239  facet1 prepended to visible_list for later deletion and partitioning
2240  facet1->f.replace == facet2
2241 
2242  adds neighboring facets to facet_mergeset if redundant or degenerate
2243 
2244  notes:
2245  mindist/maxdist may be NULL (only if both NULL)
2246  traces merge if fmax_(maxdist,-mindist) > TRACEdist
2247 
2248  see:
2249  qh_mergecycle()
2250 
2251  design:
2252  trace merge and check for degenerate simplex
2253  make ridges for both facets
2254  update qh.max_outside, qh.max_vertex, qh.min_vertex
2255  update facet2->maxoutside and keepcentrum
2256  update facet2->nummerge
2257  update tested flags for facet2
2258  if facet1 is simplicial
2259  merge facet1 into facet2
2260  else
2261  merge facet1's neighbors into facet2
2262  merge facet1's ridges into facet2
2263  merge facet1's vertices into facet2
2264  merge facet1's vertex neighbors into facet2
2265  add facet2's vertices to qh.new_vertexlist
2266  unless qh_MERGEapex
2267  test facet2 for degenerate or redundant neighbors
2268  move facet1 to qh.visible_list for later deletion
2269  move facet2 to end of qh.newfacet_list
2270 */
2271 void qh_mergefacet(facetT *facet1, facetT *facet2, realT *mindist, realT *maxdist, boolT mergeapex) {
2272  boolT traceonce= False;
2273  vertexT *vertex, **vertexp;
2274  int tracerestore=0, nummerge;
2275 
2276  if (facet1->tricoplanar || facet2->tricoplanar) {
2277  if (!qh TRInormals) {
2278  qh_fprintf(qh ferr, 6226, "Qhull internal error (qh_mergefacet): does not work for tricoplanar facets. Use option 'Q11'\n");
2279  qh_errexit2(qh_ERRqhull, facet1, facet2);
2280  }
2281  if (facet2->tricoplanar) {
2282  facet2->tricoplanar= False;
2283  facet2->keepcentrum= False;
2284  }
2285  }
2286  zzinc_(Ztotmerge);
2287  if (qh REPORTfreq2 && qh POSTmerging) {
2288  if (zzval_(Ztotmerge) > qh mergereport + qh REPORTfreq2)
2289  qh_tracemerging();
2290  }
2291 #ifndef qh_NOtrace
2292  if (qh build_cnt >= qh RERUN) {
2293  if (mindist && (-*mindist > qh TRACEdist || *maxdist > qh TRACEdist)) {
2294  tracerestore= 0;
2295  qh IStracing= qh TRACElevel;
2296  traceonce= True;
2297  qh_fprintf(qh ferr, 8075, "qh_mergefacet: ========= trace wide merge #%d(%2.2g) for f%d into f%d, last point was p%d\n", zzval_(Ztotmerge),
2298  fmax_(-*mindist, *maxdist), facet1->id, facet2->id, qh furthest_id);
2299  }else if (facet1 == qh tracefacet || facet2 == qh tracefacet) {
2300  tracerestore= qh IStracing;
2301  qh IStracing= 4;
2302  traceonce= True;
2303  qh_fprintf(qh ferr, 8076, "qh_mergefacet: ========= trace merge #%d involving f%d, furthest is p%d\n",
2304  zzval_(Ztotmerge), qh tracefacet_id, qh furthest_id);
2305  }
2306  }
2307  if (qh IStracing >= 2) {
2308  realT mergemin= -2;
2309  realT mergemax= -2;
2310 
2311  if (mindist) {
2312  mergemin= *mindist;
2313  mergemax= *maxdist;
2314  }
2315  qh_fprintf(qh ferr, 8077, "qh_mergefacet: #%d merge f%d into f%d, mindist= %2.2g, maxdist= %2.2g\n",
2316  zzval_(Ztotmerge), facet1->id, facet2->id, mergemin, mergemax);
2317  }
2318 #endif /* !qh_NOtrace */
2319  if (facet1 == facet2 || facet1->visible || facet2->visible) {
2320  qh_fprintf(qh ferr, 6099, "qhull internal error (qh_mergefacet): either f%d and f%d are the same or one is a visible facet\n",
2321  facet1->id, facet2->id);
2322  qh_errexit2(qh_ERRqhull, facet1, facet2);
2323  }
2324  if (qh num_facets - qh num_visible <= qh hull_dim + 1) {
2325  qh_fprintf(qh ferr, 6227, "\n\
2326 qhull precision error: Only %d facets remain. Can not merge another\n\
2327 pair. The input is too degenerate or the convexity constraints are\n\
2328 too strong.\n", qh hull_dim+1);
2329  if (qh hull_dim >= 5 && !qh MERGEexact)
2330  qh_fprintf(qh ferr, 8079, "Option 'Qx' may avoid this problem.\n");
2331  qh_errexit(qh_ERRprec, NULL, NULL);
2332  }
2333  if (!qh VERTEXneighbors)
2334  qh_vertexneighbors();
2335  qh_makeridges(facet1);
2336  qh_makeridges(facet2);
2337  if (qh IStracing >=4)
2338  qh_errprint("MERGING", facet1, facet2, NULL, NULL);
2339  if (mindist) {
2340  maximize_(qh max_outside, *maxdist);
2341  maximize_(qh max_vertex, *maxdist);
2342 #if qh_MAXoutside
2343  maximize_(facet2->maxoutside, *maxdist);
2344 #endif
2345  minimize_(qh min_vertex, *mindist);
2346  if (!facet2->keepcentrum
2347  && (*maxdist > qh WIDEfacet || *mindist < -qh WIDEfacet)) {
2348  facet2->keepcentrum= True;
2349  zinc_(Zwidefacet);
2350  }
2351  }
2352  nummerge= facet1->nummerge + facet2->nummerge + 1;
2353  if (nummerge >= qh_MAXnummerge)
2354  facet2->nummerge= qh_MAXnummerge;
2355  else
2356  facet2->nummerge= (short unsigned int)nummerge;
2357  facet2->newmerge= True;
2358  facet2->dupridge= False;
2359  qh_updatetested(facet1, facet2);
2360  if (qh hull_dim > 2 && qh_setsize(facet1->vertices) == qh hull_dim)
2361  qh_mergesimplex(facet1, facet2, mergeapex);
2362  else {
2363  qh vertex_visit++;
2364  FOREACHvertex_(facet2->vertices)
2365  vertex->visitid= qh vertex_visit;
2366  if (qh hull_dim == 2)
2367  qh_mergefacet2d(facet1, facet2);
2368  else {
2369  qh_mergeneighbors(facet1, facet2);
2370  qh_mergevertices(facet1->vertices, &facet2->vertices);
2371  }
2372  qh_mergeridges(facet1, facet2);
2373  qh_mergevertex_neighbors(facet1, facet2);
2374  if (!facet2->newfacet)
2375  qh_newvertices(facet2->vertices);
2376  }
2377  if (!mergeapex)
2378  qh_degen_redundant_neighbors(facet2, facet1);
2379  if (facet2->coplanar || !facet2->newfacet) {
2380  zinc_(Zmergeintohorizon);
2381  }else if (!facet1->newfacet && facet2->newfacet) {
2382  zinc_(Zmergehorizon);
2383  }else {
2384  zinc_(Zmergenew);
2385  }
2386  qh_willdelete(facet1, facet2);
2387  qh_removefacet(facet2); /* append as a newfacet to end of qh facet_list */
2388  qh_appendfacet(facet2);
2389  facet2->newfacet= True;
2390  facet2->tested= False;
2391  qh_tracemerge(facet1, facet2);
2392  if (traceonce) {
2393  qh_fprintf(qh ferr, 8080, "qh_mergefacet: end of wide tracing\n");
2394  qh IStracing= tracerestore;
2395  }
2396 } /* mergefacet */
2397 
2398 
2399 /*-<a href="qh-merge.htm#TOC"
2400  >-------------------------------</a><a name="mergefacet2d">-</a>
2401 
2402  qh_mergefacet2d( facet1, facet2 )
2403  in 2d, merges neighbors and vertices of facet1 into facet2
2404 
2405  returns:
2406  build ridges for neighbors if necessary
2407  facet2 looks like a simplicial facet except for centrum, ridges
2408  neighbors are opposite the corresponding vertex
2409  maintains orientation of facet2
2410 
2411  notes:
2412  qh_mergefacet() retains non-simplicial structures
2413  they are not needed in 2d, but later routines may use them
2414  preserves qh.vertex_visit for qh_mergevertex_neighbors()
2415 
2416  design:
2417  get vertices and neighbors
2418  determine new vertices and neighbors
2419  set new vertices and neighbors and adjust orientation
2420  make ridges for new neighbor if needed
2421 */
2422 void qh_mergefacet2d(facetT *facet1, facetT *facet2) {
2423  vertexT *vertex1A, *vertex1B, *vertex2A, *vertex2B, *vertexA, *vertexB;
2424  facetT *neighbor1A, *neighbor1B, *neighbor2A, *neighbor2B, *neighborA, *neighborB;
2425 
2426  vertex1A= SETfirstt_(facet1->vertices, vertexT);
2427  vertex1B= SETsecondt_(facet1->vertices, vertexT);
2428  vertex2A= SETfirstt_(facet2->vertices, vertexT);
2429  vertex2B= SETsecondt_(facet2->vertices, vertexT);
2430  neighbor1A= SETfirstt_(facet1->neighbors, facetT);
2431  neighbor1B= SETsecondt_(facet1->neighbors, facetT);
2432  neighbor2A= SETfirstt_(facet2->neighbors, facetT);
2433  neighbor2B= SETsecondt_(facet2->neighbors, facetT);
2434  if (vertex1A == vertex2A) {
2435  vertexA= vertex1B;
2436  vertexB= vertex2B;
2437  neighborA= neighbor2A;
2438  neighborB= neighbor1A;
2439  }else if (vertex1A == vertex2B) {
2440  vertexA= vertex1B;
2441  vertexB= vertex2A;
2442  neighborA= neighbor2B;
2443  neighborB= neighbor1A;
2444  }else if (vertex1B == vertex2A) {
2445  vertexA= vertex1A;
2446  vertexB= vertex2B;
2447  neighborA= neighbor2A;
2448  neighborB= neighbor1B;
2449  }else { /* 1B == 2B */
2450  vertexA= vertex1A;
2451  vertexB= vertex2A;
2452  neighborA= neighbor2B;
2453  neighborB= neighbor1B;
2454  }
2455  /* vertexB always from facet2, neighborB always from facet1 */
2456  if (vertexA->id > vertexB->id) {
2457  SETfirst_(facet2->vertices)= vertexA;
2458  SETsecond_(facet2->vertices)= vertexB;
2459  if (vertexB == vertex2A)
2460  facet2->toporient= !facet2->toporient;
2461  SETfirst_(facet2->neighbors)= neighborA;
2462  SETsecond_(facet2->neighbors)= neighborB;
2463  }else {
2464  SETfirst_(facet2->vertices)= vertexB;
2465  SETsecond_(facet2->vertices)= vertexA;
2466  if (vertexB == vertex2B)
2467  facet2->toporient= !facet2->toporient;
2468  SETfirst_(facet2->neighbors)= neighborB;
2469  SETsecond_(facet2->neighbors)= neighborA;
2470  }
2471  qh_makeridges(neighborB);
2472  qh_setreplace(neighborB->neighbors, facet1, facet2);
2473  trace4((qh ferr, 4036, "qh_mergefacet2d: merged v%d and neighbor f%d of f%d into f%d\n",
2474  vertexA->id, neighborB->id, facet1->id, facet2->id));
2475 } /* mergefacet2d */
2476 
2477 
2478 /*-<a href="qh-merge.htm#TOC"
2479  >-------------------------------</a><a name="mergeneighbors">-</a>
2480 
2481  qh_mergeneighbors( facet1, facet2 )
2482  merges the neighbors of facet1 into facet2
2483 
2484  see:
2485  qh_mergecycle_neighbors()
2486 
2487  design:
2488  for each neighbor of facet1
2489  if neighbor is also a neighbor of facet2
2490  if neighbor is simpilicial
2491  make ridges for later deletion as a degenerate facet
2492  update its neighbor set
2493  else
2494  move the neighbor relation to facet2
2495  remove the neighbor relation for facet1 and facet2
2496 */
2497 void qh_mergeneighbors(facetT *facet1, facetT *facet2) {
2498  facetT *neighbor, **neighborp;
2499 
2500  trace4((qh ferr, 4037, "qh_mergeneighbors: merge neighbors of f%d and f%d\n",
2501  facet1->id, facet2->id));
2502  qh visit_id++;
2503  FOREACHneighbor_(facet2) {
2504  neighbor->visitid= qh visit_id;
2505  }
2506  FOREACHneighbor_(facet1) {
2507  if (neighbor->visitid == qh visit_id) {
2508  if (neighbor->simplicial) /* is degen, needs ridges */
2509  qh_makeridges(neighbor);
2510  if (SETfirstt_(neighbor->neighbors, facetT) != facet1) /*keep newfacet->horizon*/
2511  qh_setdel(neighbor->neighbors, facet1);
2512  else {
2513  qh_setdel(neighbor->neighbors, facet2);
2514  qh_setreplace(neighbor->neighbors, facet1, facet2);
2515  }
2516  }else if (neighbor != facet2) {
2517  qh_setappend(&(facet2->neighbors), neighbor);
2518  qh_setreplace(neighbor->neighbors, facet1, facet2);
2519  }
2520  }
2521  qh_setdel(facet1->neighbors, facet2); /* here for makeridges */
2522  qh_setdel(facet2->neighbors, facet1);
2523 } /* mergeneighbors */
2524 
2525 
2526 /*-<a href="qh-merge.htm#TOC"
2527  >-------------------------------</a><a name="mergeridges">-</a>
2528 
2529  qh_mergeridges( facet1, facet2 )
2530  merges the ridge set of facet1 into facet2
2531 
2532  returns:
2533  may delete all ridges for a vertex
2534  sets vertex->delridge on deleted ridges
2535 
2536  see:
2537  qh_mergecycle_ridges()
2538 
2539  design:
2540  delete ridges between facet1 and facet2
2541  mark (delridge) vertices on these ridges for later testing
2542  for each remaining ridge
2543  rename facet1 to facet2
2544 */
2545 void qh_mergeridges(facetT *facet1, facetT *facet2) {
2546  ridgeT *ridge, **ridgep;
2547  vertexT *vertex, **vertexp;
2548 
2549  trace4((qh ferr, 4038, "qh_mergeridges: merge ridges of f%d and f%d\n",
2550  facet1->id, facet2->id));
2551  FOREACHridge_(facet2->ridges) {
2552  if ((ridge->top == facet1) || (ridge->bottom == facet1)) {
2553  FOREACHvertex_(ridge->vertices)
2554  vertex->delridge= True;
2555  qh_delridge(ridge); /* expensive in high-d, could rebuild */
2556  ridgep--; /*repeat*/
2557  }
2558  }
2559  FOREACHridge_(facet1->ridges) {
2560  if (ridge->top == facet1)
2561  ridge->top= facet2;
2562  else
2563  ridge->bottom= facet2;
2564  qh_setappend(&(facet2->ridges), ridge);
2565  }
2566 } /* mergeridges */
2567 
2568 
2569 /*-<a href="qh-merge.htm#TOC"
2570  >-------------------------------</a><a name="mergesimplex">-</a>
2571 
2572  qh_mergesimplex( facet1, facet2, mergeapex )
2573  merge simplicial facet1 into facet2
2574  mergeapex==qh_MERGEapex if merging samecycle into horizon facet
2575  vertex id is latest (most recently created)
2576  facet1 may be contained in facet2
2577  ridges exist for both facets
2578 
2579  returns:
2580  facet2 with updated vertices, ridges, neighbors
2581  updated neighbors for facet1's vertices
2582  facet1 not deleted
2583  sets vertex->delridge on deleted ridges
2584 
2585  notes:
2586  special case code since this is the most common merge
2587  called from qh_mergefacet()
2588 
2589  design:
2590  if qh_MERGEapex
2591  add vertices of facet2 to qh.new_vertexlist if necessary
2592  add apex to facet2
2593  else
2594  for each ridge between facet1 and facet2
2595  set vertex->delridge
2596  determine the apex for facet1 (i.e., vertex to be merged)
2597  unless apex already in facet2
2598  insert apex into vertices for facet2
2599  add vertices of facet2 to qh.new_vertexlist if necessary
2600  add apex to qh.new_vertexlist if necessary
2601  for each vertex of facet1
2602  if apex
2603  rename facet1 to facet2 in its vertex neighbors
2604  else
2605  delete facet1 from vertex neighors
2606  if only in facet2
2607  add vertex to qh.del_vertices for later deletion
2608  for each ridge of facet1
2609  delete ridges between facet1 and facet2
2610  append other ridges to facet2 after renaming facet to facet2
2611 */
2612 void qh_mergesimplex(facetT *facet1, facetT *facet2, boolT mergeapex) {
2613  vertexT *vertex, **vertexp, *apex;
2614  ridgeT *ridge, **ridgep;
2615  boolT issubset= False;
2616  int vertex_i= -1, vertex_n;
2617  facetT *neighbor, **neighborp, *otherfacet;
2618 
2619  if (mergeapex) {
2620  if (!facet2->newfacet)
2621  qh_newvertices(facet2->vertices); /* apex is new */
2622  apex= SETfirstt_(facet1->vertices, vertexT);
2623  if (SETfirstt_(facet2->vertices, vertexT) != apex)
2624  qh_setaddnth(&facet2->vertices, 0, apex); /* apex has last id */
2625  else
2626  issubset= True;
2627  }else {
2628  zinc_(Zmergesimplex);
2629  FOREACHvertex_(facet1->vertices)
2630  vertex->seen= False;
2631  FOREACHridge_(facet1->ridges) {
2632  if (otherfacet_(ridge, facet1) == facet2) {
2633  FOREACHvertex_(ridge->vertices) {
2634  vertex->seen= True;
2635  vertex->delridge= True;
2636  }
2637  break;
2638  }
2639  }
2640  FOREACHvertex_(facet1->vertices) {
2641  if (!vertex->seen)
2642  break; /* must occur */
2643  }
2644  apex= vertex;
2645  trace4((qh ferr, 4039, "qh_mergesimplex: merge apex v%d of f%d into facet f%d\n",
2646  apex->id, facet1->id, facet2->id));
2647  FOREACHvertex_i_(facet2->vertices) {
2648  if (vertex->id < apex->id) {
2649  break;
2650  }else if (vertex->id == apex->id) {
2651  issubset= True;
2652  break;
2653  }
2654  }
2655  if (!issubset)
2656  qh_setaddnth(&facet2->vertices, vertex_i, apex);
2657  if (!facet2->newfacet)
2658  qh_newvertices(facet2->vertices);
2659  else if (!apex->newlist) {
2660  qh_removevertex(apex);
2661  qh_appendvertex(apex);
2662  }
2663  }
2664  trace4((qh ferr, 4040, "qh_mergesimplex: update vertex neighbors of f%d\n",
2665  facet1->id));
2666  FOREACHvertex_(facet1->vertices) {
2667  if (vertex == apex && !issubset)
2668  qh_setreplace(vertex->neighbors, facet1, facet2);
2669  else {
2670  qh_setdel(vertex->neighbors, facet1);
2671  if (!SETsecond_(vertex->neighbors))
2672  qh_mergevertex_del(vertex, facet1, facet2);
2673  }
2674  }
2675  trace4((qh ferr, 4041, "qh_mergesimplex: merge ridges and neighbors of f%d into f%d\n",
2676  facet1->id, facet2->id));
2677  qh visit_id++;
2678  FOREACHneighbor_(facet2)
2679  neighbor->visitid= qh visit_id;
2680  FOREACHridge_(facet1->ridges) {
2681  otherfacet= otherfacet_(ridge, facet1);
2682  if (otherfacet == facet2) {
2683  qh_setdel(facet2->ridges, ridge);
2684  qh_setfree(&(ridge->vertices));
2685  qh_memfree(ridge, (int)sizeof(ridgeT));
2686  qh_setdel(facet2->neighbors, facet1);
2687  }else {
2688  qh_setappend(&facet2->ridges, ridge);
2689  if (otherfacet->visitid != qh visit_id) {
2690  qh_setappend(&facet2->neighbors, otherfacet);
2691  qh_setreplace(otherfacet->neighbors, facet1, facet2);
2692  otherfacet->visitid= qh visit_id;
2693  }else {
2694  if (otherfacet->simplicial) /* is degen, needs ridges */
2695  qh_makeridges(otherfacet);
2696  if (SETfirstt_(otherfacet->neighbors, facetT) != facet1)
2697  qh_setdel(otherfacet->neighbors, facet1);
2698  else { /*keep newfacet->neighbors->horizon*/
2699  qh_setdel(otherfacet->neighbors, facet2);
2700  qh_setreplace(otherfacet->neighbors, facet1, facet2);
2701  }
2702  }
2703  if (ridge->top == facet1) /* wait until after qh_makeridges */
2704  ridge->top= facet2;
2705  else
2706  ridge->bottom= facet2;
2707  }
2708  }
2709  SETfirst_(facet1->ridges)= NULL; /* it will be deleted */
2710  trace3((qh ferr, 3006, "qh_mergesimplex: merged simplex f%d apex v%d into facet f%d\n",
2711  facet1->id, getid_(apex), facet2->id));
2712 } /* mergesimplex */
2713 
2714 /*-<a href="qh-merge.htm#TOC"
2715  >-------------------------------</a><a name="mergevertex_del">-</a>
2716 
2717  qh_mergevertex_del( vertex, facet1, facet2 )
2718  delete a vertex because of merging facet1 into facet2
2719 
2720  returns:
2721  deletes vertex from facet2
2722  adds vertex to qh.del_vertices for later deletion
2723 */
2724 void qh_mergevertex_del(vertexT *vertex, facetT *facet1, facetT *facet2) {
2725 
2726  zinc_(Zmergevertex);
2727  trace2((qh ferr, 2035, "qh_mergevertex_del: deleted v%d when merging f%d into f%d\n",
2728  vertex->id, facet1->id, facet2->id));
2729  qh_setdelsorted(facet2->vertices, vertex);
2730  vertex->deleted= True;
2731  qh_setappend(&qh del_vertices, vertex);
2732 } /* mergevertex_del */
2733 
2734 /*-<a href="qh-merge.htm#TOC"
2735  >-------------------------------</a><a name="mergevertex_neighbors">-</a>
2736 
2737  qh_mergevertex_neighbors( facet1, facet2 )
2738  merge the vertex neighbors of facet1 to facet2
2739 
2740  returns:
2741  if vertex is current qh.vertex_visit
2742  deletes facet1 from vertex->neighbors
2743  else
2744  renames facet1 to facet2 in vertex->neighbors
2745  deletes vertices if only one neighbor
2746 
2747  notes:
2748  assumes vertex neighbor sets are good
2749 */
2750 void qh_mergevertex_neighbors(facetT *facet1, facetT *facet2) {
2751  vertexT *vertex, **vertexp;
2752 
2753  trace4((qh ferr, 4042, "qh_mergevertex_neighbors: merge vertex neighbors of f%d and f%d\n",
2754  facet1->id, facet2->id));
2755  if (qh tracevertex) {
2756  qh_fprintf(qh ferr, 8081, "qh_mergevertex_neighbors: of f%d and f%d at furthest p%d f0= %p\n",
2757  facet1->id, facet2->id, qh furthest_id, qh tracevertex->neighbors->e[0].p);
2758  qh_errprint("TRACE", NULL, NULL, NULL, qh tracevertex);
2759  }
2760  FOREACHvertex_(facet1->vertices) {
2761  if (vertex->visitid != qh vertex_visit)
2762  qh_setreplace(vertex->neighbors, facet1, facet2);
2763  else {
2764  qh_setdel(vertex->neighbors, facet1);
2765  if (!SETsecond_(vertex->neighbors))
2766  qh_mergevertex_del(vertex, facet1, facet2);
2767  }
2768  }
2769  if (qh tracevertex)
2770  qh_errprint("TRACE", NULL, NULL, NULL, qh tracevertex);
2771 } /* mergevertex_neighbors */
2772 
2773 
2774 /*-<a href="qh-merge.htm#TOC"
2775  >-------------------------------</a><a name="mergevertices">-</a>
2776 
2777  qh_mergevertices( vertices1, vertices2 )
2778  merges the vertex set of facet1 into facet2
2779 
2780  returns:
2781  replaces vertices2 with merged set
2782  preserves vertex_visit for qh_mergevertex_neighbors
2783  updates qh.newvertex_list
2784 
2785  design:
2786  create a merged set of both vertices (in inverse id order)
2787 */
2788 void qh_mergevertices(setT *vertices1, setT **vertices2) {
2789  int newsize= qh_setsize(vertices1)+qh_setsize(*vertices2) - qh hull_dim + 1;
2790  setT *mergedvertices;
2791  vertexT *vertex, **vertexp, **vertex2= SETaddr_(*vertices2, vertexT);
2792 
2793  mergedvertices= qh_settemp(newsize);
2794  FOREACHvertex_(vertices1) {
2795  if (!*vertex2 || vertex->id > (*vertex2)->id)
2796  qh_setappend(&mergedvertices, vertex);
2797  else {
2798  while (*vertex2 && (*vertex2)->id > vertex->id)
2799  qh_setappend(&mergedvertices, *vertex2++);
2800  if (!*vertex2 || (*vertex2)->id < vertex->id)
2801  qh_setappend(&mergedvertices, vertex);
2802  else
2803  qh_setappend(&mergedvertices, *vertex2++);
2804  }
2805  }
2806  while (*vertex2)
2807  qh_setappend(&mergedvertices, *vertex2++);
2808  if (newsize < qh_setsize(mergedvertices)) {
2809  qh_fprintf(qh ferr, 6100, "qhull internal error (qh_mergevertices): facets did not share a ridge\n");
2810  qh_errexit(qh_ERRqhull, NULL, NULL);
2811  }
2812  qh_setfree(vertices2);
2813  *vertices2= mergedvertices;
2814  qh_settemppop();
2815 } /* mergevertices */
2816 
2817 
2818 /*-<a href="qh-merge.htm#TOC"
2819  >-------------------------------</a><a name="neighbor_intersections">-</a>
2820 
2821  qh_neighbor_intersections( vertex )
2822  return intersection of all vertices in vertex->neighbors except for vertex
2823 
2824  returns:
2825  returns temporary set of vertices
2826  does not include vertex
2827  NULL if a neighbor is simplicial
2828  NULL if empty set
2829 
2830  notes:
2831  used for renaming vertices
2832 
2833  design:
2834  initialize the intersection set with vertices of the first two neighbors
2835  delete vertex from the intersection
2836  for each remaining neighbor
2837  intersect its vertex set with the intersection set
2838  return NULL if empty
2839  return the intersection set
2840 */
2841 setT *qh_neighbor_intersections(vertexT *vertex) {
2842  facetT *neighbor, **neighborp, *neighborA, *neighborB;
2843  setT *intersect;
2844  int neighbor_i, neighbor_n;
2845 
2846  FOREACHneighbor_(vertex) {
2847  if (neighbor->simplicial)
2848  return NULL;
2849  }
2850  neighborA= SETfirstt_(vertex->neighbors, facetT);
2851  neighborB= SETsecondt_(vertex->neighbors, facetT);
2852  zinc_(Zintersectnum);
2853  if (!neighborA)
2854  return NULL;
2855  if (!neighborB)
2856  intersect= qh_setcopy(neighborA->vertices, 0);
2857  else
2858  intersect= qh_vertexintersect_new(neighborA->vertices, neighborB->vertices);
2859  qh_settemppush(intersect);
2860  qh_setdelsorted(intersect, vertex);
2861  FOREACHneighbor_i_(vertex) {
2862  if (neighbor_i >= 2) {
2863  zinc_(Zintersectnum);
2864  qh_vertexintersect(&intersect, neighbor->vertices);
2865  if (!SETfirst_(intersect)) {
2866  zinc_(Zintersectfail);
2867  qh_settempfree(&intersect);
2868  return NULL;
2869  }
2870  }
2871  }
2872  trace3((qh ferr, 3007, "qh_neighbor_intersections: %d vertices in neighbor intersection of v%d\n",
2873  qh_setsize(intersect), vertex->id));
2874  return intersect;
2875 } /* neighbor_intersections */
2876 
2877 /*-<a href="qh-merge.htm#TOC"
2878  >-------------------------------</a><a name="newvertices">-</a>
2879 
2880  qh_newvertices( vertices )
2881  add vertices to end of qh.vertex_list (marks as new vertices)
2882 
2883  returns:
2884  vertices on qh.newvertex_list
2885  vertex->newlist set
2886 */
2887 void qh_newvertices(setT *vertices) {
2888  vertexT *vertex, **vertexp;
2889 
2890  FOREACHvertex_(vertices) {
2891  if (!vertex->newlist) {
2892  qh_removevertex(vertex);
2893  qh_appendvertex(vertex);
2894  }
2895  }
2896 } /* newvertices */
2897 
2898 /*-<a href="qh-merge.htm#TOC"
2899  >-------------------------------</a><a name="reducevertices">-</a>
2900 
2901  qh_reducevertices()
2902  reduce extra vertices, shared vertices, and redundant vertices
2903  facet->newmerge is set if merged since last call
2904  if !qh.MERGEvertices, only removes extra vertices
2905 
2906  returns:
2907  True if also merged degen_redundant facets
2908  vertices are renamed if possible
2909  clears facet->newmerge and vertex->delridge
2910 
2911  notes:
2912  ignored if 2-d
2913 
2914  design:
2915  merge any degenerate or redundant facets
2916  for each newly merged facet
2917  remove extra vertices
2918  if qh.MERGEvertices
2919  for each newly merged facet
2920  for each vertex
2921  if vertex was on a deleted ridge
2922  rename vertex if it is shared
2923  remove delridge flag from new vertices
2924 */
2925 boolT qh_reducevertices(void) {
2926  int numshare=0, numrename= 0;
2927  boolT degenredun= False;
2928  facetT *newfacet;
2929  vertexT *vertex, **vertexp;
2930 
2931  if (qh hull_dim == 2)
2932  return False;
2933  if (qh_merge_degenredundant())
2934  degenredun= True;
2935  LABELrestart:
2936  FORALLnew_facets {
2937  if (newfacet->newmerge) {
2938  if (!qh MERGEvertices)
2939  newfacet->newmerge= False;
2940  qh_remove_extravertices(newfacet);
2941  }
2942  }
2943  if (!qh MERGEvertices)
2944  return False;
2945  FORALLnew_facets {
2946  if (newfacet->newmerge) {
2947  newfacet->newmerge= False;
2948  FOREACHvertex_(newfacet->vertices) {
2949  if (vertex->delridge) {
2950  if (qh_rename_sharedvertex(vertex, newfacet)) {
2951  numshare++;
2952  vertexp--; /* repeat since deleted vertex */
2953  }
2954  }
2955  }
2956  }
2957  }
2958  FORALLvertex_(qh newvertex_list) {
2959  if (vertex->delridge && !vertex->deleted) {
2960  vertex->delridge= False;
2961  if (qh hull_dim >= 4 && qh_redundant_vertex(vertex)) {
2962  numrename++;
2963  if (qh_merge_degenredundant()) {
2964  degenredun= True;
2965  goto LABELrestart;
2966  }
2967  }
2968  }
2969  }
2970  trace1((qh ferr, 1014, "qh_reducevertices: renamed %d shared vertices and %d redundant vertices. Degen? %d\n",
2971  numshare, numrename, degenredun));
2972  return degenredun;
2973 } /* reducevertices */
2974 
2975 /*-<a href="qh-merge.htm#TOC"
2976  >-------------------------------</a><a name="redundant_vertex">-</a>
2977 
2978  qh_redundant_vertex( vertex )
2979  detect and rename a redundant vertex
2980  vertices have full vertex->neighbors
2981 
2982  returns:
2983  returns true if find a redundant vertex
2984  deletes vertex(vertex->deleted)
2985 
2986  notes:
2987  only needed if vertex->delridge and hull_dim >= 4
2988  may add degenerate facets to qh.facet_mergeset
2989  doesn't change vertex->neighbors or create redundant facets
2990 
2991  design:
2992  intersect vertices of all facet neighbors of vertex
2993  determine ridges for these vertices
2994  if find a new vertex for vertex amoung these ridges and vertices
2995  rename vertex to the new vertex
2996 */
2997 vertexT *qh_redundant_vertex(vertexT *vertex) {
2998  vertexT *newvertex= NULL;
2999  setT *vertices, *ridges;
3000 
3001  trace3((qh ferr, 3008, "qh_redundant_vertex: check if v%d can be renamed\n", vertex->id));
3002  if ((vertices= qh_neighbor_intersections(vertex))) {
3003  ridges= qh_vertexridges(vertex);
3004  if ((newvertex= qh_find_newvertex(vertex, vertices, ridges)))
3005  qh_renamevertex(vertex, newvertex, ridges, NULL, NULL);
3006  qh_settempfree(&ridges);
3007  qh_settempfree(&vertices);
3008  }
3009  return newvertex;
3010 } /* redundant_vertex */
3011 
3012 /*-<a href="qh-merge.htm#TOC"
3013  >-------------------------------</a><a name="remove_extravertices">-</a>
3014 
3015  qh_remove_extravertices( facet )
3016  remove extra vertices from non-simplicial facets
3017 
3018  returns:
3019  returns True if it finds them
3020 
3021  design:
3022  for each vertex in facet
3023  if vertex not in a ridge (i.e., no longer used)
3024  delete vertex from facet
3025  delete facet from vertice's neighbors
3026  unless vertex in another facet
3027  add vertex to qh.del_vertices for later deletion
3028 */
3029 boolT qh_remove_extravertices(facetT *facet) {
3030  ridgeT *ridge, **ridgep;
3031  vertexT *vertex, **vertexp;
3032  boolT foundrem= False;
3033 
3034  trace4((qh ferr, 4043, "qh_remove_extravertices: test f%d for extra vertices\n",
3035  facet->id));
3036  FOREACHvertex_(facet->vertices)
3037  vertex->seen= False;
3038  FOREACHridge_(facet->ridges) {
3039  FOREACHvertex_(ridge->vertices)
3040  vertex->seen= True;
3041  }
3042  FOREACHvertex_(facet->vertices) {
3043  if (!vertex->seen) {
3044  foundrem= True;
3045  zinc_(Zremvertex);
3046  qh_setdelsorted(facet->vertices, vertex);
3047  qh_setdel(vertex->neighbors, facet);
3048  if (!qh_setsize(vertex->neighbors)) {
3049  vertex->deleted= True;
3050  qh_setappend(&qh del_vertices, vertex);
3051  zinc_(Zremvertexdel);
3052  trace2((qh ferr, 2036, "qh_remove_extravertices: v%d deleted because it's lost all ridges\n", vertex->id));
3053  }else
3054  trace3((qh ferr, 3009, "qh_remove_extravertices: v%d removed from f%d because it's lost all ridges\n", vertex->id, facet->id));
3055  vertexp--; /*repeat*/
3056  }
3057  }
3058  return foundrem;
3059 } /* remove_extravertices */
3060 
3061 /*-<a href="qh-merge.htm#TOC"
3062  >-------------------------------</a><a name="rename_sharedvertex">-</a>
3063 
3064  qh_rename_sharedvertex( vertex, facet )
3065  detect and rename if shared vertex in facet
3066  vertices have full ->neighbors
3067 
3068  returns:
3069  newvertex or NULL
3070  the vertex may still exist in other facets (i.e., a neighbor was pinched)
3071  does not change facet->neighbors
3072  updates vertex->neighbors
3073 
3074  notes:
3075  a shared vertex for a facet is only in ridges to one neighbor
3076  this may undo a pinched facet
3077 
3078  it does not catch pinches involving multiple facets. These appear
3079  to be difficult to detect, since an exhaustive search is too expensive.
3080 
3081  design:
3082  if vertex only has two neighbors
3083  determine the ridges that contain the vertex
3084  determine the vertices shared by both neighbors
3085  if can find a new vertex in this set
3086  rename the vertex to the new vertex
3087 */
3088 vertexT *qh_rename_sharedvertex(vertexT *vertex, facetT *facet) {
3089  facetT *neighbor, **neighborp, *neighborA= NULL;
3090  setT *vertices, *ridges;
3091  vertexT *newvertex;
3092 
3093  if (qh_setsize(vertex->neighbors) == 2) {
3094  neighborA= SETfirstt_(vertex->neighbors, facetT);
3095  if (neighborA == facet)
3096  neighborA= SETsecondt_(vertex->neighbors, facetT);
3097  }else if (qh hull_dim == 3)
3098  return NULL;
3099  else {
3100  qh visit_id++;
3101  FOREACHneighbor_(facet)
3102  neighbor->visitid= qh visit_id;
3103  FOREACHneighbor_(vertex) {
3104  if (neighbor->visitid == qh visit_id) {
3105  if (neighborA)
3106  return NULL;
3107  neighborA= neighbor;
3108  }
3109  }
3110  if (!neighborA) {
3111  qh_fprintf(qh ferr, 6101, "qhull internal error (qh_rename_sharedvertex): v%d's neighbors not in f%d\n",
3112  vertex->id, facet->id);
3113  qh_errprint("ERRONEOUS", facet, NULL, NULL, vertex);
3114  qh_errexit(qh_ERRqhull, NULL, NULL);
3115  }
3116  }
3117  /* the vertex is shared by facet and neighborA */
3118  ridges= qh_settemp(qh TEMPsize);
3119  neighborA->visitid= ++qh visit_id;
3120  qh_vertexridges_facet(vertex, facet, &ridges);
3121  trace2((qh ferr, 2037, "qh_rename_sharedvertex: p%d(v%d) is shared by f%d(%d ridges) and f%d\n",
3122  qh_pointid(vertex->point), vertex->id, facet->id, qh_setsize(ridges), neighborA->id));
3123  zinc_(Zintersectnum);
3124  vertices= qh_vertexintersect_new(facet->vertices, neighborA->vertices);
3125  qh_setdel(vertices, vertex);
3126  qh_settemppush(vertices);
3127  if ((newvertex= qh_find_newvertex(vertex, vertices, ridges)))
3128  qh_renamevertex(vertex, newvertex, ridges, facet, neighborA);
3129  qh_settempfree(&vertices);
3130  qh_settempfree(&ridges);
3131  return newvertex;
3132 } /* rename_sharedvertex */
3133 
3134 /*-<a href="qh-merge.htm#TOC"
3135  >-------------------------------</a><a name="renameridgevertex">-</a>
3136 
3137  qh_renameridgevertex( ridge, oldvertex, newvertex )
3138  renames oldvertex as newvertex in ridge
3139 
3140  returns:
3141 
3142  design:
3143  delete oldvertex from ridge
3144  if newvertex already in ridge
3145  copy ridge->noconvex to another ridge if possible
3146  delete the ridge
3147  else
3148  insert newvertex into the ridge
3149  adjust the ridge's orientation
3150 */
3151 void qh_renameridgevertex(ridgeT *ridge, vertexT *oldvertex, vertexT *newvertex) {
3152  int nth= 0, oldnth;
3153  facetT *temp;
3154  vertexT *vertex, **vertexp;
3155 
3156  oldnth= qh_setindex(ridge->vertices, oldvertex);
3157  qh_setdelnthsorted(ridge->vertices, oldnth);
3158  FOREACHvertex_(ridge->vertices) {
3159  if (vertex == newvertex) {
3160  zinc_(Zdelridge);
3161  if (ridge->nonconvex) /* only one ridge has nonconvex set */
3162  qh_copynonconvex(ridge);
3163  trace2((qh ferr, 2038, "qh_renameridgevertex: ridge r%d deleted. It contained both v%d and v%d\n",
3164  ridge->id, oldvertex->id, newvertex->id));
3165  qh_delridge(ridge);
3166  return;
3167  }
3168  if (vertex->id < newvertex->id)
3169  break;
3170  nth++;
3171  }
3172  qh_setaddnth(&ridge->vertices, nth, newvertex);
3173  if (abs(oldnth - nth)%2) {
3174  trace3((qh ferr, 3010, "qh_renameridgevertex: swapped the top and bottom of ridge r%d\n",
3175  ridge->id));
3176  temp= ridge->top;
3177  ridge->top= ridge->bottom;
3178  ridge->bottom= temp;
3179  }
3180 } /* renameridgevertex */
3181 
3182 
3183 /*-<a href="qh-merge.htm#TOC"
3184  >-------------------------------</a><a name="renamevertex">-</a>
3185 
3186  qh_renamevertex( oldvertex, newvertex, ridges, oldfacet, neighborA )
3187  renames oldvertex as newvertex in ridges
3188  gives oldfacet/neighborA if oldvertex is shared between two facets
3189 
3190  returns:
3191  oldvertex may still exist afterwards
3192 
3193 
3194  notes:
3195  can not change neighbors of newvertex (since it's a subset)
3196 
3197  design:
3198  for each ridge in ridges
3199  rename oldvertex to newvertex and delete degenerate ridges
3200  if oldfacet not defined
3201  for each neighbor of oldvertex
3202  delete oldvertex from neighbor's vertices
3203  remove extra vertices from neighbor
3204  add oldvertex to qh.del_vertices
3205  else if oldvertex only between oldfacet and neighborA
3206  delete oldvertex from oldfacet and neighborA
3207  add oldvertex to qh.del_vertices
3208  else oldvertex is in oldfacet and neighborA and other facets (i.e., pinched)
3209  delete oldvertex from oldfacet
3210  delete oldfacet from oldvertice's neighbors
3211  remove extra vertices (e.g., oldvertex) from neighborA
3212 */
3213 void qh_renamevertex(vertexT *oldvertex, vertexT *newvertex, setT *ridges, facetT *oldfacet, facetT *neighborA) {
3214  facetT *neighbor, **neighborp;
3215  ridgeT *ridge, **ridgep;
3216  boolT istrace= False;
3217 
3218  if (qh IStracing >= 2 || oldvertex->id == qh tracevertex_id ||
3219  newvertex->id == qh tracevertex_id)
3220  istrace= True;
3221  FOREACHridge_(ridges)
3222  qh_renameridgevertex(ridge, oldvertex, newvertex);
3223  if (!oldfacet) {
3224  zinc_(Zrenameall);
3225  if (istrace)
3226  qh_fprintf(qh ferr, 8082, "qh_renamevertex: renamed v%d to v%d in several facets\n",
3227  oldvertex->id, newvertex->id);
3228  FOREACHneighbor_(oldvertex) {
3229  qh_maydropneighbor(neighbor);
3230  qh_setdelsorted(neighbor->vertices, oldvertex);
3231  if (qh_remove_extravertices(neighbor))
3232  neighborp--; /* neighbor may be deleted */
3233  }
3234  if (!oldvertex->deleted) {
3235  oldvertex->deleted= True;
3236  qh_setappend(&qh del_vertices, oldvertex);
3237  }
3238  }else if (qh_setsize(oldvertex->neighbors) == 2) {
3239  zinc_(Zrenameshare);
3240  if (istrace)
3241  qh_fprintf(qh ferr, 8083, "qh_renamevertex: renamed v%d to v%d in oldfacet f%d\n",
3242  oldvertex->id, newvertex->id, oldfacet->id);
3243  FOREACHneighbor_(oldvertex)
3244  qh_setdelsorted(neighbor->vertices, oldvertex);
3245  oldvertex->deleted= True;
3246  qh_setappend(&qh del_vertices, oldvertex);
3247  }else {
3248  zinc_(Zrenamepinch);
3249  if (istrace || qh IStracing)
3250  qh_fprintf(qh ferr, 8084, "qh_renamevertex: renamed pinched v%d to v%d between f%d and f%d\n",
3251  oldvertex->id, newvertex->id, oldfacet->id, neighborA->id);
3252  qh_setdelsorted(oldfacet->vertices, oldvertex);
3253  qh_setdel(oldvertex->neighbors, oldfacet);
3254  qh_remove_extravertices(neighborA);
3255  }
3256 } /* renamevertex */
3257 
3258 
3259 /*-<a href="qh-merge.htm#TOC"
3260  >-------------------------------</a><a name="test_appendmerge">-</a>
3261 
3262  qh_test_appendmerge( facet, neighbor )
3263  tests facet/neighbor for convexity
3264  appends to mergeset if non-convex
3265  if pre-merging,
3266  nop if qh.SKIPconvex, or qh.MERGEexact and coplanar
3267 
3268  returns:
3269  true if appends facet/neighbor to mergeset
3270  sets facet->center as needed
3271  does not change facet->seen
3272 
3273  design:
3274  if qh.cos_max is defined
3275  if the angle between facet normals is too shallow
3276  append an angle-coplanar merge to qh.mergeset
3277  return True
3278  make facet's centrum if needed
3279  if facet's centrum is above the neighbor
3280  set isconcave
3281  else
3282  if facet's centrum is not below the neighbor
3283  set iscoplanar
3284  make neighbor's centrum if needed
3285  if neighbor's centrum is above the facet
3286  set isconcave
3287  else if neighbor's centrum is not below the facet
3288  set iscoplanar
3289  if isconcave or iscoplanar
3290  get angle if needed
3291  append concave or coplanar merge to qh.mergeset
3292 */
3293 boolT qh_test_appendmerge(facetT *facet, facetT *neighbor) {
3294  realT dist, dist2= -REALmax, angle= -REALmax;
3295  boolT isconcave= False, iscoplanar= False, okangle= False;
3296 
3297  if (qh SKIPconvex && !qh POSTmerging)
3298  return False;
3299  if ((!qh MERGEexact || qh POSTmerging) && qh cos_max < REALmax/2) {
3300  angle= qh_getangle(facet->normal, neighbor->normal);
3301  zinc_(Zangletests);
3302  if (angle > qh cos_max) {
3303  zinc_(Zcoplanarangle);
3304  qh_appendmergeset(facet, neighbor, MRGanglecoplanar, &angle);
3305  trace2((qh ferr, 2039, "qh_test_appendmerge: coplanar angle %4.4g between f%d and f%d\n",
3306  angle, facet->id, neighbor->id));
3307  return True;
3308  }else
3309  okangle= True;
3310  }
3311  if (!facet->center)
3312  facet->center= qh_getcentrum(facet);
3313  zzinc_(Zcentrumtests);
3314  qh_distplane(facet->center, neighbor, &dist);
3315  if (dist > qh centrum_radius)
3316  isconcave= True;
3317  else {
3318  if (dist > -qh centrum_radius)
3319  iscoplanar= True;
3320  if (!neighbor->center)
3321  neighbor->center= qh_getcentrum(neighbor);
3322  zzinc_(Zcentrumtests);
3323  qh_distplane(neighbor->center, facet, &dist2);
3324  if (dist2 > qh centrum_radius)
3325  isconcave= True;
3326  else if (!iscoplanar && dist2 > -qh centrum_radius)
3327  iscoplanar= True;
3328  }
3329  if (!isconcave && (!iscoplanar || (qh MERGEexact && !qh POSTmerging)))
3330  return False;
3331  if (!okangle && qh ANGLEmerge) {
3332  angle= qh_getangle(facet->normal, neighbor->normal);
3333  zinc_(Zangletests);
3334  }
3335  if (isconcave) {
3336  zinc_(Zconcaveridge);
3337  if (qh ANGLEmerge)
3338  angle += qh_ANGLEconcave + 0.5;
3339  qh_appendmergeset(facet, neighbor, MRGconcave, &angle);
3340  trace0((qh ferr, 18, "qh_test_appendmerge: concave f%d to f%d dist %4.4g and reverse dist %4.4g angle %4.4g during p%d\n",
3341  facet->id, neighbor->id, dist, dist2, angle, qh furthest_id));
3342  }else /* iscoplanar */ {
3343  zinc_(Zcoplanarcentrum);
3344  qh_appendmergeset(facet, neighbor, MRGcoplanar, &angle);
3345  trace2((qh ferr, 2040, "qh_test_appendmerge: coplanar f%d to f%d dist %4.4g, reverse dist %4.4g angle %4.4g\n",
3346  facet->id, neighbor->id, dist, dist2, angle));
3347  }
3348  return True;
3349 } /* test_appendmerge */
3350 
3351 /*-<a href="qh-merge.htm#TOC"
3352  >-------------------------------</a><a name="test_vneighbors">-</a>
3353 
3354  qh_test_vneighbors()
3355  test vertex neighbors for convexity
3356  tests all facets on qh.newfacet_list
3357 
3358  returns:
3359  true if non-convex vneighbors appended to qh.facet_mergeset
3360  initializes vertex neighbors if needed
3361 
3362  notes:
3363  assumes all facet neighbors have been tested
3364  this can be expensive
3365  this does not guarantee that a centrum is below all facets
3366  but it is unlikely
3367  uses qh.visit_id
3368 
3369  design:
3370  build vertex neighbors if necessary
3371  for all new facets
3372  for all vertices
3373  for each unvisited facet neighbor of the vertex
3374  test new facet and neighbor for convexity
3375 */
3376 boolT qh_test_vneighbors(void /* qh.newfacet_list */) {
3377  facetT *newfacet, *neighbor, **neighborp;
3378  vertexT *vertex, **vertexp;
3379  int nummerges= 0;
3380 
3381  trace1((qh ferr, 1015, "qh_test_vneighbors: testing vertex neighbors for convexity\n"));
3382  if (!qh VERTEXneighbors)
3383  qh_vertexneighbors();
3384  FORALLnew_facets
3385  newfacet->seen= False;
3386  FORALLnew_facets {
3387  newfacet->seen= True;
3388  newfacet->visitid= qh visit_id++;
3389  FOREACHneighbor_(newfacet)
3390  newfacet->visitid= qh visit_id;
3391  FOREACHvertex_(newfacet->vertices) {
3392  FOREACHneighbor_(vertex) {
3393  if (neighbor->seen || neighbor->visitid == qh visit_id)
3394  continue;
3395  if (qh_test_appendmerge(newfacet, neighbor))
3396  nummerges++;
3397  }
3398  }
3399  }
3400  zadd_(Ztestvneighbor, nummerges);
3401  trace1((qh ferr, 1016, "qh_test_vneighbors: found %d non-convex, vertex neighbors\n",
3402  nummerges));
3403  return (nummerges > 0);
3404 } /* test_vneighbors */
3405 
3406 /*-<a href="qh-merge.htm#TOC"
3407  >-------------------------------</a><a name="tracemerge">-</a>
3408 
3409  qh_tracemerge( facet1, facet2 )
3410  print trace message after merge
3411 */
3412 void qh_tracemerge(facetT *facet1, facetT *facet2) {
3413  boolT waserror= False;
3414 
3415 #ifndef qh_NOtrace
3416  if (qh IStracing >= 4)
3417  qh_errprint("MERGED", facet2, NULL, NULL, NULL);
3418  if (facet2 == qh tracefacet || (qh tracevertex && qh tracevertex->newlist)) {
3419  qh_fprintf(qh ferr, 8085, "qh_tracemerge: trace facet and vertex after merge of f%d and f%d, furthest p%d\n", facet1->id, facet2->id, qh furthest_id);
3420  if (facet2 != qh tracefacet)
3421  qh_errprint("TRACE", qh tracefacet,
3422  (qh tracevertex && qh tracevertex->neighbors) ?
3423  SETfirstt_(qh tracevertex->neighbors, facetT) : NULL,
3424  NULL, qh tracevertex);
3425  }
3426  if (qh tracevertex) {
3427  if (qh tracevertex->deleted)
3428  qh_fprintf(qh ferr, 8086, "qh_tracemerge: trace vertex deleted at furthest p%d\n",
3429  qh furthest_id);
3430  else
3431  qh_checkvertex(qh tracevertex);
3432  }
3433  if (qh tracefacet) {
3434  qh_checkfacet(qh tracefacet, True, &waserror);
3435  if (waserror)
3436  qh_errexit(qh_ERRqhull, qh tracefacet, NULL);
3437  }
3438 #endif /* !qh_NOtrace */
3439  if (qh CHECKfrequently || qh IStracing >= 4) { /* can't check polygon here */
3440  qh_checkfacet(facet2, True, &waserror);
3441  if (waserror)
3442  qh_errexit(qh_ERRqhull, NULL, NULL);
3443  }
3444 } /* tracemerge */
3445 
3446 /*-<a href="qh-merge.htm#TOC"
3447  >-------------------------------</a><a name="tracemerging">-</a>
3448 
3449  qh_tracemerging()
3450  print trace message during POSTmerging
3451 
3452  returns:
3453  updates qh.mergereport
3454 
3455  notes:
3456  called from qh_mergecycle() and qh_mergefacet()
3457 
3458  see:
3459  qh_buildtracing()
3460 */
3461 void qh_tracemerging(void) {
3462  realT cpu;
3463  int total;
3464  time_t timedata;
3465  struct tm *tp;
3466 
3467  qh mergereport= zzval_(Ztotmerge);
3468  time(&timedata);
3469  tp= localtime(&timedata);
3470  cpu= qh_CPUclock;
3471  cpu /= qh_SECticks;
3472  total= zzval_(Ztotmerge) - zzval_(Zcyclehorizon) + zzval_(Zcyclefacettot);
3473  qh_fprintf(qh ferr, 8087, "\n\
3474 At %d:%d:%d & %2.5g CPU secs, qhull has merged %d facets. The hull\n\
3475  contains %d facets and %d vertices.\n",
3476  tp->tm_hour, tp->tm_min, tp->tm_sec, cpu,
3477  total, qh num_facets - qh num_visible,
3478  qh num_vertices-qh_setsize(qh del_vertices));
3479 } /* tracemerging */
3480 
3481 /*-<a href="qh-merge.htm#TOC"
3482  >-------------------------------</a><a name="updatetested">-</a>
3483 
3484  qh_updatetested( facet1, facet2 )
3485  clear facet2->tested and facet1->ridge->tested for merge
3486 
3487  returns:
3488  deletes facet2->center unless it's already large
3489  if so, clears facet2->ridge->tested
3490 
3491  design:
3492  clear facet2->tested
3493  clear ridge->tested for facet1's ridges
3494  if facet2 has a centrum
3495  if facet2 is large
3496  set facet2->keepcentrum
3497  else if facet2 has 3 vertices due to many merges, or not large and post merging
3498  clear facet2->keepcentrum
3499  unless facet2->keepcentrum
3500  clear facet2->center to recompute centrum later
3501  clear ridge->tested for facet2's ridges
3502 */
3503 void qh_updatetested(facetT *facet1, facetT *facet2) {
3504  ridgeT *ridge, **ridgep;
3505  int size;
3506 
3507  facet2->tested= False;
3508  FOREACHridge_(facet1->ridges)
3509  ridge->tested= False;
3510  if (!facet2->center)
3511  return;
3512  size= qh_setsize(facet2->vertices);
3513  if (!facet2->keepcentrum) {
3514  if (size > qh hull_dim + qh_MAXnewcentrum) {
3515  facet2->keepcentrum= True;
3516  zinc_(Zwidevertices);
3517  }
3518  }else if (size <= qh hull_dim + qh_MAXnewcentrum) {
3519  /* center and keepcentrum was set */
3520  if (size == qh hull_dim || qh POSTmerging)
3521  facet2->keepcentrum= False; /* if many merges need to recompute centrum */
3522  }
3523  if (!facet2->keepcentrum) {
3524  qh_memfree(facet2->center, qh normal_size);
3525  facet2->center= NULL;
3526  FOREACHridge_(facet2->ridges)
3527  ridge->tested= False;
3528  }
3529 } /* updatetested */
3530 
3531 /*-<a href="qh-merge.htm#TOC"
3532  >-------------------------------</a><a name="vertexridges">-</a>
3533 
3534  qh_vertexridges( vertex )
3535  return temporary set of ridges adjacent to a vertex
3536  vertex->neighbors defined
3537 
3538  ntoes:
3539  uses qh.visit_id
3540  does not include implicit ridges for simplicial facets
3541 
3542  design:
3543  for each neighbor of vertex
3544  add ridges that include the vertex to ridges
3545 */
3546 setT *qh_vertexridges(vertexT *vertex) {
3547  facetT *neighbor, **neighborp;
3548  setT *ridges= qh_settemp(qh TEMPsize);
3549  int size;
3550 
3551  qh visit_id++;
3552  FOREACHneighbor_(vertex)
3553  neighbor->visitid= qh visit_id;
3554  FOREACHneighbor_(vertex) {
3555  if (*neighborp) /* no new ridges in last neighbor */
3556  qh_vertexridges_facet(vertex, neighbor, &ridges);
3557  }
3558  if (qh PRINTstatistics || qh IStracing) {
3559  size= qh_setsize(ridges);
3560  zinc_(Zvertexridge);
3561  zadd_(Zvertexridgetot, size);
3562  zmax_(Zvertexridgemax, size);
3563  trace3((qh ferr, 3011, "qh_vertexridges: found %d ridges for v%d\n",
3564  size, vertex->id));
3565  }
3566  return ridges;
3567 } /* vertexridges */
3568 
3569 /*-<a href="qh-merge.htm#TOC"
3570  >-------------------------------</a><a name="vertexridges_facet">-</a>
3571 
3572  qh_vertexridges_facet( vertex, facet, ridges )
3573  add adjacent ridges for vertex in facet
3574  neighbor->visitid==qh.visit_id if it hasn't been visited
3575 
3576  returns:
3577  ridges updated
3578  sets facet->visitid to qh.visit_id-1
3579 
3580  design:
3581  for each ridge of facet
3582  if ridge of visited neighbor (i.e., unprocessed)
3583  if vertex in ridge
3584  append ridge to vertex
3585  mark facet processed
3586 */
3587 void qh_vertexridges_facet(vertexT *vertex, facetT *facet, setT **ridges) {
3588  ridgeT *ridge, **ridgep;
3589  facetT *neighbor;
3590 
3591  FOREACHridge_(facet->ridges) {
3592  neighbor= otherfacet_(ridge, facet);
3593  if (neighbor->visitid == qh visit_id
3594  && qh_setin(ridge->vertices, vertex))
3595  qh_setappend(ridges, ridge);
3596  }
3597  facet->visitid= qh visit_id-1;
3598 } /* vertexridges_facet */
3599 
3600 /*-<a href="qh-merge.htm#TOC"
3601  >-------------------------------</a><a name="willdelete">-</a>
3602 
3603  qh_willdelete( facet, replace )
3604  moves facet to visible list
3605  sets facet->f.replace to replace (may be NULL)
3606 
3607  returns:
3608  bumps qh.num_visible
3609 */
3610 void qh_willdelete(facetT *facet, facetT *replace) {
3611 
3612  qh_removefacet(facet);
3613  qh_prependfacet(facet, &qh visible_list);
3614  qh num_visible++;
3615  facet->visible= True;
3616  facet->f.replace= replace;
3617 } /* willdelete */
3618 
3619 #else /* qh_NOmerge */
3620 void qh_premerge(vertexT *apex, realT maxcentrum, realT maxangle) {
3621 }
3622 void qh_postmerge(const char *reason, realT maxcentrum, realT maxangle,
3623  boolT vneighbors) {
3624 }
3625 boolT qh_checkzero(boolT testall) {
3626  }
3627 #endif /* qh_NOmerge */
3628 
SETref_
#define SETref_(elem)
Definition: qset.h:319
qh_renameridgevertex
void qh_renameridgevertex(ridgeT *ridge, vertexT *oldvertex, vertexT *newvertex)
Definition: merge.c:3151
Zintersectmax
@ Zintersectmax
Definition: stat.h:158
Zdelridge
@ Zdelridge
Definition: stat.h:99
facetT::tricoplanar
flagT tricoplanar
Definition: libqhull.h:314
FORALLnew_facets
#define FORALLnew_facets
Definition: poly.h:89
zzadd_
#define zzadd_(id, val)
Definition: stat.h:397
qh_setdelsorted
void * qh_setdelsorted(setT *set, void *oldelem)
Definition: qset.c:504
Zrenamepinch
@ Zrenamepinch
Definition: stat.h:229
qh_test_appendmerge
boolT qh_test_appendmerge(facetT *facet, facetT *neighbor)
Definition: merge.c:3293
Wcoplanarmax
@ Wcoplanarmax
Definition: stat.h:81
qh_hashridge_find
ridgeT * qh_hashridge_find(setT *hashtable, int hashsize, ridgeT *ridge, vertexT *vertex, vertexT *oldvertex, int *hashslot)
Definition: merge.c:1319
qh_BESTnonconvex
#define qh_BESTnonconvex
Definition: user.h:691
qh_getangle
realT qh_getangle(pointT *vect1, pointT *vect2)
Definition: geom.c:644
Zdegenvertex
@ Zdegenvertex
Definition: stat.h:97
qh_CPUclock
#define qh_CPUclock
Definition: user.h:211
Zintersectnum
@ Zintersectnum
Definition: stat.h:159
qhmem
qhmemT qhmem
Definition: mem.c:62
qh_degen_redundant_neighbors
void qh_degen_redundant_neighbors(facetT *facet, facetT *delfacet)
Definition: merge.c:703
ridgeT::vertices
setT * vertices
Definition: libqhull.h:372
FOREACHridge_
#define FOREACHridge_(ridges)
Definition: libqhull.h:936
Zdropneighbor
@ Zdropneighbor
Definition: stat.h:124
facetT::center
coordT * center
Definition: libqhull.h:286
qh_MAXnummerge
#define qh_MAXnummerge
Definition: libqhull.h:313
qh_checkconvex
void qh_checkconvex(facetT *facetlist, int fault)
Definition: poly2.c:475
FORALLfacet_
#define FORALLfacet_(facetlist)
Definition: poly.h:77
qh_MAXnewcentrum
#define qh_MAXnewcentrum
Definition: user.h:715
qh_redundant_vertex
vertexT * qh_redundant_vertex(vertexT *vertex)
Definition: merge.c:2997
qh_findbest_test
void qh_findbest_test(boolT testcentrum, facetT *facet, facetT *neighbor, facetT **bestfacet, realT *distp, realT *mindistp, realT *maxdistp)
Definition: merge.c:860
qh_removevertex
void qh_removevertex(vertexT *vertex)
Definition: poly.c:1115
mergeT
Definition: merge.h:90
facetT::neighbors
setT * neighbors
Definition: libqhull.h:299
qh_test_vneighbors
boolT qh_test_vneighbors(void)
Definition: merge.c:3376
qh_mergecycle_neighbors
void qh_mergecycle_neighbors(facetT *samecycle, facetT *newfacet)
Definition: merge.c:1987
Zmergesettot
@ Zmergesettot
Definition: stat.h:179
qh_basevertices
setT * qh_basevertices(facetT *samecycle)
Definition: merge.c:384
qh_infiniteloop
void qh_infiniteloop(facetT *facet)
Definition: poly2.c:1652
qh_ALL
#define qh_ALL
Definition: libqhull.h:180
Zfindfail
@ Zfindfail
Definition: stat.h:139
mergeT::facet2
facetT * facet2
Definition: merge.h:93
qh_setdelnthsorted
void * qh_setdelnthsorted(setT *set, int nth)
Definition: qset.c:465
qh_merge_degenredundant
int qh_merge_degenredundant(void)
Definition: merge.c:1584
qh_getdistance
realT qh_getdistance(facetT *facet, facetT *neighbor, realT *mindist, realT *maxdist)
Definition: geom.c:728
qh_SECticks
#define qh_SECticks
Definition: user.h:212
qh_updatetested
void qh_updatetested(facetT *facet1, facetT *facet2)
Definition: merge.c:3503
zzinc_
#define zzinc_(id)
Definition: stat.h:384
qh_premerge
void qh_premerge(vertexT *apex, realT maxcentrum, realT maxangle)
Definition: merge.c:56
qh_mergefacet
void qh_mergefacet(facetT *facet1, facetT *facet2, realT *mindist, realT *maxdist, boolT mergeapex)
Definition: merge.c:2271
MRGridge
@ MRGridge
Definition: merge.h:63
Zrenameshare
@ Zrenameshare
Definition: stat.h:230
facetT::mergeridge
flagT mergeridge
Definition: libqhull.h:337
qh_ANGLEdegen
#define qh_ANGLEdegen
Definition: merge.h:36
zzval_
#define zzval_(id)
Definition: stat.h:413
qh_tracemerge
void qh_tracemerge(facetT *facet1, facetT *facet2)
Definition: merge.c:3412
qh_delridge
void qh_delridge(ridgeT *ridge)
Definition: poly2.c:1126
facetT::newcycle
facetT * newcycle
Definition: libqhull.h:282
qh_mergeridges
void qh_mergeridges(facetT *facet1, facetT *facet2)
Definition: merge.c:2545
qh_getmergeset_initial
void qh_getmergeset_initial(facetT *facetlist)
Definition: merge.c:1224
qh_setdel
void * qh_setdel(setT *set, void *oldelem)
Definition: qset.c:344
qh_checkvertex
void qh_checkvertex(vertexT *vertex)
Definition: poly2.c:1001
qh_settemppush
void qh_settemppush(setT *set)
Definition: qset.c:1247
qh_setdelnth
void * qh_setdelnth(setT *set, int nth)
Definition: qset.c:424
mergeT::type
mergeType type
Definition: merge.h:94
qh_mark_dupridges
void qh_mark_dupridges(facetT *facetlist)
Definition: merge.c:1460
qh_mergecycle_all
void qh_mergecycle_all(facetT *facetlist, boolT *wasmerge)
Definition: merge.c:1841
qh_comparemerge
int qh_comparemerge(const void *p1, const void *p2)
Definition: merge.c:581
realT
#define realT
Definition: user.h:154
Wconcavetot
@ Wconcavetot
Definition: stat.h:77
vertexT::point
pointT * point
Definition: libqhull.h:399
qh_setlast
void * qh_setlast(setT *set)
Definition: qset.c:895
qh_setfree
void qh_setfree(setT **setp)
Definition: qset.c:716
Zcyclehorizon
@ Zcyclehorizon
Definition: stat.h:92
qh_ASvoronoi
@ qh_ASvoronoi
Definition: libqhull.h:144
Zacoplanar
@ Zacoplanar
Definition: stat.h:51
qh_newhashtable
int qh_newhashtable(int newsize)
Definition: poly2.c:2304
getid_
#define getid_(p)
Definition: libqhull.h:823
qh_DIMreduceBuild
#define qh_DIMreduceBuild
Definition: user.h:667
Zdropdegen
@ Zdropdegen
Definition: stat.h:123
qh_setcopy
setT * qh_setcopy(setT *set, int extra)
Definition: qset.c:310
facetT::visible
flagT visible
Definition: libqhull.h:321
SETsecondt_
#define SETsecondt_(set, type)
Definition: qset.h:388
Zremvertexdel
@ Zremvertexdel
Definition: stat.h:227
mergeT::angle
realT angle
Definition: merge.h:91
qh_errprint
void qh_errprint(const char *string, facetT *atfacet, facetT *otherfacet, ridgeT *atridge, vertexT *atvertex)
Definition: user.c:277
vertexT::visitid
unsigned visitid
Definition: libqhull.h:403
Zflipped
@ Zflipped
Definition: stat.h:131
qh_checkfacet
void qh_checkfacet(facetT *facet, boolT newmerge, boolT *waserrorp)
Definition: poly2.c:627
facetT::redundant
flagT redundant
Definition: libqhull.h:347
facetT::ridges
setT * ridges
Definition: libqhull.h:297
Zcyclefacetmax
@ Zcyclefacetmax
Definition: stat.h:90
qh_printlists
void qh_printlists(void)
Definition: poly2.c:2651
qh_find_newvertex
vertexT * qh_find_newvertex(vertexT *oldvertex, setT *vertices, setT *ridges)
Definition: merge.c:773
qh_vertexintersect_new
setT * qh_vertexintersect_new(setT *vertexsetA, setT *vertexsetB)
Definition: poly2.c:3135
qh_ANGLEconcave
#define qh_ANGLEconcave
Definition: merge.h:48
zadd_
#define zadd_(id, val)
Definition: stat.h:400
facetT::tested
flagT tested
Definition: libqhull.h:343
Zmergeintohorizon
@ Zmergeintohorizon
Definition: stat.h:177
facetT::flipped
flagT flipped
Definition: libqhull.h:327
Zmergeflipdup
@ Zmergeflipdup
Definition: stat.h:172
Zneighbor
@ Zneighbor
Definition: stat.h:189
trace3
#define trace3(args)
Definition: qhull_a.h:83
ridgeT::tested
flagT tested
Definition: libqhull.h:378
qh_removefacet
void qh_removefacet(facetT *facet)
Definition: poly.c:1084
Zintersectfail
@ Zintersectfail
Definition: stat.h:157
qh_checkconnect
void qh_checkconnect(void)
Definition: merge.c:425
zinc_
#define zinc_(id)
Definition: stat.h:386
facetT
Definition: libqhull.h:262
facetT::toporient
flagT toporient
Definition: libqhull.h:322
ridgeT::bottom
facetT * bottom
Definition: libqhull.h:375
SETelemt_
#define SETelemt_(set, n, type)
Definition: qset.h:342
Zcoplanarcentrum
@ Zcoplanarcentrum
Definition: stat.h:84
ridgeT::top
facetT * top
Definition: libqhull.h:374
fmax_
#define fmax_(a, b)
Definition: geom.h:35
Zcoplanarangle
@ Zcoplanarangle
Definition: stat.h:83
Wflippedtot
@ Wflippedtot
Definition: stat.h:133
Zvertexridgemax
@ Zvertexridgemax
Definition: stat.h:266
Wacoplanartot
@ Wacoplanartot
Definition: stat.h:53
qh_vertexridges
setT * qh_vertexridges(vertexT *vertex)
Definition: merge.c:3546
qh_remove_extravertices
boolT qh_remove_extravertices(facetT *facet)
Definition: merge.c:3029
qh_makeridges
void qh_makeridges(facetT *facet)
Definition: merge.c:1370
vertexT::deleted
flagT deleted
Definition: libqhull.h:407
qh_check_dupridge
void qh_check_dupridge(facetT *facet1, realT dist1, facetT *facet2, realT dist2)
Definition: poly2.c:150
qh_setappend
void qh_setappend(setT **setp, void *newelem)
Definition: qset.c:131
wadd_
#define wadd_(id, val)
Definition: stat.h:401
qh_BESTcentrum
#define qh_BESTcentrum
Definition: user.h:679
qh_mergevertex_del
void qh_mergevertex_del(vertexT *vertex, facetT *facet1, facetT *facet2)
Definition: merge.c:2724
facetT::seen
flagT seen
Definition: libqhull.h:325
qh_newridge
ridgeT * qh_newridge(void)
Definition: poly.c:1018
facetT::samecycle
facetT * samecycle
Definition: libqhull.h:280
qh_reducevertices
boolT qh_reducevertices(void)
Definition: merge.c:2925
ridgeT::id
unsigned id
Definition: libqhull.h:376
a
list a
boolT
#define boolT
Definition: libqhull.h:121
qh_flippedmerges
void qh_flippedmerges(facetT *facetlist, boolT *wasmerge)
Definition: merge.c:982
FOREACHneighbor_
#define FOREACHneighbor_(facet)
Definition: libqhull.h:908
Wacoplanarmax
@ Wacoplanarmax
Definition: stat.h:52
ridgeT::nonconvex
flagT nonconvex
Definition: libqhull.h:379
qh_ALGORITHMfault
#define qh_ALGORITHMfault
Definition: poly.h:27
MRGredundant
@ MRGredundant
Definition: merge.h:66
Zwidefacet
@ Zwidefacet
Definition: stat.h:276
FORALLsame_cycle_
#define FORALLsame_cycle_(newfacet)
Definition: poly.h:137
qh_setdellast
void * qh_setdellast(setT *set)
Definition: qset.c:384
qh_MERGEapex
#define qh_MERGEapex
Definition: merge.h:78
trace2
#define trace2(args)
Definition: qhull_a.h:82
Zmergeinitmax
@ Zmergeinitmax
Definition: stat.h:175
facetT::nummerge
unsigned nummerge
Definition: libqhull.h:312
Zwidevertices
@ Zwidevertices
Definition: stat.h:277
qh_settemp
setT * qh_settemp(int setsize)
Definition: qset.c:1146
Zconcave
@ Zconcave
Definition: stat.h:75
otherfacet_
#define otherfacet_(ridge, facet)
Definition: libqhull.h:813
wmax_
#define wmax_(id, val)
Definition: stat.h:432
Zdupridge
@ Zdupridge
Definition: stat.h:129
Zvertexridgetot
@ Zvertexridgetot
Definition: stat.h:265
qh_settruncate
void qh_settruncate(setT *set, int size)
Definition: qset.c:1275
qh_buildtracing
void qh_buildtracing(pointT *furthest, facetT *facet)
Definition: libqhull.c:435
Zcyclefacettot
@ Zcyclefacettot
Definition: stat.h:91
False
#define False
Definition: libqhull.h:128
Zdelfacetdup
@ Zdelfacetdup
Definition: stat.h:98
Zmergesetmax
@ Zmergesetmax
Definition: stat.h:180
setT
Definition: qset.h:83
trace1
#define trace1(args)
Definition: qhull_a.h:81
REALmax
#define REALmax
Definition: user.h:155
Wdegenmax
@ Wdegenmax
Definition: stat.h:95
mergeType
mergeType
Definition: merge.h:56
qh_MAXnewmerges
#define qh_MAXnewmerges
Definition: user.h:702
Zavoidold
@ Zavoidold
Definition: stat.h:62
qh_mergefacet2d
void qh_mergefacet2d(facetT *facet1, facetT *facet2)
Definition: merge.c:2422
facetT::replace
facetT * replace
Definition: libqhull.h:278
vertexT::delridge
flagT delridge
Definition: libqhull.h:406
Zpostfacets
@ Zpostfacets
Definition: stat.h:223
qh
#define qh
Definition: libqhull.h:457
qh_maydropneighbor
void qh_maydropneighbor(facetT *facet)
Definition: merge.c:1524
SETelem_
#define SETelem_(set, n)
Definition: qset.h:331
qh_setequal_except
int qh_setequal_except(setT *setA, void *skipelemA, setT *setB, void *skipelemB)
Definition: qset.c:629
qh_setequal
int qh_setequal(setT *setA, setT *setB)
Definition: qset.c:587
qh_errexit
void qh_errexit(int exitcode, facetT *facet, ridgeT *ridge)
Definition: user.c:213
MRGflip
@ MRGflip
Definition: merge.h:62
qh_setsize
int qh_setsize(setT *set)
Definition: qset.c:1111
facetT::newmerge
flagT newmerge
Definition: libqhull.h:345
ridgeT
Definition: libqhull.h:371
Zrenameall
@ Zrenameall
Definition: stat.h:228
trace0
#define trace0(args)
Definition: qhull_a.h:80
Zintersect
@ Zintersect
Definition: stat.h:156
MRGdegen
@ MRGdegen
Definition: merge.h:65
Zpremergetot
@ Zpremergetot
Definition: stat.h:224
Zdistzero
@ Zdistzero
Definition: stat.h:110
qh_MERGEridge
#define qh_MERGEridge
Definition: poly.h:57
SETfirst_
#define SETfirst_(set)
Definition: qset.h:362
MRGconcave
@ MRGconcave
Definition: merge.h:61
SETsecond_
#define SETsecond_(set)
Definition: qset.h:380
qh_postmerge
void qh_postmerge(const char *reason, realT maxcentrum, realT maxangle, boolT vneighbors)
Definition: merge.c:129
qh_rename_sharedvertex
vertexT * qh_rename_sharedvertex(vertexT *vertex, facetT *facet)
Definition: merge.c:3088
qhull_a.h
Zmergesimplex
@ Zmergesimplex
Definition: stat.h:182
Wconcavemax
@ Wconcavemax
Definition: stat.h:76
Zcoplanar
@ Zcoplanar
Definition: stat.h:80
facetT::next
facetT * next
Definition: libqhull.h:294
qh_mergecycle_ridges
void qh_mergecycle_ridges(facetT *samecycle, facetT *newfacet)
Definition: merge.c:2084
qh_settemppop
setT * qh_settemppop(void)
Definition: qset.c:1221
Zmergenew
@ Zmergenew
Definition: stat.h:178
FORALLvertices
#define FORALLvertices
Definition: libqhull.h:877
facetT::newfacet
flagT newfacet
Definition: libqhull.h:320
qh_mergevertex_neighbors
void qh_mergevertex_neighbors(facetT *facet1, facetT *facet2)
Definition: merge.c:2750
qh_errexit2
void qh_errexit2(int exitcode, facetT *facet, facetT *otherfacet)
Definition: libqhull.c:521
facetT::cycledone
flagT cycledone
Definition: libqhull.h:342
minimize_
#define minimize_(minval, val)
Definition: geom.h:59
qh_printsummary
void qh_printsummary(FILE *fp)
Definition: libqhull.c:1205
zmax_
#define zmax_(id, val)
Definition: stat.h:431
qh_pointid
int qh_pointid(pointT *point)
Definition: poly.c:1053
Wcoplanartot
@ Wcoplanartot
Definition: stat.h:82
facetT::simplicial
flagT simplicial
Definition: libqhull.h:324
SETaddr_
#define SETaddr_(set, type)
Definition: qset.h:396
qh_distplane
void qh_distplane(pointT *point, facetT *facet, realT *dist)
Definition: geom.c:36
octree.p1
tuple p1
Definition: octree.py:54
mergeT::facet1
facetT * facet1
Definition: merge.h:92
Zmergevertex
@ Zmergevertex
Definition: stat.h:183
trace4
#define trace4(args)
Definition: qhull_a.h:84
Zcentrumtests
@ Zcentrumtests
Definition: stat.h:72
qh_printallstatistics
void qh_printallstatistics(FILE *fp, const char *string)
Definition: stat.c:559
Zhashridgetest
@ Zhashridgetest
Definition: stat.h:153
qh_ERRprec
#define qh_ERRprec
Definition: libqhull.h:196
generate_distance_plot.b
float b
Definition: generate_distance_plot.py:7
Wduplicatetot
@ Wduplicatetot
Definition: stat.h:128
qh_memfree_
#define qh_memfree_(object, insize, freelistp)
Definition: mem.h:193
Zbestcentrum
@ Zbestcentrum
Definition: stat.h:66
FOREACHvertex_i_
#define FOREACHvertex_i_(vertices)
Definition: libqhull.h:1028
Zvertexridge
@ Zvertexridge
Definition: stat.h:264
Wavoidoldmax
@ Wavoidoldmax
Definition: stat.h:63
qh_hashridge
void qh_hashridge(setT *hashtable, int hashsize, ridgeT *ridge, vertexT *oldvertex)
Definition: merge.c:1276
Zmergehorizon
@ Zmergehorizon
Definition: stat.h:173
FOREACHmerge_
#define FOREACHmerge_(merges)
Definition: merge.h:112
qh_ERRqhull
#define qh_ERRqhull
Definition: libqhull.h:198
qh_setreplace
void qh_setreplace(setT *set, void *oldelem, void *newelem)
Definition: qset.c:1080
qh_appendfacet
void qh_appendfacet(facetT *facet)
Definition: poly.c:38
facetT::maxoutside
coordT maxoutside
Definition: libqhull.h:267
qh_getmergeset
void qh_getmergeset(facetT *facetlist)
Definition: merge.c:1151
MRGanglecoplanar
@ MRGanglecoplanar
Definition: merge.h:59
vertexT::seen
flagT seen
Definition: libqhull.h:404
qh_memalloc_
#define qh_memalloc_(insize, freelistp, object, type)
Definition: mem.h:164
SETfirstt_
#define SETfirstt_(set, type)
Definition: qset.h:371
x1
x1
qh_mergesimplex
void qh_mergesimplex(facetT *facet1, facetT *facet2, boolT mergeapex)
Definition: merge.c:2612
facetT::visitid
unsigned visitid
Definition: libqhull.h:309
Zangletests
@ Zangletests
Definition: stat.h:58
qh_neighbor_intersections
setT * qh_neighbor_intersections(vertexT *vertex)
Definition: merge.c:2841
qh_compareangle
int qh_compareangle(const void *p1, const void *p2)
Definition: merge.c:569
qh_willdelete
void qh_willdelete(facetT *facet, facetT *replace)
Definition: merge.c:3610
qh_settempfree
void qh_settempfree(setT **set)
Definition: qset.c:1174
qh_mergecycle_facets
void qh_mergecycle_facets(facetT *samecycle, facetT *newfacet)
Definition: merge.c:1929
facetT::degenerate
flagT degenerate
Definition: libqhull.h:346
vertexT
Definition: libqhull.h:396
qh_mergevertices
void qh_mergevertices(setT *vertices1, setT **vertices2)
Definition: merge.c:2788
vertexT::newlist
flagT newlist
Definition: libqhull.h:408
FOREACHvertex_
#define FOREACHvertex_(vertices)
Definition: libqhull.h:950
facetT::keepcentrum
flagT keepcentrum
Definition: libqhull.h:344
Zmergeinittot
@ Zmergeinittot
Definition: stat.h:174
facetT::normal
coordT * normal
Definition: libqhull.h:274
qh_findbestneighbor
facetT * qh_findbestneighbor(facetT *facet, realT *distp, realT *mindistp, realT *maxdistp)
Definition: merge.c:913
qh_merge_nonconvex
void qh_merge_nonconvex(facetT *facet1, facetT *facet2, mergeType mergetype)
Definition: merge.c:1673
qh_mergecycle
void qh_mergecycle(facetT *samecycle, facetT *newfacet)
Definition: merge.c:1751
Ztestvneighbor
@ Ztestvneighbor
Definition: stat.h:247
Wduplicatemax
@ Wduplicatemax
Definition: stat.h:127
MRGcoplanar
@ MRGcoplanar
Definition: merge.h:58
qh_renamevertex
void qh_renamevertex(vertexT *oldvertex, vertexT *newvertex, setT *ridges, facetT *oldfacet, facetT *neighborA)
Definition: merge.c:3213
Ztotmerge
@ Ztotmerge
Definition: stat.h:250
Zremvertex
@ Zremvertex
Definition: stat.h:226
facetT::dupridge
flagT dupridge
Definition: libqhull.h:336
qh_fprintf
void qh_fprintf(FILE *fp, int msgcode, const char *fmt,...)
Definition: userprintf.c:42
qh_setaddnth
void qh_setaddnth(setT **setp, int nth, void *newelem)
Definition: qset.c:61
Zmergesettot2
@ Zmergesettot2
Definition: stat.h:181
qhmemT::IStracing
int IStracing
Definition: mem.h:131
Zonehorizon
@ Zonehorizon
Definition: stat.h:211
Zhashridge
@ Zhashridge
Definition: stat.h:152
maximize_
#define maximize_(maxval, val)
Definition: geom.h:51
qh_setindex
int qh_setindex(setT *set, void *atelem)
Definition: qset.c:821
Zduplicate
@ Zduplicate
Definition: stat.h:126
qh_gethash
int qh_gethash(int hashsize, setT *set, int size, int firstindex, void *skipelem)
Definition: poly.c:405
qh_all_merges
void qh_all_merges(boolT othermerge, boolT vneighbors)
Definition: merge.c:215
Zmergeinittot2
@ Zmergeinittot2
Definition: stat.h:176
qh_vertexintersect
void qh_vertexintersect(setT **vertexsetA, setT *vertexsetB)
Definition: poly2.c:3117
qh_newvertices
void qh_newvertices(setT *vertices)
Definition: merge.c:2887
qh_degen_redundant_facet
void qh_degen_redundant_facet(facetT *facet)
Definition: merge.c:647
Zconcaveridge
@ Zconcaveridge
Definition: stat.h:79
facetT::id
unsigned id
Definition: libqhull.h:311
qh_BESTcentrum2
#define qh_BESTcentrum2
Definition: user.h:680
qh_comparevisit
int qh_comparevisit(const void *p1, const void *p2)
Definition: merge.c:593
Wflippedmax
@ Wflippedmax
Definition: stat.h:132
qh_prependfacet
void qh_prependfacet(facetT *facet, facetT **facetlist)
Definition: poly2.c:2574
vertexT::neighbors
setT * neighbors
Definition: libqhull.h:400
FORALLvertex_
#define FORALLvertex_(vertexlist)
Definition: poly.h:101
qh_appendmergeset
void qh_appendmergeset(facetT *facet, facetT *neighbor, mergeType mergetype, realT *angle)
Definition: merge.c:320
SETindex_
#define SETindex_(set, elem)
Definition: qset.h:308
qh_checkzero
boolT qh_checkzero(boolT testall)
Definition: merge.c:488
qh_tracemerging
void qh_tracemerging(void)
Definition: merge.c:3461
qh_copynonconvex
void qh_copynonconvex(ridgeT *atridge)
Definition: merge.c:613
qh_setnew_delnthsorted
setT * qh_setnew_delnthsorted(setT *set, int size, int nth, int prepend)
Definition: qset.c:967
qh_appendvertex
void qh_appendvertex(vertexT *vertex)
Definition: poly.c:72
qh_mergecycle_vneighbors
void qh_mergecycle_vneighbors(facetT *samecycle, facetT *newfacet)
Definition: merge.c:2186
qh_setin
int qh_setin(setT *set, void *setelem)
Definition: qset.c:795
qh_mergeneighbors
void qh_mergeneighbors(facetT *facet1, facetT *facet2)
Definition: merge.c:2497
Zbestdist
@ Zbestdist
Definition: stat.h:67
FOREACHneighbor_i_
#define FOREACHneighbor_i_(facet)
Definition: libqhull.h:983
qh_vertexridges_facet
void qh_vertexridges_facet(vertexT *vertex, facetT *facet, setT **ridges)
Definition: merge.c:3587
Wdegentot
@ Wdegentot
Definition: stat.h:96
qh_memfree
void qh_memfree(void *object, int insize)
Definition: mem.c:245
qh_setcompact
void qh_setcompact(setT *set)
Definition: qset.c:276
facetT::vertices
setT * vertices
Definition: libqhull.h:295
Wavoidoldtot
@ Wavoidoldtot
Definition: stat.h:64
facetT::mergeridge2
flagT mergeridge2
Definition: libqhull.h:339
vertexT::id
unsigned id
Definition: libqhull.h:402
qh_forcedmerges
void qh_forcedmerges(boolT *wasmerge)
Definition: merge.c:1056
Zdegen
@ Zdegen
Definition: stat.h:94
Zcyclevertex
@ Zcyclevertex
Definition: stat.h:93
qh_vertexneighbors
void qh_vertexneighbors(void)
Definition: poly2.c:3174
facetT::coplanar
flagT coplanar
Definition: libqhull.h:340
Zintersecttot
@ Zintersecttot
Definition: stat.h:160
qh_getcentrum
pointT * qh_getcentrum(facetT *facet)
Definition: geom.c:700
True
#define True
Definition: libqhull.h:129
facetT::f
union facetT::@20 f

hpp-fcl
Author(s):
autogenerated on Fri Feb 14 2025 03:45:51