62 trace2((
qh,
qh->ferr, 2008,
"qh_premerge: premerge centrum %2.2g angle %2.2g for apex v%d facetlist f%d\n",
63 maxcentrum, maxangle, apex->
id,
getid_(
qh->newfacet_list)));
64 if (
qh->IStracing >= 4 &&
qh->num_facets < 50)
66 qh->centrum_radius= maxcentrum;
67 qh->cos_max= maxangle;
70 if (
qh->hull_dim >=3) {
135 if (
qh->REPORTfreq ||
qh->IStracing) {
138 if (
qh->PRINTstatistics)
141 reason, maxcentrum, maxangle);
143 trace2((
qh,
qh->ferr, 2009,
"qh_postmerge: postmerge. test vneighbors? %d\n",
145 qh->centrum_radius= maxcentrum;
146 qh->cos_max= maxangle;
150 if (
qh->visible_list !=
qh->facet_list) {
152 qh->visible_list=
qh->newfacet_list=
qh->facet_list;
159 qh->newvertex_list=
qh->vertex_list;
162 if (
qh->VERTEXneighbors) {
165 if (
qh->MERGEexact) {
170 if (!
qh->PREmerge && !
qh->MERGEexact)
222 int numcoplanar=0, numconcave=0, numdegenredun= 0, numnewmerges= 0;
224 trace2((
qh,
qh->ferr, 2010,
"qh_all_merges: starting to merge facets beginning from f%d\n",
232 mergetype= merge->
type;
257 if (
qh->VERTEXneighbors) {
259 if (
qh->hull_dim >=4 &&
qh->POSTmerging) {
264 if ((wasmerge || othermerge) && (!
qh->MERGEexact ||
qh->POSTmerging)
280 if (
qh->CHECKfrequently && !
qh->MERGEexact) {
281 qh->old_randomdist=
qh->RANDOMdist;
285 qh->RANDOMdist=
qh->old_randomdist;
287 trace1((
qh,
qh->ferr, 1009,
"qh_all_merges: merged %d coplanar facets %d concave facets and %d degen or redundant facets.\n",
288 numcoplanar, numconcave, numdegenredun));
289 if (
qh->IStracing >= 4 &&
qh->num_facets < 50)
321 mergeT *merge, *lastmerge;
331 merge->
type= mergetype;
332 if (angle &&
qh->ANGLEmerge)
333 merge->
angle= *angle;
348 qh_fprintf(
qh,
qh->ferr, 6092,
"qhull error (qh_appendmergeset): facet f%d or f%d is already a mirrored facet\n",
349 facet->
id, neighbor->
id);
353 qh_fprintf(
qh,
qh->ferr, 6093,
"qhull error (qh_appendmergeset): mirrored facets f%d and f%d do not have the same vertices\n",
354 facet->
id, neighbor->
id);
386 vertexT *apex, *vertex, **vertexp;
395 if (vertex->
visitid !=
qh->vertex_visit) {
402 trace4((
qh,
qh->ferr, 4019,
"qh_basevertices: found %d vertices\n",
426 facetT *facet, *newfacet, *errfacet= NULL, *neighbor, **neighborp;
428 facet=
qh->newfacet_list;
434 if (neighbor->visitid !=
qh->visit_id) {
437 neighbor->visitid=
qh->visit_id;
444 qh_fprintf(
qh,
qh->ferr, 6094,
"qhull error: f%d is not attached to the new facets\n",
489 facetT *facet, *neighbor, **neighborp;
490 facetT *horizon, *facetlist;
496 facetlist=
qh->facet_list;
498 facetlist=
qh->newfacet_list;
506 if (
qh->MERGEexact &&
qh->ZEROall_ok) {
507 trace2((
qh,
qh->ferr, 2011,
"qh_checkzero: skip convexity check until first pre-merge\n"));
516 if (!neighbor_i && !testall) {
525 if (dist >= -
qh->DISTround) {
527 if (!
qh->MERGEexact || testall || dist >
qh->DISTround)
531 if (!testall && horizon) {
533 if (vertex->
visitid !=
qh->vertex_visit) {
536 if (dist >= -
qh->DISTround) {
538 if (!
qh->MERGEexact || dist >
qh->DISTround)
546 trace2((
qh,
qh->ferr, 2012,
"qh_checkzero: testall %d, facets are %s\n", testall,
547 (
qh->MERGEexact && !testall) ?
548 "not concave, flipped, or duplicate ridged" :
"clearly convex"));
553 trace2((
qh,
qh->ferr, 2013,
"qh_checkzero: facet f%d needs pre-merging\n",
558 trace2((
qh,
qh->ferr, 2014,
"qh_checkzero: facet f%d and f%d are not clearly convex. v%d dist %.2g\n",
559 facet->
id, neighbor->
id, vertex->
id, dist));
572 return((
a->angle >
b->angle) ? 1 : -1);
584 return(
a->type -
b->type);
596 return(
a->visitid -
b->visitid);
614 facetT *facet, *otherfacet;
618 otherfacet= atridge->
bottom;
620 if (otherfacet ==
otherfacet_(ridge, facet) && ridge != atridge) {
622 trace4((
qh,
qh->ferr, 4020,
"qh_copynonconvex: moved nonconvex flag from r%d to r%d\n",
623 atridge->
id, ridge->
id));
649 facetT *neighbor, **neighborp;
651 trace4((
qh,
qh->ferr, 4021,
"qh_degen_redundant_facet: test facet f%d for degen/redundant\n",
663 trace2((
qh,
qh->ferr, 2015,
"qh_degen_redundant_facet: f%d is contained in f%d. merge\n", facet->
id, neighbor->
id));
669 trace2((
qh,
qh->ferr, 2016,
"qh_degen_redundant_neighbors: f%d is degenerate.\n", facet->
id));
705 facetT *neighbor, **neighborp;
708 trace4((
qh,
qh->ferr, 4022,
"qh_degen_redundant_neighbors: test neighbors of f%d with delfacet f%d\n",
712 trace2((
qh,
qh->ferr, 2017,
"qh_degen_redundant_neighbors: f%d is degenerate with %d neighbors.\n", facet->
id, size));
721 if (neighbor == facet)
729 trace2((
qh,
qh->ferr, 2018,
"qh_degen_redundant_neighbors: f%d is contained in f%d. merge\n", neighbor->
id, facet->
id));
733 if (neighbor == facet)
737 trace2((
qh,
qh->ferr, 2019,
"qh_degen_redundant_neighbors: f%d is degenerate with %d neighbors. Neighbor of f%d.\n", neighbor->
id, size, facet->
id));
781 if (
qh->IStracing >= 4) {
782 qh_fprintf(
qh,
qh->ferr, 8063,
"qh_find_newvertex: find new vertex for v%d from ",
805 trace4((
qh,
qh->ferr, 4023,
"qh_find_newvertex: vertices not in ridges for v%d\n",
812 if (
qh->PRINTstatistics) {
835 trace2((
qh,
qh->ferr, 2020,
"qh_find_newvertex: found v%d for old v%d from %d vertices and %d ridges.\n",
839 trace0((
qh,
qh->ferr, 14,
"qh_find_newvertex: no vertex for renaming v%d(all duplicated ridges) during p%d\n",
840 oldvertex->
id,
qh->furthest_id));
862 realT dist, mindist, maxdist;
867 dist *=
qh->hull_dim;
879 *bestfacet= neighbor;
914 facetT *neighbor, **neighborp, *bestfacet= NULL;
920 qh_fprintf(
qh,
qh->ferr, 6272,
"qhull error: cannot call qh_findbestneighor for f%d while qh.CENTERtype is qh_ASvoronoi\n", facet->
id);
935 &bestfacet, distp, mindistp, maxdistp);
943 &bestfacet, distp, mindistp, maxdistp);
946 qh_fprintf(
qh,
qh->ferr, 6095,
"qhull internal error (qh_findbestneighbor): no neighbors for f%d\n", facet->
id);
951 trace3((
qh,
qh->ferr, 3002,
"qh_findbestneighbor: f%d is best neighbor for f%d testcentrum? %d nonconvex? %d dist %2.2g min %2.2g max %2.2g\n",
952 bestfacet->
id, facet->
id, testcentrum, nonconvex, *distp, *mindistp, *maxdistp));
982 facetT *facet, *neighbor, *facet1;
983 realT dist, mindist, maxdist;
988 trace4((
qh,
qh->ferr, 4024,
"qh_flippedmerges: begin\n"));
1001 qh->qhmem.IStracing=
qh->IStracing=
qh->TRACElevel;
1003 trace0((
qh,
qh->ferr, 15,
"qh_flippedmerges: merge flipped f%d into f%d dist %2.2g during p%d\n",
1004 facet1->
id, neighbor->
id, dist,
qh->furthest_id));
1007 if (
qh->PRINTstatistics) {
1023 trace1((
qh,
qh->ferr, 1010,
"qh_flippedmerges: merged %d flipped facets into a good neighbor\n", nummerge));
1058 realT dist1, dist2, mindist1, mindist2, maxdist1, maxdist2;
1060 int nummerge=0, numflip=0;
1063 qh->qhmem.IStracing=
qh->IStracing=
qh->TRACElevel;
1064 trace4((
qh,
qh->ferr, 4025,
"qh_forcedmerges: begin\n"));
1072 qh->qhmem.IStracing=
qh->IStracing=
qh->TRACElevel;
1079 if (facet1 == facet2)
1082 qh_fprintf(
qh,
qh->ferr, 6096,
"qhull internal error (qh_forcedmerges): f%d and f%d had a duplicate ridge but as f%d and f%d they are no longer neighbors\n",
1101 if (
qh->PRINTstatistics) {
1116 trace1((
qh,
qh->ferr, 1011,
"qh_forcedmerges: merged %d facets and %d flipped facets across duplicated ridges\n",
1117 nummerge, numflip));
1151 facetT *facet, *neighbor, **neighborp;
1156 trace4((
qh,
qh->ferr, 4026,
"qh_getmergeset: started.\n"));
1170 if (neighbor->
seen) {
1173 }
else if (neighbor->
visitid !=
qh->visit_id) {
1187 if (
qh->POSTmerging) {
1193 trace2((
qh,
qh->ferr, 2021,
"qh_getmergeset: %d merges found\n", nummerges));
1224 facetT *facet, *neighbor, **neighborp;
1233 if (neighbor->
visitid !=
qh->visit_id) {
1252 if (
qh->POSTmerging) {
1258 trace2((
qh,
qh->ferr, 2022,
"qh_getmergeset_initial: %d merges found\n", nummerges));
1284 }
else if (ridgeA == ridge)
1286 if (++hash == hashsize)
1327 if (ridgeA == ridge)
1334 if (++hash == hashsize)
1370 facetT *neighbor, **neighborp;
1372 int neighbor_i, neighbor_n;
1377 trace4((
qh,
qh->ferr, 4027,
"qh_makeridges: make ridges for f%d\n", facet->
id));
1390 else if (!neighbor->
seen) {
1394 toporient= facet->
toporient ^ (neighbor_i & 0x1);
1399 ridge->
top= neighbor;
1404 if (facet->
toporient ^ (skip1 & 0x1) ^ flip) {
1405 ridge->
top= neighbor;
1460 facetT *facet, *neighbor, **neighborp;
1465 trace4((
qh,
qh->ferr, 4028,
"qh_mark_dupridges: identify duplicate ridges\n"));
1495 trace1((
qh,
qh->ferr, 1012,
"qh_mark_dupridges: found %d duplicated ridges\n",
1526 facetT *neighbor, **neighborp;
1529 trace4((
qh,
qh->ferr, 4029,
"qh_maydropneighbor: test f%d for no ridges to a neighbor\n",
1536 if (neighbor->
visitid !=
qh->visit_id) {
1537 trace0((
qh,
qh->ferr, 17,
"qh_maydropneighbor: facets f%d and f%d are no longer neighbors during p%d\n",
1538 facet->
id, neighbor->
id,
qh->furthest_id));
1546 trace2((
qh,
qh->ferr, 2023,
"qh_maydropneighbors: f%d is degenerate.\n", neighbor->
id));
1553 trace2((
qh,
qh->ferr, 2024,
"qh_maydropneighbors: f%d is degenerate.\n", facet->
id));
1586 facetT *bestneighbor, *facet1, *facet2;
1587 realT dist, mindist, maxdist;
1595 mergetype= merge->
type;
1602 qh->qhmem.IStracing=
qh->IStracing=
qh->TRACElevel;
1607 qh_fprintf(
qh,
qh->ferr, 6097,
"qhull internal error (qh_merge_degenredunant): f%d redundant but f%d has no replacement\n",
1608 facet1->
id, facet2->
id);
1613 if (facet1 == facet2) {
1617 trace2((
qh,
qh->ferr, 2025,
"qh_merge_degenredundant: facet f%d is contained in f%d, will merge\n",
1618 facet1->
id, facet2->
id));
1625 trace2((
qh,
qh->ferr, 2026,
"qh_merge_degenredundant: facet f%d has no neighbors. Deleted\n", facet1->
id));
1631 trace2((
qh,
qh->ferr, 2027,
"qh_merge_degenredundant: deleted v%d because f%d has no neighbors\n",
1632 vertex->
id, facet1->
id));
1638 }
else if (size < qh->hull_dim) {
1640 trace2((
qh,
qh->ferr, 2028,
"qh_merge_degenredundant: facet f%d has %d neighbors, merge into f%d dist %2.2g\n",
1641 facet1->
id, size, bestneighbor->
id, dist));
1644 if (
qh->PRINTstatistics) {
1673 facetT *bestfacet, *bestneighbor, *neighbor;
1674 realT dist, dist2, mindist, mindist2, maxdist, maxdist2;
1677 qh->qhmem.IStracing=
qh->IStracing=
qh->TRACElevel;
1678 trace3((
qh,
qh->ferr, 3003,
"qh_merge_nonconvex: merge #%d for f%d and f%d type %d\n",
1692 && ((mindist >= -
qh->MAXcoplanar && maxdist <= qh->max_outside)
1693 || dist * 1.5 < dist2)) {
1697 trace2((
qh,
qh->ferr, 2029,
"qh_merge_nonconvex: avoid merging old facet f%d dist %2.2g. Use f%d dist %2.2g instead\n",
1698 facet2->
id, dist2, facet1->
id, dist2));
1704 if (
qh->PRINTstatistics) {
1751 int traceonce=
False, tracerestore= 0;
1758 if (!
qh->TRInormals) {
1759 qh_fprintf(
qh,
qh->ferr, 6224,
"Qhull internal error (qh_mergecycle): does not work for tricoplanar facets. Use option 'Q11'\n");
1765 if (!
qh->VERTEXneighbors)
1768 if (
qh->REPORTfreq2 &&
qh->POSTmerging) {
1774 qh->qhmem.IStracing=
qh->IStracing=
qh->TRACElevel;
1775 trace2((
qh,
qh->ferr, 2030,
"qh_mergecycle: merge #%d for facets from cycle f%d into coplanar horizon f%d\n",
1777 if (newfacet ==
qh->tracefacet) {
1778 tracerestore=
qh->IStracing;
1780 qh_fprintf(
qh,
qh->ferr, 8068,
"qh_mergecycle: ========= trace merge %d of samecycle %d into trace f%d, furthest is p%d\n",
1784 if (
qh->IStracing >=4) {
1790 if (
qh->IStracing >=4)
1791 qh_errprint(
qh,
"MERGING CYCLE", samecycle, newfacet, NULL, NULL);
1806 qh_fprintf(
qh,
qh->ferr, 8072,
"qh_mergecycle: end of trace facet\n");
1807 qh->IStracing= tracerestore;
1841 facetT *facet, *same, *prev, *horizon;
1842 facetT *samecycle= NULL, *nextfacet, *nextsame;
1843 vertexT *apex, *vertex, **vertexp;
1844 int cycles=0, total=0, facets, nummerge;
1846 trace2((
qh,
qh->ferr, 2031,
"qh_mergecycle_all: begin\n"));
1847 for (facet= facetlist; facet && (nextfacet= facet->
next); facet= nextfacet) {
1850 if (!facet->mergehorizon) {
1851 qh_fprintf(
qh,
qh->ferr, 6225,
"Qhull internal error (qh_mergecycle_all): f%d without normal\n", facet->id);
1855 if (facet->f.samecycle == facet) {
1870 same= (same == facet ? NULL :nextsame)) {
1883 while (nextfacet && nextfacet->cycledone)
1884 nextfacet= nextfacet->
next;
1887 nummerge= horizon->
nummerge + facets;
1891 horizon->
nummerge= (
short unsigned int)nummerge;
1901 trace1((
qh,
qh->ferr, 1013,
"qh_mergecycle_all: merged %d same cycles or facets into coplanar horizons\n", cycles));
1931 trace4((
qh,
qh->ferr, 4030,
"qh_mergecycle_facets: make newfacet new and samecycle deleted\n"));
1938 for (same= samecycle->
f.
samecycle; same; same= (same == samecycle ? NULL : next)) {
1947 trace3((
qh,
qh->ferr, 3004,
"qh_mergecycle_facets: merged facets from cycle f%d into f%d\n",
1948 samecycle->
id, newfacet->
id));
1987 facetT *same, *neighbor, **neighborp;
1988 int delneighbors= 0, newneighbors= 0;
1989 unsigned int samevisitid;
1992 samevisitid= ++
qh->visit_id;
1999 trace4((
qh,
qh->ferr, 4031,
"qh_mergecycle_neighbors: delete shared neighbors from newfacet\n"));
2001 if (neighbor->
visitid == samevisitid) {
2009 trace4((
qh,
qh->ferr, 4032,
"qh_mergecycle_neighbors: update neighbors\n"));
2012 if (neighbor->
visitid == samevisitid)
2015 if (neighbor->
visitid !=
qh->visit_id) {
2021 if (ridge->
top == same) {
2022 ridge->
top= newfacet;
2024 }
else if (ridge->
bottom == same) {
2036 if (neighbor->
visitid !=
qh->visit_id) {
2045 trace2((
qh,
qh->ferr, 2032,
"qh_mergecycle_neighbors: deleted %d neighbors and added %d\n",
2046 delneighbors, newneighbors));
2084 facetT *same, *neighbor= NULL;
2085 int numold=0, numnew=0;
2086 int neighbor_i, neighbor_n;
2087 unsigned int samevisitid;
2092 trace4((
qh,
qh->ferr, 4033,
"qh_mergecycle_ridges: delete shared ridges from newfacet\n"));
2093 samevisitid=
qh->visit_id -1;
2096 if (neighbor->
visitid == samevisitid)
2101 trace4((
qh,
qh->ferr, 4034,
"qh_mergecycle_ridges: add ridges to newfacet\n"));
2104 if (ridge->
top == same) {
2105 ridge->
top= newfacet;
2107 }
else if (ridge->
bottom == same) {
2109 neighbor= ridge->
top;
2110 }
else if (ridge->
top == newfacet || ridge->
bottom == newfacet) {
2115 qh_fprintf(
qh,
qh->ferr, 6098,
"qhull internal error (qh_mergecycle_ridges): bad ridge r%d\n", ridge->
id);
2118 if (neighbor == newfacet) {
2122 }
else if (neighbor->
visitid == samevisitid) {
2141 toporient= same->
toporient ^ (neighbor_i & 0x1);
2143 ridge->
top= newfacet;
2146 ridge->
top= neighbor;
2156 trace2((
qh,
qh->ferr, 2033,
"qh_mergecycle_ridges: found %d old ridges and %d new ones\n",
2186 facetT *neighbor, **neighborp;
2187 unsigned int mergeid;
2188 vertexT *vertex, **vertexp, *apex;
2191 trace4((
qh,
qh->ferr, 4035,
"qh_mergecycle_vneighbors: update vertex neighbors for newfacet\n"));
2192 mergeid=
qh->visit_id - 1;
2200 if (neighbor->
visitid == mergeid)
2207 trace2((
qh,
qh->ferr, 2034,
"qh_mergecycle_vneighbors: deleted v%d when merging cycle f%d into f%d\n",
2208 vertex->
id, samecycle->
id, newfacet->
id));
2215 trace3((
qh,
qh->ferr, 3005,
"qh_mergecycle_vneighbors: merged vertices from cycle f%d into f%d\n",
2216 samecycle->
id, newfacet->
id));
2273 int tracerestore=0, nummerge;
2276 if (!
qh->TRInormals) {
2277 qh_fprintf(
qh,
qh->ferr, 6226,
"Qhull internal error (qh_mergefacet): does not work for tricoplanar facets. Use option 'Q11'\n");
2286 if (
qh->REPORTfreq2 &&
qh->POSTmerging) {
2291 if (
qh->build_cnt >=
qh->RERUN) {
2292 if (mindist && (-*mindist >
qh->TRACEdist || *maxdist >
qh->TRACEdist)) {
2294 qh->IStracing=
qh->TRACElevel;
2296 qh_fprintf(
qh,
qh->ferr, 8075,
"qh_mergefacet: ========= trace wide merge #%d(%2.2g) for f%d into f%d, last point was p%d\n",
zzval_(
Ztotmerge),
2297 fmax_(-*mindist, *maxdist), facet1->
id, facet2->
id,
qh->furthest_id);
2298 }
else if (facet1 ==
qh->tracefacet || facet2 ==
qh->tracefacet) {
2299 tracerestore=
qh->IStracing;
2302 qh_fprintf(
qh,
qh->ferr, 8076,
"qh_mergefacet: ========= trace merge #%d involving f%d, furthest is p%d\n",
2306 if (
qh->IStracing >= 2) {
2314 qh_fprintf(
qh,
qh->ferr, 8077,
"qh_mergefacet: #%d merge f%d into f%d, mindist= %2.2g, maxdist= %2.2g\n",
2319 qh_fprintf(
qh,
qh->ferr, 6099,
"qhull internal error (qh_mergefacet): either f%d and f%d are the same or one is a visible facet\n",
2320 facet1->
id, facet2->
id);
2323 if (
qh->num_facets -
qh->num_visible <=
qh->hull_dim + 1) {
2325 qhull precision error: Only %d facets remain. Can not merge another\n\
2326 pair. The input is too degenerate or the convexity constraints are\n\
2327 too strong.\n",
qh->hull_dim+1);
2328 if (
qh->hull_dim >= 5 && !
qh->MERGEexact)
2329 qh_fprintf(
qh,
qh->ferr, 8079,
"Option 'Qx' may avoid this problem.\n");
2332 if (!
qh->VERTEXneighbors)
2336 if (
qh->IStracing >=4)
2346 && (*maxdist >
qh->WIDEfacet || *mindist < -qh->WIDEfacet)) {
2355 facet2->
nummerge= (
short unsigned int)nummerge;
2365 if (
qh->hull_dim == 2)
2392 qh_fprintf(
qh,
qh->ferr, 8080,
"qh_mergefacet: end of wide tracing\n");
2393 qh->IStracing= tracerestore;
2422 vertexT *vertex1A, *vertex1B, *vertex2A, *vertex2B, *vertexA, *vertexB;
2423 facetT *neighbor1A, *neighbor1B, *neighbor2A, *neighbor2B, *neighborA, *neighborB;
2433 if (vertex1A == vertex2A) {
2436 neighborA= neighbor2A;
2437 neighborB= neighbor1A;
2438 }
else if (vertex1A == vertex2B) {
2441 neighborA= neighbor2B;
2442 neighborB= neighbor1A;
2443 }
else if (vertex1B == vertex2A) {
2446 neighborA= neighbor2A;
2447 neighborB= neighbor1B;
2451 neighborA= neighbor2B;
2452 neighborB= neighbor1B;
2455 if (vertexA->
id > vertexB->
id) {
2458 if (vertexB == vertex2A)
2465 if (vertexB == vertex2B)
2472 trace4((
qh,
qh->ferr, 4036,
"qh_mergefacet2d: merged v%d and neighbor f%d of f%d into f%d\n",
2473 vertexA->
id, neighborB->
id, facet1->
id, facet2->
id));
2497 facetT *neighbor, **neighborp;
2499 trace4((
qh,
qh->ferr, 4037,
"qh_mergeneighbors: merge neighbors of f%d and f%d\n",
2500 facet1->
id, facet2->
id));
2506 if (neighbor->
visitid ==
qh->visit_id) {
2515 }
else if (neighbor != facet2) {
2548 trace4((
qh,
qh->ferr, 4038,
"qh_mergeridges: merge ridges of f%d and f%d\n",
2549 facet1->
id, facet2->
id));
2551 if ((ridge->
top == facet1) || (ridge->
bottom == facet1)) {
2559 if (ridge->
top == facet1)
2612 vertexT *vertex, **vertexp, *apex;
2615 int vertex_i= -1, vertex_n;
2616 facetT *neighbor, **neighborp, *otherfacet;
2644 trace4((
qh,
qh->ferr, 4039,
"qh_mergesimplex: merge apex v%d of f%d into facet f%d\n",
2645 apex->
id, facet1->
id, facet2->
id));
2647 if (vertex->
id < apex->
id) {
2649 }
else if (vertex->
id == apex->
id) {
2663 trace4((
qh,
qh->ferr, 4040,
"qh_mergesimplex: update vertex neighbors of f%d\n",
2666 if (vertex == apex && !issubset)
2674 trace4((
qh,
qh->ferr, 4041,
"qh_mergesimplex: merge ridges and neighbors of f%d into f%d\n",
2675 facet1->
id, facet2->
id));
2681 if (otherfacet == facet2) {
2688 if (otherfacet->
visitid !=
qh->visit_id) {
2702 if (ridge->
top == facet1)
2709 trace3((
qh,
qh->ferr, 3006,
"qh_mergesimplex: merged simplex f%d apex v%d into facet f%d\n",
2726 trace2((
qh,
qh->ferr, 2035,
"qh_mergevertex_del: deleted v%d when merging f%d into f%d\n",
2727 vertex->
id, facet1->
id, facet2->
id));
2752 trace4((
qh,
qh->ferr, 4042,
"qh_mergevertex_neighbors: merge vertex neighbors of f%d and f%d\n",
2753 facet1->
id, facet2->
id));
2754 if (
qh->tracevertex) {
2755 qh_fprintf(
qh,
qh->ferr, 8081,
"qh_mergevertex_neighbors: of f%d and f%d at furthest p%d f0= %p\n",
2756 facet1->
id, facet2->
id,
qh->furthest_id,
qh->tracevertex->neighbors->e[0].p);
2760 if (vertex->
visitid !=
qh->vertex_visit)
2768 if (
qh->tracevertex)
2789 setT *mergedvertices;
2794 if (!*vertex2 || vertex->
id > (*vertex2)->id)
2797 while (*vertex2 && (*vertex2)->
id > vertex->
id)
2799 if (!*vertex2 || (*vertex2)->
id < vertex->
id)
2808 qh_fprintf(
qh,
qh->ferr, 6100,
"qhull internal error (qh_mergevertices): facets did not share a ridge\n");
2812 *vertices2= mergedvertices;
2841 facetT *neighbor, **neighborp, *neighborA, *neighborB;
2843 int neighbor_i, neighbor_n;
2861 if (neighbor_i >= 2) {
2871 trace3((
qh,
qh->ferr, 3007,
"qh_neighbor_intersections: %d vertices in neighbor intersection of v%d\n",
2925 int numshare=0, numrename= 0;
2930 if (
qh->hull_dim == 2)
2937 if (!
qh->MERGEvertices)
2942 if (!
qh->MERGEvertices)
2969 trace1((
qh,
qh->ferr, 1014,
"qh_reducevertices: renamed %d shared vertices and %d redundant vertices. Degen? %d\n",
2970 numshare, numrename, degenredun));
2998 setT *vertices, *ridges;
3000 trace3((
qh,
qh->ferr, 3008,
"qh_redundant_vertex: check if v%d can be renamed\n", vertex->
id));
3033 trace4((
qh,
qh->ferr, 4043,
"qh_remove_extravertices: test f%d for extra vertices\n",
3042 if (!vertex->
seen) {
3051 trace2((
qh,
qh->ferr, 2036,
"qh_remove_extravertices: v%d deleted because it's lost all ridges\n", vertex->
id));
3053 trace3((
qh,
qh->ferr, 3009,
"qh_remove_extravertices: v%d removed from f%d because it's lost all ridges\n", vertex->
id, facet->
id));
3088 facetT *neighbor, **neighborp, *neighborA= NULL;
3089 setT *vertices, *ridges;
3094 if (neighborA == facet)
3096 }
else if (
qh->hull_dim == 3)
3103 if (neighbor->
visitid ==
qh->visit_id) {
3106 neighborA= neighbor;
3110 qh_fprintf(
qh,
qh->ferr, 6101,
"qhull internal error (qh_rename_sharedvertex): v%d's neighbors not in f%d\n",
3111 vertex->
id, facet->
id);
3120 trace2((
qh,
qh->ferr, 2037,
"qh_rename_sharedvertex: p%d(v%d) is shared by f%d(%d ridges) and f%d\n",
3158 if (vertex == newvertex) {
3162 trace2((
qh,
qh->ferr, 2038,
"qh_renameridgevertex: ridge r%d deleted. It contained both v%d and v%d\n",
3163 ridge->
id, oldvertex->
id, newvertex->
id));
3167 if (vertex->
id < newvertex->
id)
3172 if (abs(oldnth - nth)%2) {
3173 trace3((
qh,
qh->ferr, 3010,
"qh_renameridgevertex: swapped the top and bottom of ridge r%d\n",
3213 facetT *neighbor, **neighborp;
3217 if (
qh->IStracing >= 2 || oldvertex->
id ==
qh->tracevertex_id ||
3218 newvertex->
id ==
qh->tracevertex_id)
3225 qh_fprintf(
qh,
qh->ferr, 8082,
"qh_renamevertex: renamed v%d to v%d in several facets\n",
3226 oldvertex->
id, newvertex->
id);
3240 qh_fprintf(
qh,
qh->ferr, 8083,
"qh_renamevertex: renamed v%d to v%d in oldfacet f%d\n",
3241 oldvertex->
id, newvertex->
id, oldfacet->
id);
3248 if (istrace ||
qh->IStracing)
3249 qh_fprintf(
qh,
qh->ferr, 8084,
"qh_renamevertex: renamed pinched v%d to v%d between f%d and f%d\n",
3250 oldvertex->
id, newvertex->
id, oldfacet->
id, neighborA->
id);
3296 if (
qh->SKIPconvex && !
qh->POSTmerging)
3298 if ((!
qh->MERGEexact ||
qh->POSTmerging) &&
qh->cos_max <
REALmax/2) {
3301 if (angle >
qh->cos_max) {
3304 trace2((
qh,
qh->ferr, 2039,
"qh_test_appendmerge: coplanar angle %4.4g between f%d and f%d\n",
3305 angle, facet->
id, neighbor->
id));
3314 if (dist >
qh->centrum_radius)
3317 if (dist > -
qh->centrum_radius)
3323 if (dist2 >
qh->centrum_radius)
3325 else if (!iscoplanar && dist2 > -
qh->centrum_radius)
3328 if (!isconcave && (!iscoplanar || (
qh->MERGEexact && !
qh->POSTmerging)))
3330 if (!okangle &&
qh->ANGLEmerge) {
3339 trace0((
qh,
qh->ferr, 18,
"qh_test_appendmerge: concave f%d to f%d dist %4.4g and reverse dist %4.4g angle %4.4g during p%d\n",
3340 facet->
id, neighbor->
id, dist, dist2, angle,
qh->furthest_id));
3344 trace2((
qh,
qh->ferr, 2040,
"qh_test_appendmerge: coplanar f%d to f%d dist %4.4g, reverse dist %4.4g angle %4.4g\n",
3345 facet->
id, neighbor->
id, dist, dist2, angle));
3376 facetT *newfacet, *neighbor, **neighborp;
3380 trace1((
qh,
qh->ferr, 1015,
"qh_test_vneighbors: testing vertex neighbors for convexity\n"));
3381 if (!
qh->VERTEXneighbors)
3400 trace1((
qh,
qh->ferr, 1016,
"qh_test_vneighbors: found %d non-convex, vertex neighbors\n",
3402 return (nummerges > 0);
3415 if (
qh->IStracing >= 4)
3417 if (facet2 ==
qh->tracefacet || (
qh->tracevertex &&
qh->tracevertex->newlist)) {
3418 qh_fprintf(
qh,
qh->ferr, 8085,
"qh_tracemerge: trace facet and vertex after merge of f%d and f%d, furthest p%d\n", facet1->
id, facet2->
id,
qh->furthest_id);
3419 if (facet2 !=
qh->tracefacet)
3421 (
qh->tracevertex &&
qh->tracevertex->neighbors) ?
3423 NULL,
qh->tracevertex);
3425 if (
qh->tracevertex) {
3426 if (
qh->tracevertex->deleted)
3427 qh_fprintf(
qh,
qh->ferr, 8086,
"qh_tracemerge: trace vertex deleted at furthest p%d\n",
3432 if (
qh->tracefacet) {
3438 if (
qh->CHECKfrequently ||
qh->IStracing >= 4) {
3468 tp= localtime(&timedata);
3473 At %d:%d:%d & %2.5g CPU secs, qhull has merged %d facets. The hull\n\
3474 contains %d facets and %d vertices.\n",
3475 tp->tm_hour, tp->tm_min, tp->tm_sec, cpu,
3476 total,
qh->num_facets -
qh->num_visible,
3519 if (size ==
qh->hull_dim ||
qh->POSTmerging)
3546 facetT *neighbor, **neighborp;
3557 if (
qh->PRINTstatistics ||
qh->IStracing) {
3562 trace3((
qh,
qh->ferr, 3011,
"qh_vertexridges: found %d ridges for v%d\n",