00157                                                                      {
00158   int goodvisible, goodhorizon;
00159   vertexT *vertex;
00160   facetT *newfacet;
00161   realT dist, newbalance, pbalance;
00162   boolT isoutside= False;
00163   int numpart, numpoints, numnew, firstnew;
00164 
00165   qh maxoutdone= False;
00166   if (qh_pointid (furthest) == -1)
00167     qh_setappend (&qh other_points, furthest);
00168   if (!facet) {
00169     fprintf (qh ferr, "qh_addpoint: NULL facet.  Use qh_findbestfacet\n");
00170     qh_errexit (qh_ERRqhull, NULL, NULL);
00171   }
00172   if (checkdist) {
00173     facet= qh_findbest (furthest, facet, !qh_ALL, False, !qh_NOupper,
00174                         &dist, &isoutside, &numpart);
00175     zzadd_(Zpartition, numpart);
00176     if (!isoutside) {
00177       zinc_(Znotmax);  /* last point of outsideset is no longer furthest. */
00178       facet->notfurthest= True;
00179       qh_partitioncoplanar (furthest, facet, &dist);
00180       return True;
00181     }
00182   }
00183   qh_buildtracing (furthest, facet);
00184   if (qh STOPpoint < 0 && qh furthest_id == -qh STOPpoint-1) {
00185     facet->notfurthest= True;
00186     return False;
00187   }
00188   qh_findhorizon (furthest, facet, &goodvisible, &goodhorizon); 
00189   if (qh ONLYgood && !(goodvisible+goodhorizon) && !qh GOODclosest) {
00190     zinc_(Znotgood);  
00191     facet->notfurthest= True;
00192     /* last point of outsideset is no longer furthest.  This is ok
00193        since all points of the outside are likely to be bad */
00194     qh_resetlists (False /*qh visible_list newvertex_list newfacet_list */);
00195     return True;
00196   }
00197   zzinc_(Zprocessed);
00198   firstnew= qh facet_id;
00199   vertex= qh_makenewfacets (furthest /*visible_list, attaches if !ONLYgood */);
00200   qh_makenewplanes (/* newfacet_list */);
00201   numnew= qh facet_id - firstnew;
00202   newbalance= numnew - (realT) (qh num_facets-qh num_visible)
00203                          * qh hull_dim/qh num_vertices;
00204   wadd_(Wnewbalance, newbalance);
00205   wadd_(Wnewbalance2, newbalance * newbalance);
00206   if (qh ONLYgood 
00207   && !qh_findgood (qh newfacet_list, goodhorizon) && !qh GOODclosest) {
00208     FORALLnew_facets 
00209       qh_delfacet (newfacet);
00210     qh_delvertex (vertex);
00211     qh_resetlists (True /*qh visible_list newvertex_list newfacet_list */);
00212     zinc_(Znotgoodnew);
00213     facet->notfurthest= True;
00214     return True;
00215   }
00216   if (qh ONLYgood)
00217     qh_attachnewfacets(/*visible_list*/);
00218   qh_matchnewfacets();
00219   qh_updatevertices();
00220   if (qh STOPcone && qh furthest_id == qh STOPcone-1) {
00221     facet->notfurthest= True;
00222     return False;  /* visible_list etc. still defined */
00223   }
00224   if (qh PREmerge || qh MERGEexact) {
00225     qh_premerge (vertex, qh premerge_centrum, qh premerge_cos);
00226     if (zzval_(Ztotmerge) > qh_USEfindbestnew)
00227       qh findbestnew= True;
00228     else {
00229       FORALLnew_facets {
00230         if (!newfacet->simplicial) {
00231           qh findbestnew= True;  /* use qh_findbestnew instead of qh_findbest*/
00232           break;
00233         }
00234       }
00235     }
00236   }else if (qh BESToutside)
00237     qh findbestnew= True;
00238   qh_partitionvisible (/*visible_list, newfacet_list*/ !qh_ALL, &numpoints);
00239   qh findbestnew= False;
00240   qh findbest_notsharp= False;
00241   zinc_(Zpbalance);
00242   pbalance= numpoints - (realT) qh hull_dim /* assumes all points extreme */
00243                 * (qh num_points - qh num_vertices)/qh num_vertices;
00244   wadd_(Wpbalance, pbalance);
00245   wadd_(Wpbalance2, pbalance * pbalance);
00246   qh_deletevisible (/*qh visible_list*/);
00247   zmax_(Zmaxvertex, qh num_vertices);
00248   qh NEWfacets= False;
00249   if (qh IStracing >= 4)
00250     qh_printfacetlist (qh newfacet_list, NULL, True);
00251   if (qh CHECKfrequently) {
00252     if (qh num_facets < 50)
00253       qh_checkpolygon (qh facet_list);
00254     else
00255       qh_checkpolygon (qh newfacet_list);
00256   }
00257   if (qh STOPpoint > 0 && qh furthest_id == qh STOPpoint-1) 
00258     return False; 
00259   qh_resetlists (True /*qh visible_list newvertex_list newfacet_list */);
00260   trace2((qh ferr, "qh_addpoint: added p%d new facets %d new balance %2.2g point balance %2.2g\n",
00261     qh_pointid (furthest), numnew, newbalance, pbalance));
00262   if (qh hull_dim > 3 && qh TRACEpoint == qh_pointid (furthest)) {
00263     qh IStracing= 0;
00264     qhmem.IStracing= 0;
00265   }
00266   return True;
00267 } /* addpoint */

00034                         {
00035   
00036    /* zdef_(type,name,doc,average) */
00037   zzdef_(zdoc, Zdoc2, "precision statistics", -1);
00038   zdef_(zinc, Znewvertex, NULL, -1);
00039   zdef_(wadd, Wnewvertex, "ave. distance of a new vertex to a facet (not 0s)", Znewvertex);
00040   zzdef_(wmax, Wnewvertexmax, "max. distance of a new vertex to a facet", -1);
00041   zdef_(wmax, Wvertexmax, "max. distance of an output vertex to a facet", -1);
00042   zdef_(wmin, Wvertexmin, "min. distance of an output vertex to a facet", -1);
00043   zdef_(wmin, Wmindenom, "min. denominator in hyperplane computation", -1);
00044 
00045   qhstat precision= qhstat next;  /* call qh_precision for each of these */
00046   zzdef_(zdoc, Zdoc3, "precision problems", -1);
00047   zzdef_(zinc, Zcoplanarridges, "coplanar half ridges in output", -1);
00048   zzdef_(zinc, Zconcaveridges, "concave half ridges in output", -1);
00049   zzdef_(zinc, Zflippedfacets, "flipped facets", -1);
00050   zzdef_(zinc, Zcoplanarhorizon, "coplanar horizon facets for new vertices", -1);
00051   zzdef_(zinc, Zcoplanarpart, "coplanar points during partitioning", -1);
00052   zzdef_(zinc, Zminnorm, "degenerate hyperplanes recomputed with gaussian elimination", -1);
00053   zzdef_(zinc, Znearlysingular, "nearly singular or axis-parallel hyperplanes", -1);
00054   zzdef_(zinc, Zback0, "zero divisors during back substitute", -1);
00055   zzdef_(zinc, Zgauss0, "zero divisors during gaussian elimination", -1);
00056   zzdef_(zinc, Zmultiridge, "ridges with multiple neighbors", -1);
00057 }

