62 trace2((
qh ferr, 2008,
"qh_premerge: premerge centrum %2.2g angle %2.2g for apex v%d facetlist f%d\n",
63 maxcentrum, maxangle, apex->
id,
getid_(
qh newfacet_list)));
64 if (
qh IStracing >= 4 &&
qh num_facets < 50)
66 qh centrum_radius= maxcentrum;
70 if (
qh hull_dim >=3) {
135 if (
qh REPORTfreq ||
qh IStracing) {
138 if (
qh PRINTstatistics)
140 qh_fprintf(
qh ferr, 8062,
"\n%s with 'C%.2g' and 'A%.2g'\n",
141 reason, maxcentrum, maxangle);
143 trace2((
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) {
170 if (!
qh PREmerge && !
qh MERGEexact)
222 int numcoplanar=0, numconcave=0, numdegenredun= 0, numnewmerges= 0;
224 trace2((
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 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 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 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 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 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 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 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 ferr, 2013,
"qh_checkzero: facet f%d needs pre-merging\n",
558 trace2((
qh ferr, 2014,
"qh_checkzero: facet f%d and f%d are not clearly convex. v%d dist %.2g\n",
559 facet->
id, neighbor->
id, vertex->
id, dist));
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 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 ferr, 4021,
"qh_degen_redundant_facet: test facet f%d for degen/redundant\n",
663 trace2((
qh ferr, 2015,
"qh_degen_redundant_facet: f%d is contained in f%d. merge\n", facet->
id, neighbor->
id));
669 trace2((
qh ferr, 2016,
"qh_degen_redundant_neighbors: f%d is degenerate.\n", facet->
id));
705 facetT *neighbor, **neighborp;
708 trace4((
qh ferr, 4022,
"qh_degen_redundant_neighbors: test neighbors of f%d with delfacet f%d\n",
712 trace2((
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 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 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 ferr, 8063,
"qh_find_newvertex: find new vertex for v%d from ",
805 trace4((
qh ferr, 4023,
"qh_find_newvertex: vertices not in ridges for v%d\n",
812 if (
qh PRINTstatistics) {
835 trace2((
qh ferr, 2020,
"qh_find_newvertex: found v%d for old v%d from %d vertices and %d ridges.\n",
839 trace0((
qh ferr, 14,
"qh_find_newvertex: no vertex for renaming v%d(all duplicated ridges) during p%d\n",
840 oldvertex->
id,
qh furthest_id));
862 realT dist, mindist, maxdist;
879 *bestfacet= neighbor;
914 facetT *neighbor, **neighborp, *bestfacet= NULL;
920 qh_fprintf(
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 ferr, 6095,
"qhull internal error (qh_findbestneighbor): no neighbors for f%d\n", facet->
id);
952 trace3((
qh ferr, 3002,
"qh_findbestneighbor: f%d is best neighbor for f%d testcentrum? %d nonconvex? %d dist %2.2g min %2.2g max %2.2g\n",
953 bestfacet->
id, facet->
id, testcentrum, nonconvex, *distp, *mindistp, *maxdistp));
983 facetT *facet, *neighbor, *facet1;
984 realT dist, mindist, maxdist;
989 trace4((
qh ferr, 4024,
"qh_flippedmerges: begin\n"));
1004 trace0((
qh ferr, 15,
"qh_flippedmerges: merge flipped f%d into f%d dist %2.2g during p%d\n",
1005 facet1->
id, neighbor->
id, dist,
qh furthest_id));
1008 if (
qh PRINTstatistics) {
1024 trace1((
qh ferr, 1010,
"qh_flippedmerges: merged %d flipped facets into a good neighbor\n", nummerge));
1059 realT dist1, dist2, mindist1, mindist2, maxdist1, maxdist2;
1061 int nummerge=0, numflip=0;
1065 trace4((
qh ferr, 4025,
"qh_forcedmerges: begin\n"));
1080 if (facet1 == facet2)
1083 qh_fprintf(
qh ferr, 6096,
"qhull internal error (qh_forcedmerges): f%d and f%d had a duplicate ridge but as f%d and f%d they are no longer neighbors\n",
1102 if (
qh PRINTstatistics) {
1117 trace1((
qh ferr, 1011,
"qh_forcedmerges: merged %d facets and %d flipped facets across duplicated ridges\n",
1118 nummerge, numflip));
1152 facetT *facet, *neighbor, **neighborp;
1157 trace4((
qh ferr, 4026,
"qh_getmergeset: started.\n"));
1171 if (neighbor->
seen) {
1174 }
else if (neighbor->
visitid !=
qh visit_id) {
1188 if (
qh POSTmerging) {
1194 trace2((
qh ferr, 2021,
"qh_getmergeset: %d merges found\n", nummerges));
1225 facetT *facet, *neighbor, **neighborp;
1253 if (
qh POSTmerging) {
1259 trace2((
qh ferr, 2022,
"qh_getmergeset_initial: %d merges found\n", nummerges));
1285 }
else if (ridgeA == ridge)
1287 if (++hash == hashsize)
1328 if (ridgeA == ridge)
1335 if (++hash == hashsize)
1371 facetT *neighbor, **neighborp;
1373 int neighbor_i, neighbor_n;
1378 trace4((
qh ferr, 4027,
"qh_makeridges: make ridges for f%d\n", facet->
id));
1391 else if (!neighbor->
seen) {
1395 toporient= facet->
toporient ^ (neighbor_i & 0x1);
1400 ridge->
top= neighbor;
1405 if (facet->
toporient ^ (skip1 & 0x1) ^ flip) {
1406 ridge->
top= neighbor;
1461 facetT *facet, *neighbor, **neighborp;
1466 trace4((
qh ferr, 4028,
"qh_mark_dupridges: identify duplicate ridges\n"));
1496 trace1((
qh ferr, 1012,
"qh_mark_dupridges: found %d duplicated ridges\n",
1527 facetT *neighbor, **neighborp;
1530 trace4((
qh ferr, 4029,
"qh_maydropneighbor: test f%d for no ridges to a neighbor\n",
1538 trace0((
qh ferr, 17,
"qh_maydropneighbor: facets f%d and f%d are no longer neighbors during p%d\n",
1539 facet->
id, neighbor->
id,
qh furthest_id));
1547 trace2((
qh ferr, 2023,
"qh_maydropneighbors: f%d is degenerate.\n", neighbor->
id));
1554 trace2((
qh ferr, 2024,
"qh_maydropneighbors: f%d is degenerate.\n", facet->
id));
1587 facetT *bestneighbor, *facet1, *facet2;
1588 realT dist, mindist, maxdist;
1596 mergetype= merge->
type;
1608 qh_fprintf(
qh ferr, 6097,
"qhull internal error (qh_merge_degenredunant): f%d redundant but f%d has no replacement\n",
1609 facet1->
id, facet2->
id);
1614 if (facet1 == facet2) {
1618 trace2((
qh ferr, 2025,
"qh_merge_degenredundant: facet f%d is contained in f%d, will merge\n",
1619 facet1->
id, facet2->
id));
1626 trace2((
qh ferr, 2026,
"qh_merge_degenredundant: facet f%d has no neighbors. Deleted\n", facet1->
id));
1632 trace2((
qh ferr, 2027,
"qh_merge_degenredundant: deleted v%d because f%d has no neighbors\n",
1633 vertex->
id, facet1->
id));
1639 }
else if (size <
qh hull_dim) {
1641 trace2((
qh ferr, 2028,
"qh_merge_degenredundant: facet f%d has %d neighbors, merge into f%d dist %2.2g\n",
1642 facet1->
id, size, bestneighbor->
id, dist));
1645 if (
qh PRINTstatistics) {
1674 facetT *bestfacet, *bestneighbor, *neighbor;
1675 realT dist, dist2, mindist, mindist2, maxdist, maxdist2;
1679 trace3((
qh ferr, 3003,
"qh_merge_nonconvex: merge #%d for f%d and f%d type %d\n",
1693 && ((mindist >= -
qh MAXcoplanar && maxdist <=
qh max_outside)
1694 || dist * 1.5 < dist2)) {
1698 trace2((
qh ferr, 2029,
"qh_merge_nonconvex: avoid merging old facet f%d dist %2.2g. Use f%d dist %2.2g instead\n",
1699 facet2->
id, dist2, facet1->
id, dist2));
1705 if (
qh PRINTstatistics) {
1752 int traceonce=
False, tracerestore= 0;
1759 if (!
qh TRInormals) {
1760 qh_fprintf(
qh ferr, 6224,
"Qhull internal error (qh_mergecycle): does not work for tricoplanar facets. Use option 'Q11'\n");
1766 if (!
qh VERTEXneighbors)
1769 if (
qh REPORTfreq2 &&
qh POSTmerging) {
1776 trace2((
qh ferr, 2030,
"qh_mergecycle: merge #%d for facets from cycle f%d into coplanar horizon f%d\n",
1778 if (newfacet ==
qh tracefacet) {
1779 tracerestore=
qh IStracing;
1781 qh_fprintf(
qh ferr, 8068,
"qh_mergecycle: ========= trace merge %d of samecycle %d into trace f%d, furthest is p%d\n",
1785 if (
qh IStracing >=4) {
1791 if (
qh IStracing >=4)
1792 qh_errprint(
"MERGING CYCLE", samecycle, newfacet, NULL, NULL);
1807 qh_fprintf(
qh ferr, 8072,
"qh_mergecycle: end of trace facet\n");
1808 qh IStracing= tracerestore;
1842 facetT *facet, *same, *prev, *horizon;
1843 facetT *samecycle= NULL, *nextfacet, *nextsame;
1844 vertexT *apex, *vertex, **vertexp;
1845 int cycles=0, total=0, facets, nummerge;
1847 trace2((
qh ferr, 2031,
"qh_mergecycle_all: begin\n"));
1848 for (facet= facetlist; facet && (nextfacet= facet->
next); facet= nextfacet) {
1851 if (!facet->mergehorizon) {
1852 qh_fprintf(
qh ferr, 6225,
"Qhull internal error (qh_mergecycle_all): f%d without normal\n", facet->id);
1856 if (facet->f.samecycle == facet) {
1871 same= (same == facet ? NULL :nextsame)) {
1884 while (nextfacet && nextfacet->cycledone)
1885 nextfacet= nextfacet->
next;
1888 nummerge= horizon->
nummerge + facets;
1892 horizon->
nummerge= (
short unsigned int)nummerge;
1902 trace1((
qh ferr, 1013,
"qh_mergecycle_all: merged %d same cycles or facets into coplanar horizons\n", cycles));
1932 trace4((
qh ferr, 4030,
"qh_mergecycle_facets: make newfacet new and samecycle deleted\n"));
1939 for (same= samecycle->
f.
samecycle; same; same= (same == samecycle ? NULL : next)) {
1948 trace3((
qh ferr, 3004,
"qh_mergecycle_facets: merged facets from cycle f%d into f%d\n",
1949 samecycle->
id, newfacet->
id));
1988 facetT *same, *neighbor, **neighborp;
1989 int delneighbors= 0, newneighbors= 0;
1990 unsigned int samevisitid;
1993 samevisitid= ++
qh visit_id;
2000 trace4((
qh ferr, 4031,
"qh_mergecycle_neighbors: delete shared neighbors from newfacet\n"));
2002 if (neighbor->
visitid == samevisitid) {
2010 trace4((
qh ferr, 4032,
"qh_mergecycle_neighbors: update neighbors\n"));
2013 if (neighbor->
visitid == samevisitid)
2022 if (ridge->
top == same) {
2023 ridge->
top= newfacet;
2025 }
else if (ridge->
bottom == same) {
2046 trace2((
qh ferr, 2032,
"qh_mergecycle_neighbors: deleted %d neighbors and added %d\n",
2047 delneighbors, newneighbors));
2085 facetT *same, *neighbor= NULL;
2086 int numold=0, numnew=0;
2087 int neighbor_i, neighbor_n;
2088 unsigned int samevisitid;
2093 trace4((
qh ferr, 4033,
"qh_mergecycle_ridges: delete shared ridges from newfacet\n"));
2094 samevisitid=
qh visit_id -1;
2097 if (neighbor->
visitid == samevisitid)
2102 trace4((
qh ferr, 4034,
"qh_mergecycle_ridges: add ridges to newfacet\n"));
2105 if (ridge->
top == same) {
2106 ridge->
top= newfacet;
2108 }
else if (ridge->
bottom == same) {
2110 neighbor= ridge->
top;
2111 }
else if (ridge->
top == newfacet || ridge->
bottom == newfacet) {
2116 qh_fprintf(
qh ferr, 6098,
"qhull internal error (qh_mergecycle_ridges): bad ridge r%d\n", ridge->
id);
2119 if (neighbor == newfacet) {
2123 }
else if (neighbor->
visitid == samevisitid) {
2142 toporient= same->
toporient ^ (neighbor_i & 0x1);
2144 ridge->
top= newfacet;
2147 ridge->
top= neighbor;
2157 trace2((
qh ferr, 2033,
"qh_mergecycle_ridges: found %d old ridges and %d new ones\n",
2187 facetT *neighbor, **neighborp;
2188 unsigned int mergeid;
2189 vertexT *vertex, **vertexp, *apex;
2192 trace4((
qh ferr, 4035,
"qh_mergecycle_vneighbors: update vertex neighbors for newfacet\n"));
2193 mergeid=
qh visit_id - 1;
2201 if (neighbor->
visitid == mergeid)
2208 trace2((
qh ferr, 2034,
"qh_mergecycle_vneighbors: deleted v%d when merging cycle f%d into f%d\n",
2209 vertex->
id, samecycle->
id, newfacet->
id));
2216 trace3((
qh ferr, 3005,
"qh_mergecycle_vneighbors: merged vertices from cycle f%d into f%d\n",
2217 samecycle->
id, newfacet->
id));
2274 int tracerestore=0, nummerge;
2277 if (!
qh TRInormals) {
2278 qh_fprintf(
qh ferr, 6226,
"Qhull internal error (qh_mergefacet): does not work for tricoplanar facets. Use option 'Q11'\n");
2287 if (
qh REPORTfreq2 &&
qh POSTmerging) {
2292 if (
qh build_cnt >=
qh RERUN) {
2293 if (mindist && (-*mindist >
qh TRACEdist || *maxdist >
qh TRACEdist)) {
2295 qh IStracing=
qh TRACElevel;
2297 qh_fprintf(
qh ferr, 8075,
"qh_mergefacet: ========= trace wide merge #%d(%2.2g) for f%d into f%d, last point was p%d\n",
zzval_(
Ztotmerge),
2298 fmax_(-*mindist, *maxdist), facet1->
id, facet2->
id,
qh furthest_id);
2299 }
else if (facet1 ==
qh tracefacet || facet2 ==
qh tracefacet) {
2300 tracerestore=
qh IStracing;
2303 qh_fprintf(
qh ferr, 8076,
"qh_mergefacet: ========= trace merge #%d involving f%d, furthest is p%d\n",
2307 if (
qh IStracing >= 2) {
2315 qh_fprintf(
qh ferr, 8077,
"qh_mergefacet: #%d merge f%d into f%d, mindist= %2.2g, maxdist= %2.2g\n",
2320 qh_fprintf(
qh ferr, 6099,
"qhull internal error (qh_mergefacet): either f%d and f%d are the same or one is a visible facet\n",
2321 facet1->
id, facet2->
id);
2324 if (
qh num_facets -
qh num_visible <=
qh hull_dim + 1) {
2326 qhull precision error: Only %d facets remain. Can not merge another\n\
2327 pair. The input is too degenerate or the convexity constraints are\n\
2328 too strong.\n",
qh hull_dim+1);
2329 if (
qh hull_dim >= 5 && !
qh MERGEexact)
2330 qh_fprintf(
qh ferr, 8079,
"Option 'Qx' may avoid this problem.\n");
2333 if (!
qh VERTEXneighbors)
2337 if (
qh IStracing >=4)
2338 qh_errprint(
"MERGING", facet1, facet2, NULL, NULL);
2347 && (*maxdist >
qh WIDEfacet || *mindist < -
qh WIDEfacet)) {
2356 facet2->
nummerge= (
short unsigned int)nummerge;
2366 if (
qh hull_dim == 2)
2393 qh_fprintf(
qh ferr, 8080,
"qh_mergefacet: end of wide tracing\n");
2394 qh IStracing= tracerestore;
2423 vertexT *vertex1A, *vertex1B, *vertex2A, *vertex2B, *vertexA, *vertexB;
2424 facetT *neighbor1A, *neighbor1B, *neighbor2A, *neighbor2B, *neighborA, *neighborB;
2434 if (vertex1A == vertex2A) {
2437 neighborA= neighbor2A;
2438 neighborB= neighbor1A;
2439 }
else if (vertex1A == vertex2B) {
2442 neighborA= neighbor2B;
2443 neighborB= neighbor1A;
2444 }
else if (vertex1B == vertex2A) {
2447 neighborA= neighbor2A;
2448 neighborB= neighbor1B;
2452 neighborA= neighbor2B;
2453 neighborB= neighbor1B;
2456 if (vertexA->
id > vertexB->
id) {
2459 if (vertexB == vertex2A)
2466 if (vertexB == vertex2B)
2473 trace4((
qh ferr, 4036,
"qh_mergefacet2d: merged v%d and neighbor f%d of f%d into f%d\n",
2474 vertexA->
id, neighborB->
id, facet1->
id, facet2->
id));
2498 facetT *neighbor, **neighborp;
2500 trace4((
qh ferr, 4037,
"qh_mergeneighbors: merge neighbors of f%d and f%d\n",
2501 facet1->
id, facet2->
id));
2516 }
else if (neighbor != facet2) {
2549 trace4((
qh ferr, 4038,
"qh_mergeridges: merge ridges of f%d and f%d\n",
2550 facet1->
id, facet2->
id));
2552 if ((ridge->
top == facet1) || (ridge->
bottom == facet1)) {
2560 if (ridge->
top == facet1)
2613 vertexT *vertex, **vertexp, *apex;
2616 int vertex_i= -1, vertex_n;
2617 facetT *neighbor, **neighborp, *otherfacet;
2645 trace4((
qh ferr, 4039,
"qh_mergesimplex: merge apex v%d of f%d into facet f%d\n",
2646 apex->
id, facet1->
id, facet2->
id));
2648 if (vertex->
id < apex->
id) {
2650 }
else if (vertex->
id == apex->
id) {
2664 trace4((
qh ferr, 4040,
"qh_mergesimplex: update vertex neighbors of f%d\n",
2667 if (vertex == apex && !issubset)
2675 trace4((
qh ferr, 4041,
"qh_mergesimplex: merge ridges and neighbors of f%d into f%d\n",
2676 facet1->
id, facet2->
id));
2682 if (otherfacet == facet2) {
2689 if (otherfacet->
visitid !=
qh visit_id) {
2703 if (ridge->
top == facet1)
2710 trace3((
qh ferr, 3006,
"qh_mergesimplex: merged simplex f%d apex v%d into facet f%d\n",
2727 trace2((
qh ferr, 2035,
"qh_mergevertex_del: deleted v%d when merging f%d into f%d\n",
2728 vertex->
id, facet1->
id, facet2->
id));
2753 trace4((
qh ferr, 4042,
"qh_mergevertex_neighbors: merge vertex neighbors of f%d and f%d\n",
2754 facet1->
id, facet2->
id));
2755 if (
qh tracevertex) {
2756 qh_fprintf(
qh ferr, 8081,
"qh_mergevertex_neighbors: of f%d and f%d at furthest p%d f0= %p\n",
2757 facet1->
id, facet2->
id,
qh furthest_id,
qh tracevertex->neighbors->e[0].p);
2790 setT *mergedvertices;
2795 if (!*vertex2 || vertex->
id > (*vertex2)->id)
2798 while (*vertex2 && (*vertex2)->
id > vertex->
id)
2800 if (!*vertex2 || (*vertex2)->
id < vertex->
id)
2809 qh_fprintf(
qh ferr, 6100,
"qhull internal error (qh_mergevertices): facets did not share a ridge\n");
2813 *vertices2= mergedvertices;
2842 facetT *neighbor, **neighborp, *neighborA, *neighborB;
2844 int neighbor_i, neighbor_n;
2862 if (neighbor_i >= 2) {
2872 trace3((
qh ferr, 3007,
"qh_neighbor_intersections: %d vertices in neighbor intersection of v%d\n",
2926 int numshare=0, numrename= 0;
2931 if (
qh hull_dim == 2)
2938 if (!
qh MERGEvertices)
2943 if (!
qh MERGEvertices)
2970 trace1((
qh ferr, 1014,
"qh_reducevertices: renamed %d shared vertices and %d redundant vertices. Degen? %d\n",
2971 numshare, numrename, degenredun));
2999 setT *vertices, *ridges;
3001 trace3((
qh ferr, 3008,
"qh_redundant_vertex: check if v%d can be renamed\n", vertex->
id));
3034 trace4((
qh ferr, 4043,
"qh_remove_extravertices: test f%d for extra vertices\n",
3043 if (!vertex->
seen) {
3052 trace2((
qh ferr, 2036,
"qh_remove_extravertices: v%d deleted because it's lost all ridges\n", vertex->
id));
3054 trace3((
qh ferr, 3009,
"qh_remove_extravertices: v%d removed from f%d because it's lost all ridges\n", vertex->
id, facet->
id));
3089 facetT *neighbor, **neighborp, *neighborA= NULL;
3090 setT *vertices, *ridges;
3095 if (neighborA == facet)
3097 }
else if (
qh hull_dim == 3)
3107 neighborA= neighbor;
3111 qh_fprintf(
qh ferr, 6101,
"qhull internal error (qh_rename_sharedvertex): v%d's neighbors not in f%d\n",
3112 vertex->
id, facet->
id);
3113 qh_errprint(
"ERRONEOUS", facet, NULL, NULL, vertex);
3121 trace2((
qh ferr, 2037,
"qh_rename_sharedvertex: p%d(v%d) is shared by f%d(%d ridges) and f%d\n",
3159 if (vertex == newvertex) {
3163 trace2((
qh ferr, 2038,
"qh_renameridgevertex: ridge r%d deleted. It contained both v%d and v%d\n",
3164 ridge->
id, oldvertex->
id, newvertex->
id));
3168 if (vertex->
id < newvertex->
id)
3173 if (abs(oldnth - nth)%2) {
3174 trace3((
qh ferr, 3010,
"qh_renameridgevertex: swapped the top and bottom of ridge r%d\n",
3214 facetT *neighbor, **neighborp;
3218 if (
qh IStracing >= 2 || oldvertex->
id ==
qh tracevertex_id ||
3219 newvertex->
id ==
qh tracevertex_id)
3226 qh_fprintf(
qh ferr, 8082,
"qh_renamevertex: renamed v%d to v%d in several facets\n",
3227 oldvertex->
id, newvertex->
id);
3241 qh_fprintf(
qh ferr, 8083,
"qh_renamevertex: renamed v%d to v%d in oldfacet f%d\n",
3242 oldvertex->
id, newvertex->
id, oldfacet->
id);
3249 if (istrace ||
qh IStracing)
3250 qh_fprintf(
qh ferr, 8084,
"qh_renamevertex: renamed pinched v%d to v%d between f%d and f%d\n",
3251 oldvertex->
id, newvertex->
id, oldfacet->
id, neighborA->
id);
3297 if (
qh SKIPconvex && !
qh POSTmerging)
3299 if ((!
qh MERGEexact ||
qh POSTmerging) &&
qh cos_max <
REALmax/2) {
3302 if (angle >
qh cos_max) {
3305 trace2((
qh ferr, 2039,
"qh_test_appendmerge: coplanar angle %4.4g between f%d and f%d\n",
3306 angle, facet->
id, neighbor->
id));
3315 if (dist >
qh centrum_radius)
3318 if (dist > -
qh centrum_radius)
3324 if (dist2 >
qh centrum_radius)
3326 else if (!iscoplanar && dist2 > -
qh centrum_radius)
3329 if (!isconcave && (!iscoplanar || (
qh MERGEexact && !
qh POSTmerging)))
3331 if (!okangle &&
qh ANGLEmerge) {
3340 trace0((
qh ferr, 18,
"qh_test_appendmerge: concave f%d to f%d dist %4.4g and reverse dist %4.4g angle %4.4g during p%d\n",
3341 facet->
id, neighbor->
id, dist, dist2, angle,
qh furthest_id));
3345 trace2((
qh ferr, 2040,
"qh_test_appendmerge: coplanar f%d to f%d dist %4.4g, reverse dist %4.4g angle %4.4g\n",
3346 facet->
id, neighbor->
id, dist, dist2, angle));
3377 facetT *newfacet, *neighbor, **neighborp;
3381 trace1((
qh ferr, 1015,
"qh_test_vneighbors: testing vertex neighbors for convexity\n"));
3382 if (!
qh VERTEXneighbors)
3401 trace1((
qh ferr, 1016,
"qh_test_vneighbors: found %d non-convex, vertex neighbors\n",
3403 return (nummerges > 0);
3416 if (
qh IStracing >= 4)
3418 if (facet2 ==
qh tracefacet || (
qh tracevertex &&
qh tracevertex->newlist)) {
3419 qh_fprintf(
qh ferr, 8085,
"qh_tracemerge: trace facet and vertex after merge of f%d and f%d, furthest p%d\n", facet1->
id, facet2->
id,
qh furthest_id);
3420 if (facet2 !=
qh tracefacet)
3422 (
qh tracevertex &&
qh tracevertex->neighbors) ?
3424 NULL,
qh tracevertex);
3426 if (
qh tracevertex) {
3427 if (
qh tracevertex->deleted)
3428 qh_fprintf(
qh ferr, 8086,
"qh_tracemerge: trace vertex deleted at furthest p%d\n",
3433 if (
qh tracefacet) {
3439 if (
qh CHECKfrequently ||
qh IStracing >= 4) {
3469 tp= localtime(&timedata);
3474 At %d:%d:%d & %2.5g CPU secs, qhull has merged %d facets. The hull\n\
3475 contains %d facets and %d vertices.\n",
3476 tp->tm_hour, tp->tm_min, tp->tm_sec, cpu,
3477 total,
qh num_facets -
qh num_visible,
3520 if (size ==
qh hull_dim ||
qh POSTmerging)
3547 facetT *neighbor, **neighborp;
3558 if (
qh PRINTstatistics ||
qh IStracing) {
3563 trace3((
qh ferr, 3011,
"qh_vertexridges: found %d ridges for v%d\n",