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-2010 C.B. Barber.
24 $Id$$Change: 1164 $
25 $DateTime: 2010/01/07 21:52:00 $$Author$
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 */
qh_premerge(vertexT * apex,realT maxcentrum,realT maxangle)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 */
qh_postmerge(const char * reason,realT maxcentrum,realT maxangle,boolT vneighbors)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 */
qh_all_merges(boolT othermerge,boolT vneighbors)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 !qh_NOmem */
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 */
qh_appendmergeset(facetT * facet,facetT * neighbor,mergeType mergetype,realT * angle)320 void qh_appendmergeset(facetT *facet, facetT *neighbor, mergeType mergetype, realT *angle) {
321 mergeT *merge, *lastmerge;
322 void **freelistp; /* used !qh_NOmem */
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 */
qh_basevertices(facetT * samecycle)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 */
qh_checkconnect(void)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 */
qh_checkzero(boolT testall)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) {
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 */
qh_compareangle(const void * p1,const void * p2)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 */
qh_comparemerge(const void * p1,const void * p2)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 */
qh_comparevisit(const void * p1,const void * p2)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 */
qh_copynonconvex(ridgeT * atridge)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 */
qh_degen_redundant_facet(facetT * facet)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 */
qh_degen_redundant_neighbors(facetT * facet,facetT * delfacet)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 */
qh_find_newvertex(vertexT * oldvertex,setT * vertices,setT * ridges)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 */
qh_findbest_test(boolT testcentrum,facetT * facet,facetT * neighbor,facetT ** bestfacet,realT * distp,realT * mindistp,realT * maxdistp)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 avoids merging old into new
897 assumes ridge->nonconvex only set on one ridge between a pair of facets
898 could use an early out predicate but not worth it
899
900 design:
901 if a large facet
902 will test centrum
903 else
904 will test vertices
905 if a large facet
906 test nonconvex neighbors for best merge
907 else
908 test all neighbors for the best merge
909 if testing centrum
910 get distance information
911 */
qh_findbestneighbor(facetT * facet,realT * distp,realT * mindistp,realT * maxdistp)912 facetT *qh_findbestneighbor(facetT *facet, realT *distp, realT *mindistp, realT *maxdistp) {
913 facetT *neighbor, **neighborp, *bestfacet= NULL;
914 ridgeT *ridge, **ridgep;
915 boolT nonconvex= True, testcentrum= False;
916 int size= qh_setsize(facet->vertices);
917
918 *distp= REALmax;
919 if (size > qh_BESTcentrum2 * qh hull_dim + qh_BESTcentrum) {
920 testcentrum= True;
921 zinc_(Zbestcentrum);
922 if (!facet->center)
923 facet->center= qh_getcentrum(facet);
924 }
925 if (size > qh hull_dim + qh_BESTnonconvex) {
926 FOREACHridge_(facet->ridges) {
927 if (ridge->nonconvex) {
928 neighbor= otherfacet_(ridge, facet);
929 qh_findbest_test(testcentrum, facet, neighbor,
930 &bestfacet, distp, mindistp, maxdistp);
931 }
932 }
933 }
934 if (!bestfacet) {
935 nonconvex= False;
936 FOREACHneighbor_(facet)
937 qh_findbest_test(testcentrum, facet, neighbor,
938 &bestfacet, distp, mindistp, maxdistp);
939 }
940 if (!bestfacet) {
941 qh_fprintf(qh ferr, 6095, "qhull internal error (qh_findbestneighbor): no neighbors for f%d\n", facet->id);
942
943 qh_errexit(qh_ERRqhull, facet, NULL);
944 }
945 if (testcentrum)
946 qh_getdistance(facet, bestfacet, mindistp, maxdistp);
947 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",
948 bestfacet->id, facet->id, testcentrum, nonconvex, *distp, *mindistp, *maxdistp));
949 return(bestfacet);
950 } /* findbestneighbor */
951
952
953 /*-<a href="qh-merge.htm#TOC"
954 >-------------------------------</a><a name="flippedmerges">-</a>
955
956 qh_flippedmerges( facetlist, wasmerge )
957 merge flipped facets into best neighbor
958 assumes qh.facet_mergeset at top of temporary stack
959
960 returns:
961 no flipped facets on facetlist
962 sets wasmerge if merge occurred
963 degen/redundant merges passed through
964
965 notes:
966 othermerges not needed since qh.facet_mergeset is empty before & after
967 keep it in case of change
968
969 design:
970 append flipped facets to qh.facetmergeset
971 for each flipped merge
972 find best neighbor
973 merge facet into neighbor
974 merge degenerate and redundant facets
975 remove flipped merges from qh.facet_mergeset
976 */
qh_flippedmerges(facetT * facetlist,boolT * wasmerge)977 void qh_flippedmerges(facetT *facetlist, boolT *wasmerge) {
978 facetT *facet, *neighbor, *facet1;
979 realT dist, mindist, maxdist;
980 mergeT *merge, **mergep;
981 setT *othermerges;
982 int nummerge=0;
983
984 trace4((qh ferr, 4024, "qh_flippedmerges: begin\n"));
985 FORALLfacet_(facetlist) {
986 if (facet->flipped && !facet->visible)
987 qh_appendmergeset(facet, facet, MRGflip, NULL);
988 }
989 othermerges= qh_settemppop(); /* was facet_mergeset */
990 qh facet_mergeset= qh_settemp(qh TEMPsize);
991 qh_settemppush(othermerges);
992 FOREACHmerge_(othermerges) {
993 facet1= merge->facet1;
994 if (merge->type != MRGflip || facet1->visible)
995 continue;
996 if (qh TRACEmerge-1 == zzval_(Ztotmerge))
997 qhmem.IStracing= qh IStracing= qh TRACElevel;
998 neighbor= qh_findbestneighbor(facet1, &dist, &mindist, &maxdist);
999 trace0((qh ferr, 15, "qh_flippedmerges: merge flipped f%d into f%d dist %2.2g during p%d\n",
1000 facet1->id, neighbor->id, dist, qh furthest_id));
1001 qh_mergefacet(facet1, neighbor, &mindist, &maxdist, !qh_MERGEapex);
1002 nummerge++;
1003 if (qh PRINTstatistics) {
1004 zinc_(Zflipped);
1005 wadd_(Wflippedtot, dist);
1006 wmax_(Wflippedmax, dist);
1007 }
1008 qh_merge_degenredundant();
1009 }
1010 FOREACHmerge_(othermerges) {
1011 if (merge->facet1->visible || merge->facet2->visible)
1012 qh_memfree(merge, (int)sizeof(mergeT));
1013 else
1014 qh_setappend(&qh facet_mergeset, merge);
1015 }
1016 qh_settempfree(&othermerges);
1017 if (nummerge)
1018 *wasmerge= True;
1019 trace1((qh ferr, 1010, "qh_flippedmerges: merged %d flipped facets into a good neighbor\n", nummerge));
1020 } /* flippedmerges */
1021
1022
1023 /*-<a href="qh-merge.htm#TOC"
1024 >-------------------------------</a><a name="forcedmerges">-</a>
1025
1026 qh_forcedmerges( wasmerge )
1027 merge duplicated ridges
1028
1029 returns:
1030 removes all duplicate ridges on facet_mergeset
1031 wasmerge set if merge
1032 qh.facet_mergeset may include non-forced merges(none for now)
1033 qh.degen_mergeset includes degen/redun merges
1034
1035 notes:
1036 duplicate ridges occur when the horizon is pinched,
1037 i.e. a subridge occurs in more than two horizon ridges.
1038 could rename vertices that pinch the horizon
1039 assumes qh_merge_degenredundant() has not be called
1040 othermerges isn't needed since facet_mergeset is empty afterwards
1041 keep it in case of change
1042
1043 design:
1044 for each duplicate ridge
1045 find current facets by chasing f.replace links
1046 determine best direction for facet
1047 merge one facet into the other
1048 remove duplicate ridges from qh.facet_mergeset
1049 */
qh_forcedmerges(boolT * wasmerge)1050 void qh_forcedmerges(boolT *wasmerge) {
1051 facetT *facet1, *facet2;
1052 mergeT *merge, **mergep;
1053 realT dist1, dist2, mindist1, mindist2, maxdist1, maxdist2;
1054 setT *othermerges;
1055 int nummerge=0, numflip=0;
1056
1057 if (qh TRACEmerge-1 == zzval_(Ztotmerge))
1058 qhmem.IStracing= qh IStracing= qh TRACElevel;
1059 trace4((qh ferr, 4025, "qh_forcedmerges: begin\n"));
1060 othermerges= qh_settemppop(); /* was facet_mergeset */
1061 qh facet_mergeset= qh_settemp(qh TEMPsize);
1062 qh_settemppush(othermerges);
1063 FOREACHmerge_(othermerges) {
1064 if (merge->type != MRGridge)
1065 continue;
1066 facet1= merge->facet1;
1067 facet2= merge->facet2;
1068 while (facet1->visible) /* must exist, no qh_merge_degenredunant */
1069 facet1= facet1->f.replace; /* previously merged facet */
1070 while (facet2->visible)
1071 facet2= facet2->f.replace; /* previously merged facet */
1072 if (facet1 == facet2)
1073 continue;
1074 if (!qh_setin(facet2->neighbors, facet1)) {
1075 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",
1076 merge->facet1->id, merge->facet2->id, facet1->id, facet2->id);
1077 qh_errexit2 (qh_ERRqhull, facet1, facet2);
1078 }
1079 if (qh TRACEmerge-1 == zzval_(Ztotmerge))
1080 qhmem.IStracing= qh IStracing= qh TRACElevel;
1081 dist1= qh_getdistance(facet1, facet2, &mindist1, &maxdist1);
1082 dist2= qh_getdistance(facet2, facet1, &mindist2, &maxdist2);
1083 trace0((qh ferr, 16, "qh_forcedmerges: duplicate ridge between f%d and f%d, dist %2.2g and reverse dist %2.2g during p%d\n",
1084 facet1->id, facet2->id, dist1, dist2, qh furthest_id));
1085 if (dist1 < dist2)
1086 qh_mergefacet(facet1, facet2, &mindist1, &maxdist1, !qh_MERGEapex);
1087 else {
1088 qh_mergefacet(facet2, facet1, &mindist2, &maxdist2, !qh_MERGEapex);
1089 dist1= dist2;
1090 facet1= facet2;
1091 }
1092 if (facet1->flipped) {
1093 zinc_(Zmergeflipdup);
1094 numflip++;
1095 }else
1096 nummerge++;
1097 if (qh PRINTstatistics) {
1098 zinc_(Zduplicate);
1099 wadd_(Wduplicatetot, dist1);
1100 wmax_(Wduplicatemax, dist1);
1101 }
1102 }
1103 FOREACHmerge_(othermerges) {
1104 if (merge->type == MRGridge)
1105 qh_memfree(merge, (int)sizeof(mergeT));
1106 else
1107 qh_setappend(&qh facet_mergeset, merge);
1108 }
1109 qh_settempfree(&othermerges);
1110 if (nummerge)
1111 *wasmerge= True;
1112 trace1((qh ferr, 1011, "qh_forcedmerges: merged %d facets and %d flipped facets across duplicated ridges\n",
1113 nummerge, numflip));
1114 } /* forcedmerges */
1115
1116
1117 /*-<a href="qh-merge.htm#TOC"
1118 >-------------------------------</a><a name="getmergeset">-</a>
1119
1120 qh_getmergeset( facetlist )
1121 determines nonconvex facets on facetlist
1122 tests !tested ridges and nonconvex ridges of !tested facets
1123
1124 returns:
1125 returns sorted qh.facet_mergeset of facet-neighbor pairs to be merged
1126 all ridges tested
1127
1128 notes:
1129 assumes no nonconvex ridges with both facets tested
1130 uses facet->tested/ridge->tested to prevent duplicate tests
1131 can not limit tests to modified ridges since the centrum changed
1132 uses qh.visit_id
1133
1134 see:
1135 qh_getmergeset_initial()
1136
1137 design:
1138 for each facet on facetlist
1139 for each ridge of facet
1140 if untested ridge
1141 test ridge for convexity
1142 if non-convex
1143 append ridge to qh.facet_mergeset
1144 sort qh.facet_mergeset by angle
1145 */
qh_getmergeset(facetT * facetlist)1146 void qh_getmergeset(facetT *facetlist) {
1147 facetT *facet, *neighbor, **neighborp;
1148 ridgeT *ridge, **ridgep;
1149 int nummerges;
1150
1151 nummerges= qh_setsize(qh facet_mergeset);
1152 trace4((qh ferr, 4026, "qh_getmergeset: started.\n"));
1153 qh visit_id++;
1154 FORALLfacet_(facetlist) {
1155 if (facet->tested)
1156 continue;
1157 facet->visitid= qh visit_id;
1158 facet->tested= True; /* must be non-simplicial due to merge */
1159 FOREACHneighbor_(facet)
1160 neighbor->seen= False;
1161 FOREACHridge_(facet->ridges) {
1162 if (ridge->tested && !ridge->nonconvex)
1163 continue;
1164 /* if tested & nonconvex, need to append merge */
1165 neighbor= otherfacet_(ridge, facet);
1166 if (neighbor->seen) {
1167 ridge->tested= True;
1168 ridge->nonconvex= False;
1169 }else if (neighbor->visitid != qh visit_id) {
1170 ridge->tested= True;
1171 ridge->nonconvex= False;
1172 neighbor->seen= True; /* only one ridge is marked nonconvex */
1173 if (qh_test_appendmerge(facet, neighbor))
1174 ridge->nonconvex= True;
1175 }
1176 }
1177 }
1178 nummerges= qh_setsize(qh facet_mergeset);
1179 if (qh ANGLEmerge)
1180 qsort(SETaddr_(qh facet_mergeset, mergeT), (size_t)nummerges, sizeof(mergeT *), qh_compareangle);
1181 else
1182 qsort(SETaddr_(qh facet_mergeset, mergeT), (size_t)nummerges, sizeof(mergeT *), qh_comparemerge);
1183 if (qh POSTmerging) {
1184 zadd_(Zmergesettot2, nummerges);
1185 }else {
1186 zadd_(Zmergesettot, nummerges);
1187 zmax_(Zmergesetmax, nummerges);
1188 }
1189 trace2((qh ferr, 2021, "qh_getmergeset: %d merges found\n", nummerges));
1190 } /* getmergeset */
1191
1192
1193 /*-<a href="qh-merge.htm#TOC"
1194 >-------------------------------</a><a name="getmergeset_initial">-</a>
1195
1196 qh_getmergeset_initial( facetlist )
1197 determine initial qh.facet_mergeset for facets
1198 tests all facet/neighbor pairs on facetlist
1199
1200 returns:
1201 sorted qh.facet_mergeset with nonconvex ridges
1202 sets facet->tested, ridge->tested, and ridge->nonconvex
1203
1204 notes:
1205 uses visit_id, assumes ridge->nonconvex is False
1206
1207 see:
1208 qh_getmergeset()
1209
1210 design:
1211 for each facet on facetlist
1212 for each untested neighbor of facet
1213 test facet and neighbor for convexity
1214 if non-convex
1215 append merge to qh.facet_mergeset
1216 mark one of the ridges as nonconvex
1217 sort qh.facet_mergeset by angle
1218 */
qh_getmergeset_initial(facetT * facetlist)1219 void qh_getmergeset_initial(facetT *facetlist) {
1220 facetT *facet, *neighbor, **neighborp;
1221 ridgeT *ridge, **ridgep;
1222 int nummerges;
1223
1224 qh visit_id++;
1225 FORALLfacet_(facetlist) {
1226 facet->visitid= qh visit_id;
1227 facet->tested= True;
1228 FOREACHneighbor_(facet) {
1229 if (neighbor->visitid != qh visit_id) {
1230 if (qh_test_appendmerge(facet, neighbor)) {
1231 FOREACHridge_(neighbor->ridges) {
1232 if (facet == otherfacet_(ridge, neighbor)) {
1233 ridge->nonconvex= True;
1234 break; /* only one ridge is marked nonconvex */
1235 }
1236 }
1237 }
1238 }
1239 }
1240 FOREACHridge_(facet->ridges)
1241 ridge->tested= True;
1242 }
1243 nummerges= qh_setsize(qh facet_mergeset);
1244 if (qh ANGLEmerge)
1245 qsort(SETaddr_(qh facet_mergeset, mergeT), (size_t)nummerges, sizeof(mergeT *), qh_compareangle);
1246 else
1247 qsort(SETaddr_(qh facet_mergeset, mergeT), (size_t)nummerges, sizeof(mergeT *), qh_comparemerge);
1248 if (qh POSTmerging) {
1249 zadd_(Zmergeinittot2, nummerges);
1250 }else {
1251 zadd_(Zmergeinittot, nummerges);
1252 zmax_(Zmergeinitmax, nummerges);
1253 }
1254 trace2((qh ferr, 2022, "qh_getmergeset_initial: %d merges found\n", nummerges));
1255 } /* getmergeset_initial */
1256
1257
1258 /*-<a href="qh-merge.htm#TOC"
1259 >-------------------------------</a><a name="hashridge">-</a>
1260
1261 qh_hashridge( hashtable, hashsize, ridge, oldvertex )
1262 add ridge to hashtable without oldvertex
1263
1264 notes:
1265 assumes hashtable is large enough
1266
1267 design:
1268 determine hash value for ridge without oldvertex
1269 find next empty slot for ridge
1270 */
qh_hashridge(setT * hashtable,int hashsize,ridgeT * ridge,vertexT * oldvertex)1271 void qh_hashridge(setT *hashtable, int hashsize, ridgeT *ridge, vertexT *oldvertex) {
1272 int hash;
1273 ridgeT *ridgeA;
1274
1275 hash= qh_gethash(hashsize, ridge->vertices, qh hull_dim-1, 0, oldvertex);
1276 while (True) {
1277 if (!(ridgeA= SETelemt_(hashtable, hash, ridgeT))) {
1278 SETelem_(hashtable, hash)= ridge;
1279 break;
1280 }else if (ridgeA == ridge)
1281 break;
1282 if (++hash == hashsize)
1283 hash= 0;
1284 }
1285 } /* hashridge */
1286
1287
1288 /*-<a href="qh-merge.htm#TOC"
1289 >-------------------------------</a><a name="hashridge_find">-</a>
1290
1291 qh_hashridge_find( hashtable, hashsize, ridge, vertex, oldvertex, hashslot )
1292 returns matching ridge without oldvertex in hashtable
1293 for ridge without vertex
1294 if oldvertex is NULL
1295 matches with any one skip
1296
1297 returns:
1298 matching ridge or NULL
1299 if no match,
1300 if ridge already in table
1301 hashslot= -1
1302 else
1303 hashslot= next NULL index
1304
1305 notes:
1306 assumes hashtable is large enough
1307 can't match ridge to itself
1308
1309 design:
1310 get hash value for ridge without vertex
1311 for each hashslot
1312 return match if ridge matches ridgeA without oldvertex
1313 */
qh_hashridge_find(setT * hashtable,int hashsize,ridgeT * ridge,vertexT * vertex,vertexT * oldvertex,int * hashslot)1314 ridgeT *qh_hashridge_find(setT *hashtable, int hashsize, ridgeT *ridge,
1315 vertexT *vertex, vertexT *oldvertex, int *hashslot) {
1316 int hash;
1317 ridgeT *ridgeA;
1318
1319 *hashslot= 0;
1320 zinc_(Zhashridge);
1321 hash= qh_gethash(hashsize, ridge->vertices, qh hull_dim-1, 0, vertex);
1322 while ((ridgeA= SETelemt_(hashtable, hash, ridgeT))) {
1323 if (ridgeA == ridge)
1324 *hashslot= -1;
1325 else {
1326 zinc_(Zhashridgetest);
1327 if (qh_setequal_except(ridge->vertices, vertex, ridgeA->vertices, oldvertex))
1328 return ridgeA;
1329 }
1330 if (++hash == hashsize)
1331 hash= 0;
1332 }
1333 if (!*hashslot)
1334 *hashslot= hash;
1335 return NULL;
1336 } /* hashridge_find */
1337
1338
1339 /*-<a href="qh-merge.htm#TOC"
1340 >-------------------------------</a><a name="makeridges">-</a>
1341
1342 qh_makeridges( facet )
1343 creates explicit ridges between simplicial facets
1344
1345 returns:
1346 facet with ridges and without qh_MERGEridge
1347 ->simplicial is False
1348
1349 notes:
1350 allows qh_MERGEridge flag
1351 uses existing ridges
1352 duplicate neighbors ok if ridges already exist (qh_mergecycle_ridges)
1353
1354 see:
1355 qh_mergecycle_ridges()
1356
1357 design:
1358 look for qh_MERGEridge neighbors
1359 mark neighbors that already have ridges
1360 for each unprocessed neighbor of facet
1361 create a ridge for neighbor and facet
1362 if any qh_MERGEridge neighbors
1363 delete qh_MERGEridge flags (already handled by qh_mark_dupridges)
1364 */
qh_makeridges(facetT * facet)1365 void qh_makeridges(facetT *facet) {
1366 facetT *neighbor, **neighborp;
1367 ridgeT *ridge, **ridgep;
1368 int neighbor_i, neighbor_n;
1369 boolT toporient, mergeridge= False;
1370
1371 if (!facet->simplicial)
1372 return;
1373 trace4((qh ferr, 4027, "qh_makeridges: make ridges for f%d\n", facet->id));
1374 facet->simplicial= False;
1375 FOREACHneighbor_(facet) {
1376 if (neighbor == qh_MERGEridge)
1377 mergeridge= True;
1378 else
1379 neighbor->seen= False;
1380 }
1381 FOREACHridge_(facet->ridges)
1382 otherfacet_(ridge, facet)->seen= True;
1383 FOREACHneighbor_i_(facet) {
1384 if (neighbor == qh_MERGEridge)
1385 continue; /* fixed by qh_mark_dupridges */
1386 else if (!neighbor->seen) { /* no current ridges */
1387 ridge= qh_newridge();
1388 ridge->vertices= qh_setnew_delnthsorted(facet->vertices, qh hull_dim,
1389 neighbor_i, 0);
1390 toporient= facet->toporient ^ (neighbor_i & 0x1);
1391 if (toporient) {
1392 ridge->top= facet;
1393 ridge->bottom= neighbor;
1394 }else {
1395 ridge->top= neighbor;
1396 ridge->bottom= facet;
1397 }
1398 #if 0 /* this also works */
1399 flip= (facet->toporient ^ neighbor->toporient)^(skip1 & 0x1) ^ (skip2 & 0x1);
1400 if (facet->toporient ^ (skip1 & 0x1) ^ flip) {
1401 ridge->top= neighbor;
1402 ridge->bottom= facet;
1403 }else {
1404 ridge->top= facet;
1405 ridge->bottom= neighbor;
1406 }
1407 #endif
1408 qh_setappend(&(facet->ridges), ridge);
1409 qh_setappend(&(neighbor->ridges), ridge);
1410 }
1411 }
1412 if (mergeridge) {
1413 while (qh_setdel(facet->neighbors, qh_MERGEridge))
1414 ; /* delete each one */
1415 }
1416 } /* makeridges */
1417
1418
1419 /*-<a href="qh-merge.htm#TOC"
1420 >-------------------------------</a><a name="mark_dupridges">-</a>
1421
1422 qh_mark_dupridges( facetlist )
1423 add duplicated ridges to qh.facet_mergeset
1424 facet->dupridge is true
1425
1426 returns:
1427 duplicate ridges on qh.facet_mergeset
1428 ->mergeridge/->mergeridge2 set
1429 duplicate ridges marked by qh_MERGEridge and both sides facet->dupridge
1430 no MERGEridges in neighbor sets
1431
1432 notes:
1433 duplicate ridges occur when the horizon is pinched,
1434 i.e. a subridge occurs in more than two horizon ridges.
1435 could rename vertices that pinch the horizon
1436 uses qh.visit_id
1437
1438 design:
1439 for all facets on facetlist
1440 if facet contains a duplicate ridge
1441 for each neighbor of facet
1442 if neighbor marked qh_MERGEridge (one side of the merge)
1443 set facet->mergeridge
1444 else
1445 if neighbor contains a duplicate ridge
1446 and the back link is qh_MERGEridge
1447 append duplicate ridge to qh.facet_mergeset
1448 for each duplicate ridge
1449 make ridge sets in preparation for merging
1450 remove qh_MERGEridge from neighbor set
1451 for each duplicate ridge
1452 restore the missing neighbor from the neighbor set that was qh_MERGEridge
1453 add the missing ridge for this neighbor
1454 */
qh_mark_dupridges(facetT * facetlist)1455 void qh_mark_dupridges(facetT *facetlist) {
1456 facetT *facet, *neighbor, **neighborp;
1457 int nummerge=0;
1458 mergeT *merge, **mergep;
1459
1460
1461 trace4((qh ferr, 4028, "qh_mark_dupridges: identify duplicate ridges\n"));
1462 FORALLfacet_(facetlist) {
1463 if (facet->dupridge) {
1464 FOREACHneighbor_(facet) {
1465 if (neighbor == qh_MERGEridge) {
1466 facet->mergeridge= True;
1467 continue;
1468 }
1469 if (neighbor->dupridge
1470 && !qh_setin(neighbor->neighbors, facet)) { /* qh_MERGEridge */
1471 qh_appendmergeset(facet, neighbor, MRGridge, NULL);
1472 facet->mergeridge2= True;
1473 facet->mergeridge= True;
1474 nummerge++;
1475 }
1476 }
1477 }
1478 }
1479 if (!nummerge)
1480 return;
1481 FORALLfacet_(facetlist) { /* gets rid of qh_MERGEridge */
1482 if (facet->mergeridge && !facet->mergeridge2)
1483 qh_makeridges(facet);
1484 }
1485 FOREACHmerge_(qh facet_mergeset) { /* restore the missing neighbors */
1486 if (merge->type == MRGridge) {
1487 qh_setappend(&merge->facet2->neighbors, merge->facet1);
1488 qh_makeridges(merge->facet1); /* and the missing ridges */
1489 }
1490 }
1491 trace1((qh ferr, 1012, "qh_mark_dupridges: found %d duplicated ridges\n",
1492 nummerge));
1493 } /* mark_dupridges */
1494
1495 /*-<a href="qh-merge.htm#TOC"
1496 >-------------------------------</a><a name="maydropneighbor">-</a>
1497
1498 qh_maydropneighbor( facet )
1499 drop neighbor relationship if no ridge between facet and neighbor
1500
1501 returns:
1502 neighbor sets updated
1503 appends degenerate facets to qh.facet_mergeset
1504
1505 notes:
1506 won't cause redundant facets since vertex inclusion is the same
1507 may drop vertex and neighbor if no ridge
1508 uses qh.visit_id
1509
1510 design:
1511 visit all neighbors with ridges
1512 for each unvisited neighbor of facet
1513 delete neighbor and facet from the neighbor sets
1514 if neighbor becomes degenerate
1515 append neighbor to qh.degen_mergeset
1516 if facet is degenerate
1517 append facet to qh.degen_mergeset
1518 */
qh_maydropneighbor(facetT * facet)1519 void qh_maydropneighbor(facetT *facet) {
1520 ridgeT *ridge, **ridgep;
1521 realT angledegen= qh_ANGLEdegen;
1522 facetT *neighbor, **neighborp;
1523
1524 qh visit_id++;
1525 trace4((qh ferr, 4029, "qh_maydropneighbor: test f%d for no ridges to a neighbor\n",
1526 facet->id));
1527 FOREACHridge_(facet->ridges) {
1528 ridge->top->visitid= qh visit_id;
1529 ridge->bottom->visitid= qh visit_id;
1530 }
1531 FOREACHneighbor_(facet) {
1532 if (neighbor->visitid != qh visit_id) {
1533 trace0((qh ferr, 17, "qh_maydropneighbor: facets f%d and f%d are no longer neighbors during p%d\n",
1534 facet->id, neighbor->id, qh furthest_id));
1535 zinc_(Zdropneighbor);
1536 qh_setdel(facet->neighbors, neighbor);
1537 neighborp--; /* repeat, deleted a neighbor */
1538 qh_setdel(neighbor->neighbors, facet);
1539 if (qh_setsize(neighbor->neighbors) < qh hull_dim) {
1540 zinc_(Zdropdegen);
1541 qh_appendmergeset(neighbor, neighbor, MRGdegen, &angledegen);
1542 trace2((qh ferr, 2023, "qh_maydropneighbors: f%d is degenerate.\n", neighbor->id));
1543 }
1544 }
1545 }
1546 if (qh_setsize(facet->neighbors) < qh hull_dim) {
1547 zinc_(Zdropdegen);
1548 qh_appendmergeset(facet, facet, MRGdegen, &angledegen);
1549 trace2((qh ferr, 2024, "qh_maydropneighbors: f%d is degenerate.\n", facet->id));
1550 }
1551 } /* maydropneighbor */
1552
1553
1554 /*-<a href="qh-merge.htm#TOC"
1555 >-------------------------------</a><a name="merge_degenredundant">-</a>
1556
1557 qh_merge_degenredundant()
1558 merge all degenerate and redundant facets
1559 qh.degen_mergeset contains merges from qh_degen_redundant_neighbors()
1560
1561 returns:
1562 number of merges performed
1563 resets facet->degenerate/redundant
1564 if deleted (visible) facet has no neighbors
1565 sets ->f.replace to NULL
1566
1567 notes:
1568 redundant merges happen before degenerate ones
1569 merging and renaming vertices can result in degen/redundant facets
1570
1571 design:
1572 for each merge on qh.degen_mergeset
1573 if redundant merge
1574 if non-redundant facet merged into redundant facet
1575 recheck facet for redundancy
1576 else
1577 merge redundant facet into other facet
1578 */
qh_merge_degenredundant(void)1579 int qh_merge_degenredundant(void) {
1580 int size;
1581 mergeT *merge;
1582 facetT *bestneighbor, *facet1, *facet2;
1583 realT dist, mindist, maxdist;
1584 vertexT *vertex, **vertexp;
1585 int nummerges= 0;
1586 mergeType mergetype;
1587
1588 while ((merge= (mergeT*)qh_setdellast(qh degen_mergeset))) {
1589 facet1= merge->facet1;
1590 facet2= merge->facet2;
1591 mergetype= merge->type;
1592 qh_memfree(merge, (int)sizeof(mergeT));
1593 if (facet1->visible)
1594 continue;
1595 facet1->degenerate= False;
1596 facet1->redundant= False;
1597 if (qh TRACEmerge-1 == zzval_(Ztotmerge))
1598 qhmem.IStracing= qh IStracing= qh TRACElevel;
1599 if (mergetype == MRGredundant) {
1600 zinc_(Zneighbor);
1601 while (facet2->visible) {
1602 if (!facet2->f.replace) {
1603 qh_fprintf(qh ferr, 6097, "qhull internal error (qh_merge_degenredunant): f%d redundant but f%d has no replacement\n",
1604 facet1->id, facet2->id);
1605 qh_errexit2 (qh_ERRqhull, facet1, facet2);
1606 }
1607 facet2= facet2->f.replace;
1608 }
1609 if (facet1 == facet2) {
1610 qh_degen_redundant_facet(facet1); /* in case of others */
1611 continue;
1612 }
1613 trace2((qh ferr, 2025, "qh_merge_degenredundant: facet f%d is contained in f%d, will merge\n",
1614 facet1->id, facet2->id));
1615 qh_mergefacet(facet1, facet2, NULL, NULL, !qh_MERGEapex);
1616 /* merge distance is already accounted for */
1617 nummerges++;
1618 }else { /* mergetype == MRGdegen, other merges may have fixed */
1619 if (!(size= qh_setsize(facet1->neighbors))) {
1620 zinc_(Zdelfacetdup);
1621 trace2((qh ferr, 2026, "qh_merge_degenredundant: facet f%d has no neighbors. Deleted\n", facet1->id));
1622 qh_willdelete(facet1, NULL);
1623 FOREACHvertex_(facet1->vertices) {
1624 qh_setdel(vertex->neighbors, facet1);
1625 if (!SETfirst_(vertex->neighbors)) {
1626 zinc_(Zdegenvertex);
1627 trace2((qh ferr, 2027, "qh_merge_degenredundant: deleted v%d because f%d has no neighbors\n",
1628 vertex->id, facet1->id));
1629 vertex->deleted= True;
1630 qh_setappend(&qh del_vertices, vertex);
1631 }
1632 }
1633 nummerges++;
1634 }else if (size < qh hull_dim) {
1635 bestneighbor= qh_findbestneighbor(facet1, &dist, &mindist, &maxdist);
1636 trace2((qh ferr, 2028, "qh_merge_degenredundant: facet f%d has %d neighbors, merge into f%d dist %2.2g\n",
1637 facet1->id, size, bestneighbor->id, dist));
1638 qh_mergefacet(facet1, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
1639 nummerges++;
1640 if (qh PRINTstatistics) {
1641 zinc_(Zdegen);
1642 wadd_(Wdegentot, dist);
1643 wmax_(Wdegenmax, dist);
1644 }
1645 } /* else, another merge fixed the degeneracy and redundancy tested */
1646 }
1647 }
1648 return nummerges;
1649 } /* merge_degenredundant */
1650
1651 /*-<a href="qh-merge.htm#TOC"
1652 >-------------------------------</a><a name="merge_nonconvex">-</a>
1653
1654 qh_merge_nonconvex( facet1, facet2, mergetype )
1655 remove non-convex ridge between facet1 into facet2
1656 mergetype gives why the facet's are non-convex
1657
1658 returns:
1659 merges one of the facets into the best neighbor
1660
1661 design:
1662 if one of the facets is a new facet
1663 prefer merging new facet into old facet
1664 find best neighbors for both facets
1665 merge the nearest facet into its best neighbor
1666 update the statistics
1667 */
qh_merge_nonconvex(facetT * facet1,facetT * facet2,mergeType mergetype)1668 void qh_merge_nonconvex(facetT *facet1, facetT *facet2, mergeType mergetype) {
1669 facetT *bestfacet, *bestneighbor, *neighbor;
1670 realT dist, dist2, mindist, mindist2, maxdist, maxdist2;
1671
1672 if (qh TRACEmerge-1 == zzval_(Ztotmerge))
1673 qhmem.IStracing= qh IStracing= qh TRACElevel;
1674 trace3((qh ferr, 3003, "qh_merge_nonconvex: merge #%d for f%d and f%d type %d\n",
1675 zzval_(Ztotmerge) + 1, facet1->id, facet2->id, mergetype));
1676 /* concave or coplanar */
1677 if (!facet1->newfacet) {
1678 bestfacet= facet2; /* avoid merging old facet if new is ok */
1679 facet2= facet1;
1680 facet1= bestfacet;
1681 }else
1682 bestfacet= facet1;
1683 bestneighbor= qh_findbestneighbor(bestfacet, &dist, &mindist, &maxdist);
1684 neighbor= qh_findbestneighbor(facet2, &dist2, &mindist2, &maxdist2);
1685 if (dist < dist2) {
1686 qh_mergefacet(bestfacet, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
1687 }else if (qh AVOIDold && !facet2->newfacet
1688 && ((mindist >= -qh MAXcoplanar && maxdist <= qh max_outside)
1689 || dist * 1.5 < dist2)) {
1690 zinc_(Zavoidold);
1691 wadd_(Wavoidoldtot, dist);
1692 wmax_(Wavoidoldmax, dist);
1693 trace2((qh ferr, 2029, "qh_merge_nonconvex: avoid merging old facet f%d dist %2.2g. Use f%d dist %2.2g instead\n",
1694 facet2->id, dist2, facet1->id, dist2));
1695 qh_mergefacet(bestfacet, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
1696 }else {
1697 qh_mergefacet(facet2, neighbor, &mindist2, &maxdist2, !qh_MERGEapex);
1698 dist= dist2;
1699 }
1700 if (qh PRINTstatistics) {
1701 if (mergetype == MRGanglecoplanar) {
1702 zinc_(Zacoplanar);
1703 wadd_(Wacoplanartot, dist);
1704 wmax_(Wacoplanarmax, dist);
1705 }else if (mergetype == MRGconcave) {
1706 zinc_(Zconcave);
1707 wadd_(Wconcavetot, dist);
1708 wmax_(Wconcavemax, dist);
1709 }else { /* MRGcoplanar */
1710 zinc_(Zcoplanar);
1711 wadd_(Wcoplanartot, dist);
1712 wmax_(Wcoplanarmax, dist);
1713 }
1714 }
1715 } /* merge_nonconvex */
1716
1717 /*-<a href="qh-merge.htm#TOC"
1718 >-------------------------------</a><a name="mergecycle">-</a>
1719
1720 qh_mergecycle( samecycle, newfacet )
1721 merge a cycle of facets starting at samecycle into a newfacet
1722 newfacet is a horizon facet with ->normal
1723 samecycle facets are simplicial from an apex
1724
1725 returns:
1726 initializes vertex neighbors on first merge
1727 samecycle deleted (placed on qh.visible_list)
1728 newfacet at end of qh.facet_list
1729 deleted vertices on qh.del_vertices
1730
1731 see:
1732 qh_mergefacet()
1733 called by qh_mergecycle_all() for multiple, same cycle facets
1734
1735 design:
1736 make vertex neighbors if necessary
1737 make ridges for newfacet
1738 merge neighbor sets of samecycle into newfacet
1739 merge ridges of samecycle into newfacet
1740 merge vertex neighbors of samecycle into newfacet
1741 make apex of samecycle the apex of newfacet
1742 if newfacet wasn't a new facet
1743 add its vertices to qh.newvertex_list
1744 delete samecycle facets a make newfacet a newfacet
1745 */
qh_mergecycle(facetT * samecycle,facetT * newfacet)1746 void qh_mergecycle(facetT *samecycle, facetT *newfacet) {
1747 int traceonce= False, tracerestore= 0;
1748 vertexT *apex;
1749 #ifndef qh_NOtrace
1750 facetT *same;
1751 #endif
1752
1753 if (newfacet->tricoplanar) {
1754 if (!qh TRInormals) {
1755 qh_fprintf(qh ferr, 6224, "Qhull internal error (qh_mergecycle): does not work for tricoplanar facets. Use option 'Q11'\n");
1756 qh_errexit(qh_ERRqhull, newfacet, NULL);
1757 }
1758 newfacet->tricoplanar= False;
1759 newfacet->keepcentrum= False;
1760 }
1761 if (!qh VERTEXneighbors)
1762 qh_vertexneighbors();
1763 zzinc_(Ztotmerge);
1764 if (qh REPORTfreq2 && qh POSTmerging) {
1765 if (zzval_(Ztotmerge) > qh mergereport + qh REPORTfreq2)
1766 qh_tracemerging();
1767 }
1768 #ifndef qh_NOtrace
1769 if (qh TRACEmerge == zzval_(Ztotmerge))
1770 qhmem.IStracing= qh IStracing= qh TRACElevel;
1771 trace2((qh ferr, 2030, "qh_mergecycle: merge #%d for facets from cycle f%d into coplanar horizon f%d\n",
1772 zzval_(Ztotmerge), samecycle->id, newfacet->id));
1773 if (newfacet == qh tracefacet) {
1774 tracerestore= qh IStracing;
1775 qh IStracing= 4;
1776 qh_fprintf(qh ferr, 8068, "qh_mergecycle: ========= trace merge %d of samecycle %d into trace f%d, furthest is p%d\n",
1777 zzval_(Ztotmerge), samecycle->id, newfacet->id, qh furthest_id);
1778 traceonce= True;
1779 }
1780 if (qh IStracing >=4) {
1781 qh_fprintf(qh ferr, 8069, " same cycle:");
1782 FORALLsame_cycle_(samecycle)
1783 qh_fprintf(qh ferr, 8070, " f%d", same->id);
1784 qh_fprintf(qh ferr, 8071, "\n");
1785 }
1786 if (qh IStracing >=4)
1787 qh_errprint("MERGING CYCLE", samecycle, newfacet, NULL, NULL);
1788 #endif /* !qh_NOtrace */
1789 apex= SETfirstt_(samecycle->vertices, vertexT);
1790 qh_makeridges(newfacet);
1791 qh_mergecycle_neighbors(samecycle, newfacet);
1792 qh_mergecycle_ridges(samecycle, newfacet);
1793 qh_mergecycle_vneighbors(samecycle, newfacet);
1794 if (SETfirstt_(newfacet->vertices, vertexT) != apex)
1795 qh_setaddnth(&newfacet->vertices, 0, apex); /* apex has last id */
1796 if (!newfacet->newfacet)
1797 qh_newvertices(newfacet->vertices);
1798 qh_mergecycle_facets(samecycle, newfacet);
1799 qh_tracemerge(samecycle, newfacet);
1800 /* check for degen_redundant_neighbors after qh_forcedmerges() */
1801 if (traceonce) {
1802 qh_fprintf(qh ferr, 8072, "qh_mergecycle: end of trace facet\n");
1803 qh IStracing= tracerestore;
1804 }
1805 } /* mergecycle */
1806
1807 /*-<a href="qh-merge.htm#TOC"
1808 >-------------------------------</a><a name="mergecycle_all">-</a>
1809
1810 qh_mergecycle_all( facetlist, wasmerge )
1811 merge all samecycles of coplanar facets into horizon
1812 don't merge facets with ->mergeridge (these already have ->normal)
1813 all facets are simplicial from apex
1814 all facet->cycledone == False
1815
1816 returns:
1817 all newfacets merged into coplanar horizon facets
1818 deleted vertices on qh.del_vertices
1819 sets wasmerge if any merge
1820
1821 see:
1822 calls qh_mergecycle for multiple, same cycle facets
1823
1824 design:
1825 for each facet on facetlist
1826 skip facets with duplicate ridges and normals
1827 check that facet is in a samecycle (->mergehorizon)
1828 if facet only member of samecycle
1829 sets vertex->delridge for all vertices except apex
1830 merge facet into horizon
1831 else
1832 mark all facets in samecycle
1833 remove facets with duplicate ridges from samecycle
1834 merge samecycle into horizon (deletes facets from facetlist)
1835 */
qh_mergecycle_all(facetT * facetlist,boolT * wasmerge)1836 void qh_mergecycle_all(facetT *facetlist, boolT *wasmerge) {
1837 facetT *facet, *same, *prev, *horizon;
1838 facetT *samecycle= NULL, *nextfacet, *nextsame;
1839 vertexT *apex, *vertex, **vertexp;
1840 int cycles=0, total=0, facets, nummerge;
1841
1842 trace2((qh ferr, 2031, "qh_mergecycle_all: begin\n"));
1843 for (facet= facetlist; facet && (nextfacet= facet->next); facet= nextfacet) {
1844 if (facet->normal)
1845 continue;
1846 if (!facet->mergehorizon) {
1847 qh_fprintf(qh ferr, 6225, "Qhull internal error (qh_mergecycle_all): f%d without normal\n", facet->id);
1848 qh_errexit(qh_ERRqhull, facet, NULL);
1849 }
1850 horizon= SETfirstt_(facet->neighbors, facetT);
1851 if (facet->f.samecycle == facet) {
1852 zinc_(Zonehorizon);
1853 /* merge distance done in qh_findhorizon */
1854 apex= SETfirstt_(facet->vertices, vertexT);
1855 FOREACHvertex_(facet->vertices) {
1856 if (vertex != apex)
1857 vertex->delridge= True;
1858 }
1859 horizon->f.newcycle= NULL;
1860 qh_mergefacet(facet, horizon, NULL, NULL, qh_MERGEapex);
1861 }else {
1862 samecycle= facet;
1863 facets= 0;
1864 prev= facet;
1865 for (same= facet->f.samecycle; same; /* FORALLsame_cycle_(facet) */
1866 same= (same == facet ? NULL :nextsame)) { /* ends at facet */
1867 nextsame= same->f.samecycle;
1868 if (same->cycledone || same->visible)
1869 qh_infiniteloop(same);
1870 same->cycledone= True;
1871 if (same->normal) {
1872 prev->f.samecycle= same->f.samecycle; /* unlink ->mergeridge */
1873 same->f.samecycle= NULL;
1874 }else {
1875 prev= same;
1876 facets++;
1877 }
1878 }
1879 while (nextfacet && nextfacet->cycledone) /* will delete samecycle */
1880 nextfacet= nextfacet->next;
1881 horizon->f.newcycle= NULL;
1882 qh_mergecycle(samecycle, horizon);
1883 nummerge= horizon->nummerge + facets;
1884 if (nummerge > qh_MAXnummerge)
1885 horizon->nummerge= qh_MAXnummerge;
1886 else
1887 horizon->nummerge= (short unsigned int)nummerge;
1888 zzinc_(Zcyclehorizon);
1889 total += facets;
1890 zzadd_(Zcyclefacettot, facets);
1891 zmax_(Zcyclefacetmax, facets);
1892 }
1893 cycles++;
1894 }
1895 if (cycles)
1896 *wasmerge= True;
1897 trace1((qh ferr, 1013, "qh_mergecycle_all: merged %d same cycles or facets into coplanar horizons\n", cycles));
1898 } /* mergecycle_all */
1899
1900 /*-<a href="qh-merge.htm#TOC"
1901 >-------------------------------</a><a name="mergecycle_facets">-</a>
1902
1903 qh_mergecycle_facets( samecycle, newfacet )
1904 finish merge of samecycle into newfacet
1905
1906 returns:
1907 samecycle prepended to visible_list for later deletion and partitioning
1908 each facet->f.replace == newfacet
1909
1910 newfacet moved to end of qh.facet_list
1911 makes newfacet a newfacet (get's facet1->id if it was old)
1912 sets newfacet->newmerge
1913 clears newfacet->center (unless merging into a large facet)
1914 clears newfacet->tested and ridge->tested for facet1
1915
1916 adds neighboring facets to facet_mergeset if redundant or degenerate
1917
1918 design:
1919 make newfacet a new facet and set its flags
1920 move samecycle facets to qh.visible_list for later deletion
1921 unless newfacet is large
1922 remove its centrum
1923 */
qh_mergecycle_facets(facetT * samecycle,facetT * newfacet)1924 void qh_mergecycle_facets(facetT *samecycle, facetT *newfacet) {
1925 facetT *same, *next;
1926
1927 trace4((qh ferr, 4030, "qh_mergecycle_facets: make newfacet new and samecycle deleted\n"));
1928 qh_removefacet(newfacet); /* append as a newfacet to end of qh facet_list */
1929 qh_appendfacet(newfacet);
1930 newfacet->newfacet= True;
1931 newfacet->simplicial= False;
1932 newfacet->newmerge= True;
1933
1934 for (same= samecycle->f.samecycle; same; same= (same == samecycle ? NULL : next)) {
1935 next= same->f.samecycle; /* reused by willdelete */
1936 qh_willdelete(same, newfacet);
1937 }
1938 if (newfacet->center
1939 && qh_setsize(newfacet->vertices) <= qh hull_dim + qh_MAXnewcentrum) {
1940 qh_memfree(newfacet->center, qh normal_size);
1941 newfacet->center= NULL;
1942 }
1943 trace3((qh ferr, 3004, "qh_mergecycle_facets: merged facets from cycle f%d into f%d\n",
1944 samecycle->id, newfacet->id));
1945 } /* mergecycle_facets */
1946
1947 /*-<a href="qh-merge.htm#TOC"
1948 >-------------------------------</a><a name="mergecycle_neighbors">-</a>
1949
1950 qh_mergecycle_neighbors( samecycle, newfacet )
1951 add neighbors for samecycle facets to newfacet
1952
1953 returns:
1954 newfacet with updated neighbors and vice-versa
1955 newfacet has ridges
1956 all neighbors of newfacet marked with qh.visit_id
1957 samecycle facets marked with qh.visit_id-1
1958 ridges updated for simplicial neighbors of samecycle with a ridge
1959
1960 notes:
1961 assumes newfacet not in samecycle
1962 usually, samecycle facets are new, simplicial facets without internal ridges
1963 not so if horizon facet is coplanar to two different samecycles
1964
1965 see:
1966 qh_mergeneighbors()
1967
1968 design:
1969 check samecycle
1970 delete neighbors from newfacet that are also in samecycle
1971 for each neighbor of a facet in samecycle
1972 if neighbor is simplicial
1973 if first visit
1974 move the neighbor relation to newfacet
1975 update facet links for its ridges
1976 else
1977 make ridges for neighbor
1978 remove samecycle reference
1979 else
1980 update neighbor sets
1981 */
qh_mergecycle_neighbors(facetT * samecycle,facetT * newfacet)1982 void qh_mergecycle_neighbors(facetT *samecycle, facetT *newfacet) {
1983 facetT *same, *neighbor, **neighborp;
1984 int delneighbors= 0, newneighbors= 0;
1985 unsigned int samevisitid;
1986 ridgeT *ridge, **ridgep;
1987
1988 samevisitid= ++qh visit_id;
1989 FORALLsame_cycle_(samecycle) {
1990 if (same->visitid == samevisitid || same->visible)
1991 qh_infiniteloop(samecycle);
1992 same->visitid= samevisitid;
1993 }
1994 newfacet->visitid= ++qh visit_id;
1995 trace4((qh ferr, 4031, "qh_mergecycle_neighbors: delete shared neighbors from newfacet\n"));
1996 FOREACHneighbor_(newfacet) {
1997 if (neighbor->visitid == samevisitid) {
1998 SETref_(neighbor)= NULL; /* samecycle neighbors deleted */
1999 delneighbors++;
2000 }else
2001 neighbor->visitid= qh visit_id;
2002 }
2003 qh_setcompact(newfacet->neighbors);
2004
2005 trace4((qh ferr, 4032, "qh_mergecycle_neighbors: update neighbors\n"));
2006 FORALLsame_cycle_(samecycle) {
2007 FOREACHneighbor_(same) {
2008 if (neighbor->visitid == samevisitid)
2009 continue;
2010 if (neighbor->simplicial) {
2011 if (neighbor->visitid != qh visit_id) {
2012 qh_setappend(&newfacet->neighbors, neighbor);
2013 qh_setreplace(neighbor->neighbors, same, newfacet);
2014 newneighbors++;
2015 neighbor->visitid= qh visit_id;
2016 FOREACHridge_(neighbor->ridges) { /* update ridge in case of qh_makeridges */
2017 if (ridge->top == same) {
2018 ridge->top= newfacet;
2019 break;
2020 }else if (ridge->bottom == same) {
2021 ridge->bottom= newfacet;
2022 break;
2023 }
2024 }
2025 }else {
2026 qh_makeridges(neighbor);
2027 qh_setdel(neighbor->neighbors, same);
2028 /* same can't be horizon facet for neighbor */
2029 }
2030 }else { /* non-simplicial neighbor */
2031 qh_setdel(neighbor->neighbors, same);
2032 if (neighbor->visitid != qh visit_id) {
2033 qh_setappend(&neighbor->neighbors, newfacet);
2034 qh_setappend(&newfacet->neighbors, neighbor);
2035 neighbor->visitid= qh visit_id;
2036 newneighbors++;
2037 }
2038 }
2039 }
2040 }
2041 trace2((qh ferr, 2032, "qh_mergecycle_neighbors: deleted %d neighbors and added %d\n",
2042 delneighbors, newneighbors));
2043 } /* mergecycle_neighbors */
2044
2045 /*-<a href="qh-merge.htm#TOC"
2046 >-------------------------------</a><a name="mergecycle_ridges">-</a>
2047
2048 qh_mergecycle_ridges( samecycle, newfacet )
2049 add ridges/neighbors for facets in samecycle to newfacet
2050 all new/old neighbors of newfacet marked with qh.visit_id
2051 facets in samecycle marked with qh.visit_id-1
2052 newfacet marked with qh.visit_id
2053
2054 returns:
2055 newfacet has merged ridges
2056
2057 notes:
2058 ridge already updated for simplicial neighbors of samecycle with a ridge
2059
2060 see:
2061 qh_mergeridges()
2062 qh_makeridges()
2063
2064 design:
2065 remove ridges between newfacet and samecycle
2066 for each facet in samecycle
2067 for each ridge in facet
2068 update facet pointers in ridge
2069 skip ridges processed in qh_mergecycle_neighors
2070 free ridges between newfacet and samecycle
2071 free ridges between facets of samecycle (on 2nd visit)
2072 append remaining ridges to newfacet
2073 if simpilicial facet
2074 for each neighbor of facet
2075 if simplicial facet
2076 and not samecycle facet or newfacet
2077 make ridge between neighbor and newfacet
2078 */
qh_mergecycle_ridges(facetT * samecycle,facetT * newfacet)2079 void qh_mergecycle_ridges(facetT *samecycle, facetT *newfacet) {
2080 facetT *same, *neighbor= NULL;
2081 int numold=0, numnew=0;
2082 int neighbor_i, neighbor_n;
2083 unsigned int samevisitid;
2084 ridgeT *ridge, **ridgep;
2085 boolT toporient;
2086 void **freelistp; /* used !qh_NOmem */
2087
2088 trace4((qh ferr, 4033, "qh_mergecycle_ridges: delete shared ridges from newfacet\n"));
2089 samevisitid= qh visit_id -1;
2090 FOREACHridge_(newfacet->ridges) {
2091 neighbor= otherfacet_(ridge, newfacet);
2092 if (neighbor->visitid == samevisitid)
2093 SETref_(ridge)= NULL; /* ridge free'd below */
2094 }
2095 qh_setcompact(newfacet->ridges);
2096
2097 trace4((qh ferr, 4034, "qh_mergecycle_ridges: add ridges to newfacet\n"));
2098 FORALLsame_cycle_(samecycle) {
2099 FOREACHridge_(same->ridges) {
2100 if (ridge->top == same) {
2101 ridge->top= newfacet;
2102 neighbor= ridge->bottom;
2103 }else if (ridge->bottom == same) {
2104 ridge->bottom= newfacet;
2105 neighbor= ridge->top;
2106 }else if (ridge->top == newfacet || ridge->bottom == newfacet) {
2107 qh_setappend(&newfacet->ridges, ridge);
2108 numold++; /* already set by qh_mergecycle_neighbors */
2109 continue;
2110 }else {
2111 qh_fprintf(qh ferr, 6098, "qhull internal error (qh_mergecycle_ridges): bad ridge r%d\n", ridge->id);
2112 qh_errexit(qh_ERRqhull, NULL, ridge);
2113 }
2114 if (neighbor == newfacet) {
2115 qh_setfree(&(ridge->vertices));
2116 qh_memfree_(ridge, (int)sizeof(ridgeT), freelistp);
2117 numold++;
2118 }else if (neighbor->visitid == samevisitid) {
2119 qh_setdel(neighbor->ridges, ridge);
2120 qh_setfree(&(ridge->vertices));
2121 qh_memfree_(ridge, (int)sizeof(ridgeT), freelistp);
2122 numold++;
2123 }else {
2124 qh_setappend(&newfacet->ridges, ridge);
2125 numold++;
2126 }
2127 }
2128 if (same->ridges)
2129 qh_settruncate(same->ridges, 0);
2130 if (!same->simplicial)
2131 continue;
2132 FOREACHneighbor_i_(same) { /* note: !newfact->simplicial */
2133 if (neighbor->visitid != samevisitid && neighbor->simplicial) {
2134 ridge= qh_newridge();
2135 ridge->vertices= qh_setnew_delnthsorted(same->vertices, qh hull_dim,
2136 neighbor_i, 0);
2137 toporient= same->toporient ^ (neighbor_i & 0x1);
2138 if (toporient) {
2139 ridge->top= newfacet;
2140 ridge->bottom= neighbor;
2141 }else {
2142 ridge->top= neighbor;
2143 ridge->bottom= newfacet;
2144 }
2145 qh_setappend(&(newfacet->ridges), ridge);
2146 qh_setappend(&(neighbor->ridges), ridge);
2147 numnew++;
2148 }
2149 }
2150 }
2151
2152 trace2((qh ferr, 2033, "qh_mergecycle_ridges: found %d old ridges and %d new ones\n",
2153 numold, numnew));
2154 } /* mergecycle_ridges */
2155
2156 /*-<a href="qh-merge.htm#TOC"
2157 >-------------------------------</a><a name="mergecycle_vneighbors">-</a>
2158
2159 qh_mergecycle_vneighbors( samecycle, newfacet )
2160 create vertex neighbors for newfacet from vertices of facets in samecycle
2161 samecycle marked with visitid == qh.visit_id - 1
2162
2163 returns:
2164 newfacet vertices with updated neighbors
2165 marks newfacet with qh.visit_id-1
2166 deletes vertices that are merged away
2167 sets delridge on all vertices (faster here than in mergecycle_ridges)
2168
2169 see:
2170 qh_mergevertex_neighbors()
2171
2172 design:
2173 for each vertex of samecycle facet
2174 set vertex->delridge
2175 delete samecycle facets from vertex neighbors
2176 append newfacet to vertex neighbors
2177 if vertex only in newfacet
2178 delete it from newfacet
2179 add it to qh.del_vertices for later deletion
2180 */
qh_mergecycle_vneighbors(facetT * samecycle,facetT * newfacet)2181 void qh_mergecycle_vneighbors(facetT *samecycle, facetT *newfacet) {
2182 facetT *neighbor, **neighborp;
2183 unsigned int mergeid;
2184 vertexT *vertex, **vertexp, *apex;
2185 setT *vertices;
2186
2187 trace4((qh ferr, 4035, "qh_mergecycle_vneighbors: update vertex neighbors for newfacet\n"));
2188 mergeid= qh visit_id - 1;
2189 newfacet->visitid= mergeid;
2190 vertices= qh_basevertices(samecycle); /* temp */
2191 apex= SETfirstt_(samecycle->vertices, vertexT);
2192 qh_setappend(&vertices, apex);
2193 FOREACHvertex_(vertices) {
2194 vertex->delridge= True;
2195 FOREACHneighbor_(vertex) {
2196 if (neighbor->visitid == mergeid)
2197 SETref_(neighbor)= NULL;
2198 }
2199 qh_setcompact(vertex->neighbors);
2200 qh_setappend(&vertex->neighbors, newfacet);
2201 if (!SETsecond_(vertex->neighbors)) {
2202 zinc_(Zcyclevertex);
2203 trace2((qh ferr, 2034, "qh_mergecycle_vneighbors: deleted v%d when merging cycle f%d into f%d\n",
2204 vertex->id, samecycle->id, newfacet->id));
2205 qh_setdelsorted(newfacet->vertices, vertex);
2206 vertex->deleted= True;
2207 qh_setappend(&qh del_vertices, vertex);
2208 }
2209 }
2210 qh_settempfree(&vertices);
2211 trace3((qh ferr, 3005, "qh_mergecycle_vneighbors: merged vertices from cycle f%d into f%d\n",
2212 samecycle->id, newfacet->id));
2213 } /* mergecycle_vneighbors */
2214
2215 /*-<a href="qh-merge.htm#TOC"
2216 >-------------------------------</a><a name="mergefacet">-</a>
2217
2218 qh_mergefacet( facet1, facet2, mindist, maxdist, mergeapex )
2219 merges facet1 into facet2
2220 mergeapex==qh_MERGEapex if merging new facet into coplanar horizon
2221
2222 returns:
2223 qh.max_outside and qh.min_vertex updated
2224 initializes vertex neighbors on first merge
2225
2226 returns:
2227 facet2 contains facet1's vertices, neighbors, and ridges
2228 facet2 moved to end of qh.facet_list
2229 makes facet2 a newfacet
2230 sets facet2->newmerge set
2231 clears facet2->center (unless merging into a large facet)
2232 clears facet2->tested and ridge->tested for facet1
2233
2234 facet1 prepended to visible_list for later deletion and partitioning
2235 facet1->f.replace == facet2
2236
2237 adds neighboring facets to facet_mergeset if redundant or degenerate
2238
2239 notes:
2240 mindist/maxdist may be NULL (only if both NULL)
2241 traces merge if fmax_(maxdist,-mindist) > TRACEdist
2242
2243 see:
2244 qh_mergecycle()
2245
2246 design:
2247 trace merge and check for degenerate simplex
2248 make ridges for both facets
2249 update qh.max_outside, qh.max_vertex, qh.min_vertex
2250 update facet2->maxoutside and keepcentrum
2251 update facet2->nummerge
2252 update tested flags for facet2
2253 if facet1 is simplicial
2254 merge facet1 into facet2
2255 else
2256 merge facet1's neighbors into facet2
2257 merge facet1's ridges into facet2
2258 merge facet1's vertices into facet2
2259 merge facet1's vertex neighbors into facet2
2260 add facet2's vertices to qh.new_vertexlist
2261 unless qh_MERGEapex
2262 test facet2 for degenerate or redundant neighbors
2263 move facet1 to qh.visible_list for later deletion
2264 move facet2 to end of qh.newfacet_list
2265 */
qh_mergefacet(facetT * facet1,facetT * facet2,realT * mindist,realT * maxdist,boolT mergeapex)2266 void qh_mergefacet(facetT *facet1, facetT *facet2, realT *mindist, realT *maxdist, boolT mergeapex) {
2267 boolT traceonce= False;
2268 vertexT *vertex, **vertexp;
2269 int tracerestore=0, nummerge;
2270
2271 if (facet1->tricoplanar || facet2->tricoplanar) {
2272 if (!qh TRInormals) {
2273 qh_fprintf(qh ferr, 6226, "Qhull internal error (qh_mergefacet): does not work for tricoplanar facets. Use option 'Q11'\n");
2274 qh_errexit2 (qh_ERRqhull, facet1, facet2);
2275 }
2276 if (facet2->tricoplanar) {
2277 facet2->tricoplanar= False;
2278 facet2->keepcentrum= False;
2279 }
2280 }
2281 zzinc_(Ztotmerge);
2282 if (qh REPORTfreq2 && qh POSTmerging) {
2283 if (zzval_(Ztotmerge) > qh mergereport + qh REPORTfreq2)
2284 qh_tracemerging();
2285 }
2286 #ifndef qh_NOtrace
2287 if (qh build_cnt >= qh RERUN) {
2288 if (mindist && (-*mindist > qh TRACEdist || *maxdist > qh TRACEdist)) {
2289 tracerestore= 0;
2290 qh IStracing= qh TRACElevel;
2291 traceonce= True;
2292 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),
2293 fmax_(-*mindist, *maxdist), facet1->id, facet2->id, qh furthest_id);
2294 }else if (facet1 == qh tracefacet || facet2 == qh tracefacet) {
2295 tracerestore= qh IStracing;
2296 qh IStracing= 4;
2297 traceonce= True;
2298 qh_fprintf(qh ferr, 8076, "qh_mergefacet: ========= trace merge #%d involving f%d, furthest is p%d\n",
2299 zzval_(Ztotmerge), qh tracefacet_id, qh furthest_id);
2300 }
2301 }
2302 if (qh IStracing >= 2) {
2303 realT mergemin= -2;
2304 realT mergemax= -2;
2305
2306 if (mindist) {
2307 mergemin= *mindist;
2308 mergemax= *maxdist;
2309 }
2310 qh_fprintf(qh ferr, 8077, "qh_mergefacet: #%d merge f%d into f%d, mindist= %2.2g, maxdist= %2.2g\n",
2311 zzval_(Ztotmerge), facet1->id, facet2->id, mergemin, mergemax);
2312 }
2313 #endif /* !qh_NOtrace */
2314 if (facet1 == facet2 || facet1->visible || facet2->visible) {
2315 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",
2316 facet1->id, facet2->id);
2317 qh_errexit2 (qh_ERRqhull, facet1, facet2);
2318 }
2319 if (qh num_facets - qh num_visible <= qh hull_dim + 1) {
2320 qh_fprintf(qh ferr, 6227, "\n\
2321 qhull precision error: Only %d facets remain. Can not merge another\n\
2322 pair. The input is too degenerate or the convexity constraints are\n\
2323 too strong.\n", qh hull_dim+1);
2324 if (qh hull_dim >= 5 && !qh MERGEexact)
2325 qh_fprintf(qh ferr, 8079, "Option 'Qx' may avoid this problem.\n");
2326 qh_errexit(qh_ERRinput, NULL, NULL);
2327 }
2328 if (!qh VERTEXneighbors)
2329 qh_vertexneighbors();
2330 qh_makeridges(facet1);
2331 qh_makeridges(facet2);
2332 if (qh IStracing >=4)
2333 qh_errprint("MERGING", facet1, facet2, NULL, NULL);
2334 if (mindist) {
2335 maximize_(qh max_outside, *maxdist);
2336 maximize_(qh max_vertex, *maxdist);
2337 #if qh_MAXoutside
2338 maximize_(facet2->maxoutside, *maxdist);
2339 #endif
2340 minimize_(qh min_vertex, *mindist);
2341 if (!facet2->keepcentrum
2342 && (*maxdist > qh WIDEfacet || *mindist < -qh WIDEfacet)) {
2343 facet2->keepcentrum= True;
2344 zinc_(Zwidefacet);
2345 }
2346 }
2347 nummerge= facet1->nummerge + facet2->nummerge + 1;
2348 if (nummerge >= qh_MAXnummerge)
2349 facet2->nummerge= qh_MAXnummerge;
2350 else
2351 facet2->nummerge= (short unsigned int)nummerge;
2352 facet2->newmerge= True;
2353 facet2->dupridge= False;
2354 qh_updatetested (facet1, facet2);
2355 if (qh hull_dim > 2 && qh_setsize(facet1->vertices) == qh hull_dim)
2356 qh_mergesimplex(facet1, facet2, mergeapex);
2357 else {
2358 qh vertex_visit++;
2359 FOREACHvertex_(facet2->vertices)
2360 vertex->visitid= qh vertex_visit;
2361 if (qh hull_dim == 2)
2362 qh_mergefacet2d(facet1, facet2);
2363 else {
2364 qh_mergeneighbors(facet1, facet2);
2365 qh_mergevertices(facet1->vertices, &facet2->vertices);
2366 }
2367 qh_mergeridges(facet1, facet2);
2368 qh_mergevertex_neighbors(facet1, facet2);
2369 if (!facet2->newfacet)
2370 qh_newvertices(facet2->vertices);
2371 }
2372 if (!mergeapex)
2373 qh_degen_redundant_neighbors(facet2, facet1);
2374 if (facet2->coplanar || !facet2->newfacet) {
2375 zinc_(Zmergeintohorizon);
2376 }else if (!facet1->newfacet && facet2->newfacet) {
2377 zinc_(Zmergehorizon);
2378 }else {
2379 zinc_(Zmergenew);
2380 }
2381 qh_willdelete(facet1, facet2);
2382 qh_removefacet(facet2); /* append as a newfacet to end of qh facet_list */
2383 qh_appendfacet(facet2);
2384 facet2->newfacet= True;
2385 facet2->tested= False;
2386 qh_tracemerge(facet1, facet2);
2387 if (traceonce) {
2388 qh_fprintf(qh ferr, 8080, "qh_mergefacet: end of wide tracing\n");
2389 qh IStracing= tracerestore;
2390 }
2391 } /* mergefacet */
2392
2393
2394 /*-<a href="qh-merge.htm#TOC"
2395 >-------------------------------</a><a name="mergefacet2d">-</a>
2396
2397 qh_mergefacet2d( facet1, facet2 )
2398 in 2d, merges neighbors and vertices of facet1 into facet2
2399
2400 returns:
2401 build ridges for neighbors if necessary
2402 facet2 looks like a simplicial facet except for centrum, ridges
2403 neighbors are opposite the corresponding vertex
2404 maintains orientation of facet2
2405
2406 notes:
2407 qh_mergefacet() retains non-simplicial structures
2408 they are not needed in 2d, but later routines may use them
2409 preserves qh.vertex_visit for qh_mergevertex_neighbors()
2410
2411 design:
2412 get vertices and neighbors
2413 determine new vertices and neighbors
2414 set new vertices and neighbors and adjust orientation
2415 make ridges for new neighbor if needed
2416 */
qh_mergefacet2d(facetT * facet1,facetT * facet2)2417 void qh_mergefacet2d(facetT *facet1, facetT *facet2) {
2418 vertexT *vertex1A, *vertex1B, *vertex2A, *vertex2B, *vertexA, *vertexB;
2419 facetT *neighbor1A, *neighbor1B, *neighbor2A, *neighbor2B, *neighborA, *neighborB;
2420
2421 vertex1A= SETfirstt_(facet1->vertices, vertexT);
2422 vertex1B= SETsecondt_(facet1->vertices, vertexT);
2423 vertex2A= SETfirstt_(facet2->vertices, vertexT);
2424 vertex2B= SETsecondt_(facet2->vertices, vertexT);
2425 neighbor1A= SETfirstt_(facet1->neighbors, facetT);
2426 neighbor1B= SETsecondt_(facet1->neighbors, facetT);
2427 neighbor2A= SETfirstt_(facet2->neighbors, facetT);
2428 neighbor2B= SETsecondt_(facet2->neighbors, facetT);
2429 if (vertex1A == vertex2A) {
2430 vertexA= vertex1B;
2431 vertexB= vertex2B;
2432 neighborA= neighbor2A;
2433 neighborB= neighbor1A;
2434 }else if (vertex1A == vertex2B) {
2435 vertexA= vertex1B;
2436 vertexB= vertex2A;
2437 neighborA= neighbor2B;
2438 neighborB= neighbor1A;
2439 }else if (vertex1B == vertex2A) {
2440 vertexA= vertex1A;
2441 vertexB= vertex2B;
2442 neighborA= neighbor2A;
2443 neighborB= neighbor1B;
2444 }else { /* 1B == 2B */
2445 vertexA= vertex1A;
2446 vertexB= vertex2A;
2447 neighborA= neighbor2B;
2448 neighborB= neighbor1B;
2449 }
2450 /* vertexB always from facet2, neighborB always from facet1 */
2451 if (vertexA->id > vertexB->id) {
2452 SETfirst_(facet2->vertices)= vertexA;
2453 SETsecond_(facet2->vertices)= vertexB;
2454 if (vertexB == vertex2A)
2455 facet2->toporient= !facet2->toporient;
2456 SETfirst_(facet2->neighbors)= neighborA;
2457 SETsecond_(facet2->neighbors)= neighborB;
2458 }else {
2459 SETfirst_(facet2->vertices)= vertexB;
2460 SETsecond_(facet2->vertices)= vertexA;
2461 if (vertexB == vertex2B)
2462 facet2->toporient= !facet2->toporient;
2463 SETfirst_(facet2->neighbors)= neighborB;
2464 SETsecond_(facet2->neighbors)= neighborA;
2465 }
2466 qh_makeridges(neighborB);
2467 qh_setreplace(neighborB->neighbors, facet1, facet2);
2468 trace4((qh ferr, 4036, "qh_mergefacet2d: merged v%d and neighbor f%d of f%d into f%d\n",
2469 vertexA->id, neighborB->id, facet1->id, facet2->id));
2470 } /* mergefacet2d */
2471
2472
2473 /*-<a href="qh-merge.htm#TOC"
2474 >-------------------------------</a><a name="mergeneighbors">-</a>
2475
2476 qh_mergeneighbors( facet1, facet2 )
2477 merges the neighbors of facet1 into facet2
2478
2479 see:
2480 qh_mergecycle_neighbors()
2481
2482 design:
2483 for each neighbor of facet1
2484 if neighbor is also a neighbor of facet2
2485 if neighbor is simpilicial
2486 make ridges for later deletion as a degenerate facet
2487 update its neighbor set
2488 else
2489 move the neighbor relation to facet2
2490 remove the neighbor relation for facet1 and facet2
2491 */
qh_mergeneighbors(facetT * facet1,facetT * facet2)2492 void qh_mergeneighbors(facetT *facet1, facetT *facet2) {
2493 facetT *neighbor, **neighborp;
2494
2495 trace4((qh ferr, 4037, "qh_mergeneighbors: merge neighbors of f%d and f%d\n",
2496 facet1->id, facet2->id));
2497 qh visit_id++;
2498 FOREACHneighbor_(facet2) {
2499 neighbor->visitid= qh visit_id;
2500 }
2501 FOREACHneighbor_(facet1) {
2502 if (neighbor->visitid == qh visit_id) {
2503 if (neighbor->simplicial) /* is degen, needs ridges */
2504 qh_makeridges(neighbor);
2505 if (SETfirstt_(neighbor->neighbors, facetT) != facet1) /*keep newfacet->horizon*/
2506 qh_setdel(neighbor->neighbors, facet1);
2507 else {
2508 qh_setdel(neighbor->neighbors, facet2);
2509 qh_setreplace(neighbor->neighbors, facet1, facet2);
2510 }
2511 }else if (neighbor != facet2) {
2512 qh_setappend(&(facet2->neighbors), neighbor);
2513 qh_setreplace(neighbor->neighbors, facet1, facet2);
2514 }
2515 }
2516 qh_setdel(facet1->neighbors, facet2); /* here for makeridges */
2517 qh_setdel(facet2->neighbors, facet1);
2518 } /* mergeneighbors */
2519
2520
2521 /*-<a href="qh-merge.htm#TOC"
2522 >-------------------------------</a><a name="mergeridges">-</a>
2523
2524 qh_mergeridges( facet1, facet2 )
2525 merges the ridge set of facet1 into facet2
2526
2527 returns:
2528 may delete all ridges for a vertex
2529 sets vertex->delridge on deleted ridges
2530
2531 see:
2532 qh_mergecycle_ridges()
2533
2534 design:
2535 delete ridges between facet1 and facet2
2536 mark (delridge) vertices on these ridges for later testing
2537 for each remaining ridge
2538 rename facet1 to facet2
2539 */
qh_mergeridges(facetT * facet1,facetT * facet2)2540 void qh_mergeridges(facetT *facet1, facetT *facet2) {
2541 ridgeT *ridge, **ridgep;
2542 vertexT *vertex, **vertexp;
2543
2544 trace4((qh ferr, 4038, "qh_mergeridges: merge ridges of f%d and f%d\n",
2545 facet1->id, facet2->id));
2546 FOREACHridge_(facet2->ridges) {
2547 if ((ridge->top == facet1) || (ridge->bottom == facet1)) {
2548 FOREACHvertex_(ridge->vertices)
2549 vertex->delridge= True;
2550 qh_delridge(ridge); /* expensive in high-d, could rebuild */
2551 ridgep--; /*repeat*/
2552 }
2553 }
2554 FOREACHridge_(facet1->ridges) {
2555 if (ridge->top == facet1)
2556 ridge->top= facet2;
2557 else
2558 ridge->bottom= facet2;
2559 qh_setappend(&(facet2->ridges), ridge);
2560 }
2561 } /* mergeridges */
2562
2563
2564 /*-<a href="qh-merge.htm#TOC"
2565 >-------------------------------</a><a name="mergesimplex">-</a>
2566
2567 qh_mergesimplex( facet1, facet2, mergeapex )
2568 merge simplicial facet1 into facet2
2569 mergeapex==qh_MERGEapex if merging samecycle into horizon facet
2570 vertex id is latest (most recently created)
2571 facet1 may be contained in facet2
2572 ridges exist for both facets
2573
2574 returns:
2575 facet2 with updated vertices, ridges, neighbors
2576 updated neighbors for facet1's vertices
2577 facet1 not deleted
2578 sets vertex->delridge on deleted ridges
2579
2580 notes:
2581 special case code since this is the most common merge
2582 called from qh_mergefacet()
2583
2584 design:
2585 if qh_MERGEapex
2586 add vertices of facet2 to qh.new_vertexlist if necessary
2587 add apex to facet2
2588 else
2589 for each ridge between facet1 and facet2
2590 set vertex->delridge
2591 determine the apex for facet1 (i.e., vertex to be merged)
2592 unless apex already in facet2
2593 insert apex into vertices for facet2
2594 add vertices of facet2 to qh.new_vertexlist if necessary
2595 add apex to qh.new_vertexlist if necessary
2596 for each vertex of facet1
2597 if apex
2598 rename facet1 to facet2 in its vertex neighbors
2599 else
2600 delete facet1 from vertex neighors
2601 if only in facet2
2602 add vertex to qh.del_vertices for later deletion
2603 for each ridge of facet1
2604 delete ridges between facet1 and facet2
2605 append other ridges to facet2 after renaming facet to facet2
2606 */
qh_mergesimplex(facetT * facet1,facetT * facet2,boolT mergeapex)2607 void qh_mergesimplex(facetT *facet1, facetT *facet2, boolT mergeapex) {
2608 vertexT *vertex, **vertexp, *apex;
2609 ridgeT *ridge, **ridgep;
2610 boolT issubset= False;
2611 int vertex_i= -1, vertex_n;
2612 facetT *neighbor, **neighborp, *otherfacet;
2613
2614 if (mergeapex) {
2615 if (!facet2->newfacet)
2616 qh_newvertices(facet2->vertices); /* apex is new */
2617 apex= SETfirstt_(facet1->vertices, vertexT);
2618 if (SETfirstt_(facet2->vertices, vertexT) != apex)
2619 qh_setaddnth(&facet2->vertices, 0, apex); /* apex has last id */
2620 else
2621 issubset= True;
2622 }else {
2623 zinc_(Zmergesimplex);
2624 FOREACHvertex_(facet1->vertices)
2625 vertex->seen= False;
2626 FOREACHridge_(facet1->ridges) {
2627 if (otherfacet_(ridge, facet1) == facet2) {
2628 FOREACHvertex_(ridge->vertices) {
2629 vertex->seen= True;
2630 vertex->delridge= True;
2631 }
2632 break;
2633 }
2634 }
2635 FOREACHvertex_(facet1->vertices) {
2636 if (!vertex->seen)
2637 break; /* must occur */
2638 }
2639 apex= vertex;
2640 trace4((qh ferr, 4039, "qh_mergesimplex: merge apex v%d of f%d into facet f%d\n",
2641 apex->id, facet1->id, facet2->id));
2642 FOREACHvertex_i_(facet2->vertices) {
2643 if (vertex->id < apex->id) {
2644 break;
2645 }else if (vertex->id == apex->id) {
2646 issubset= True;
2647 break;
2648 }
2649 }
2650 if (!issubset)
2651 qh_setaddnth(&facet2->vertices, vertex_i, apex);
2652 if (!facet2->newfacet)
2653 qh_newvertices(facet2->vertices);
2654 else if (!apex->newlist) {
2655 qh_removevertex(apex);
2656 qh_appendvertex(apex);
2657 }
2658 }
2659 trace4((qh ferr, 4040, "qh_mergesimplex: update vertex neighbors of f%d\n",
2660 facet1->id));
2661 FOREACHvertex_(facet1->vertices) {
2662 if (vertex == apex && !issubset)
2663 qh_setreplace(vertex->neighbors, facet1, facet2);
2664 else {
2665 qh_setdel(vertex->neighbors, facet1);
2666 if (!SETsecond_(vertex->neighbors))
2667 qh_mergevertex_del(vertex, facet1, facet2);
2668 }
2669 }
2670 trace4((qh ferr, 4041, "qh_mergesimplex: merge ridges and neighbors of f%d into f%d\n",
2671 facet1->id, facet2->id));
2672 qh visit_id++;
2673 FOREACHneighbor_(facet2)
2674 neighbor->visitid= qh visit_id;
2675 FOREACHridge_(facet1->ridges) {
2676 otherfacet= otherfacet_(ridge, facet1);
2677 if (otherfacet == facet2) {
2678 qh_setdel(facet2->ridges, ridge);
2679 qh_setfree(&(ridge->vertices));
2680 qh_memfree(ridge, (int)sizeof(ridgeT));
2681 qh_setdel(facet2->neighbors, facet1);
2682 }else {
2683 qh_setappend(&facet2->ridges, ridge);
2684 if (otherfacet->visitid != qh visit_id) {
2685 qh_setappend(&facet2->neighbors, otherfacet);
2686 qh_setreplace(otherfacet->neighbors, facet1, facet2);
2687 otherfacet->visitid= qh visit_id;
2688 }else {
2689 if (otherfacet->simplicial) /* is degen, needs ridges */
2690 qh_makeridges(otherfacet);
2691 if (SETfirstt_(otherfacet->neighbors, facetT) != facet1)
2692 qh_setdel(otherfacet->neighbors, facet1);
2693 else { /*keep newfacet->neighbors->horizon*/
2694 qh_setdel(otherfacet->neighbors, facet2);
2695 qh_setreplace(otherfacet->neighbors, facet1, facet2);
2696 }
2697 }
2698 if (ridge->top == facet1) /* wait until after qh_makeridges */
2699 ridge->top= facet2;
2700 else
2701 ridge->bottom= facet2;
2702 }
2703 }
2704 SETfirst_(facet1->ridges)= NULL; /* it will be deleted */
2705 trace3((qh ferr, 3006, "qh_mergesimplex: merged simplex f%d apex v%d into facet f%d\n",
2706 facet1->id, getid_(apex), facet2->id));
2707 } /* mergesimplex */
2708
2709 /*-<a href="qh-merge.htm#TOC"
2710 >-------------------------------</a><a name="mergevertex_del">-</a>
2711
2712 qh_mergevertex_del( vertex, facet1, facet2 )
2713 delete a vertex because of merging facet1 into facet2
2714
2715 returns:
2716 deletes vertex from facet2
2717 adds vertex to qh.del_vertices for later deletion
2718 */
qh_mergevertex_del(vertexT * vertex,facetT * facet1,facetT * facet2)2719 void qh_mergevertex_del(vertexT *vertex, facetT *facet1, facetT *facet2) {
2720
2721 zinc_(Zmergevertex);
2722 trace2((qh ferr, 2035, "qh_mergevertex_del: deleted v%d when merging f%d into f%d\n",
2723 vertex->id, facet1->id, facet2->id));
2724 qh_setdelsorted(facet2->vertices, vertex);
2725 vertex->deleted= True;
2726 qh_setappend(&qh del_vertices, vertex);
2727 } /* mergevertex_del */
2728
2729 /*-<a href="qh-merge.htm#TOC"
2730 >-------------------------------</a><a name="mergevertex_neighbors">-</a>
2731
2732 qh_mergevertex_neighbors( facet1, facet2 )
2733 merge the vertex neighbors of facet1 to facet2
2734
2735 returns:
2736 if vertex is current qh.vertex_visit
2737 deletes facet1 from vertex->neighbors
2738 else
2739 renames facet1 to facet2 in vertex->neighbors
2740 deletes vertices if only one neighbor
2741
2742 notes:
2743 assumes vertex neighbor sets are good
2744 */
qh_mergevertex_neighbors(facetT * facet1,facetT * facet2)2745 void qh_mergevertex_neighbors(facetT *facet1, facetT *facet2) {
2746 vertexT *vertex, **vertexp;
2747
2748 trace4((qh ferr, 4042, "qh_mergevertex_neighbors: merge vertex neighbors of f%d and f%d\n",
2749 facet1->id, facet2->id));
2750 if (qh tracevertex) {
2751 qh_fprintf(qh ferr, 8081, "qh_mergevertex_neighbors: of f%d and f%d at furthest p%d f0= %p\n",
2752 facet1->id, facet2->id, qh furthest_id, qh tracevertex->neighbors->e[0].p);
2753 qh_errprint("TRACE", NULL, NULL, NULL, qh tracevertex);
2754 }
2755 FOREACHvertex_(facet1->vertices) {
2756 if (vertex->visitid != qh vertex_visit)
2757 qh_setreplace(vertex->neighbors, facet1, facet2);
2758 else {
2759 qh_setdel(vertex->neighbors, facet1);
2760 if (!SETsecond_(vertex->neighbors))
2761 qh_mergevertex_del(vertex, facet1, facet2);
2762 }
2763 }
2764 if (qh tracevertex)
2765 qh_errprint("TRACE", NULL, NULL, NULL, qh tracevertex);
2766 } /* mergevertex_neighbors */
2767
2768
2769 /*-<a href="qh-merge.htm#TOC"
2770 >-------------------------------</a><a name="mergevertices">-</a>
2771
2772 qh_mergevertices( vertices1, vertices2 )
2773 merges the vertex set of facet1 into facet2
2774
2775 returns:
2776 replaces vertices2 with merged set
2777 preserves vertex_visit for qh_mergevertex_neighbors
2778 updates qh.newvertex_list
2779
2780 design:
2781 create a merged set of both vertices (in inverse id order)
2782 */
qh_mergevertices(setT * vertices1,setT ** vertices2)2783 void qh_mergevertices(setT *vertices1, setT **vertices2) {
2784 int newsize= qh_setsize(vertices1)+qh_setsize(*vertices2) - qh hull_dim + 1;
2785 setT *mergedvertices;
2786 vertexT *vertex, **vertexp, **vertex2= SETaddr_(*vertices2, vertexT);
2787
2788 mergedvertices= qh_settemp(newsize);
2789 FOREACHvertex_(vertices1) {
2790 if (!*vertex2 || vertex->id > (*vertex2)->id)
2791 qh_setappend(&mergedvertices, vertex);
2792 else {
2793 while (*vertex2 && (*vertex2)->id > vertex->id)
2794 qh_setappend(&mergedvertices, *vertex2++);
2795 if (!*vertex2 || (*vertex2)->id < vertex->id)
2796 qh_setappend(&mergedvertices, vertex);
2797 else
2798 qh_setappend(&mergedvertices, *vertex2++);
2799 }
2800 }
2801 while (*vertex2)
2802 qh_setappend(&mergedvertices, *vertex2++);
2803 if (newsize < qh_setsize(mergedvertices)) {
2804 qh_fprintf(qh ferr, 6100, "qhull internal error (qh_mergevertices): facets did not share a ridge\n");
2805 qh_errexit(qh_ERRqhull, NULL, NULL);
2806 }
2807 qh_setfree(vertices2);
2808 *vertices2= mergedvertices;
2809 qh_settemppop();
2810 } /* mergevertices */
2811
2812
2813 /*-<a href="qh-merge.htm#TOC"
2814 >-------------------------------</a><a name="neighbor_intersections">-</a>
2815
2816 qh_neighbor_intersections( vertex )
2817 return intersection of all vertices in vertex->neighbors except for vertex
2818
2819 returns:
2820 returns temporary set of vertices
2821 does not include vertex
2822 NULL if a neighbor is simplicial
2823 NULL if empty set
2824
2825 notes:
2826 used for renaming vertices
2827
2828 design:
2829 initialize the intersection set with vertices of the first two neighbors
2830 delete vertex from the intersection
2831 for each remaining neighbor
2832 intersect its vertex set with the intersection set
2833 return NULL if empty
2834 return the intersection set
2835 */
qh_neighbor_intersections(vertexT * vertex)2836 setT *qh_neighbor_intersections(vertexT *vertex) {
2837 facetT *neighbor, **neighborp, *neighborA, *neighborB;
2838 setT *intersect;
2839 int neighbor_i, neighbor_n;
2840
2841 FOREACHneighbor_(vertex) {
2842 if (neighbor->simplicial)
2843 return NULL;
2844 }
2845 neighborA= SETfirstt_(vertex->neighbors, facetT);
2846 neighborB= SETsecondt_(vertex->neighbors, facetT);
2847 zinc_(Zintersectnum);
2848 if (!neighborA)
2849 return NULL;
2850 if (!neighborB)
2851 intersect= qh_setcopy(neighborA->vertices, 0);
2852 else
2853 intersect= qh_vertexintersect_new(neighborA->vertices, neighborB->vertices);
2854 qh_settemppush(intersect);
2855 qh_setdelsorted(intersect, vertex);
2856 FOREACHneighbor_i_(vertex) {
2857 if (neighbor_i >= 2) {
2858 zinc_(Zintersectnum);
2859 qh_vertexintersect(&intersect, neighbor->vertices);
2860 if (!SETfirst_(intersect)) {
2861 zinc_(Zintersectfail);
2862 qh_settempfree(&intersect);
2863 return NULL;
2864 }
2865 }
2866 }
2867 trace3((qh ferr, 3007, "qh_neighbor_intersections: %d vertices in neighbor intersection of v%d\n",
2868 qh_setsize(intersect), vertex->id));
2869 return intersect;
2870 } /* neighbor_intersections */
2871
2872 /*-<a href="qh-merge.htm#TOC"
2873 >-------------------------------</a><a name="newvertices">-</a>
2874
2875 qh_newvertices( vertices )
2876 add vertices to end of qh.vertex_list (marks as new vertices)
2877
2878 returns:
2879 vertices on qh.newvertex_list
2880 vertex->newlist set
2881 */
qh_newvertices(setT * vertices)2882 void qh_newvertices(setT *vertices) {
2883 vertexT *vertex, **vertexp;
2884
2885 FOREACHvertex_(vertices) {
2886 if (!vertex->newlist) {
2887 qh_removevertex(vertex);
2888 qh_appendvertex(vertex);
2889 }
2890 }
2891 } /* newvertices */
2892
2893 /*-<a href="qh-merge.htm#TOC"
2894 >-------------------------------</a><a name="reducevertices">-</a>
2895
2896 qh_reducevertices()
2897 reduce extra vertices, shared vertices, and redundant vertices
2898 facet->newmerge is set if merged since last call
2899 if !qh.MERGEvertices, only removes extra vertices
2900
2901 returns:
2902 True if also merged degen_redundant facets
2903 vertices are renamed if possible
2904 clears facet->newmerge and vertex->delridge
2905
2906 notes:
2907 ignored if 2-d
2908
2909 design:
2910 merge any degenerate or redundant facets
2911 for each newly merged facet
2912 remove extra vertices
2913 if qh.MERGEvertices
2914 for each newly merged facet
2915 for each vertex
2916 if vertex was on a deleted ridge
2917 rename vertex if it is shared
2918 remove delridge flag from new vertices
2919 */
qh_reducevertices(void)2920 boolT qh_reducevertices(void) {
2921 int numshare=0, numrename= 0;
2922 boolT degenredun= False;
2923 facetT *newfacet;
2924 vertexT *vertex, **vertexp;
2925
2926 if (qh hull_dim == 2)
2927 return False;
2928 if (qh_merge_degenredundant())
2929 degenredun= True;
2930 LABELrestart:
2931 FORALLnew_facets {
2932 if (newfacet->newmerge) {
2933 if (!qh MERGEvertices)
2934 newfacet->newmerge= False;
2935 qh_remove_extravertices(newfacet);
2936 }
2937 }
2938 if (!qh MERGEvertices)
2939 return False;
2940 FORALLnew_facets {
2941 if (newfacet->newmerge) {
2942 newfacet->newmerge= False;
2943 FOREACHvertex_(newfacet->vertices) {
2944 if (vertex->delridge) {
2945 if (qh_rename_sharedvertex(vertex, newfacet)) {
2946 numshare++;
2947 vertexp--; /* repeat since deleted vertex */
2948 }
2949 }
2950 }
2951 }
2952 }
2953 FORALLvertex_(qh newvertex_list) {
2954 if (vertex->delridge && !vertex->deleted) {
2955 vertex->delridge= False;
2956 if (qh hull_dim >= 4 && qh_redundant_vertex(vertex)) {
2957 numrename++;
2958 if (qh_merge_degenredundant()) {
2959 degenredun= True;
2960 goto LABELrestart;
2961 }
2962 }
2963 }
2964 }
2965 trace1((qh ferr, 1014, "qh_reducevertices: renamed %d shared vertices and %d redundant vertices. Degen? %d\n",
2966 numshare, numrename, degenredun));
2967 return degenredun;
2968 } /* reducevertices */
2969
2970 /*-<a href="qh-merge.htm#TOC"
2971 >-------------------------------</a><a name="redundant_vertex">-</a>
2972
2973 qh_redundant_vertex( vertex )
2974 detect and rename a redundant vertex
2975 vertices have full vertex->neighbors
2976
2977 returns:
2978 returns true if find a redundant vertex
2979 deletes vertex(vertex->deleted)
2980
2981 notes:
2982 only needed if vertex->delridge and hull_dim >= 4
2983 may add degenerate facets to qh.facet_mergeset
2984 doesn't change vertex->neighbors or create redundant facets
2985
2986 design:
2987 intersect vertices of all facet neighbors of vertex
2988 determine ridges for these vertices
2989 if find a new vertex for vertex amoung these ridges and vertices
2990 rename vertex to the new vertex
2991 */
qh_redundant_vertex(vertexT * vertex)2992 vertexT *qh_redundant_vertex(vertexT *vertex) {
2993 vertexT *newvertex= NULL;
2994 setT *vertices, *ridges;
2995
2996 trace3((qh ferr, 3008, "qh_redundant_vertex: check if v%d can be renamed\n", vertex->id));
2997 if ((vertices= qh_neighbor_intersections(vertex))) {
2998 ridges= qh_vertexridges(vertex);
2999 if ((newvertex= qh_find_newvertex(vertex, vertices, ridges)))
3000 qh_renamevertex(vertex, newvertex, ridges, NULL, NULL);
3001 qh_settempfree(&ridges);
3002 qh_settempfree(&vertices);
3003 }
3004 return newvertex;
3005 } /* redundant_vertex */
3006
3007 /*-<a href="qh-merge.htm#TOC"
3008 >-------------------------------</a><a name="remove_extravertices">-</a>
3009
3010 qh_remove_extravertices( facet )
3011 remove extra vertices from non-simplicial facets
3012
3013 returns:
3014 returns True if it finds them
3015
3016 design:
3017 for each vertex in facet
3018 if vertex not in a ridge (i.e., no longer used)
3019 delete vertex from facet
3020 delete facet from vertice's neighbors
3021 unless vertex in another facet
3022 add vertex to qh.del_vertices for later deletion
3023 */
qh_remove_extravertices(facetT * facet)3024 boolT qh_remove_extravertices(facetT *facet) {
3025 ridgeT *ridge, **ridgep;
3026 vertexT *vertex, **vertexp;
3027 boolT foundrem= False;
3028
3029 trace4((qh ferr, 4043, "qh_remove_extravertices: test f%d for extra vertices\n",
3030 facet->id));
3031 FOREACHvertex_(facet->vertices)
3032 vertex->seen= False;
3033 FOREACHridge_(facet->ridges) {
3034 FOREACHvertex_(ridge->vertices)
3035 vertex->seen= True;
3036 }
3037 FOREACHvertex_(facet->vertices) {
3038 if (!vertex->seen) {
3039 foundrem= True;
3040 zinc_(Zremvertex);
3041 qh_setdelsorted(facet->vertices, vertex);
3042 qh_setdel(vertex->neighbors, facet);
3043 if (!qh_setsize(vertex->neighbors)) {
3044 vertex->deleted= True;
3045 qh_setappend(&qh del_vertices, vertex);
3046 zinc_(Zremvertexdel);
3047 trace2((qh ferr, 2036, "qh_remove_extravertices: v%d deleted because it's lost all ridges\n", vertex->id));
3048 }else
3049 trace3((qh ferr, 3009, "qh_remove_extravertices: v%d removed from f%d because it's lost all ridges\n", vertex->id, facet->id));
3050 vertexp--; /*repeat*/
3051 }
3052 }
3053 return foundrem;
3054 } /* remove_extravertices */
3055
3056 /*-<a href="qh-merge.htm#TOC"
3057 >-------------------------------</a><a name="rename_sharedvertex">-</a>
3058
3059 qh_rename_sharedvertex( vertex, facet )
3060 detect and rename if shared vertex in facet
3061 vertices have full ->neighbors
3062
3063 returns:
3064 newvertex or NULL
3065 the vertex may still exist in other facets (i.e., a neighbor was pinched)
3066 does not change facet->neighbors
3067 updates vertex->neighbors
3068
3069 notes:
3070 a shared vertex for a facet is only in ridges to one neighbor
3071 this may undo a pinched facet
3072
3073 it does not catch pinches involving multiple facets. These appear
3074 to be difficult to detect, since an exhaustive search is too expensive.
3075
3076 design:
3077 if vertex only has two neighbors
3078 determine the ridges that contain the vertex
3079 determine the vertices shared by both neighbors
3080 if can find a new vertex in this set
3081 rename the vertex to the new vertex
3082 */
qh_rename_sharedvertex(vertexT * vertex,facetT * facet)3083 vertexT *qh_rename_sharedvertex(vertexT *vertex, facetT *facet) {
3084 facetT *neighbor, **neighborp, *neighborA= NULL;
3085 setT *vertices, *ridges;
3086 vertexT *newvertex;
3087
3088 if (qh_setsize(vertex->neighbors) == 2) {
3089 neighborA= SETfirstt_(vertex->neighbors, facetT);
3090 if (neighborA == facet)
3091 neighborA= SETsecondt_(vertex->neighbors, facetT);
3092 }else if (qh hull_dim == 3)
3093 return NULL;
3094 else {
3095 qh visit_id++;
3096 FOREACHneighbor_(facet)
3097 neighbor->visitid= qh visit_id;
3098 FOREACHneighbor_(vertex) {
3099 if (neighbor->visitid == qh visit_id) {
3100 if (neighborA)
3101 return NULL;
3102 neighborA= neighbor;
3103 }
3104 }
3105 if (!neighborA) {
3106 qh_fprintf(qh ferr, 6101, "qhull internal error (qh_rename_sharedvertex): v%d's neighbors not in f%d\n",
3107 vertex->id, facet->id);
3108 qh_errprint("ERRONEOUS", facet, NULL, NULL, vertex);
3109 qh_errexit(qh_ERRqhull, NULL, NULL);
3110 }
3111 }
3112 /* the vertex is shared by facet and neighborA */
3113 ridges= qh_settemp(qh TEMPsize);
3114 neighborA->visitid= ++qh visit_id;
3115 qh_vertexridges_facet(vertex, facet, &ridges);
3116 trace2((qh ferr, 2037, "qh_rename_sharedvertex: p%d(v%d) is shared by f%d(%d ridges) and f%d\n",
3117 qh_pointid(vertex->point), vertex->id, facet->id, qh_setsize(ridges), neighborA->id));
3118 zinc_(Zintersectnum);
3119 vertices= qh_vertexintersect_new(facet->vertices, neighborA->vertices);
3120 qh_setdel(vertices, vertex);
3121 qh_settemppush(vertices);
3122 if ((newvertex= qh_find_newvertex(vertex, vertices, ridges)))
3123 qh_renamevertex(vertex, newvertex, ridges, facet, neighborA);
3124 qh_settempfree(&vertices);
3125 qh_settempfree(&ridges);
3126 return newvertex;
3127 } /* rename_sharedvertex */
3128
3129 /*-<a href="qh-merge.htm#TOC"
3130 >-------------------------------</a><a name="renameridgevertex">-</a>
3131
3132 qh_renameridgevertex( ridge, oldvertex, newvertex )
3133 renames oldvertex as newvertex in ridge
3134
3135 returns:
3136
3137 design:
3138 delete oldvertex from ridge
3139 if newvertex already in ridge
3140 copy ridge->noconvex to another ridge if possible
3141 delete the ridge
3142 else
3143 insert newvertex into the ridge
3144 adjust the ridge's orientation
3145 */
qh_renameridgevertex(ridgeT * ridge,vertexT * oldvertex,vertexT * newvertex)3146 void qh_renameridgevertex(ridgeT *ridge, vertexT *oldvertex, vertexT *newvertex) {
3147 int nth= 0, oldnth;
3148 facetT *temp;
3149 vertexT *vertex, **vertexp;
3150
3151 oldnth= qh_setindex(ridge->vertices, oldvertex);
3152 qh_setdelnthsorted(ridge->vertices, oldnth);
3153 FOREACHvertex_(ridge->vertices) {
3154 if (vertex == newvertex) {
3155 zinc_(Zdelridge);
3156 if (ridge->nonconvex) /* only one ridge has nonconvex set */
3157 qh_copynonconvex(ridge);
3158 qh_delridge(ridge);
3159 trace2((qh ferr, 2038, "qh_renameridgevertex: ridge r%d deleted. It contained both v%d and v%d\n",
3160 ridge->id, oldvertex->id, newvertex->id));
3161 return;
3162 }
3163 if (vertex->id < newvertex->id)
3164 break;
3165 nth++;
3166 }
3167 qh_setaddnth(&ridge->vertices, nth, newvertex);
3168 if (abs(oldnth - nth)%2) {
3169 trace3((qh ferr, 3010, "qh_renameridgevertex: swapped the top and bottom of ridge r%d\n",
3170 ridge->id));
3171 temp= ridge->top;
3172 ridge->top= ridge->bottom;
3173 ridge->bottom= temp;
3174 }
3175 } /* renameridgevertex */
3176
3177
3178 /*-<a href="qh-merge.htm#TOC"
3179 >-------------------------------</a><a name="renamevertex">-</a>
3180
3181 qh_renamevertex( oldvertex, newvertex, ridges, oldfacet, neighborA )
3182 renames oldvertex as newvertex in ridges
3183 gives oldfacet/neighborA if oldvertex is shared between two facets
3184
3185 returns:
3186 oldvertex may still exist afterwards
3187
3188
3189 notes:
3190 can not change neighbors of newvertex (since it's a subset)
3191
3192 design:
3193 for each ridge in ridges
3194 rename oldvertex to newvertex and delete degenerate ridges
3195 if oldfacet not defined
3196 for each neighbor of oldvertex
3197 delete oldvertex from neighbor's vertices
3198 remove extra vertices from neighbor
3199 add oldvertex to qh.del_vertices
3200 else if oldvertex only between oldfacet and neighborA
3201 delete oldvertex from oldfacet and neighborA
3202 add oldvertex to qh.del_vertices
3203 else oldvertex is in oldfacet and neighborA and other facets (i.e., pinched)
3204 delete oldvertex from oldfacet
3205 delete oldfacet from oldvertice's neighbors
3206 remove extra vertices (e.g., oldvertex) from neighborA
3207 */
qh_renamevertex(vertexT * oldvertex,vertexT * newvertex,setT * ridges,facetT * oldfacet,facetT * neighborA)3208 void qh_renamevertex(vertexT *oldvertex, vertexT *newvertex, setT *ridges, facetT *oldfacet, facetT *neighborA) {
3209 facetT *neighbor, **neighborp;
3210 ridgeT *ridge, **ridgep;
3211 boolT istrace= False;
3212
3213 if (qh IStracing >= 2 || oldvertex->id == qh tracevertex_id ||
3214 newvertex->id == qh tracevertex_id)
3215 istrace= True;
3216 FOREACHridge_(ridges)
3217 qh_renameridgevertex(ridge, oldvertex, newvertex);
3218 if (!oldfacet) {
3219 zinc_(Zrenameall);
3220 if (istrace)
3221 qh_fprintf(qh ferr, 8082, "qh_renamevertex: renamed v%d to v%d in several facets\n",
3222 oldvertex->id, newvertex->id);
3223 FOREACHneighbor_(oldvertex) {
3224 qh_maydropneighbor(neighbor);
3225 qh_setdelsorted(neighbor->vertices, oldvertex);
3226 if (qh_remove_extravertices(neighbor))
3227 neighborp--; /* neighbor may be deleted */
3228 }
3229 if (!oldvertex->deleted) {
3230 oldvertex->deleted= True;
3231 qh_setappend(&qh del_vertices, oldvertex);
3232 }
3233 }else if (qh_setsize(oldvertex->neighbors) == 2) {
3234 zinc_(Zrenameshare);
3235 if (istrace)
3236 qh_fprintf(qh ferr, 8083, "qh_renamevertex: renamed v%d to v%d in oldfacet f%d\n",
3237 oldvertex->id, newvertex->id, oldfacet->id);
3238 FOREACHneighbor_(oldvertex)
3239 qh_setdelsorted(neighbor->vertices, oldvertex);
3240 oldvertex->deleted= True;
3241 qh_setappend(&qh del_vertices, oldvertex);
3242 }else {
3243 zinc_(Zrenamepinch);
3244 if (istrace || qh IStracing)
3245 qh_fprintf(qh ferr, 8084, "qh_renamevertex: renamed pinched v%d to v%d between f%d and f%d\n",
3246 oldvertex->id, newvertex->id, oldfacet->id, neighborA->id);
3247 qh_setdelsorted(oldfacet->vertices, oldvertex);
3248 qh_setdel(oldvertex->neighbors, oldfacet);
3249 qh_remove_extravertices(neighborA);
3250 }
3251 } /* renamevertex */
3252
3253
3254 /*-<a href="qh-merge.htm#TOC"
3255 >-------------------------------</a><a name="test_appendmerge">-</a>
3256
3257 qh_test_appendmerge( facet, neighbor )
3258 tests facet/neighbor for convexity
3259 appends to mergeset if non-convex
3260 if pre-merging,
3261 nop if qh.SKIPconvex, or qh.MERGEexact and coplanar
3262
3263 returns:
3264 true if appends facet/neighbor to mergeset
3265 sets facet->center as needed
3266 does not change facet->seen
3267
3268 design:
3269 if qh.cos_max is defined
3270 if the angle between facet normals is too shallow
3271 append an angle-coplanar merge to qh.mergeset
3272 return True
3273 make facet's centrum if needed
3274 if facet's centrum is above the neighbor
3275 set isconcave
3276 else
3277 if facet's centrum is not below the neighbor
3278 set iscoplanar
3279 make neighbor's centrum if needed
3280 if neighbor's centrum is above the facet
3281 set isconcave
3282 else if neighbor's centrum is not below the facet
3283 set iscoplanar
3284 if isconcave or iscoplanar
3285 get angle if needed
3286 append concave or coplanar merge to qh.mergeset
3287 */
qh_test_appendmerge(facetT * facet,facetT * neighbor)3288 boolT qh_test_appendmerge(facetT *facet, facetT *neighbor) {
3289 realT dist, dist2= -REALmax, angle= -REALmax;
3290 boolT isconcave= False, iscoplanar= False, okangle= False;
3291
3292 if (qh SKIPconvex && !qh POSTmerging)
3293 return False;
3294 if ((!qh MERGEexact || qh POSTmerging) && qh cos_max < REALmax/2) {
3295 angle= qh_getangle(facet->normal, neighbor->normal);
3296 zinc_(Zangletests);
3297 if (angle > qh cos_max) {
3298 zinc_(Zcoplanarangle);
3299 qh_appendmergeset(facet, neighbor, MRGanglecoplanar, &angle);
3300 trace2((qh ferr, 2039, "qh_test_appendmerge: coplanar angle %4.4g between f%d and f%d\n",
3301 angle, facet->id, neighbor->id));
3302 return True;
3303 }else
3304 okangle= True;
3305 }
3306 if (!facet->center)
3307 facet->center= qh_getcentrum(facet);
3308 zzinc_(Zcentrumtests);
3309 qh_distplane(facet->center, neighbor, &dist);
3310 if (dist > qh centrum_radius)
3311 isconcave= True;
3312 else {
3313 if (dist > -qh centrum_radius)
3314 iscoplanar= True;
3315 if (!neighbor->center)
3316 neighbor->center= qh_getcentrum(neighbor);
3317 zzinc_(Zcentrumtests);
3318 qh_distplane(neighbor->center, facet, &dist2);
3319 if (dist2 > qh centrum_radius)
3320 isconcave= True;
3321 else if (!iscoplanar && dist2 > -qh centrum_radius)
3322 iscoplanar= True;
3323 }
3324 if (!isconcave && (!iscoplanar || (qh MERGEexact && !qh POSTmerging)))
3325 return False;
3326 if (!okangle && qh ANGLEmerge) {
3327 angle= qh_getangle(facet->normal, neighbor->normal);
3328 zinc_(Zangletests);
3329 }
3330 if (isconcave) {
3331 zinc_(Zconcaveridge);
3332 if (qh ANGLEmerge)
3333 angle += qh_ANGLEconcave + 0.5;
3334 qh_appendmergeset(facet, neighbor, MRGconcave, &angle);
3335 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",
3336 facet->id, neighbor->id, dist, dist2, angle, qh furthest_id));
3337 }else /* iscoplanar */ {
3338 zinc_(Zcoplanarcentrum);
3339 qh_appendmergeset(facet, neighbor, MRGcoplanar, &angle);
3340 trace2((qh ferr, 2040, "qh_test_appendmerge: coplanar f%d to f%d dist %4.4g, reverse dist %4.4g angle %4.4g\n",
3341 facet->id, neighbor->id, dist, dist2, angle));
3342 }
3343 return True;
3344 } /* test_appendmerge */
3345
3346 /*-<a href="qh-merge.htm#TOC"
3347 >-------------------------------</a><a name="test_vneighbors">-</a>
3348
3349 qh_test_vneighbors()
3350 test vertex neighbors for convexity
3351 tests all facets on qh.newfacet_list
3352
3353 returns:
3354 true if non-convex vneighbors appended to qh.facet_mergeset
3355 initializes vertex neighbors if needed
3356
3357 notes:
3358 assumes all facet neighbors have been tested
3359 this can be expensive
3360 this does not guarantee that a centrum is below all facets
3361 but it is unlikely
3362 uses qh.visit_id
3363
3364 design:
3365 build vertex neighbors if necessary
3366 for all new facets
3367 for all vertices
3368 for each unvisited facet neighbor of the vertex
3369 test new facet and neighbor for convexity
3370 */
qh_test_vneighbors(void)3371 boolT qh_test_vneighbors(void /* qh newfacet_list */) {
3372 facetT *newfacet, *neighbor, **neighborp;
3373 vertexT *vertex, **vertexp;
3374 int nummerges= 0;
3375
3376 trace1((qh ferr, 1015, "qh_test_vneighbors: testing vertex neighbors for convexity\n"));
3377 if (!qh VERTEXneighbors)
3378 qh_vertexneighbors();
3379 FORALLnew_facets
3380 newfacet->seen= False;
3381 FORALLnew_facets {
3382 newfacet->seen= True;
3383 newfacet->visitid= qh visit_id++;
3384 FOREACHneighbor_(newfacet)
3385 newfacet->visitid= qh visit_id;
3386 FOREACHvertex_(newfacet->vertices) {
3387 FOREACHneighbor_(vertex) {
3388 if (neighbor->seen || neighbor->visitid == qh visit_id)
3389 continue;
3390 if (qh_test_appendmerge(newfacet, neighbor))
3391 nummerges++;
3392 }
3393 }
3394 }
3395 zadd_(Ztestvneighbor, nummerges);
3396 trace1((qh ferr, 1016, "qh_test_vneighbors: found %d non-convex, vertex neighbors\n",
3397 nummerges));
3398 return (nummerges > 0);
3399 } /* test_vneighbors */
3400
3401 /*-<a href="qh-merge.htm#TOC"
3402 >-------------------------------</a><a name="tracemerge">-</a>
3403
3404 qh_tracemerge( facet1, facet2 )
3405 print trace message after merge
3406 */
qh_tracemerge(facetT * facet1,facetT * facet2)3407 void qh_tracemerge(facetT *facet1, facetT *facet2) {
3408 boolT waserror= False;
3409
3410 #ifndef qh_NOtrace
3411 if (qh IStracing >= 4)
3412 qh_errprint("MERGED", facet2, NULL, NULL, NULL);
3413 if (facet2 == qh tracefacet || (qh tracevertex && qh tracevertex->newlist)) {
3414 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);
3415 if (facet2 != qh tracefacet)
3416 qh_errprint("TRACE", qh tracefacet,
3417 (qh tracevertex && qh tracevertex->neighbors) ?
3418 SETfirstt_(qh tracevertex->neighbors, facetT) : NULL,
3419 NULL, qh tracevertex);
3420 }
3421 if (qh tracevertex) {
3422 if (qh tracevertex->deleted)
3423 qh_fprintf(qh ferr, 8086, "qh_tracemerge: trace vertex deleted at furthest p%d\n",
3424 qh furthest_id);
3425 else
3426 qh_checkvertex(qh tracevertex);
3427 }
3428 if (qh tracefacet) {
3429 qh_checkfacet(qh tracefacet, True, &waserror);
3430 if (waserror)
3431 qh_errexit(qh_ERRqhull, qh tracefacet, NULL);
3432 }
3433 #endif /* !qh_NOtrace */
3434 if (qh CHECKfrequently || qh IStracing >= 4) { /* can't check polygon here */
3435 qh_checkfacet(facet2, True, &waserror);
3436 if (waserror)
3437 qh_errexit(qh_ERRqhull, NULL, NULL);
3438 }
3439 } /* tracemerge */
3440
3441 /*-<a href="qh-merge.htm#TOC"
3442 >-------------------------------</a><a name="tracemerging">-</a>
3443
3444 qh_tracemerging()
3445 print trace message during POSTmerging
3446
3447 returns:
3448 updates qh.mergereport
3449
3450 notes:
3451 called from qh_mergecycle() and qh_mergefacet()
3452
3453 see:
3454 qh_buildtracing()
3455 */
qh_tracemerging(void)3456 void qh_tracemerging(void) {
3457 realT cpu;
3458 int total;
3459 time_t timedata;
3460 struct tm *tp;
3461
3462 qh mergereport= zzval_(Ztotmerge);
3463 time(&timedata);
3464 tp= localtime(&timedata);
3465 cpu= qh_CPUclock;
3466 cpu /= qh_SECticks;
3467 total= zzval_(Ztotmerge) - zzval_(Zcyclehorizon) + zzval_(Zcyclefacettot);
3468 qh_fprintf(qh ferr, 8087, "\n\
3469 At %d:%d:%d & %2.5g CPU secs, qhull has merged %d facets. The hull\n\
3470 contains %d facets and %d vertices.\n",
3471 tp->tm_hour, tp->tm_min, tp->tm_sec, cpu,
3472 total, qh num_facets - qh num_visible,
3473 qh num_vertices-qh_setsize(qh del_vertices));
3474 } /* tracemerging */
3475
3476 /*-<a href="qh-merge.htm#TOC"
3477 >-------------------------------</a><a name="updatetested">-</a>
3478
3479 qh_updatetested( facet1, facet2 )
3480 clear facet2->tested and facet1->ridge->tested for merge
3481
3482 returns:
3483 deletes facet2->center unless it's already large
3484 if so, clears facet2->ridge->tested
3485
3486 design:
3487 clear facet2->tested
3488 clear ridge->tested for facet1's ridges
3489 if facet2 has a centrum
3490 if facet2 is large
3491 set facet2->keepcentrum
3492 else if facet2 has 3 vertices due to many merges, or not large and post merging
3493 clear facet2->keepcentrum
3494 unless facet2->keepcentrum
3495 clear facet2->center to recompute centrum later
3496 clear ridge->tested for facet2's ridges
3497 */
qh_updatetested(facetT * facet1,facetT * facet2)3498 void qh_updatetested(facetT *facet1, facetT *facet2) {
3499 ridgeT *ridge, **ridgep;
3500 int size;
3501
3502 facet2->tested= False;
3503 FOREACHridge_(facet1->ridges)
3504 ridge->tested= False;
3505 if (!facet2->center)
3506 return;
3507 size= qh_setsize(facet2->vertices);
3508 if (!facet2->keepcentrum) {
3509 if (size > qh hull_dim + qh_MAXnewcentrum) {
3510 facet2->keepcentrum= True;
3511 zinc_(Zwidevertices);
3512 }
3513 }else if (size <= qh hull_dim + qh_MAXnewcentrum) {
3514 /* center and keepcentrum was set */
3515 if (size == qh hull_dim || qh POSTmerging)
3516 facet2->keepcentrum= False; /* if many merges need to recompute centrum */
3517 }
3518 if (!facet2->keepcentrum) {
3519 qh_memfree(facet2->center, qh normal_size);
3520 facet2->center= NULL;
3521 FOREACHridge_(facet2->ridges)
3522 ridge->tested= False;
3523 }
3524 } /* updatetested */
3525
3526 /*-<a href="qh-merge.htm#TOC"
3527 >-------------------------------</a><a name="vertexridges">-</a>
3528
3529 qh_vertexridges( vertex )
3530 return temporary set of ridges adjacent to a vertex
3531 vertex->neighbors defined
3532
3533 ntoes:
3534 uses qh.visit_id
3535 does not include implicit ridges for simplicial facets
3536
3537 design:
3538 for each neighbor of vertex
3539 add ridges that include the vertex to ridges
3540 */
qh_vertexridges(vertexT * vertex)3541 setT *qh_vertexridges(vertexT *vertex) {
3542 facetT *neighbor, **neighborp;
3543 setT *ridges= qh_settemp(qh TEMPsize);
3544 int size;
3545
3546 qh visit_id++;
3547 FOREACHneighbor_(vertex)
3548 neighbor->visitid= qh visit_id;
3549 FOREACHneighbor_(vertex) {
3550 if (*neighborp) /* no new ridges in last neighbor */
3551 qh_vertexridges_facet(vertex, neighbor, &ridges);
3552 }
3553 if (qh PRINTstatistics || qh IStracing) {
3554 size= qh_setsize(ridges);
3555 zinc_(Zvertexridge);
3556 zadd_(Zvertexridgetot, size);
3557 zmax_(Zvertexridgemax, size);
3558 trace3((qh ferr, 3011, "qh_vertexridges: found %d ridges for v%d\n",
3559 size, vertex->id));
3560 }
3561 return ridges;
3562 } /* vertexridges */
3563
3564 /*-<a href="qh-merge.htm#TOC"
3565 >-------------------------------</a><a name="vertexridges_facet">-</a>
3566
3567 qh_vertexridges_facet( vertex, facet, ridges )
3568 add adjacent ridges for vertex in facet
3569 neighbor->visitid==qh.visit_id if it hasn't been visited
3570
3571 returns:
3572 ridges updated
3573 sets facet->visitid to qh.visit_id-1
3574
3575 design:
3576 for each ridge of facet
3577 if ridge of visited neighbor (i.e., unprocessed)
3578 if vertex in ridge
3579 append ridge to vertex
3580 mark facet processed
3581 */
qh_vertexridges_facet(vertexT * vertex,facetT * facet,setT ** ridges)3582 void qh_vertexridges_facet(vertexT *vertex, facetT *facet, setT **ridges) {
3583 ridgeT *ridge, **ridgep;
3584 facetT *neighbor;
3585
3586 FOREACHridge_(facet->ridges) {
3587 neighbor= otherfacet_(ridge, facet);
3588 if (neighbor->visitid == qh visit_id
3589 && qh_setin(ridge->vertices, vertex))
3590 qh_setappend(ridges, ridge);
3591 }
3592 facet->visitid= qh visit_id-1;
3593 } /* vertexridges_facet */
3594
3595 /*-<a href="qh-merge.htm#TOC"
3596 >-------------------------------</a><a name="willdelete">-</a>
3597
3598 qh_willdelete( facet, replace )
3599 moves facet to visible list
3600 sets facet->f.replace to replace (may be NULL)
3601
3602 returns:
3603 bumps qh.num_visible
3604 */
qh_willdelete(facetT * facet,facetT * replace)3605 void qh_willdelete(facetT *facet, facetT *replace) {
3606
3607 qh_removefacet(facet);
3608 qh_prependfacet(facet, &qh visible_list);
3609 qh num_visible++;
3610 facet->visible= True;
3611 facet->f.replace= replace;
3612 } /* willdelete */
3613
3614 #else /* qh_NOmerge */
qh_premerge(vertexT * apex,realT maxcentrum,realT maxangle)3615 void qh_premerge(vertexT *apex, realT maxcentrum, realT maxangle) {
3616 }
qh_postmerge(const char * reason,realT maxcentrum,realT maxangle,boolT vneighbors)3617 void qh_postmerge(const char *reason, realT maxcentrum, realT maxangle,
3618 boolT vneighbors) {
3619 }
qh_checkzero(boolT testall)3620 boolT qh_checkzero(boolT testall) {
3621 }
3622 #endif /* qh_NOmerge */
3623
3624