00058                         {
00059   zzdef_(zdoc, Zdoc1, "summary information", -1);
00060   zdef_(zinc, Zvertices, "number of vertices in output", -1);
00061   zdef_(zinc, Znumfacets, "number of facets in output", -1);
00062   zdef_(zinc, Znonsimplicial, "number of non-simplicial facets in output", -1);
00063   zdef_(zinc, Znowsimplicial, "number of simplicial facets that were merged", -1);
00064   zdef_(zinc, Znumridges, "number of ridges in output", -1);
00065   zdef_(zadd, Znumridges, "average number of ridges per facet", Znumfacets);
00066   zdef_(zmax, Zmaxridges, "maximum number of ridges", -1);
00067   zdef_(zadd, Znumneighbors, "average number of neighbors per facet", Znumfacets);
00068   zdef_(zmax, Zmaxneighbors, "maximum number of neighbors", -1);
00069   zdef_(zadd, Znumvertices, "average number of vertices per facet", Znumfacets);
00070   zdef_(zmax, Zmaxvertices, "maximum number of vertices", -1);
00071   zdef_(zadd, Znumvneighbors, "average number of neighbors per vertex", Zvertices);
00072   zdef_(zmax, Zmaxvneighbors, "maximum number of neighbors", -1);
00073   zdef_(wadd, Wcpu, "cpu seconds for qhull after input", -1);
00074   zdef_(zinc, Ztotvertices, "vertices created altogether", -1);
00075   zzdef_(zinc, Zsetplane, "facets created altogether", -1);
00076   zdef_(zinc, Ztotridges, "ridges created altogether", -1);
00077   zdef_(zinc, Zpostfacets, "facets before post merge", -1);
00078   zdef_(zadd, Znummergetot, "average merges per facet (at most 511)", Znumfacets);
00079   zdef_(zmax, Znummergemax, "  maximum merges for a facet (at most 511)", -1);
00080   zdef_(zinc, Zangle, NULL, -1);
00081   zdef_(wadd, Wangle, "average angle (cosine) of facet normals for all ridges", Zangle);
00082   zdef_(wmax, Wanglemax, "  maximum angle (cosine) of facet normals across a ridge", -1);
00083   zdef_(wmin, Wanglemin, "  minimum angle (cosine) of facet normals across a ridge", -1);
00084   zdef_(wadd, Wareatot, "total area of facets", -1);
00085   zdef_(wmax, Wareamax, "  maximum facet area", -1);
00086   zdef_(wmin, Wareamin, "  minimum facet area", -1);
00087 }  

00088                         {
00089   zdef_(zdoc, Zdoc9, "build hull statistics", -1);
00090   zzdef_(zinc, Zprocessed, "points processed", -1);
00091   zzdef_(zinc, Zretry, "retries due to precision problems", -1);
00092   zdef_(wmax, Wretrymax, "  max. random joggle", -1);
00093   zdef_(zmax, Zmaxvertex, "max. vertices at any one time", -1);
00094   zdef_(zinc, Ztotvisible, "ave. visible facets per iteration", Zprocessed);
00095   zdef_(zinc, Zinsidevisible, "  ave. visible facets without an horizon neighbor", Zprocessed);
00096   zdef_(zadd, Zvisfacettot,  "  ave. facets deleted per iteration", Zprocessed);
00097   zdef_(zmax, Zvisfacetmax,  "    maximum", -1);
00098   zdef_(zadd, Zvisvertextot, "ave. visible vertices per iteration", Zprocessed);
00099   zdef_(zmax, Zvisvertexmax, "    maximum", -1);
00100   zdef_(zadd, Zdelvertextot, "  ave. vertices deleted per iteration", Zprocessed);
00101   zdef_(zmax, Zdelvertexmax, "    maximum vertices deleted", -1);
00102   zdef_(zinc, Ztothorizon, "ave. horizon facets per iteration", Zprocessed);
00103   zdef_(zadd, Znewfacettot,  "ave. new or merged facets per iteration", Zprocessed);
00104   zdef_(zmax, Znewfacetmax,  "    maximum (includes initial simplex)", -1);
00105   zdef_(wadd, Wnewbalance, "average new facet balance", Zprocessed);
00106   zdef_(wadd, Wnewbalance2, "  standard deviation", -1);
00107   zdef_(wadd, Wpbalance, "average partition balance", Zpbalance);
00108   zdef_(wadd, Wpbalance2, "  standard deviation", -1);
00109   zdef_(zinc, Zpbalance, "  number of trials", -1);
00110   zdef_(zinc, Zsearchpoints, "searches of all points for initial simplex", -1);
00111   zdef_(zinc, Zdetsimplex, "determinants computed (area & initial hull)", -1);
00112   zdef_(zinc, Znoarea, "determinants not computed because vertex too low", -1);
00113   zdef_(zinc, Znotmax, "points ignored (not above max_outside)", -1);
00114   zdef_(zinc, Znotgood, "points ignored (not above a good facet)", -1);
00115   zdef_(zinc, Znotgoodnew, "points ignored (didn't create a good new facet)", -1);
00116   zdef_(zinc, Zgoodfacet, "good facets found", -1);
00117   zzdef_(zinc, Znumvisibility, "distance tests for facet visibility", -1);
00118   zdef_(zinc, Zdistvertex, "distance tests to report minimum vertex", -1);
00119   zdef_(zinc, Ztotcheck, "points checked for facets' outer planes", -1);
00120   zdef_(zinc, Zcheckpart, "  ave. distance tests per check", Ztotcheck);
00121 }

00122                        {
00123   zdef_(zdoc, Zdoc4, "partitioning statistics", -1);
00124   zdef_(zinc, Zpartinside, "inside points", -1);
00125   zdef_(zinc, Zpartnear, "  inside points kept with a facet", -1);
00126   zdef_(zinc, Zcoplanarinside, "  inside points that were coplanar with a facet", -1);
00127   zdef_(wadd, Wmaxout, "difference in max_outside at final check", -1);
00128   
00129   zzdef_(zinc, Zpartitionall, "distance tests for initial partition", -1);
00130   zdef_(zinc, Ztotpartition, "partitions of a point", -1);
00131   zzdef_(zinc, Zpartition, "distance tests for partitioning", -1);
00132   zzdef_(zinc, Zdistcheck, "distance tests for checking flipped facets", -1); 
00133   zzdef_(zinc, Zdistconvex, "distance tests for checking convexity", -1); 
00134   zdef_(zinc, Zdistgood, "distance tests for checking good point", -1); 
00135   zdef_(zinc, Zdistio, "distance tests for output", -1); 
00136   zdef_(zinc, Zdiststat, "distance tests for statistics", -1); 
00137   zdef_(zinc, Zdistplane, "total number of distance tests", -1);
00138   zdef_(zinc, Ztotpartcoplanar, "partitions of coplanar points or deleted vertices", -1);
00139   zzdef_(zinc, Zpartcoplanar, "   distance tests for these partitions", -1);
00140   zdef_(zinc, Zcomputefurthest, "distance tests for computing furthest", -1);
00141 }

00142                        {
00143   zdef_(zdoc, Zdoc5, "statistics for matching ridges", -1);
00144   zdef_(zinc, Zhashlookup, "total lookups for matching ridges of new facets", -1);
00145   zdef_(zinc, Zhashtests, "average number of tests to match a ridge", Zhashlookup);
00146   zdef_(zinc, Zhashridge, "total lookups of subridges (duplicates and boundary)", -1);
00147   zdef_(zinc, Zhashridgetest, "average number of tests per subridge", Zhashridge);
00148   zdef_(zinc, Zdupsame, "duplicated ridges in same merge cycle", -1);
00149   zdef_(zinc, Zdupflip, "duplicated ridges with flipped facets", -1);
00150 
00151   zdef_(zdoc, Zdoc6, "statistics for determining merges", -1);
00152   zdef_(zinc, Zangletests, "angles computed for ridge convexity", -1);
00153   zdef_(zinc, Zbestcentrum, "best merges used centrum instead of vertices",-1);
00154   zzdef_(zinc, Zbestdist, "distance tests for best merge", -1);
00155   zzdef_(zinc, Zcentrumtests, "distance tests for centrum convexity", -1);
00156   zzdef_(zinc, Zdistzero, "distance tests for checking simplicial convexity", -1);
00157   zdef_(zinc, Zcoplanarangle, "coplanar angles in getmergeset", -1);
00158   zdef_(zinc, Zcoplanarcentrum, "coplanar centrums in getmergeset", -1);
00159   zdef_(zinc, Zconcaveridge, "concave ridges in getmergeset", -1);
00160 }

