70 if (!
qh->STOPpoint && !
qh->STOPcone) {
71 if (
qh->ZEROall_ok && !
qh->TESTvneighbors &&
qh->MERGEexact)
73 if (
qh->ZEROall_ok && !
qh->TESTvneighbors && !
qh->WAScoplanar) {
74 trace2((
qh,
qh->ferr, 2055,
"qh_qhull: all facets are clearly convex and no coplanar points. Post-merging and check of maxout not needed.\n"));
79 (
qh->POSTmerge ?
False :
qh->TESTvneighbors));
80 else if (!
qh->POSTmerge &&
qh->TESTvneighbors)
85 qh->postmerge_cos,
qh->TESTvneighbors);
86 if (
qh->visible_list ==
qh->facet_list) {
97 qh_fprintf(
qh,
qh->ferr, 8115,
"\nTesting all coplanar points.\n");
101 if (
qh->KEEPnearinside && !
qh->maxoutdone)
105 qh_fprintf(
qh,
qh->ferr, 6164,
"qhull internal error (qh_qhull): temporary sets not empty(%d)\n",
111 trace1((
qh,
qh->ferr, 1036,
"Qhull: algorithm completed\n"));
169 int goodvisible, goodhorizon;
172 realT dist, newbalance, pbalance;
174 int numpart, numpoints, numnew, firstnew;
180 qh_fprintf(
qh,
qh->ferr, 6213,
"qhull internal error (qh_addpoint): NULL facet. Need to call qh_findbestfacet first\n");
185 &dist, &isoutside, &numpart);
195 if (
qh->STOPpoint < 0 &&
qh->furthest_id == -
qh->STOPpoint-1) {
200 if (
qh->ONLYgood && !(goodvisible+goodhorizon) && !
qh->GOODclosest) {
209 firstnew=
qh->facet_id;
212 numnew=
qh->facet_id - firstnew;
213 newbalance= numnew - (
realT) (
qh->num_facets-
qh->num_visible)
214 *
qh->hull_dim/
qh->num_vertices;
231 if (
qh->STOPcone &&
qh->furthest_id ==
qh->STOPcone-1) {
236 if (
qh->PREmerge ||
qh->MERGEexact) {
248 }
else if (
qh->BESToutside)
254 pbalance= numpoints - (
realT)
qh->hull_dim
255 * (
qh->num_points -
qh->num_vertices)/
qh->num_vertices;
261 if (
qh->IStracing >= 4) {
262 if (
qh->num_facets < 2000)
266 }
else if (
qh->CHECKfrequently) {
267 if (
qh->num_facets < 50)
272 if (
qh->STOPpoint > 0 &&
qh->furthest_id ==
qh->STOPpoint-1)
276 trace2((
qh,
qh->ferr, 2056,
"qh_addpoint: added p%d new facets %d new balance %2.2g point balance %2.2g\n",
277 qh_pointid(
qh, furthest), numnew, newbalance, pbalance));
295 restart= setjmp(
qh->restartexit);
304 qh_fprintf(
qh,
qh->ferr, 6229,
"qhull precision error: %d attempts to construct a convex hull\n\
305 with joggled input. Increase joggle above 'QJ%2.2g'\n\
306 or modify qh_JOGGLE... parameters in user.h\n",
307 qh->build_cnt,
qh->JOGGLEmax);
310 if (
qh->build_cnt && !restart)
312 }
else if (
qh->build_cnt &&
qh->build_cnt >=
qh->RERUN)
317 if (!
qh->qhull_optionsiz)
318 qh->qhull_optionsiz= (int)strlen(
qh->qhull_options);
320 qh->qhull_options [
qh->qhull_optionsiz]=
'\0';
324 if (
qh->build_cnt ==
qh->RERUN) {
325 qh->IStracing=
qh->TRACElastrun;
327 qh->TRACElevel= (
qh->IStracing?
qh->IStracing : 3);
330 qh->qhmem.IStracing=
qh->IStracing;
370 trace1((
qh,
qh->ferr, 1037,
"qh_buildhull: start build hull\n"));
373 qh_fprintf(
qh,
qh->ferr, 6165,
"qhull internal error (qh_buildhull): visible or new facet f%d in facet list\n",
380 qh_fprintf(
qh,
qh->ferr, 6166,
"qhull internal error (qh_buildhull): new vertex f%d in vertex list\n",
386 if ((
qh->STOPpoint>0 &&
id ==
qh->STOPpoint-1) ||
387 (
qh->STOPpoint<0 &&
id == -
qh->STOPpoint-1) ||
388 (
qh->STOPcone>0 &&
id ==
qh->STOPcone-1)) {
389 trace1((
qh,
qh->ferr, 1038,
"qh_buildhull: stop point or cone P%d in initial hull\n",
id));
393 qh->facet_next=
qh->facet_list;
401 if (
qh->num_outside && !furthest) {
402 qh_fprintf(
qh,
qh->ferr, 6167,
"qhull internal error (qh_buildhull): %d outside points were never processed.\n",
qh->num_outside);
405 trace1((
qh,
qh->ferr, 1039,
"qh_buildhull: completed the hull construction\n"));
438 int total, furthestid;
443 qh->old_randomdist=
qh->RANDOMdist;
447 tp= localtime(&timedata);
452 At %02d:%02d:%02d & %2.5g CPU secs, qhull has created %d facets and merged %d.\n\
453 The current hull contains %d facets and %d vertices. Last point was p%d\n",
454 tp->tm_hour, tp->tm_min, tp->tm_sec, cpu,
qh->facet_id -1,
455 total,
qh->num_facets,
qh->num_vertices,
qh->furthest_id);
459 if (
qh->TRACEpoint == furthestid) {
460 qh->IStracing=
qh->TRACElevel;
461 qh->qhmem.IStracing=
qh->TRACElevel;
464 qh->qhmem.IStracing= 0;
466 if (
qh->REPORTfreq && (
qh->facet_id-1 >
qh->lastreport+
qh->REPORTfreq)) {
467 qh->lastreport=
qh->facet_id-1;
469 tp= localtime(&timedata);
476 At %02d:%02d:%02d & %2.5g CPU secs, qhull has created %d facets and merged %d.\n\
477 The current hull contains %d facets and %d vertices. There are %d\n\
478 outside points. Next is point p%d(v%d), %2.2g above f%d.\n",
479 tp->tm_hour, tp->tm_min, tp->tm_sec, cpu,
qh->facet_id -1,
480 total,
qh->num_facets,
qh->num_vertices,
qh->num_outside+1,
481 furthestid,
qh->vertex_id, dist,
getid_(facet));
482 }
else if (
qh->IStracing >=1) {
486 qh_fprintf(
qh,
qh->ferr, 8120,
"qh_addpoint: add p%d(v%d) to hull of %d facets(%2.2g above f%d) and %d outside at %4.4g CPU secs. Previous was p%d.\n",
487 furthestid,
qh->vertex_id,
qh->num_facets, dist,
488 getid_(facet),
qh->num_outside+1, cpu,
qh->furthest_id);
491 if (
qh->visit_id > (
unsigned) INT_MAX) {
498 if (
qh->vertex_visit > (
unsigned) INT_MAX) {
504 qh->furthest_id= furthestid;
505 qh->RANDOMdist=
qh->old_randomdist;
557 facetT *neighbor, **neighborp, *visible;
558 int numhorizon= 0, coplanar= 0;
561 trace1((
qh,
qh->ferr, 1040,
"qh_findhorizon: find horizon for point p%d facet f%d\n",
qh_pointid(
qh, point),facet->
id));
562 *goodvisible= *goodhorizon= 0;
569 qh->visible_list= facet;
572 if (
qh->IStracing >=4)
577 qh_fprintf(
qh,
qh->ferr, 6230,
"Qhull internal error (qh_findhorizon): does not work for tricoplanar facets. Use option 'Q11'\n");
587 if (dist >
qh->MINvisible) {
596 if (
qh->IStracing >=4)
599 if (dist > -
qh->MAXcoplanar) {
614 trace2((
qh,
qh->ferr, 2057,
"qh_findhorizon: point p%d is coplanar to horizon f%d, dist=%2.7g < qh->MINvisible(%2.7g)\n",
622 if (
qh->IStracing >=4)
629 qh_fprintf(
qh,
qh->ferr, 6168,
"qhull precision error (qh_findhorizon): empty horizon\n\
630 QhullPoint p%d was above all facets.\n",
qh_pointid(
qh, point));
634 trace1((
qh,
qh->ferr, 1041,
"qh_findhorizon: %d horizon facets(good %d), %d visible(good %d), %d coplanar\n",
635 numhorizon, *goodhorizon,
qh->num_visible, *goodvisible, coplanar));
636 if (
qh->IStracing >= 4 &&
qh->num_facets < 50)
668 while ((facet=
qh->facet_next) !=
qh->facet_tail) {
670 qh->facet_next= facet->
next;
676 qh->facet_next= facet->
next;
679 if (
qh->NARROWhull) {
683 #if qh_COMPUTEfurthest
689 if (dist < qh->MINoutside) {
690 qh->facet_next= facet->
next;
694 if (!
qh->RANDOMoutside && !
qh->VIRTUALmemory) {
695 if (
qh->PICKfurthest) {
697 facet=
qh->facet_next;
702 if (
qh->RANDOMoutside) {
704 if (
qh->NARROWhull) {
706 if (facet ==
qh->facet_next)
714 idx= (int)floor((
qh->num_outside - outcoplanar) * randr);
720 else if (size > idx) {
727 qh_fprintf(
qh,
qh->ferr, 6169,
"qhull internal error (qh_nextfurthest): num_outside %d is too low\nby at least %d, or a random real %g >= 1.0\n",
728 qh->num_outside, idx+1, randr);
731 facet=
qh->facet_tail->previous;
780 pointT *point, **pointp, *bestpoint;
781 int size, point_i, point_n, point_end, remaining, i, id;
785 trace1((
qh,
qh->ferr, 1042,
"qh_partitionall: partition all points into outside sets\n"));
789 for (i=numpoints, point= points; i--; point +=
qh->hull_dim)
797 if (
id >=0 &&
qh->STOPcone-1 !=
id && -
qh->STOPpoint-1 !=
id)
799 if (
qh->GOODvertexp &&
qh->ONLYgood && !
qh->MERGING) {
803 if (!
qh->BESToutside) {
806 remaining=
qh->num_facets;
807 point_end= numpoints;
809 size= point_end/(remaining--) + 100;
817 if (dist < distoutside)
818 SETelem_(pointset, point_end++)= point;
824 }
else if (dist > bestdist) {
835 #if !qh_COMPUTEfurthest
844 if (
qh->BESToutside ||
qh->MERGING ||
qh->KEEPcoplanar ||
qh->KEEPinside) {
855 if (
qh->IStracing >= 4)
899 realT bestdist, dist2= 0, angle;
900 int numpart= 0, oldfindbest;
909 &bestdist, &isoutside, &numpart);
912 if (!
qh->DELAUNAY && !
qh->KEEPinside) {
913 if (
qh->KEEPnearinside) {
914 if (bestdist < -qh->NEARinside) {
916 trace4((
qh,
qh->ferr, 4062,
"qh_partitioncoplanar: point p%d is more than near-inside facet f%d dist %2.2g findbestnew %d\n",
920 }
else if (bestdist < -qh->MAXcoplanar) {
921 trace4((
qh,
qh->ferr, 4063,
"qh_partitioncoplanar: point p%d is inside facet f%d dist %2.2g findbestnew %d\n",
931 if (bestdist >
qh->max_outside) {
932 if (!dist && facet != bestfacet) {
939 trace2((
qh,
qh->ferr, 2058,
"qh_partitioncoplanar: repartition point p%d from f%d. It is above flipped facet f%d dist %2.2g\n",
941 oldfindbest=
qh->findbestnew;
944 qh->findbestnew= oldfindbest;
948 qh->max_outside= bestdist;
949 if (bestdist >
qh->TRACEdist) {
950 qh_fprintf(
qh,
qh->ferr, 8122,
"qh_partitioncoplanar: ====== p%d from f%d increases max_outside to %2.2g of f%d last p%d\n",
955 if (
qh->KEEPcoplanar +
qh->KEEPinside +
qh->KEEPnearinside) {
961 if (!oldfurthest || dist2 < bestdist)
966 trace4((
qh,
qh->ferr, 4064,
"qh_partitioncoplanar: point p%d is coplanar with facet f%d(or inside) dist %2.2g\n",
1010 #if qh_COMPUTEfurthest
1014 if (
qh->findbestnew)
1015 bestfacet=
qh_findbestnew(
qh, point, facet, &bestdist,
qh->BESToutside, &isoutside, &numpart);
1018 &bestdist, &isoutside, &numpart);
1021 if (
qh->NARROWhull) {
1022 if (
qh->DELAUNAY && !isoutside && bestdist >= -
qh->MAXcoplanar)
1024 if (
qh->KEEPnearinside) {
1025 if (bestdist >= -
qh->NEARinside)
1027 }
else if (bestdist >= -
qh->MAXcoplanar)
1039 #if !qh_COMPUTEfurthest
1043 #if qh_COMPUTEfurthest
1046 if (dist < bestdist)
1059 trace4((
qh,
qh->ferr, 4065,
"qh_partitionpoint: point p%d is outside facet f%d new? %d (or narrowhull)\n",
1061 }
else if (
qh->DELAUNAY || bestdist >= -
qh->MAXcoplanar) {
1065 if ((
qh->KEEPcoplanar +
qh->KEEPnearinside) || bestdist >
qh->max_outside)
1068 trace4((
qh,
qh->ferr, 4066,
"qh_partitionpoint: point p%d is coplanar to facet f%d (dropped)\n",
1071 }
else if (
qh->KEEPnearinside && bestdist > -
qh->NEARinside) {
1076 trace4((
qh,
qh->ferr, 4067,
"qh_partitionpoint: point p%d is inside all facets, closest to f%d dist %2.2g\n",
1118 facetT *visible, *newfacet;
1120 int coplanar=0, size;
1132 while (newfacet && newfacet->
visible) {
1134 if (count++ >
qh->facet_id)
1138 newfacet=
qh->newfacet_list;
1139 if (newfacet ==
qh->facet_tail) {
1140 qh_fprintf(
qh,
qh->ferr, 6170,
"qhull precision error (qh_partitionvisible): all new facets deleted as\n degenerate facets. Can not continue.\n");
1145 *numoutside += size;
1146 qh->num_outside -= size;
1150 if (visible->
coplanarset && (
qh->KEEPcoplanar +
qh->KEEPinside +
qh->KEEPnearinside)) {
1162 if (vertex->
point) {
1169 trace1((
qh,
qh->ferr, 1043,
"qh_partitionvisible: partitioned %d points from outsidesets and %d points from coplanarsets\n", *numoutside, coplanar));
1182 if (
qh->ALLOWrestart && !
qh->PREmerge && !
qh->MERGEexact) {
1184 trace0((
qh,
qh->ferr, 26,
"qh_precision: qhull restart because of %s\n", reason));
1206 realT ratio, outerplane, innerplane;
1208 int size, id, nummerged, numvertices, numcoplanars= 0, nonsimplicial=0;
1213 int numtricoplanars= 0;
1229 if (
id >=0 &&
qh->STOPcone-1 !=
id && -
qh->STOPpoint-1 !=
id)
1231 if (
qh->STOPcone ||
qh->STOPpoint)
1232 qh_fprintf(
qh, fp, 9288,
"\nAt a premature exit due to 'TVn', 'TCn', 'TRn', or precision error with 'QJn'.");
1233 if (
qh->UPPERdelaunay)
1234 goodused=
qh->GOODvertex +
qh->GOODpoint +
qh->SPLITthresholds;
1235 else if (
qh->DELAUNAY)
1236 goodused=
qh->GOODvertex +
qh->GOODpoint +
qh->GOODthreshold;
1238 goodused=
qh->num_good;
1241 if (
qh->UPPERdelaunay)
1243 Furthest-site Voronoi vertices by the convex hull of %d points in %d-d:\n\n", size,
qh->hull_dim);
1246 Voronoi diagram by the convex hull of %d points in %d-d:\n\n", size,
qh->hull_dim);
1247 qh_fprintf(
qh, fp, 9291,
" Number of Voronoi regions%s: %d\n",
1248 qh->ATinfinity ?
" and at-infinity" :
"", numvertices);
1250 qh_fprintf(
qh, fp, 9292,
" Total number of deleted points due to merging: %d\n", numdel);
1251 if (numcoplanars - numdel > 0)
1252 qh_fprintf(
qh, fp, 9293,
" Number of nearly incident points: %d\n", numcoplanars - numdel);
1253 else if (size - numvertices - numdel > 0)
1254 qh_fprintf(
qh, fp, 9294,
" Total number of nearly incident points: %d\n", size - numvertices - numdel);
1255 qh_fprintf(
qh, fp, 9295,
" Number of%s Voronoi vertices: %d\n",
1256 goodused ?
" 'good'" :
"",
qh->num_good);
1258 qh_fprintf(
qh, fp, 9296,
" Number of%s non-simplicial Voronoi vertices: %d\n",
1259 goodused ?
" 'good'" :
"", nonsimplicial);
1260 }
else if (
qh->DELAUNAY) {
1261 if (
qh->UPPERdelaunay)
1263 Furthest-site Delaunay triangulation by the convex hull of %d points in %d-d:\n\n", size,
qh->hull_dim);
1266 Delaunay triangulation by the convex hull of %d points in %d-d:\n\n", size,
qh->hull_dim);
1267 qh_fprintf(
qh, fp, 9299,
" Number of input sites%s: %d\n",
1268 qh->ATinfinity ?
" and at-infinity" :
"", numvertices);
1270 qh_fprintf(
qh, fp, 9300,
" Total number of deleted points due to merging: %d\n", numdel);
1271 if (numcoplanars - numdel > 0)
1272 qh_fprintf(
qh, fp, 9301,
" Number of nearly incident points: %d\n", numcoplanars - numdel);
1273 else if (size - numvertices - numdel > 0)
1274 qh_fprintf(
qh, fp, 9302,
" Total number of nearly incident points: %d\n", size - numvertices - numdel);
1275 qh_fprintf(
qh, fp, 9303,
" Number of%s Delaunay regions: %d\n",
1276 goodused ?
" 'good'" :
"",
qh->num_good);
1278 qh_fprintf(
qh, fp, 9304,
" Number of%s non-simplicial Delaunay regions: %d\n",
1279 goodused ?
" 'good'" :
"", nonsimplicial);
1280 }
else if (
qh->HALFspace) {
1282 Halfspace intersection by the convex hull of %d points in %d-d:\n\n", size,
qh->hull_dim);
1283 qh_fprintf(
qh, fp, 9306,
" Number of halfspaces: %d\n", size);
1284 qh_fprintf(
qh, fp, 9307,
" Number of non-redundant halfspaces: %d\n", numvertices);
1286 if (
qh->KEEPinside &&
qh->KEEPcoplanar)
1287 s=
"similar and redundant";
1288 else if (
qh->KEEPinside)
1292 qh_fprintf(
qh, fp, 9308,
" Number of %s halfspaces: %d\n", s, numcoplanars);
1294 qh_fprintf(
qh, fp, 9309,
" Number of intersection points: %d\n",
qh->num_facets -
qh->num_visible);
1296 qh_fprintf(
qh, fp, 9310,
" Number of 'good' intersection points: %d\n",
qh->num_good);
1298 qh_fprintf(
qh, fp, 9311,
" Number of%s non-simplicial intersection points: %d\n",
1299 goodused ?
" 'good'" :
"", nonsimplicial);
1302 Convex hull of %d points in %d-d:\n\n", size,
qh->hull_dim);
1303 qh_fprintf(
qh, fp, 9313,
" Number of vertices: %d\n", numvertices);
1305 if (
qh->KEEPinside &&
qh->KEEPcoplanar)
1306 s=
"coplanar and interior";
1307 else if (
qh->KEEPinside)
1311 qh_fprintf(
qh, fp, 9314,
" Number of %s points: %d\n", s, numcoplanars);
1313 qh_fprintf(
qh, fp, 9315,
" Number of facets: %d\n",
qh->num_facets -
qh->num_visible);
1315 qh_fprintf(
qh, fp, 9316,
" Number of 'good' facets: %d\n",
qh->num_good);
1317 qh_fprintf(
qh, fp, 9317,
" Number of%s non-simplicial facets: %d\n",
1318 goodused ?
" 'good'" :
"", nonsimplicial);
1320 if (numtricoplanars)
1321 qh_fprintf(
qh, fp, 9318,
" Number of triangulated facets: %d\n", numtricoplanars);
1323 qh->rbox_command,
qh->qhull_command);
1324 if (
qh->ROTATErandom != INT_MIN)
1331 qh_fprintf(
qh, fp, 9324,
" Number of facets in hull: %d\n",
qh->num_facets -
qh->num_visible);
1336 qh_fprintf(
qh, fp, 9326,
" average new facet balance: %2.2g\n",
1340 qh_fprintf(
qh, fp, 9327,
" new facet standard deviation: %2.2g\n", stddev);
1341 qh_fprintf(
qh, fp, 9328,
" average partition balance: %2.2g\n",
1345 qh_fprintf(
qh, fp, 9329,
" partition standard deviation: %2.2g\n", stddev);
1353 qh_fprintf(
qh, fp, 9332,
" Number of merged facets: %d\n", nummerged);
1355 if (!
qh->RANDOMoutside &&
qh->QHULLfinished) {
1356 cpu= (float)
qh->hulltime;
1359 qh_fprintf(
qh, fp, 9333,
" CPU seconds to compute hull (after input): %2.4g\n", cpu);
1362 if (!
qh->PREmerge && !
qh->MERGEexact)
1363 qh_fprintf(
qh, fp, 9334,
" Percentage of runs with precision errors: %4.1f\n",
1367 qh_fprintf(
qh, fp, 9335,
" After %d retries, input joggled by: %2.2g\n",
1370 qh_fprintf(
qh, fp, 9336,
" Input joggled by: %2.2g\n",
qh->JOGGLEmax);
1372 if (
qh->totarea != 0.0)
1375 if (
qh->totvol != 0.0)
1380 if (outerplane > 2 *
qh->DISTround) {
1381 qh_fprintf(
qh, fp, 9339,
" Maximum distance of %spoint above facet: %2.2g",
1382 (
qh->QHULLfinished ?
"" :
"merged "), outerplane);
1383 ratio= outerplane/(
qh->ONEmerge +
qh->DISTround);
1385 if (ratio > 0.05 && 2*
qh->ONEmerge >
qh->MINoutside &&
qh->JOGGLEmax >
REALmax/2)
1390 if (innerplane < -2 * qh->DISTround) {
1391 qh_fprintf(
qh, fp, 9342,
" Maximum distance of %svertex below facet: %2.2g",
1392 (
qh->QHULLfinished ?
"" :
"merged "), innerplane);
1393 ratio= -innerplane/(
qh->ONEmerge+
qh->DISTround);
1394 if (ratio > 0.05 &&
qh->JOGGLEmax >
REALmax/2)