30 for (scan= (
int)hash; (elem=
SETelem_(hashtable, scan));
31 scan= (++scan >= hashsize ? 0 : scan)) {
68 facetT *facet, *bestfacet, *errfacet1= NULL, *errfacet2= NULL;
72 int numpart= 0, facet_i, facet_n, notgood= 0, notverified= 0;
75 trace1((
qh,
qh->ferr, 1020,
"qh_check_bestdist: check points below nearest facet. Facet_list f%d\n",
78 maxoutside +=
qh->DISTround;
80 trace1((
qh,
qh->ferr, 1021,
"qh_check_bestdist: check that all points are within %2.2g of best facet\n", maxoutside));
84 qhull output completed. Verifying that %d points are\n\
85 below %2.2g of the nearest %sfacet.\n",
86 qh_setsize(
qh, facets), maxoutside, (
qh->ONLYgood ?
"good " :
""));
92 facet=
qh->facet_list;
95 if (point ==
qh->GOODpointp)
102 if (dist > maxoutside) {
103 if (
qh->ONLYgood && !bestfacet->
good
105 && dist > maxoutside))
109 qh_fprintf(
qh,
qh->ferr, 6109,
"qhull precision error: point p%d is outside facet f%d, distance= %6.8g maxoutside= %6.8g\n",
110 facet_i, bestfacet->
id, dist, maxoutside);
111 if (errfacet1 != bestfacet) {
112 errfacet2= errfacet1;
113 errfacet1= bestfacet;
116 }
else if (unassigned && dist < -qh->MAXcoplanar)
121 qh_fprintf(
qh,
qh->ferr, 8092,
"\n%d points were well inside the hull. If the hull contains\n\
122 a lens-shaped component, these points were not verified. Use\n\
123 options 'Qci Tv' to verify all points.\n", notverified);
124 if (maxdist >
qh->outside_err) {
125 qh_fprintf(
qh,
qh->ferr, 6110,
"qhull precision error (qh_check_bestdist): a coplanar point is %6.2g from convex hull. The maximum value(qh.outside_err) is %6.2g\n",
126 maxdist,
qh->outside_err);
128 }
else if (waserror &&
qh->outside_err >
REALmax/2)
131 trace0((
qh,
qh->ferr, 20,
"qh_check_bestdist: max distance outside %2.2g\n", maxdist));
151 vertexT *vertex, **vertexp, *vertexA, **vertexAp;
152 realT dist, innerplane, mergedist, outerplane, prevdist, ratio;
155 mergedist=
fmin_(dist1, dist2);
157 prevdist=
fmax_(outerplane, innerplane);
160 ratio= mergedist/prevdist;
163 if (vertex > vertexA){
169 trace0((
qh,
qh->ferr, 16,
"qh_check_dupridge: duplicate ridge between f%d and f%d due to nearly-coincident vertices (%2.2g), dist %2.2g, reverse dist %2.2g, ratio %2.2g while processing p%d\n",
170 facet1->
id, facet2->
id, minvertex, dist1, dist2, ratio,
qh->furthest_id));
172 qh_fprintf(
qh,
qh->ferr, 6271,
"qhull precision error (qh_check_dupridge): wide merge (%.0f times wider) due to duplicate ridge with nearly coincident points (%2.2g) between f%d and f%d, merge dist %2.2g, while processing p%d\n- Ignore error with option 'Q12'\n- To be fixed in a later version of Qhull\n",
173 ratio, minvertex, facet1->
id, facet2->
id, mergedist,
qh->furthest_id);
175 qh_fprintf(
qh,
qh->ferr, 8145,
"- A bounding box for the input sites may alleviate this error.\n");
177 qh_fprintf(
qh,
qh->ferr, 8146,
"- Vertex distance %2.2g is greater than %d times maximum distance %2.2g\n Please report to bradb@shore.net with steps to reproduce and all output\n",
219 facetT *facet, *bestfacet, *neighbor, **neighborp, *facetlist;
220 realT dist, maxoutside, minvertex, old_maxoutside;
222 int numpart= 0, facet_i, facet_n, notgood= 0;
223 setT *facets, *vertices;
226 trace1((
qh,
qh->ferr, 1022,
"qh_check_maxout: check and update maxoutside for each facet.\n"));
227 maxoutside= minvertex= 0;
228 if (
qh->VERTEXneighbors
229 && (
qh->PRINTsummary ||
qh->KEEPinside ||
qh->KEEPcoplanar
230 ||
qh->TRACElevel ||
qh->PRINTstatistics
232 trace1((
qh,
qh->ferr, 1023,
"qh_check_maxout: determine actual maxoutside and minvertex\n"));
239 if (-dist >
qh->TRACEdist || dist >
qh->TRACEdist
240 || neighbor ==
qh->tracefacet || vertex ==
qh->tracevertex)
241 qh_fprintf(
qh,
qh->ferr, 8093,
"qh_check_maxout: p%d(v%d) is %.2g from f%d\n",
248 qh->min_vertex= minvertex;
253 old_maxoutside=
fmax_(
qh->max_outside, maxoutside);
257 if (point ==
qh->GOODpointp)
263 if (bestfacet && dist > maxoutside) {
264 if (
qh->ONLYgood && !bestfacet->
good
266 && dist > maxoutside))
271 if (dist >
qh->TRACEdist || (bestfacet && bestfacet ==
qh->tracefacet))
272 qh_fprintf(
qh,
qh->ferr, 8094,
"qh_check_maxout: p%d is %.2g above f%d\n",
273 qh_pointid(
qh, point), dist, (bestfacet ? bestfacet->
id : UINT_MAX));
277 (maxoutside > 2*old_maxoutside);
284 qh->max_outside= maxoutside;
287 trace1((
qh,
qh->ferr, 1024,
"qh_check_maxout: maxoutside %2.2g, min_vertex %2.2g, outside of not good %d\n",
288 maxoutside,
qh->min_vertex, notgood));
307 if (
qh->VERIFYoutput |
qh->IStracing |
qh->CHECKfrequently) {
330 if (dist > *maxoutside) {
331 if (*errfacet1 != facet) {
332 *errfacet2= *errfacet1;
335 qh_fprintf(
qh,
qh->ferr, 6111,
"qhull precision error: point p%d is outside facet f%d, distance= %6.8g maxoutside= %6.8g\n",
366 facetT *facet, *errfacet1= NULL, *errfacet2= NULL;
368 pointT *point, **pointp, *pointtemp;
372 maxoutside +=
qh->DISTround;
374 trace1((
qh,
qh->ferr, 1025,
"qh_check_points: check all points below %2.2g of all facet planes\n",
377 total= (float)
qh->num_good * (
float)
qh->num_points;
379 total= (float)
qh->num_facets * (
float)
qh->num_points;
382 qh_fprintf(
qh,
qh->ferr, 7075,
"qhull input warning: merging without checking outer planes('Q5' or 'Po').\n\
383 Verify may report that a point is outside of a facet.\n");
392 qh_fprintf(
qh,
qh->ferr, 7076,
"qhull input warning: exact merge ('Qx'). Verify may report that a point\n\
393 is outside of a facet. See qh-optq.htm#Qx\n");
394 else if (
qh->SKIPcheckmax ||
qh->NOnearinside)
395 qh_fprintf(
qh,
qh->ferr, 7077,
"qhull input warning: no outer plane check ('Q5') or no processing of\n\
396 near-inside points ('Q8'). Verify may report that a point is outside\n\
399 if (
qh->PRINTprecision) {
402 Output completed. Verifying that all points are below outer planes of\n\
403 all %sfacets. Will make %2.0f distance computations.\n",
404 (
qh->ONLYgood ?
"good " :
""), total);
407 Output completed. Verifying that all points are below %2.2g of\n\
408 all %sfacets. Will make %2.0f distance computations.\n",
409 maxoutside, (
qh->ONLYgood ?
"good " :
""), total);
412 if (!facet->
good &&
qh->ONLYgood)
417 qh_fprintf(
qh,
qh->ferr, 7061,
"qhull warning (qh_check_points): missing normal for facet f%d\n", facet->
id);
427 if (point !=
qh->GOODpointp)
428 qh_check_point(
qh, point, facet, &maxoutside, &maxdist, &errfacet1, &errfacet2);
431 if (point !=
qh->GOODpointp)
432 qh_check_point(
qh, point, facet, &maxoutside, &maxdist, &errfacet1, &errfacet2);
435 if (maxdist >
qh->outside_err) {
436 qh_fprintf(
qh,
qh->ferr, 6112,
"qhull precision error (qh_check_points): a coplanar point is %6.2g from convex hull. The maximum value(qh.outside_err) is %6.2g\n",
437 maxdist,
qh->outside_err );
439 }
else if (errfacet1 &&
qh->outside_err >
REALmax/2)
442 trace0((
qh,
qh->ferr, 21,
"qh_check_points: max distance outside %2.2g\n", maxdist));
476 facetT *facet, *neighbor, **neighborp, *errfacet1=NULL, *errfacet2=NULL;
483 trace1((
qh,
qh->ferr, 1026,
"qh_checkconvex: check all ridges are convex\n"));
491 qh_fprintf(
qh,
qh->ferr, 6113,
"qhull precision error: f%d is flipped(interior point is outside)\n",
498 allsimplicial=
False;
505 allsimplicial=
False;
509 if (dist > -
qh->DISTround) {
512 qh_fprintf(
qh,
qh->ferr, 6114,
"qhull precision error: initial simplex is not convex. Distance=%.2g\n", dist);
515 if (dist >
qh->DISTround) {
518 qh_fprintf(
qh,
qh->ferr, 6115,
"qhull precision error: f%d is concave to f%d, since p%d(v%d) is %6.4g above\n",
523 }
else if (
qh->ZEROcentrum) {
527 qh_fprintf(
qh,
qh->ferr, 6116,
"qhull precision error: f%d is clearly not convex to f%d, since p%d(v%d) is %6.4g above\n",
536 trace0((
qh,
qh->ferr, 22,
"qhull precision error: f%d may be coplanar to f%d, since p%d(v%d) is within %6.4g during p%d\n",
542 if (!allsimplicial) {
549 centrum_warning=
True;
550 qh_fprintf(
qh,
qh->ferr, 7062,
"qhull warning: recomputing centrums for convexity test. This may lead to false, precision errors.\n");
562 if (dist >
qh->DISTround) {
565 qh_fprintf(
qh,
qh->ferr, 6117,
"qhull precision error: f%d is concave to f%d. Centrum of f%d is %6.4g above f%d\n",
566 facet->
id, neighbor->
id, facet->
id, dist, neighbor->
id);
570 }
else if (dist >= 0.0) {
574 qh_fprintf(
qh,
qh->ferr, 6118,
"qhull precision error: f%d is coplanar or concave to f%d. Centrum of f%d is %6.4g above f%d\n",
575 facet->
id, neighbor->
id, facet->
id, dist, neighbor->
id);
585 if (waserror && !
qh->FORCEoutput)
628 facetT *neighbor, **neighborp, *errother=NULL;
629 ridgeT *ridge, **ridgep, *errridge= NULL, *ridge2;
631 unsigned previousid= INT_MAX;
632 int numneighbors, numvertices, numridges=0, numRvertices=0;
634 int skipA, skipB, ridge_i, ridge_n, i;
638 qh_fprintf(
qh,
qh->ferr, 6119,
"qhull internal error (qh_checkfacet): facet f%d is on the visible_list\n",
643 qh_fprintf(
qh,
qh->ferr, 6120,
"qhull internal error (qh_checkfacet): facet f%d does not have a normal\n",
654 qh_fprintf(
qh,
qh->ferr, 6121,
"qhull internal error (qh_checkfacet): deleted vertex v%d in f%d\n", vertex->
id, facet->
id);
658 if (vertex->
id >= previousid) {
659 qh_fprintf(
qh,
qh->ferr, 6122,
"qhull internal error (qh_checkfacet): vertices of f%d are not in descending id order at v%d\n", facet->
id, vertex->
id);
663 previousid= vertex->
id;
669 if (numvertices+numneighbors != 2*
qh->hull_dim
671 qh_fprintf(
qh,
qh->ferr, 6123,
"qhull internal error (qh_checkfacet): for simplicial facet f%d, #vertices %d + #neighbors %d != 2*qh->hull_dim\n",
672 facet->
id, numvertices, numneighbors);
678 &&(numvertices < qh->hull_dim || numneighbors < qh->hull_dim)
680 qh_fprintf(
qh,
qh->ferr, 6124,
"qhull internal error (qh_checkfacet): for facet f%d, #vertices %d or #neighbors %d < qh->hull_dim\n",
681 facet->
id, numvertices, numneighbors);
685 if (numridges < numneighbors
686 ||(
qh->hull_dim == 3 && numvertices > numridges && !
qh->NEWfacets)
687 ||(
qh->hull_dim == 2 && numridges + numvertices + numneighbors != 6)) {
689 qh_fprintf(
qh,
qh->ferr, 6125,
"qhull internal error (qh_checkfacet): for facet f%d, #ridges %d < #neighbors %d or(3-d) > #vertices %d or(2-d) not all 2\n",
690 facet->
id, numridges, numneighbors, numvertices);
697 qh_fprintf(
qh,
qh->ferr, 6126,
"qhull internal error (qh_checkfacet): facet f%d still has a MERGE or DUP neighbor\n", facet->
id);
704 qh_fprintf(
qh,
qh->ferr, 6127,
"qhull internal error (qh_checkfacet): facet f%d has neighbor f%d, but f%d does not have neighbor f%d\n",
705 facet->
id, neighbor->
id, neighbor->
id, facet->
id);
709 if (!neighbor->
seen) {
710 qh_fprintf(
qh,
qh->ferr, 6128,
"qhull internal error (qh_checkfacet): facet f%d has a duplicate neighbor f%d\n",
711 facet->
id, neighbor->
id);
723 qh_fprintf(
qh,
qh->ferr, 6129,
"qhull internal error (qh_checkfacet): facet f%d has a duplicate ridge r%d\n",
724 facet->
id, ridge->
id);
730 if (numRvertices !=
qh->hull_dim - 1) {
731 qh_fprintf(
qh,
qh->ferr, 6130,
"qhull internal error (qh_checkfacet): ridge between f%d and f%d has %d vertices\n",
739 qh_fprintf(
qh,
qh->ferr, 6131,
"qhull internal error (qh_checkfacet): for facet f%d, neighbor f%d of ridge r%d not in facet\n",
740 facet->
id, neighbor->
id, ridge->
id);
747 if (!neighbor->
seen) {
748 qh_fprintf(
qh,
qh->ferr, 6132,
"qhull internal error (qh_checkfacet): facet f%d does not have a ridge for neighbor f%d\n",
749 facet->
id, neighbor->
id);
766 qh_fprintf(
qh,
qh->ferr, 6133,
"qhull internal error (qh_checkfacet): vertex v%d in r%d not in f%d intersect f%d\n",
767 vertex->
id, ridge->
id, facet->
id, neighbor->
id);
775 if (!vertex->
seen2) {
776 if (
qh->IStracing >=3 || !
qh->MERGING) {
777 qh_fprintf(
qh,
qh->ferr, 6134,
"qhull precision error (qh_checkfacet): vertex v%d in f%d intersect f%d but\n\
778 not in a ridge. This is ok under merging. Last point was p%d\n",
779 vertex->
id, facet->
id, neighbor->
id,
qh->furthest_id);
780 if (!
qh->FORCEoutput && !
qh->MERGING) {
797 qh_fprintf(
qh,
qh->ferr, 6135,
"qhull internal error (qh_checkfacet): facet f%d skip %d and neighbor f%d skip %d do not match \n",
798 facet->
id, skipA, neighbor->
id, skipB);
805 if (
qh->hull_dim < 5 && (
qh->IStracing > 2 ||
qh->CHECKfrequently)) {
807 for (i=ridge_i+1; i < ridge_n; i++) {
810 qh_fprintf(
qh,
qh->ferr, 6227,
"Qhull internal error (qh_checkfacet): ridges r%d and r%d have the same vertices\n",
811 ridge->
id, ridge2->id);
819 qh_errprint(
qh,
"ERRONEOUS", facet, errother, errridge, NULL);
836 if (facetlist ==
qh->facet_list)
840 qh_fprintf(
qh,
qh->ferr, 6136,
"qhull precision error: facet f%d is flipped, distance= %6.12g\n",
842 if (!
qh->FORCEoutput) {
850 A flipped facet occurs when its distance to the interior point is\n\
851 greater than %2.2g, the maximum roundoff error.\n", -
qh->DISTround);
880 vertexT *vertex, **vertexp, *vertexlist;
881 int numfacets= 0, numvertices= 0, numridges= 0;
882 int totvneighbors= 0, totvertices= 0;
885 trace1((
qh,
qh->ferr, 1027,
"qh_checkpolygon: check all facets from f%d\n", facetlist->
id));
886 if (facetlist !=
qh->facet_list ||
qh->ONLYgood)
889 if (facet ==
qh->visible_list)
893 if (facet ==
qh->facet_next)
901 qh_fprintf(
qh,
qh->ferr, 6137,
"qhull internal error (qh_checkpolygon): f%d has outside points before qh->facet_next\n",
911 if (
qh->visible_list && !visibleseen && facetlist ==
qh->facet_list) {
912 qh_fprintf(
qh,
qh->ferr, 6138,
"qhull internal error (qh_checkpolygon): visible list f%d no longer on facet list\n",
qh->visible_list->id);
916 if (facetlist ==
qh->facet_list)
917 vertexlist=
qh->vertex_list;
918 else if (facetlist ==
qh->newfacet_list)
919 vertexlist=
qh->newvertex_list;
930 numridges +=
qh->hull_dim;
939 qh_fprintf(
qh,
qh->ferr, 6139,
"qhull internal error (qh_checkpolygon): unknown point %p for vertex v%d first_point %p\n",
940 vertex->
point, vertex->
id,
qh->first_point);
946 qh->vertex_visit += (
unsigned int)numfacets;
947 if (facetlist ==
qh->facet_list) {
948 if (numfacets !=
qh->num_facets -
qh->num_visible) {
949 qh_fprintf(
qh,
qh->ferr, 6140,
"qhull internal error (qh_checkpolygon): actual number of facets is %d, cumulative facet count is %d - %d visible facets\n",
950 numfacets,
qh->num_facets,
qh->num_visible);
954 if (
qh->VERTEXneighbors) {
963 if (totvneighbors != totvertices) {
964 qh_fprintf(
qh,
qh->ferr, 6141,
"qhull internal error (qh_checkpolygon): vertex neighbors inconsistent. Totvneighbors %d, totvertices %d\n",
965 totvneighbors, totvertices);
970 qh_fprintf(
qh,
qh->ferr, 6142,
"qhull internal error (qh_checkpolygon): actual number of vertices is %d, cumulative vertex count is %d\n",
974 if (
qh->hull_dim == 2 && numvertices != numfacets) {
975 qh_fprintf(
qh,
qh->ferr, 6143,
"qhull internal error (qh_checkpolygon): #vertices %d != #facets %d\n",
976 numvertices, numfacets);
979 if (
qh->hull_dim == 3 && numvertices + numfacets - numridges/2 != 2) {
980 qh_fprintf(
qh,
qh->ferr, 7063,
"qhull warning: #vertices %d + #facets %d - #edges %d != 2\n\
981 A vertex appears twice in a edge list. May occur during merging.",
982 numvertices, numfacets, numridges/2);
1003 facetT *neighbor, **neighborp, *errfacet=NULL;
1006 qh_fprintf(
qh,
qh->ferr, 6144,
"qhull internal error (qh_checkvertex): unknown point id %p\n", vertex->
point);
1009 if (vertex->
id >=
qh->vertex_id) {
1010 qh_fprintf(
qh,
qh->ferr, 6145,
"qhull internal error (qh_checkvertex): unknown vertex id %d\n", vertex->
id);
1013 if (!waserror && !vertex->
deleted) {
1017 qh_fprintf(
qh,
qh->ferr, 6146,
"qhull internal error (qh_checkvertex): neighbor f%d does not contain v%d\n", neighbor->
id, vertex->
id);
1043 if (
qh->CENTERtype !=
type) {
1061 trace2((
qh,
qh->ferr, 2043,
"qh_clearcenters: switched to center type %d\n",
type));
1083 facetT *facet= NULL, *newfacet;
1085 int vertex_i, vertex_n, nth;
1090 qh->num_facets=
qh->num_vertices=
qh->num_visible= 0;
1096 newfacet->toporient= (
unsigned char)toporient;
1098 newfacet->newfacet=
True;
1106 if (facet != newfacet)
1107 SETelem_(newfacet->neighbors, nth++)= facet;
1112 trace1((
qh,
qh->ferr, 1028,
"qh_createsimplex: created simplex\n"));
1148 if (vertex ==
qh->tracevertex)
1149 qh->tracevertex= NULL;
1170 ridgeT *ridge, *firstridge;
1172 int cntvertices, cntprojected=0;
1178 if (cntvertices != 3) {
1179 qh_fprintf(
qh,
qh->ferr, 6147,
"qhull internal error (qh_facet3vertex): only %d vertices for simplicial facet f%d\n",
1180 cntvertices, facet->
id);
1193 if (++cntprojected > cntvertices || ridge == firstridge)
1196 if (!ridge || cntprojected != cntvertices) {
1197 qh_fprintf(
qh,
qh->ferr, 6148,
"qhull internal error (qh_facet3vertex): ridges for facet %d don't match up. got at least %d\n",
1198 facet->
id, cntprojected);
1242 int numpart, totpart= 0;
1246 bestdist, isoutside, &totpart);
1247 if (*bestdist < -qh->DISTround) {
1250 if ((isoutside && *isoutside && bestoutside)
1251 || (isoutside && !*isoutside && bestfacet->
upperdelaunay)) {
1253 bestoutside,
False, bestoutside,
1254 bestdist, isoutside, &totpart);
1258 trace3((
qh,
qh->ferr, 3014,
"qh_findbestfacet: f%d dist %2.2g isoutside %d totpart %d\n",
1259 bestfacet->
id, *bestdist, (isoutside ? *isoutside : UINT_MAX), totpart));
1279 facetT *neighbor, **neighborp, *bestfacet= NULL;
1291 if (dist > bestdist) {
1292 bestfacet= neighbor;
1306 if (dist > bestdist) {
1307 bestfacet= neighbor;
1316 trace3((
qh,
qh->ferr, 3025,
"qh_findbestlower: all neighbors of facet %d are flipped or upper Delaunay. Search all facets\n",
1321 *bestdistp= bestdist;
1322 trace3((
qh,
qh->ferr, 3015,
"qh_findbestlower: f%d dist %2.2g for f%d p%d\n",
1350 facetT *bestfacet= NULL, *facet;
1357 if (facet->flipped || !facet->normal)
1361 if (dist > *bestdist) {
1364 if (dist >
qh->MINoutside) {
1371 trace3((
qh,
qh->ferr, 3016,
"qh_findfacet_all: f%d dist %2.2g isoutside %d totpart %d\n",
1372 getid_(bestfacet), *bestdist, *isoutside, totpart));
1409 facetT *facet, *bestfacet= NULL;
1417 if (
qh->GOODvertex>0 && !
qh->MERGING) {
1425 if (
qh->GOODpoint && numgood) {
1430 if ((
qh->GOODpoint > 0) ^ (dist > 0.0)) {
1437 if (
qh->GOODthreshold && (numgood || goodhorizon ||
qh->GOODclosest)) {
1443 if (angle < bestangle) {
1450 if (!numgood && (!goodhorizon ||
qh->GOODclosest)) {
1451 if (
qh->GOODclosest) {
1452 if (
qh->GOODclosest->visible)
1453 qh->GOODclosest= NULL;
1456 if (angle < bestangle)
1457 bestfacet=
qh->GOODclosest;
1460 if (bestfacet && bestfacet !=
qh->GOODclosest) {
1461 if (
qh->GOODclosest)
1463 qh->GOODclosest= bestfacet;
1466 trace2((
qh,
qh->ferr, 2044,
"qh_findgood: f%d is closest(%2.2g) to thresholds\n",
1467 bestfacet->
id, bestangle));
1470 }
else if (
qh->GOODclosest) {
1472 qh->GOODclosest= NULL;
1476 trace2((
qh,
qh->ferr, 2045,
"qh_findgood: found %d good facets with %d good horizon\n",
1477 numgood, goodhorizon));
1478 if (!numgood &&
qh->GOODvertex>0 && !
qh->MERGING)
1509 facetT *facet, *bestfacet=NULL;
1511 int numgood=0, startgood;
1513 if (!
qh->GOODvertex && !
qh->GOODthreshold && !
qh->GOODpoint
1514 && !
qh->SPLITthresholds)
1522 if (
qh->GOODvertex <0 || (
qh->GOODvertex > 0 &&
qh->MERGING)) {
1527 qh_fprintf(
qh,
qh->ferr, 7064,
"qhull warning: good vertex p%d does not match last good facet f%d. Ignored.\n",
1530 }
else if (
qh->GOODvertex > 0)
1531 qh_fprintf(
qh,
qh->ferr, 7065,
"qhull warning: point p%d is not a vertex('QV%d').\n",
1532 qh->GOODvertex-1,
qh->GOODvertex-1);
1534 qh_fprintf(
qh,
qh->ferr, 7066,
"qhull warning: point p%d is a vertex for every facet('QV-%d').\n",
1535 -
qh->GOODvertex - 1, -
qh->GOODvertex - 1);
1542 if (
qh->SPLITthresholds) {
1548 if (angle < bestangle) {
1555 if (!numgood && bestfacet) {
1558 trace0((
qh,
qh->ferr, 23,
"qh_findgood_all: f%d is closest(%2.2g) to thresholds\n",
1559 bestfacet->
id, bestangle));
1563 qh->num_good= numgood;
1564 trace0((
qh,
qh->ferr, 24,
"qh_findgood_all: %d good facets remain out of %d facets\n",
1565 numgood, startgood));
1579 facetT *facet, *bestfacet= NULL;
1584 #if qh_COMPUTEfurthest
1592 if (dist > bestdist) {
1601 trace1((
qh,
qh->ferr, 1029,
"qh_furthestnext: made f%d next facet(dist %.2g)\n",
1602 bestfacet->
id, bestdist));
1622 pointT *point, **pointp, *bestpoint= NULL;
1628 if (dist > bestdist) {
1636 #if !qh_COMPUTEfurthest
1641 trace3((
qh,
qh->ferr, 3017,
"qh_furthestout: p%d is furthest outside point of f%d\n",
1654 qh_fprintf(
qh,
qh->ferr, 6149,
"qhull internal error (qh_infiniteloop): potential infinite loop detected\n");
1684 setT *maxpoints, *vertices;
1692 qh->facet_id=
qh->vertex_id=
qh->ridge_id= 0;
1693 qh->visit_id=
qh->vertex_visit= 0;
1696 if (
qh->GOODpoint > 0)
1698 else if (
qh->GOODpoint < 0)
1700 if (
qh->GOODvertex > 0)
1702 else if (
qh->GOODvertex < 0)
1705 && (
qh->GOODpointp <
qh->first_point
1708 && (
qh->GOODvertexp <
qh->first_point
1710 qh_fprintf(
qh,
qh->ferr, 6150,
"qhull input error: either QGn or QVn point is > p%d\n",
1717 qh->MINlastcoord,
qh->MAXlastcoord,
qh->MAXwidth);
1719 if (
qh->DELAUNAY &&
qh->upper_threshold[
qh->hull_dim-1] >
REALmax/2
1720 &&
qh->lower_threshold[
qh->hull_dim-1] < -
REALmax/2) {
1723 && !
qh->GOODthreshold && !
qh->SPLITthresholds)
1727 if (
qh->UPPERdelaunay) {
1732 if (!
qh->GOODthreshold)
1733 qh->SPLITthresholds=
True;
1741 if (
qh->PRINToptions1st ||
qh->TRACElevel ||
qh->IStracing) {
1742 if (
qh->TRACElevel ||
qh->IStracing)
1744 qh->IStracing ?
qh->IStracing :
qh->TRACElevel,
qh->rbox_command,
qh->qhull_command);
1748 qh->facet_next=
qh->facet_list;
1751 qh->cos_max=
qh->premerge_cos;
1752 qh->centrum_radius=
qh->premerge_centrum;
1755 if (
qh->GOODvertex > 0 &&
qh->MERGING) {
1756 qh_fprintf(
qh,
qh->ferr, 6151,
"qhull input error: 'Qg QVn' (only good vertex) does not work with merging.\nUse 'QJ' to joggle the input or 'Q0' to turn off merging.\n");
1759 if (!(
qh->GOODthreshold ||
qh->GOODpoint
1760 || (!
qh->MERGEexact && !
qh->PREmerge &&
qh->GOODvertexp))) {
1761 qh_fprintf(
qh,
qh->ferr, 6152,
"qhull input error: 'Qg' (ONLYgood) needs a good threshold('Pd0D0'), a\n\
1762 good point(QGn or QG-n), or a good vertex with 'QJ' or 'Q0' (QVn).\n");
1765 if (
qh->GOODvertex > 0 && !
qh->MERGING
1768 &dist, !
qh_ALL, &isoutside, &numpart);
1771 qh_fprintf(
qh,
qh->ferr, 6153,
"qhull input error: point for QV%d is inside initial simplex. It can not be made a vertex.\n",
1785 trace1((
qh,
qh->ferr, 1030,
"qh_initbuild: initial hull created and points partitioned\n"));
1803 facetT *facet, *firstfacet, *neighbor, **neighborp;
1811 qh->facet_next=
qh->facet_list;
1813 firstfacet=
qh->facet_list;
1825 trace1((
qh,
qh->ferr, 1031,
"qh_initialhull: initial orientation incorrect. Correct all facets\n"));
1836 if (
qh->DELAUNAY && !
qh->ATinfinity) {
1837 if (
qh->UPPERdelaunay)
1838 qh_fprintf(
qh,
qh->ferr, 6240,
"Qhull precision error: Initial simplex is cocircular or cospherical. Option 'Qs' searches all points. Can not compute the upper Delaunay triangulation or upper Voronoi diagram of cocircular/cospherical points.\n");
1840 qh_fprintf(
qh,
qh->ferr, 6239,
"Qhull precision error: Initial simplex is cocircular or cospherical. Use option 'Qz' for the Delaunay triangulation or Voronoi diagram of cocircular/cospherical points. Option 'Qz' adds a point \"at infinity\". Use option 'Qs' to search all points for the initial simplex.\n");
1844 qh_fprintf(
qh,
qh->ferr, 6154,
"Qhull precision error: Initial simplex is flat (facet %d is coplanar with the interior point)\n",
1853 if (minangle < qh_MAXnarrow && !qh->NOnarrow) {
1854 realT diff= 1.0 + minangle;
1858 if (minangle < qh_WARNnarrow && !qh->RERUN &&
qh->PRINTprecision)
1865 if (
qh->IStracing >= 1) {
1866 qh_fprintf(
qh,
qh->ferr, 8105,
"qh_initialhull: simplex constructed, interior point:");
1867 for (k=0; k <
qh->hull_dim; k++)
1894 setT *vertices, *simplex, *tested;
1896 int idx, point_i, point_n, k;
1903 else if (
qh->RANDOMoutside) {
1907 idx= (int)floor(
qh->num_points * randr);
1910 idx= idx <
qh->num_points ? idx : 0;
1921 if (point_i & 0x1) {
1979 if (vertex->
point == point)
2021 facetT *visible, *newfacet= NULL, *newfacet2= NULL, *neighbor, **neighborp;
2025 qh->newfacet_list=
qh->facet_tail;
2026 qh->newvertex_list=
qh->vertex_tail;
2034 neighbor->seen=
False;
2041 if (!
qh->ONLYgood) {
2043 newfacet= newfacet2;
2051 trace1((
qh,
qh->ferr, 1032,
"qh_makenewfacets: created %d new facets from point p%d to horizon\n",
2053 if (
qh->IStracing >= 4)
2089 boolT same, ismatch;
2091 facetT *facet, *newfacet, *maxmatch= NULL, *maxmatch2= NULL, *nextfacet;
2092 int skip, newskip, nextskip= 0, maxskip= 0, maxskip2= 0, makematch;
2097 trace2((
qh,
qh->ferr, 2046,
"qh_matchduplicates: find duplicate matches for f%d skip %d hash %d hashcount %d\n",
2098 atfacet->
id, atskip, hash, *hashcount));
2099 for (makematch= 0; makematch < 2; makematch++) {
2101 for (newfacet= atfacet, newskip= atskip; newfacet; newfacet= nextfacet, newskip= nextskip) {
2106 scan= (++scan >= hashsize ? 0 : scan)) {
2114 qh_fprintf(
qh,
qh->ferr, 6155,
"qhull internal error (qh_matchduplicates): missing dupridge at f%d skip %d for new f%d skip %d hash %d\n",
2115 facet->
id, skip, newfacet->
id, newskip, hash);
2118 }
else if (ismatch && makematch) {
2126 trace4((
qh,
qh->ferr, 4059,
"qh_matchduplicates: duplicate f%d skip %d matched with new f%d skip %d merge\n",
2127 facet->
id, skip, newfacet->
id, newskip));
2129 }
else if (ismatch) {
2133 if (mindist > maxdist) {
2137 maxmatch2= newfacet;
2140 trace3((
qh,
qh->ferr, 3018,
"qh_matchduplicates: duplicate f%d skip %d new f%d skip %d at dist %2.2g, max is now f%d f%d\n",
2141 facet->
id, skip, newfacet->
id, newskip, mindist,
2142 maxmatch->
id, maxmatch2->id));
2148 if (makematch && !facet
2150 qh_fprintf(
qh,
qh->ferr, 6156,
"qhull internal error (qh_matchduplicates): no MERGEridge match for duplicate f%d skip %d at hash %d\n",
2151 newfacet->
id, newskip, hash);
2158 qh_fprintf(
qh,
qh->ferr, 6157,
"qhull internal error (qh_matchduplicates): no maximum match at duplicate f%d skip %d at hash %d\n",
2159 atfacet->
id, atskip, hash);
2163 SETelem_(maxmatch2->neighbors, maxskip2)= maxmatch;
2166 trace0((
qh,
qh->ferr, 25,
"qh_matchduplicates: duplicate f%d skip %d matched with new f%d skip %d keep\n",
2167 maxmatch->
id, maxskip, maxmatch2->id, maxskip2));
2169 if (
qh->IStracing >= 4)
2170 qh_errprint(
qh,
"DUPLICATED/MATCH", maxmatch, maxmatch2, NULL, NULL);
2202 realT dist, innerplane;
2204 if (!
qh->KEEPcoplanar && !
qh->KEEPinside) {
2209 }
else if (!
qh->KEEPcoplanar || !
qh->KEEPinside) {
2212 innerplane -=
qh->JOGGLEmax * sqrt((
realT)
qh->hull_dim);
2219 if (dist < innerplane) {
2220 if (!
qh->KEEPinside)
2222 }
else if (!
qh->KEEPcoplanar)
2250 vertexT *bestvertex= NULL, *vertex, **vertexp, *apex;
2252 facetT *neighbor, **neighborp;
2254 int dim=
qh->hull_dim;
2259 if (!
qh->VERTEXneighbors || !facet->
center) {
2260 qh_fprintf(
qh,
qh->ferr, 6158,
"qhull internal error (qh_nearvertex): qh.VERTEXneighbors and facet->center required for tricoplanar facets\n");
2267 if (neighbor->
center == center) {
2276 if (dist < bestdist) {
2283 *bestdistp= sqrt(bestdist);
2285 qh_fprintf(
qh,
qh->ferr, 6261,
"qhull internal error (qh_nearvertex): did not find bestvertex for f%d p%d\n", facet->
id,
qh_pointid(
qh, point));
2288 trace3((
qh,
qh->ferr, 3019,
"qh_nearvertex: v%d dist %2.2g for f%d p%d\n",
2309 if (newsize<0 || size<0) {
2310 qh_fprintf(
qh,
qh->qhmem.ferr, 6236,
"qhull error (qh_newhashtable): negative request (%d) or size (%d). Did int overflow due to high-D?\n", newsize, size);
2313 if ((size%3) && (size%5))
2334 memset((
char *) vertex, (
size_t)0,
sizeof(
vertexT));
2335 if (
qh->vertex_id == UINT_MAX) {
2337 qh_fprintf(
qh,
qh->ferr, 6159,
"qhull error: more than 2^32 vertices. vertexT.id field overflows. Vertices would not be sorted correctly.\n");
2340 if (
qh->vertex_id ==
qh->tracevertex_id)
2341 qh->tracevertex= vertex;
2342 vertex->id=
qh->vertex_id++;
2343 vertex->point= point;
2369 vertexT *atvertex, *vertex, *othervertex;
2377 if (ridge == atridge)
2386 if (vertex == atvertex) {
2388 *vertexp= othervertex;
2422 trace1((
qh,
qh->ferr, 1033,
"qh_outcoplanar: move outsideset to coplanarset for qh->NARROWhull\n"));
2426 if (
qh->KEEPcoplanar ||
qh->KEEPnearinside) {
2450 if (id < qh->num_points)
2451 return qh->first_point +
id *
qh->hull_dim;
2452 id -=
qh->num_points;
2475 qh_fprintf(
qh,
qh->ferr, 7067,
"qhull internal warning (point_add): unknown point %p id %d\n",
2477 else if (
id >= size) {
2478 qh_fprintf(
qh,
qh->ferr, 6160,
"qhull internal errror(point_add): point p%d is out of bounds(%d)\n",
2522 if (vertex->
visitid !=
qh->vertex_visit) {
2575 facetT *prevfacet, *list;
2578 trace4((
qh,
qh->ferr, 4061,
"qh_prependfacet: prepend f%d before f%d\n",
2581 (*facetlist)=
qh->facet_tail;
2586 prevfacet->
next= facet;
2588 facet->
next= *facetlist;
2589 if (
qh->facet_list == list)
2590 qh->facet_list= facet;
2591 if (
qh->facet_next == list)
2592 qh->facet_next= facet;
2614 facetT *facet, *neighbor;
2615 int id, facet_i, facet_n, neighbor_i= 0, neighbor_n= 0;
2624 if (neighbor_i == neighbor_n)
2658 if (++count % 100 == 0)
2662 qh_fprintf(
qh,
qh->ferr, 8111,
"\n new facets %d visible facets %d next facet for qh_addpoint %d\n vertices(new %d):",
2667 if (++count % 100 == 0)
2687 facetT *newfacet, *visible;
2688 int totnew=0, totver=0;
2702 qh->newvertex_list= NULL;
2705 qh->newfacet_list= NULL;
2713 qh->visible_list= NULL;
2768 facetT *facet, *nextfacet, *owner;
2769 int onlygood=
qh->ONLYgood;
2770 facetT *neighbor, *visible= NULL, *facet1, *facet2, *new_facet_list= NULL;
2771 facetT *orig_neighbor= NULL, *otherfacet;
2772 vertexT *new_vertex_list= NULL;
2775 int neighbor_i, neighbor_n;
2777 if (
qh->hasTriangulation)
2779 trace1((
qh,
qh->ferr, 1034,
"qh_triangulate: triangulate non-simplicial facets\n"));
2780 if (
qh->hull_dim == 2)
2790 qh->newvertex_list=
qh->vertex_tail;
2791 for (facet=
qh->facet_list; facet && facet->
next; facet= nextfacet) {
2792 nextfacet= facet->
next;
2796 if (!new_facet_list)
2797 new_facet_list= facet;
2800 trace2((
qh,
qh->ferr, 2047,
"qh_triangulate: delete null facets from f%d -- apex same as second vertex\n",
getid_(new_facet_list)));
2801 for (facet= new_facet_list; facet && facet->
next; facet= nextfacet) {
2802 nextfacet= facet->
next;
2807 qh_fprintf(
qh,
qh->ferr, 6161,
"qhull error (qh_triangulate): ridges still defined for f%d\n", facet->
id);
2817 trace2((
qh,
qh->ferr, 2048,
"qh_triangulate: delete %d or more mirror facets -- same vertices and neighbors\n",
qh_setsize(
qh,
qh->degen_mergeset)));
2818 qh->visible_list=
qh->facet_tail;
2822 mergetype= merge->
type;
2830 trace2((
qh,
qh->ferr, 2049,
"qh_triangulate: update neighbor lists for vertices from v%d\n",
getid_(new_vertex_list)));
2831 qh->newvertex_list= new_vertex_list;
2832 qh->visible_list= NULL;
2836 trace2((
qh,
qh->ferr, 2050,
"qh_triangulate: identify degenerate tricoplanar facets from f%d\n",
getid_(new_facet_list)));
2837 trace2((
qh,
qh->ferr, 2051,
"qh_triangulate: and replace facet->f.triowner with tricoplanar facets that own center, normal, etc.\n"));
2841 if (neighbor_i == 0) {
2845 orig_neighbor= neighbor;
2850 otherfacet= neighbor;
2851 if (orig_neighbor == otherfacet) {
2861 trace2((
qh,
qh->ferr, 2052,
"qh_triangulate: delete visible facets -- non-simplicial, null, and mirrored facets\n"));
2864 for (facet= new_facet_list; facet && facet->
next; facet= nextfacet) {
2865 nextfacet= facet->
next;
2871 if (visible && !owner) {
2873 trace2((
qh,
qh->ferr, 2053,
"qh_triangulate: all tricoplanar facets degenerate for non-simplicial facet f%d\n",
2882 if (facet->
f.
triowner != visible || visible==NULL) {
2883 qh_fprintf(
qh,
qh->ferr, 6162,
"qhull error (qh_triangulate): tricoplanar facet f%d not owned by its visible, non-simplicial facet f%d\n", facet->
id,
getid_(visible));
2890 nextfacet= visible->
next;
2896 if (!
qh->TRInormals) {
2905 if (visible && !owner) {
2906 trace2((
qh,
qh->ferr, 2054,
"qh_triangulate: all tricoplanar facets degenerate for last non-simplicial facet f%d\n",
2912 qh->ONLYgood= onlygood;
2913 if (
qh->CHECKfrequently)
2915 qh->hasTriangulation=
True;
2956 facetT *neighbor, **neighborp;
2960 trace3((
qh,
qh->ferr, 3020,
"qh_triangulate_facet: triangulate facet f%d\n", facetA->
id));
2962 if (
qh->IStracing >= 4)
2973 qh->newfacet_list=
qh->facet_tail;
2984 if (
qh->TRInormals) {
2988 memcpy((
char *)newfacet->
normal, facetA->
normal,
qh->normal_size);
2994 memcpy((
char *)newfacet->
center, facetA->
center,
qh->center_size);
3011 qh->visible_list= NULL;
3012 if (!(*first_vertex))
3013 (*first_vertex)=
qh->newvertex_list;
3014 qh->newvertex_list= NULL;
3030 int errmirror=
False;
3032 trace3((
qh,
qh->ferr, 3021,
"qh_triangulate_link: relink old facets f%d and f%d between neighbors f%d and f%d\n",
3033 oldfacetA->
id, oldfacetB->
id, facetA->
id, facetB->
id));
3042 qh_fprintf(
qh,
qh->ferr, 6163,
"qhull error (qh_triangulate_link): mirror facets f%d and f%d do not match for old facets f%d and f%d\n",
3043 facetA->
id, facetB->
id, oldfacetA->
id, oldfacetB->
id);
3061 facetT *neighbor, *neighborB;
3062 int neighbor_i, neighbor_n;
3064 trace3((
qh,
qh->ferr, 3022,
"qh_triangulate_mirror: delete mirrored facets f%d and f%d\n",
3065 facetA->
id, facetB->
id));
3068 if (neighbor == neighborB)
3090 facetT *neighbor, *otherfacet;
3092 trace3((
qh,
qh->ferr, 3023,
"qh_triangulate_null: delete null facet f%d\n", facetA->
id));
3122 *vertexsetA= intersection;
3140 while (*vertexA && *vertexB) {
3141 if (*vertexA == *vertexB) {
3143 vertexA++; vertexB++;
3145 if ((*vertexA)->id > (*vertexB)->id)
3151 return intersection;
3178 if (
qh->VERTEXneighbors)
3180 trace1((
qh,
qh->ferr, 1035,
"qh_vertexneighbors: determing neighboring facets for each vertex\n"));
3186 if (vertex->
visitid !=
qh->vertex_visit) {
3193 qh->VERTEXneighbors=
True;
3215 if ((*vertexA)->id > (*vertexB)->id)
3217 if (*vertexA == *vertexB)