00161                        {
00162   zdef_(zdoc, Zdoc7, "statistics for merging", -1);
00163   zdef_(zinc, Zpremergetot, "merge iterations", -1);
00164   zdef_(zadd, Zmergeinittot, "ave. initial non-convex ridges per iteration", Zpremergetot);
00165   zdef_(zadd, Zmergeinitmax, "  maximum", -1);
00166   zdef_(zadd, Zmergesettot, "  ave. additional non-convex ridges per iteration", Zpremergetot);
00167   zdef_(zadd, Zmergesetmax, "  maximum additional in one pass", -1);
00168   zdef_(zadd, Zmergeinittot2, "initial non-convex ridges for post merging", -1);
00169   zdef_(zadd, Zmergesettot2, "  additional non-convex ridges", -1);
00170   zdef_(wmax, Wmaxoutside, "max distance of vertex or coplanar point above facet (w/roundoff)", -1);
00171   zdef_(wmin, Wminvertex, "max distance of merged vertex below facet (or roundoff)", -1);
00172   zdef_(zinc, Zwidefacet, "centrums frozen due to a wide merge", -1);
00173   zdef_(zinc, Zwidevertices, "centrums frozen due to extra vertices", -1);
00174   zzdef_(zinc, Ztotmerge, "total number of facets or cycles of facets merged", -1);
00175   zdef_(zinc, Zmergesimplex, "merged a simplex", -1);
00176   zdef_(zinc, Zonehorizon, "simplices merged into coplanar horizon", -1);
00177   zzdef_(zinc, Zcyclehorizon, "cycles of facets merged into coplanar horizon", -1);
00178   zzdef_(zadd, Zcyclefacettot, "  ave. facets per cycle", Zcyclehorizon);
00179   zdef_(zmax, Zcyclefacetmax, "  max. facets", -1);
00180   zdef_(zinc, Zmergeintohorizon, "new facets merged into horizon", -1);
00181   zdef_(zinc, Zmergenew, "new facets merged", -1);
00182   zdef_(zinc, Zmergehorizon, "horizon facets merged into new facets", -1);
00183   zdef_(zinc, Zmergevertex, "vertices deleted by merging", -1);
00184   zdef_(zinc, Zcyclevertex, "vertices deleted by merging into coplanar horizon", -1);
00185   zdef_(zinc, Zdegenvertex, "vertices deleted by degenerate facet", -1);
00186   zdef_(zinc, Zmergeflipdup, "merges due to flipped facets in duplicated ridge", -1);
00187   zdef_(zinc, Zneighbor, "merges due to redundant neighbors", -1);
00188   zdef_(zadd, Ztestvneighbor, "non-convex vertex neighbors", -1); 
00189 }

00034                                       {
00035   int i;
00036 
00037   for (i=0; i < qh_PRINTEND; i++) {
00038     if (qh PRINTout[i] == format)
00039       break;
00040     if (!qh PRINTout[i]) {
00041       qh PRINTout[i]= format;
00042       break;
00043     }
00044   }
00045 } /* appendprint */

00277                                  {
00278   int restart;
00279 
00280   qh ALLOWrestart= True;
00281   while (True) {
00282     restart= setjmp (qh restartexit); /* simple statement for CRAY J916 */
00283     if (restart) {       /* only from qh_precision() */
00284       zzinc_(Zretry);
00285       wmax_(Wretrymax, qh JOGGLEmax);
00286       qh ERREXITcalled= False;
00287       qh STOPcone= True; /* if break, prevents normal output */
00288     }
00289     if (!qh RERUN && qh JOGGLEmax < REALmax/2) {
00290       if (qh build_cnt > qh_JOGGLEmaxretry) {
00291         fprintf(qh ferr, "\n\
00292 qhull precision error: %d attempts to construct a convex hull\n\
00293         with joggled input.  Increase joggle above 'QJ%2.2g'\n\
00294         or modify qh_JOGGLE... parameters in user.h\n",
00295            qh build_cnt, qh JOGGLEmax);
00296         qh_errexit (qh_ERRqhull, NULL, NULL);
00297       }
00298       if (qh build_cnt && !restart)
00299         break;
00300     }else if (qh build_cnt && qh build_cnt >= qh RERUN)
00301       break;
00302     qh STOPcone= False;
00303     qh_freebuild (True);  /* first call is a nop */
00304     qh build_cnt++;
00305     if (!qh qhull_optionsiz)
00306       qh qhull_optionsiz= strlen (qh qhull_options);
00307     else { 
00308       qh qhull_options [qh qhull_optionsiz]= '\0';
00309       qh qhull_optionlen= 80;
00310     }
00311     qh_option("_run", &qh build_cnt, NULL);
00312     if (qh build_cnt == qh RERUN) {
00313       qh IStracing= qh TRACElastrun;  /* duplicated from qh_initqhull_globals */
00314       if (qh TRACEpoint != -1 || qh TRACEdist < REALmax/2 || qh TRACEmerge) {
00315         qh TRACElevel= (qh IStracing? qh IStracing : 3);
00316         qh IStracing= 0;
00317       }
00318       qhmem.IStracing= qh IStracing;
00319     }
00320     if (qh JOGGLEmax < REALmax/2)
00321       qh_joggleinput();
00322     qh_initbuild();
00323     qh_buildhull();
00324     if (qh JOGGLEmax < REALmax/2 && !qh MERGING)
00325       qh_checkconvex (qh facet_list, qh_ALGORITHMfault);
00326   }
00327   qh ALLOWrestart= False;
00328 } /* qh_build_withrestart */

00352                         {
00353   facetT *facet;
00354   pointT *furthest;
00355   vertexT *vertex;
00356   int id;
00357   
00358   trace1((qh ferr, "qh_buildhull: start build hull\n"));
00359   FORALLfacets {
00360     if (facet->visible || facet->newfacet) {
00361       fprintf (qh ferr, "qhull internal error (qh_buildhull): visible or new facet f%d in facet list\n",
00362                    facet->id);    
00363       qh_errexit (qh_ERRqhull, facet, NULL);
00364     }
00365   }
00366   FORALLvertices {
00367     if (vertex->newlist) {
00368       fprintf (qh ferr, "qhull internal error (qh_buildhull): new vertex f%d in vertex list\n",
00369                    vertex->id);
00370       qh_errprint ("ERRONEOUS", NULL, NULL, NULL, vertex);
00371       qh_errexit (qh_ERRqhull, NULL, NULL);
00372     }
00373     id= qh_pointid (vertex->point);
00374     if ((qh STOPpoint>0 && id == qh STOPpoint-1) ||
00375         (qh STOPpoint<0 && id == -qh STOPpoint-1) ||
00376         (qh STOPcone>0 && id == qh STOPcone-1)) {
00377       trace1((qh ferr,"qh_buildhull: stop point or cone P%d in initial hull\n", id));
00378       return;
00379     }
00380   }
00381   qh facet_next= qh facet_list;      /* advance facet when processed */
00382   while ((furthest= qh_nextfurthest (&facet))) {
00383     qh num_outside--;  /* if ONLYmax, furthest may not be outside */
00384     if (!qh_addpoint (furthest, facet, qh ONLYmax))
00385       break;
00386   }
00387   if (qh NARROWhull) /* move points from outsideset to coplanarset */
00388     qh_outcoplanar( /* facet_list */ );
00389   if (qh num_outside && !furthest) {
00390     fprintf (qh ferr, "qhull internal error (qh_buildhull): %d outside points were never processed.\n", qh num_outside);
00391     qh_errexit (qh_ERRqhull, NULL, NULL);
00392   }
00393   trace1((qh ferr, "qh_buildhull: completed the hull construction\n"));
00394 } /* buildhull */

