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