00423                                                        {
00424   realT dist= 0;
00425   float cpu;
00426   int total, furthestid;
00427   time_t timedata;
00428   struct tm *tp;
00429   vertexT *vertex;
00430 
00431   qh old_randomdist= qh RANDOMdist;
00432   qh RANDOMdist= False;
00433   if (!furthest) {
00434     time (&timedata);
00435     tp= localtime (&timedata);
00436     cpu= qh_CPUclock - qh hulltime;
00437     cpu /= qh_SECticks;
00438     total= zzval_(Ztotmerge) - zzval_(Zcyclehorizon) + zzval_(Zcyclefacettot);
00439     fprintf (qh ferr, "\n\
00440 At %02d:%02d:%02d & %2.5g CPU secs, qhull has created %d facets and merged %d.\n\
00441  The current hull contains %d facets and %d vertices.  Last point was p%d\n",
00442       tp->tm_hour, tp->tm_min, tp->tm_sec, cpu, qh facet_id -1,
00443       total, qh num_facets, qh num_vertices, qh furthest_id);
00444     return;
00445   }
00446   furthestid= qh_pointid (furthest);
00447   if (qh TRACEpoint == furthestid) {
00448     qh IStracing= qh TRACElevel;
00449     qhmem.IStracing= qh TRACElevel;
00450   }
00451   if (qh REPORTfreq && (qh facet_id-1 > qh lastreport+qh REPORTfreq)) {
00452     qh lastreport= qh facet_id-1;
00453     time (&timedata);
00454     tp= localtime (&timedata);
00455     cpu= qh_CPUclock - qh hulltime;
00456     cpu /= qh_SECticks;
00457     total= zzval_(Ztotmerge) - zzval_(Zcyclehorizon) + zzval_(Zcyclefacettot);
00458     zinc_(Zdistio);
00459     qh_distplane (furthest, facet, &dist);
00460     fprintf (qh ferr, "\n\
00461 At %02d:%02d:%02d & %2.5g CPU secs, qhull has created %d facets and merged %d.\n\
00462  The current hull contains %d facets and %d vertices.  There are %d\n\
00463  outside points.  Next is point p%d (v%d), %2.2g above f%d.\n",
00464       tp->tm_hour, tp->tm_min, tp->tm_sec, cpu, qh facet_id -1,
00465       total, qh num_facets, qh num_vertices, qh num_outside+1,
00466       furthestid, qh vertex_id, dist, getid_(facet));
00467   }else if (qh IStracing >=1) {
00468     cpu= qh_CPUclock - qh hulltime;
00469     cpu /= qh_SECticks;
00470     qh_distplane (furthest, facet, &dist);
00471     fprintf (qh ferr, "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",
00472       furthestid, qh vertex_id, qh num_facets, dist,
00473       getid_(facet), qh num_outside+1, cpu, qh furthest_id);
00474   }
00475   if (qh visit_id > (unsigned) INT_MAX) {
00476     qh visit_id= 0;
00477     FORALLfacets
00478       facet->visitid= qh visit_id;
00479   }
00480   if (qh vertex_visit > (unsigned) INT_MAX) {
00481     qh vertex_visit= 0;
00482     FORALLvertices
00483       vertex->visitid= qh vertex_visit;
00484   }
00485   qh furthest_id= furthestid;
00486   qh RANDOMdist= qh old_randomdist;
00487 } /* buildtracing */

00502                                                                   {
00503   
00504   qh_errprint("ERRONEOUS", facet, otherfacet, NULL, NULL);
00505   qh_errexit (exitcode, NULL, NULL);
00506 } /* errexit2 */

00536                                                                                       {
00537   facetT *neighbor, **neighborp, *visible;
00538   int numhorizon= 0, coplanar= 0;
00539   realT dist;
00540   
00541   trace1((qh ferr,"qh_findhorizon: find horizon for point p%d facet f%d\n",qh_pointid(point),facet->id));
00542   *goodvisible= *goodhorizon= 0;
00543   zinc_(Ztotvisible);
00544   qh_removefacet(facet);  /* visible_list at end of qh facet_list */
00545   qh_appendfacet(facet);
00546   qh num_visible= 1;
00547   if (facet->good)
00548     (*goodvisible)++;
00549   qh visible_list= facet;
00550   facet->visible= True;
00551   facet->f.replace= NULL;
00552   if (qh IStracing >=4)
00553     qh_errprint ("visible", facet, NULL, NULL, NULL);
00554   qh visit_id++;
00555   FORALLvisible_facets {
00556     visible->visitid= qh visit_id;
00557     FOREACHneighbor_(visible) {
00558       if (neighbor->visitid == qh visit_id) 
00559         continue;
00560       neighbor->visitid= qh visit_id;
00561       zzinc_(Znumvisibility);
00562       qh_distplane(point, neighbor, &dist);
00563       if (dist > qh MINvisible) {
00564         zinc_(Ztotvisible);
00565         qh_removefacet(neighbor);  /* append to end of qh visible_list */
00566         qh_appendfacet(neighbor);
00567         neighbor->visible= True;
00568         neighbor->f.replace= NULL;
00569         qh num_visible++;
00570         if (neighbor->good)
00571           (*goodvisible)++;
00572         if (qh IStracing >=4)
00573           qh_errprint ("visible", neighbor, NULL, NULL, NULL);
00574       }else {
00575         if (dist > - qh MAXcoplanar) {
00576           neighbor->coplanar= True;
00577           zzinc_(Zcoplanarhorizon);
00578           qh_precision ("coplanar horizon");
00579           coplanar++;
00580           if (qh MERGING) {
00581             if (dist > 0) {
00582               maximize_(qh max_outside, dist);
00583               maximize_(qh max_vertex, dist);
00584 #if qh_MAXoutside
00585               maximize_(neighbor->maxoutside, dist);
00586 #endif
00587             }else
00588               minimize_(qh min_vertex, dist);  /* due to merge later */
00589           }
00590           trace2((qh ferr, "qh_findhorizon: point p%d is coplanar to horizon f%d, dist=%2.7g < qh MINvisible (%2.7g)\n",
00591               qh_pointid(point), neighbor->id, dist, qh MINvisible));
00592         }else
00593           neighbor->coplanar= False;
00594         zinc_(Ztothorizon);
00595         numhorizon++;
00596         if (neighbor->good)
00597           (*goodhorizon)++;
00598         if (qh IStracing >=4)
00599           qh_errprint ("horizon", neighbor, NULL, NULL, NULL);
00600       }
00601     }
00602   }
00603   if (!numhorizon) {
00604     qh_precision ("empty horizon");
00605     fprintf(qh ferr, "qhull precision error (qh_findhorizon): empty horizon\n\
00606 Point p%d was above all facets.\n", qh_pointid(point));
00607     qh_printfacetlist (qh facet_list, NULL, True);
00608     qh_errexit(qh_ERRprec, NULL, NULL);
00609   }
00610   trace1((qh ferr, "qh_findhorizon: %d horizon facets (good %d), %d visible (good %d), %d coplanar\n", 
00611        numhorizon, *goodhorizon, qh num_visible, *goodvisible, coplanar));
00612   if (qh IStracing >= 4 && qh num_facets < 50) 
00613     qh_printlists ();
00614 } /* findhorizon */

00185                            {
00186 
00187   trace5((qh ferr, "qh_freebuffers: freeing up global memory buffers\n"));
00188   /* allocated by qh_initqhull_buffers */
00189   qh_memfree (qh NEARzero, qh hull_dim * sizeof(realT));
00190   qh_memfree (qh lower_threshold, (qh input_dim+1) * sizeof(realT));
00191   qh_memfree (qh upper_threshold, (qh input_dim+1) * sizeof(realT));
00192   qh_memfree (qh lower_bound, (qh input_dim+1) * sizeof(realT));
00193   qh_memfree (qh upper_bound, (qh input_dim+1) * sizeof(realT));
00194   qh_memfree (qh gm_matrix, (qh hull_dim+1) * qh hull_dim * sizeof(coordT));
00195   qh_memfree (qh gm_row, (qh hull_dim+1) * sizeof(coordT *));
00196   qh NEARzero= qh lower_threshold= qh upper_threshold= NULL;
00197   qh lower_bound= qh upper_bound= NULL;
00198   qh gm_matrix= NULL;
00199   qh gm_row= NULL;
00200   qh_setfree (&qh other_points);
00201   qh_setfree (&qh del_vertices);
00202   qh_setfree (&qh searchset);
00203   if (qh line)                /* allocated by qh_readinput, freed if no error */
00204     free (qh line);
00205   if (qh half_space)
00206     free (qh half_space);
00207   if (qh temp_malloc)
00208     free (qh temp_malloc);
00209   if (qh feasible_point)      /* allocated by qh_readfeasible */
00210     free (qh feasible_point);
00211   if (qh feasible_string)     /* allocated by qh_initflags */
00212     free (qh feasible_string);
00213   qh line= qh feasible_string= NULL;
00214   qh half_space= qh feasible_point= qh temp_malloc= NULL;
00215   /* usually allocated by qh_readinput */
00216   if (qh first_point && qh POINTSmalloc) {
00217     free(qh first_point);
00218     qh first_point= NULL;
00219   }
00220   if (qh input_points && qh input_malloc) { /* set by qh_joggleinput */
00221     free (qh input_points);
00222     qh input_points= NULL;
00223   }
00224   trace5((qh ferr, "qh_freebuffers: finished\n"));
00225 } /* freebuffers */

00249                                  {
00250   facetT *facet;
00251   vertexT *vertex;
00252   ridgeT *ridge, **ridgep;
00253   mergeT *merge, **mergep;
00254 
00255   trace1((qh ferr, "qh_freebuild: free memory from qh_inithull and qh_buildhull\n"));
00256   if (qh del_vertices)
00257     qh_settruncate (qh del_vertices, 0);
00258   if (allmem) {
00259     qh_clearcenters (qh_ASnone);
00260     while ((vertex= qh vertex_list)) {
00261       if (vertex->next)
00262         qh_delvertex (vertex);
00263       else {
00264         qh_memfree (vertex, sizeof(vertexT));
00265         qh newvertex_list= qh vertex_list= NULL;
00266       }
00267     }
00268   }else if (qh VERTEXneighbors) {
00269     FORALLvertices 
00270       qh_setfreelong (&(vertex->neighbors));
00271   }
00272   qh VERTEXneighbors= False;
00273   qh GOODclosest= NULL;
00274   if (allmem) {
00275     FORALLfacets {
00276       FOREACHridge_(facet->ridges)
00277         ridge->seen= False;
00278     }
00279     FORALLfacets {
00280       if (facet->visible) {
00281         FOREACHridge_(facet->ridges) {
00282           if (!otherfacet_(ridge, facet)->visible)
00283             ridge->seen= True;  /* an unattached ridge */
00284         }
00285       }
00286     }
00287     while ((facet= qh facet_list)) {
00288       FOREACHridge_(facet->ridges) {
00289         if (ridge->seen) {
00290           qh_setfree(&(ridge->vertices));
00291           qh_memfree(ridge, sizeof(ridgeT));
00292         }else
00293           ridge->seen= True;
00294       }
00295       qh_setfree (&(facet->outsideset));
00296       qh_setfree (&(facet->coplanarset));
00297       qh_setfree (&(facet->neighbors));
00298       qh_setfree (&(facet->ridges));
00299       qh_setfree (&(facet->vertices));
00300       if (facet->next)
00301         qh_delfacet (facet);
00302       else {
00303         qh_memfree (facet, sizeof(facetT));
00304         qh visible_list= qh newfacet_list= qh facet_list= NULL;
00305       }
00306     }
00307   }else {
00308     FORALLfacets {
00309       qh_setfreelong (&(facet->outsideset));
00310       qh_setfreelong (&(facet->coplanarset));
00311       if (!facet->simplicial) {
00312         qh_setfreelong (&(facet->neighbors));
00313         qh_setfreelong (&(facet->ridges));
00314         qh_setfreelong (&(facet->vertices));
00315       }
00316     }
00317   }
00318   qh_setfree (&(qh hash_table));
00319   qh_memfree (qh interior_point, qh normal_size);
00320   qh interior_point= NULL;
00321   FOREACHmerge_(qh facet_mergeset)  /* usually empty */
00322     qh_memfree (merge, sizeof(mergeT));
00323   qh facet_mergeset= NULL;  /* temp set */
00324   qh degen_mergeset= NULL;  /* temp set */
00325   qh_settempfree_all();
00326 } /* freebuild */

00638                                            {
00639   facetT *facet;
00640   int size, index;
00641   realT randr, dist;
00642   pointT *furthest;
00643 
00644   while ((facet= qh facet_next) != qh facet_tail) {
00645     if (!facet->outsideset) {
00646       qh facet_next= facet->next;
00647       continue;
00648     }
00649     SETreturnsize_(facet->outsideset, size);
00650     if (!size) {
00651       qh_setfree (&facet->outsideset);
00652       qh facet_next= facet->next;
00653       continue;
00654     }
00655     if (qh NARROWhull) {
00656       if (facet->notfurthest) 
00657         qh_furthestout (facet);
00658       furthest= (pointT*)qh_setlast (facet->outsideset);
00659 #if qh_COMPUTEfurthest
00660       qh_distplane (furthest, facet, &dist);
00661       zinc_(Zcomputefurthest);
00662 #else
00663       dist= facet->furthestdist;
00664 #endif
00665       if (dist < qh MINoutside) { /* remainder of outside set is coplanar for qh_outcoplanar */
00666         qh facet_next= facet->next;
00667         continue;
00668       }
00669     }
00670     if (!qh RANDOMoutside && !qh VIRTUALmemory) {
00671       if (qh PICKfurthest) {
00672         qh_furthestnext (/* qh facet_list */);
00673         facet= qh facet_next;
00674       }
00675       *visible= facet;
00676       return ((pointT*)qh_setdellast (facet->outsideset));
00677     }
00678     if (qh RANDOMoutside) {
00679       int outcoplanar = 0;
00680       if (qh NARROWhull) {
00681         FORALLfacets {
00682           if (facet == qh facet_next)
00683             break;
00684           if (facet->outsideset)
00685             outcoplanar += qh_setsize( facet->outsideset);
00686         }
00687       }
00688       randr= qh_RANDOMint;
00689       randr= randr/(qh_RANDOMmax+1);
00690       index= (int)floor((qh num_outside - outcoplanar) * randr);
00691       FORALLfacet_(qh facet_next) {
00692         if (facet->outsideset) {
00693           SETreturnsize_(facet->outsideset, size);
00694           if (!size)
00695             qh_setfree (&facet->outsideset);
00696           else if (size > index) {
00697             *visible= facet;
00698             return ((pointT*)qh_setdelnth (facet->outsideset, index));
00699           }else
00700             index -= size;
00701         }
00702       }
00703       fprintf (qh ferr, "qhull internal error (qh_nextfurthest): num_outside %d is too low\nby at least %d, or a random real %g >= 1.0\n",
00704               qh num_outside, index+1, randr);
00705       qh_errexit (qh_ERRqhull, NULL, NULL);
00706     }else { /* VIRTUALmemory */
00707       facet= qh facet_tail->previous;
00708       if (!(furthest= (pointT*)qh_setdellast(facet->outsideset))) {
00709         if (facet->outsideset)
00710           qh_setfree (&facet->outsideset);
00711         qh_removefacet (facet);
00712         qh_prependfacet (facet, &qh facet_list);
00713         continue;
00714       }
00715       *visible= facet;
00716       return furthest;
00717     }
00718   }
00719   return NULL;
00720 } /* nextfurthest */

01832                                                 {
01833   char buf[200];
01834   int len, maxlen;
01835 
01836   sprintf (buf, "  %s", option);
01837   if (i)
01838     sprintf (buf+strlen(buf), " %d", *i);
01839   if (r)
01840     sprintf (buf+strlen(buf), " %2.2g", *r);
01841   len= strlen(buf);
01842   qh qhull_optionlen += len;
01843   maxlen= sizeof (qh qhull_options) - len -1;
01844   maximize_(maxlen, 0);
01845   if (qh qhull_optionlen >= 80 && maxlen > 0) {
01846     qh qhull_optionlen= len;
01847     strncat (qh qhull_options, "\n", maxlen--);
01848   }    
01849   strncat (qh qhull_options, buf, maxlen);
01850 } /* option */

00754                                                                    {
00755   setT *pointset;
00756   vertexT *vertex, **vertexp;
00757   pointT *point, **pointp, *bestpoint;
00758   int size, point_i, point_n, point_end, remaining, i, id;
00759   facetT *facet;
00760   realT bestdist= -REALmax, dist, distoutside;
00761     
00762   trace1((qh ferr, "qh_partitionall: partition all points into outside sets\n"));
00763   pointset= qh_settemp (numpoints);
00764   qh num_outside= 0;
00765   pointp= SETaddr_(pointset, pointT);
00766   for (i=numpoints, point= points; i--; point += qh hull_dim)
00767     *(pointp++)= point;
00768   qh_settruncate (pointset, numpoints);
00769   FOREACHvertex_(vertices) {
00770     if ((id= qh_pointid(vertex->point)) >= 0)
00771       SETelem_(pointset, id)= NULL;
00772   }
00773   id= qh_pointid (qh GOODpointp);
00774   if (id >=0 && qh STOPcone-1 != id && -qh STOPpoint-1 != id)
00775     SETelem_(pointset, id)= NULL;
00776   if (qh GOODvertexp && qh ONLYgood && !qh MERGING) { /* matches qhull()*/
00777     if ((id= qh_pointid(qh GOODvertexp)) >= 0)
00778       SETelem_(pointset, id)= NULL;
00779   }
00780   if (!qh BESToutside) {  /* matches conditional for qh_partitionpoint below */
00781     if (qh MERGING)
00782       distoutside= qh_DISToutside; /* defined in user.h */
00783     else
00784       distoutside= qh MINoutside;
00785     zval_(Ztotpartition)= qh num_points - qh hull_dim - 1; /*misses GOOD... */
00786     remaining= qh num_facets;
00787     point_end= numpoints;
00788     FORALLfacets {
00789       size= point_end/(remaining--) + 100;
00790       facet->outsideset= qh_setnew (size);
00791       bestpoint= NULL;
00792       point_end= 0;
00793       FOREACHpoint_i_(pointset) {
00794         if (point) {
00795           zzinc_(Zpartitionall);
00796           qh_distplane (point, facet, &dist);
00797           if (dist < distoutside)
00798             SETelem_(pointset, point_end++)= point;
00799           else {
00800             qh num_outside++;
00801             if (!bestpoint) {
00802               bestpoint= point;
00803               bestdist= dist;
00804             }else if (dist > bestdist) {
00805               qh_setappend (&facet->outsideset, bestpoint);
00806               bestpoint= point;
00807               bestdist= dist;
00808             }else 
00809               qh_setappend (&facet->outsideset, point);
00810           }
00811         }
00812       }
00813       if (bestpoint) {
00814         qh_setappend (&facet->outsideset, bestpoint);
00815 #if !qh_COMPUTEfurthest
00816         facet->furthestdist= bestdist;
00817 #endif
00818       }else
00819         qh_setfree (&facet->outsideset);
00820       qh_settruncate (pointset, point_end);
00821     }
00822   }
00823   if (qh BESToutside || qh MERGING || qh KEEPcoplanar || qh KEEPinside) {
00824     qh findbestnew= True;
00825     FOREACHpoint_i_(pointset) { 
00826       if (point)
00827         qh_partitionpoint(point, qh facet_list);
00828     }
00829     qh findbestnew= False;
00830   }
00831   zzadd_(Zpartitionall, zzval_(Zpartition));
00832   zzval_(Zpartition)= 0;
00833   qh_settempfree(&pointset);
00834   if (qh IStracing >= 4)
00835     qh_printfacetlist (qh facet_list, NULL, True);
00836 } /* partitionall */

00872                                                                       {
00873   facetT *bestfacet;
00874   pointT *oldfurthest;
00875   realT bestdist, dist2;
00876   int numpart= 0;
00877   boolT isoutside, istrace= False;
00878 
00879   qh WAScoplanar= True;
00880   if (!dist) {
00881     if (qh findbestnew)
00882       bestfacet= qh_findbestnew (point, facet, 
00883                           &bestdist, NULL, &numpart);
00884     else
00885       bestfacet= qh_findbest (point, facet, qh_ALL, False, !qh_NOupper, 
00886                           &bestdist, &isoutside, &numpart);
00887     zinc_(Ztotpartcoplanar);
00888     zzadd_(Zpartcoplanar, numpart);
00889     if (!qh KEEPinside) {
00890       if (qh KEEPnearinside) {
00891         if (bestdist < -qh NEARinside) { 
00892           zinc_(Zcoplanarinside);
00893           return;
00894         }
00895       }else if (bestdist < -qh MAXcoplanar) {
00896         zinc_(Zcoplanarinside);
00897         return;
00898       }
00899     }
00900   }else {
00901     bestfacet= facet;
00902     bestdist= *dist;
00903   }
00904   if (qh KEEPcoplanar + qh KEEPinside + qh KEEPnearinside) {
00905     oldfurthest= (pointT*)qh_setlast (bestfacet->coplanarset);
00906     if (oldfurthest) {
00907       zinc_(Zcomputefurthest);
00908       qh_distplane (oldfurthest, bestfacet, &dist2);
00909     }
00910     if (!oldfurthest || dist2 < bestdist) {
00911       qh_setappend(&bestfacet->coplanarset, point);
00912       if (bestdist > qh max_outside) {
00913         qh max_outside= bestdist;
00914         if (bestdist > qh TRACEdist)
00915           istrace= True;
00916       }
00917     }else
00918       qh_setappend2ndlast(&bestfacet->coplanarset, point);
00919   }else { /* !KEEPcoplanar && !KEEPinside */
00920     if (bestdist > qh max_outside) {
00921       qh max_outside= bestdist;
00922       if (bestdist > qh TRACEdist) 
00923         istrace= True;
00924     }
00925   }
00926   if (istrace) {
00927     fprintf (qh ferr, "qh_partitioncoplanar: ====== p%d increases max_outside to %2.2g of f%d last p%d\n",
00928                    qh_pointid(point), bestdist, bestfacet->id, qh furthest_id);
00929     qh_errprint ("DISTANT", bestfacet, NULL, NULL, NULL);
00930   }
00931   trace4((qh ferr, "qh_partitioncoplanar: point p%d is coplanar with facet f%d (or inside) dist %2.2g\n",
00932           qh_pointid(point), bestfacet->id, bestdist));
00933 } /* partitioncoplanar */

00970                                                       {
00971   realT bestdist;
00972   boolT isoutside;
00973   facetT *bestfacet;
00974   int numpart;
00975 #if qh_COMPUTEfurthest
00976   realT dist;
00977 #endif
00978 
00979   if (qh findbestnew)
00980     bestfacet= qh_findbestnew (point, facet,
00981                           &bestdist, &isoutside, &numpart);
00982   else
00983     bestfacet= qh_findbest (point, facet, qh BESToutside, True, !qh_NOupper,
00984                           &bestdist, &isoutside, &numpart);
00985   zinc_(Ztotpartition);
00986   zzadd_(Zpartition, numpart);
00987   if (qh NARROWhull) {
00988     if (qh DELAUNAY && !isoutside && bestdist >= -qh MAXcoplanar)
00989       qh_precision ("nearly incident point (narrow hull)");
00990     if (qh KEEPnearinside) {
00991       if (bestdist >= -qh NEARinside)
00992         isoutside= True;
00993     }else if (bestdist >= -qh MAXcoplanar)
00994       isoutside= True;
00995   }
00996 
00997   if (isoutside) {
00998     if (!bestfacet->outsideset 
00999     || !qh_setlast (bestfacet->outsideset)) {
01000       qh_setappend(&(bestfacet->outsideset), point);
01001       if (!bestfacet->newfacet) {
01002         qh_removefacet (bestfacet);  /* make sure it's after qh facet_next */
01003         qh_appendfacet (bestfacet);
01004       }
01005 #if !qh_COMPUTEfurthest
01006       bestfacet->furthestdist= bestdist;
01007 #endif
01008     }else {
01009 #if qh_COMPUTEfurthest
01010       zinc_(Zcomputefurthest);
01011       qh_distplane (oldfurthest, bestfacet, &dist);
01012       if (dist < bestdist) 
01013         qh_setappend(&(bestfacet->outsideset), point);
01014       else
01015         qh_setappend2ndlast(&(bestfacet->outsideset), point);
01016 #else
01017       if (bestfacet->furthestdist < bestdist) {
01018         qh_setappend(&(bestfacet->outsideset), point);
01019         bestfacet->furthestdist= bestdist;
01020       }else
01021         qh_setappend2ndlast(&(bestfacet->outsideset), point);
01022 #endif
01023     }
01024     qh num_outside++;
01025     trace4((qh ferr, "qh_partitionpoint: point p%d is outside facet f%d\n",
01026           qh_pointid(point), bestfacet->id));
01027   }else if (bestdist >= -qh MAXcoplanar) {
01028     zzinc_(Zcoplanarpart);
01029     if (qh DELAUNAY)
01030       qh_precision ("nearly incident point");
01031     if (qh KEEPcoplanar + qh KEEPnearinside || bestdist > qh max_outside) 
01032       qh_partitioncoplanar (point, bestfacet, &bestdist);
01033   }else if (qh KEEPnearinside && bestdist > -qh NEARinside) {
01034     zinc_(Zpartnear);
01035     qh_partitioncoplanar (point, bestfacet, &bestdist);
01036   }else {
01037     zinc_(Zpartinside);
01038     trace4((qh ferr, "qh_partitionpoint: point p%d is inside all facets, closest to f%d dist %2.2g\n",
01039           qh_pointid(point), bestfacet->id, bestdist));
01040     if (qh KEEPinside)    
01041       qh_partitioncoplanar (point, bestfacet, &bestdist);
01042   }
01043 } /* partitionpoint */

01079                                                                             {
01080   facetT *visible, *newfacet;
01081   pointT *point, **pointp;
01082   int coplanar=0, size;
01083   unsigned count;
01084   vertexT *vertex, **vertexp;
01085   
01086   if (qh ONLYmax)
01087     maximize_(qh MINoutside, qh max_vertex);
01088   *numoutside= 0;
01089   FORALLvisible_facets {
01090     if (!visible->outsideset && !visible->coplanarset)
01091       continue;
01092     newfacet= visible->f.replace;
01093     count= 0;
01094     while (newfacet && newfacet->visible) {
01095       newfacet= newfacet->f.replace;
01096       if (count++ > qh facet_id)
01097         qh_infiniteloop (visible);
01098     }
01099     if (!newfacet)
01100       newfacet= qh newfacet_list;
01101     if (visible->outsideset) {
01102       size= qh_setsize (visible->outsideset);
01103       *numoutside += size;
01104       qh num_outside -= size;
01105       FOREACHpoint_(visible->outsideset) 
01106         qh_partitionpoint (point, newfacet);
01107     }
01108     if (visible->coplanarset && (qh KEEPcoplanar + qh KEEPinside + qh KEEPnearinside)) {
01109       size= qh_setsize (visible->coplanarset);
01110       coplanar += size;
01111       FOREACHpoint_(visible->coplanarset) {
01112         if (allpoints)
01113           qh_partitionpoint (point, newfacet);
01114         else
01115           qh_partitioncoplanar (point, newfacet, NULL);
01116       }
01117     }
01118   }
01119   FOREACHvertex_(qh del_vertices) {
01120     if (vertex->point) {
01121       if (allpoints)
01122         qh_partitionpoint (vertex->point, qh newfacet_list);
01123       else
01124         qh_partitioncoplanar (vertex->point, qh newfacet_list, NULL);
01125     }
01126   }
01127   trace1((qh ferr,"qh_partitionvisible: partitioned %d points from outsidesets and %d points from coplanarsets\n", *numoutside, coplanar));
01128 } /* partitionvisible */

01138                                  {
01139 
01140   if (qh ALLOWrestart && !qh PREmerge && !qh MERGEexact) {
01141     if (qh JOGGLEmax < REALmax/2) {
01142       trace0((qh ferr, "qh_precision: qhull restart because of %s\n", reason));
01143       longjmp(qh restartexit, qh_ERRprec);
01144     }
01145   }
01146 } /* qh_precision */

01161                                {
01162   realT ratio, outerplane, innerplane;
01163   float cpu;
01164   int size, id, nummerged, numvertices, numcoplanars= 0, nonsimplicial=0;
01165   int goodused;
01166   facetT *facet;
01167   char *s;
01168 
01169   size= qh num_points + qh_setsize (qh other_points);
01170   numvertices= qh num_vertices - qh_setsize (qh del_vertices);
01171   id= qh_pointid (qh GOODpointp);
01172   FORALLfacets {
01173     if (facet->coplanarset)
01174       numcoplanars += qh_setsize( facet->coplanarset);
01175     if (facet->good) {
01176       if (!facet->simplicial && qh_setsize(facet->vertices) != qh hull_dim)
01177         nonsimplicial++;
01178     }
01179   }
01180   if (id >=0 && qh STOPcone-1 != id && -qh STOPpoint-1 != id)
01181     size--;
01182   if (qh STOPcone || qh STOPpoint)
01183       fprintf (fp, "\nAt a premature exit due to 'TVn', 'TCn', or precision error.");
01184   if (qh UPPERdelaunay)
01185     goodused= qh GOODvertex + qh GOODpoint + qh SPLITthresholds;
01186   else if (qh DELAUNAY)
01187     goodused= qh GOODvertex + qh GOODpoint + qh GOODthreshold;
01188   else
01189     goodused= qh num_good;
01190   nummerged= zzval_(Ztotmerge) - zzval_(Zcyclehorizon) + zzval_(Zcyclefacettot);
01191   if (qh VORONOI) {
01192     if (qh UPPERdelaunay)
01193       fprintf (fp, "\n\
01194 Furthest-site Voronoi vertices by the convex hull of %d points in %d-d:\n\n", size, qh hull_dim);
01195     else
01196       fprintf (fp, "\n\
01197 Voronoi diagram by the convex hull of %d points in %d-d:\n\n", size, qh hull_dim);
01198     fprintf(fp, "  Number of Voronoi regions%s: %d\n",
01199               qh ATinfinity ? " and at-infinity" : "", numvertices);
01200     if (numcoplanars) 
01201       fprintf(fp, "  Number of nearly incident points: %d\n", numcoplanars); 
01202     else if (size > numvertices) 
01203       fprintf(fp, "  Total number of nearly incident points: %d\n", size - numvertices); 
01204     fprintf(fp, "  Number of%s Voronoi vertices: %d\n", 
01205               goodused ? " 'good'" : "", qh num_good);
01206     if (nonsimplicial) 
01207       fprintf(fp, "  Number of%s non-simplicial Voronoi vertices: %d\n", 
01208               goodused ? " 'good'" : "", nonsimplicial);
01209   }else if (qh DELAUNAY) {
01210     if (qh UPPERdelaunay)
01211       fprintf (fp, "\n\
01212 Furthest-site Delaunay triangulation by the convex hull of %d points in %d-d:\n\n", size, qh hull_dim);
01213     else
01214       fprintf (fp, "\n\
01215 Delaunay triangulation by the convex hull of %d points in %d-d:\n\n", size, qh hull_dim);
01216     fprintf(fp, "  Number of input sites%s: %d\n", 
01217               qh ATinfinity ? " and at-infinity" : "", numvertices);
01218     if (numcoplanars) 
01219       fprintf(fp, "  Number of nearly incident points: %d\n", numcoplanars); 
01220     else if (size > numvertices) 
01221       fprintf(fp, "  Total number of nearly incident points: %d\n", size - numvertices); 
01222     fprintf(fp, "  Number of%s Delaunay regions: %d\n", 
01223               goodused ? " 'good'" : "", qh num_good);
01224     if (nonsimplicial) 
01225       fprintf(fp, "  Number of%s non-simplicial Delaunay regions: %d\n", 
01226               goodused ? " 'good'" : "", nonsimplicial);
01227   }else if (qh HALFspace) {
01228     fprintf (fp, "\n\
01229 Halfspace intersection by the convex hull of %d points in %d-d:\n\n", size, qh hull_dim);
01230     fprintf(fp, "  Number of halfspaces: %d\n", size);
01231     fprintf(fp, "  Number of non-redundant halfspaces: %d\n", numvertices);
01232     if (numcoplanars) {
01233       if (qh KEEPinside && qh KEEPcoplanar)
01234         s= "similar and redundant";
01235       else if (qh KEEPinside)
01236         s= "redundant";
01237       else
01238         s= "similar"; 
01239       fprintf(fp, "  Number of %s halfspaces: %d\n", s, numcoplanars);
01240     } 
01241     fprintf(fp, "  Number of intersection points: %d\n", qh num_facets - qh num_visible);
01242     if (goodused)
01243       fprintf(fp, "  Number of 'good' intersection points: %d\n", qh num_good);
01244     if (nonsimplicial) 
01245       fprintf(fp, "  Number of%s non-simplicial intersection points: %d\n", 
01246               goodused ? " 'good'" : "", nonsimplicial);
01247   }else {
01248     fprintf (fp, "\n\
01249 Convex hull of %d points in %d-d:\n\n", size, qh hull_dim);
01250     fprintf(fp, "  Number of vertices: %d\n", numvertices);
01251     if (numcoplanars) {
01252       if (qh KEEPinside && qh KEEPcoplanar)
01253         s= "coplanar and interior";
01254       else if (qh KEEPinside)
01255         s= "interior";
01256       else
01257         s= "coplanar"; 
01258       fprintf(fp, "  Number of %s points: %d\n", s, numcoplanars);
01259     } 
01260     fprintf(fp, "  Number of facets: %d\n", qh num_facets - qh num_visible);
01261     if (goodused)
01262       fprintf(fp, "  Number of 'good' facets: %d\n", qh num_good);
01263     if (nonsimplicial) 
01264       fprintf(fp, "  Number of%s non-simplicial facets: %d\n", 
01265               goodused ? " 'good'" : "", nonsimplicial);
01266   }
01267   fprintf(fp, "\nStatistics for: %s | %s", 
01268                       qh rbox_command, qh qhull_command);
01269   if (qh ROTATErandom != INT_MIN)
01270     fprintf(fp, " QR%d\n\n", qh ROTATErandom);
01271   else
01272     fprintf(fp, "\n\n");
01273   fprintf(fp, "  Number of points processed: %d\n", zzval_(Zprocessed));
01274   fprintf(fp, "  Number of hyperplanes created: %d\n", zzval_(Zsetplane));
01275   if (qh DELAUNAY)
01276     fprintf(fp, "  Number of facets in hull: %d\n", qh num_facets - qh num_visible);
01277   fprintf(fp, "  Number of distance tests for qhull: %d\n", zzval_(Zpartition)+
01278       zzval_(Zpartitionall)+zzval_(Znumvisibility)+zzval_(Zpartcoplanar));
01279 #if 0  /* NOTE: must print before printstatistics() */
01280   {realT stddev, ave;
01281   fprintf(fp, "  average new facet balance: %2.2g\n",
01282           wval_(Wnewbalance)/zval_(Zprocessed));
01283   stddev= qh_stddev (zval_(Zprocessed), wval_(Wnewbalance), 
01284                                  wval_(Wnewbalance2), &ave);
01285   fprintf(fp, "  new facet standard deviation: %2.2g\n", stddev);
01286   fprintf(fp, "  average partition balance: %2.2g\n",
01287           wval_(Wpbalance)/zval_(Zpbalance));
01288   stddev= qh_stddev (zval_(Zpbalance), wval_(Wpbalance), 
01289                                  wval_(Wpbalance2), &ave);
01290   fprintf(fp, "  partition standard deviation: %2.2g\n", stddev);
01291   }
01292 #endif
01293   if (nummerged) {
01294     fprintf(fp,"  Number of merged facets: %d\n", nummerged);
01295     fprintf(fp,"  Number of distance tests for merging: %d\n",zzval_(Zbestdist)+
01296           zzval_(Zcentrumtests)+zzval_(Zdistconvex)+zzval_(Zdistcheck)+
01297           zzval_(Zdistzero));
01298   }
01299   if (!qh RANDOMoutside && qh QHULLfinished) {
01300     cpu= qh hulltime;
01301     cpu /= qh_SECticks;
01302     wval_(Wcpu)= cpu;
01303     fprintf (fp, "  CPU seconds to compute hull (after input): %2.4g\n", cpu);
01304   }
01305   if (qh RERUN) {
01306     if (!qh PREmerge && !qh MERGEexact)
01307       fprintf(fp, "  Percentage of runs with precision errors: %4.1f\n",
01308            zzval_(Zretry)*100.0/qh build_cnt);  /* careful of order */
01309   }else if (qh JOGGLEmax < REALmax/2) {
01310     if (zzval_(Zretry))
01311       fprintf(fp, "  After %d retries, input joggled by: %2.2g\n",
01312          zzval_(Zretry), qh JOGGLEmax);
01313     else
01314       fprintf(fp, "  Input joggled by: %2.2g\n", qh JOGGLEmax);
01315   }
01316   if (qh totarea != 0.0) 
01317     fprintf(fp, "  %s facet area:   %2.8g\n", 
01318             zzval_(Ztotmerge) ? "Approximate" : "Total", qh totarea);
01319   if (qh totvol != 0.0) 
01320     fprintf(fp, "  %s volume:       %2.8g\n", 
01321             zzval_(Ztotmerge) ? "Approximate" : "Total", qh totvol);
01322   if (qh MERGING) {
01323     qh_outerinner (NULL, &outerplane, &innerplane);
01324     if (outerplane > 2 * qh DISTround) {
01325       fprintf(fp, "  Maximum distance of %spoint above facet: %2.2g", 
01326             (qh QHULLfinished ? "" : "merged "), outerplane);
01327       ratio= outerplane/(qh ONEmerge + qh DISTround);
01328       if (ratio > 0.05 && qh ONEmerge > qh MINoutside && qh JOGGLEmax > REALmax/2)
01329         fprintf (fp, " (%.1fx)\n", ratio);
01330       else
01331         fprintf (fp, "\n");
01332     }
01333     if (innerplane < -2 * qh DISTround) {
01334       fprintf(fp, "  Maximum distance of %svertex below facet: %2.2g", 
01335             (qh QHULLfinished ? "" : "merged "), innerplane);
01336       ratio= -innerplane/(qh ONEmerge+qh DISTround);
01337       if (ratio > 0.05 && qh JOGGLEmax > REALmax/2)
01338         fprintf (fp, " (%.1fx)\n", ratio);
01339       else
01340         fprintf (fp, "\n");
01341     }
01342   }
01343   fprintf(fp, "\n");
01344 } /* printsummary */

00057                      {
00058   int numoutside;
00059 
00060   qh hulltime= qh_CPUclock;
00061   if (qh RERUN || qh JOGGLEmax < REALmax/2) 
00062     qh_build_withrestart();
00063   else {
00064     qh_initbuild();
00065     qh_buildhull();
00066   }
00067   if (!qh STOPpoint && !qh STOPcone) {
00068     if (qh ZEROall_ok && !qh TESTvneighbors && qh MERGEexact)
00069       qh_checkzero( qh_ALL);
00070     if (qh ZEROall_ok && !qh TESTvneighbors && !qh WAScoplanar) {
00071       trace2((qh ferr, "qh_qhull: all facets are clearly convex and no coplanar points.  Post-merging and check of maxout not needed.\n"));
00072     }else {
00073       if (qh MERGEexact || (qh hull_dim > qh_DIMreduceBuild && qh PREmerge))
00074         qh_postmerge ("First post-merge", qh premerge_centrum, qh premerge_cos, 
00075              (qh POSTmerge ? False : qh TESTvneighbors));
00076       else if (!qh POSTmerge && qh TESTvneighbors) 
00077         qh_postmerge ("For testing vertex neighbors", qh premerge_centrum,
00078              qh premerge_cos, True); 
00079       if (qh POSTmerge)
00080         qh_postmerge ("For post-merging", qh postmerge_centrum, 
00081              qh postmerge_cos, qh TESTvneighbors);
00082       if (qh visible_list == qh facet_list) { /* i.e., merging done */
00083         qh findbestnew= True;
00084         qh_partitionvisible (/*visible_list, newfacet_list*/ !qh_ALL, &numoutside);
00085         qh findbestnew= False;
00086         qh_deletevisible (/*qh visible_list*/);
00087         qh_resetlists (False /*qh visible_list newvertex_list newfacet_list */);
00088       }
00089       if (qh DOcheckmax){
00090         if (qh REPORTfreq) {
00091           qh_buildtracing (NULL, NULL); 
00092           fprintf (qh ferr, "\nTesting all coplanar points.\n");
00093         }
00094         qh_check_maxout();
00095       }
00096     }
00097   }
00098   if (qh KEEPnearinside && !qh maxoutdone)  
00099     qh_nearcoplanar();
00100   if (qh_setsize ((setT*)qhmem.tempstack) != 0) {
00101     fprintf (qh ferr, "qhull internal error (qh_qhull): temporary sets not empty (%d)\n",
00102              qh_setsize ((setT*)qhmem.tempstack));
00103     qh_errexit (qh_ERRqhull, NULL, NULL);
00104   }
00105   qh hulltime= qh_CPUclock - qh hulltime;
00106   qh QHULLfinished= True;
00107   trace1((qh ferr, "qh_qhull: algorithm completed\n"));
00108 } /* qhull */

01942                                               {
01943   double result;
01944 
01945   result= strtod (s, endp);
01946   if (s < (*endp) && (*endp)[-1] == ' ')
01947     (*endp)--;
01948   return result;
01949 } /* strtod */

01951                                            {
01952   int result;
01953 
01954   result= (int) strtol (s, endp, 10);
01955   if (s< (*endp) && (*endp)[-1] == ' ')
01956     (*endp)--;
01957   return result;
01958 } /* strtol */