for (same= newfacet->f.samecycle; \
         same; same= (same == newfacet ?  NULL : same->f.samecycle))

00024                                                                               {
00025   int scan;
00026   void *elem;
00027 
00028   for (scan= (int)hash; (elem= SETelem_(hashtable, scan)); 
00029        scan= (++scan >= hashsize ? 0 : scan)) {
00030     if (elem == newelem)
00031       break;
00032   }
00033   /* loop terminates because qh_HASHfactor >= 1.1 by qh_initbuffers */
00034   if (!elem)
00035     SETelem_(hashtable, scan)= newelem;
00036 } /* addhash */

00033                                    {
00034   facetT *tail= qh facet_tail;
00035 
00036   if (tail == qh newfacet_list)
00037     qh newfacet_list= facet;
00038   if (tail == qh facet_next)
00039     qh facet_next= facet;
00040   facet->previous= tail->previous;
00041   facet->next= tail;
00042   if (tail->previous)
00043     tail->previous->next= facet;
00044   else
00045     qh facet_list= facet;
00046   tail->previous= facet;
00047   qh num_facets++;
00048   trace4((qh ferr, "qh_appendfacet: append f%d to facet_list\n", facet->id));
00049 } /* appendfacet */

00067                                        {
00068   vertexT *tail= qh vertex_tail;
00069 
00070   if (tail == qh newvertex_list)
00071     qh newvertex_list= vertex;
00072   vertex->newlist= True;
00073   vertex->previous= tail->previous;
00074   vertex->next= tail;
00075   if (tail->previous)
00076     tail->previous->next= vertex;
00077   else
00078     qh vertex_list= vertex;
00079   tail->previous= vertex;
00080   qh num_vertices++;
00081   trace4((qh ferr, "qh_appendvertex: append v%d to vertex_list\n", vertex->id));
00082 } /* appendvertex */

00124                                 {
00125   facetT *newfacet= NULL, *neighbor, **neighborp, *horizon, *visible;
00126   ridgeT *ridge, **ridgep;
00127 
00128   qh NEWfacets= True;
00129   trace3((qh ferr, "qh_attachnewfacets: delete interior ridges\n"));
00130   qh visit_id++;
00131   FORALLvisible_facets {
00132     visible->visitid= qh visit_id;
00133     if (visible->ridges) {
00134       FOREACHridge_(visible->ridges) {
00135         neighbor= otherfacet_(ridge, visible);
00136         if (neighbor->visitid == qh visit_id
00137             || (!neighbor->visible && neighbor->simplicial)) {
00138           if (!neighbor->visible)  /* delete ridge for simplicial horizon */
00139             qh_setdel (neighbor->ridges, ridge);
00140           qh_setfree (&(ridge->vertices)); /* delete on 2nd visit */
00141           qh_memfree (ridge, sizeof(ridgeT));
00142         }
00143       }
00144       SETfirst_(visible->ridges)= NULL;
00145     }
00146     SETfirst_(visible->neighbors)= NULL;
00147   }
00148   trace1((qh ferr, "qh_attachnewfacets: attach horizon facets to new facets\n"));
00149   FORALLnew_facets {
00150     horizon= SETfirstt_(newfacet->neighbors, facetT);
00151     if (horizon->simplicial) {
00152       visible= NULL;
00153       FOREACHneighbor_(horizon) {   /* may have more than one horizon ridge */
00154         if (neighbor->visible) {
00155           if (visible) {
00156             if (qh_setequal_skip (newfacet->vertices, 0, horizon->vertices,
00157                                   SETindex_(horizon->neighbors, neighbor))) {
00158               visible= neighbor;
00159               break;
00160             }
00161           }else
00162             visible= neighbor;
00163         }
00164       }
00165       if (visible) {
00166         visible->f.replace= newfacet;
00167         qh_setreplace (horizon->neighbors, visible, newfacet);
00168       }else {
00169         fprintf (qh ferr, "qhull internal error (qh_attachnewfacets): couldn't find visible facet for horizon f%d of newfacet f%d\n",
00170                  horizon->id, newfacet->id);
00171         qh_errexit2 (qh_ERRqhull, horizon, newfacet);
00172       }
00173     }else { /* non-simplicial, with a ridge for newfacet */
00174       FOREACHneighbor_(horizon) {    /* may hold for many new facets */
00175         if (neighbor->visible) {
00176           neighbor->f.replace= newfacet;
00177           qh_setdelnth (horizon->neighbors,
00178                         SETindex_(horizon->neighbors, neighbor));
00179           neighborp--; /* repeat */
00180         }
00181       }
00182       qh_setappend (&horizon->neighbors, newfacet);
00183       ridge= SETfirstt_(newfacet->ridges, ridgeT);
00184       if (ridge->top == horizon)
00185         ridge->bottom= newfacet;
00186       else
00187         ridge->top= newfacet;
00188       }
00189   } /* newfacets */
00190   if (qh PRINTstatistics) {
00191     FORALLvisible_facets {
00192       if (!visible->f.replace) 
00193         zinc_(Zinsidevisible);
00194     }
00195   }
00196 } /* attachnewfacets */

00062                               {
00063   boolT waserror= False, isoutside, unassigned;
00064   facetT *facet, *bestfacet, *errfacet1= NULL, *errfacet2= NULL;
00065   facetT *facetlist; 
00066   realT dist, maxoutside, maxdist= -REALmax;
00067   pointT *point;
00068   int numpart, facet_i, facet_n, notgood= 0, notverified= 0;
00069   setT *facets;
00070 
00071   trace1((qh ferr, "qh_check_bestdist: check points below nearest facet.  Facet_list f%d\n",
00072       qh facet_list->id));
00073   maxoutside= qh_maxouter();
00074   maxoutside += qh DISTround;
00075   /* one more qh.DISTround for check computation */
00076   trace1((qh ferr, "qh_check_bestdist: check that all points are within %2.2g of best facet\n", maxoutside));
00077   facets= qh_pointfacet (/*qh facet_list*/);
00078   if (!qh_QUICKhelp && qh PRINTprecision)
00079     fprintf (qh ferr, "\n\
00080 qhull output completed.  Verifying that %d points are\n\
00081 below %2.2g of the nearest %sfacet.\n",
00082              qh_setsize(facets), maxoutside, (qh ONLYgood ?  "good " : ""));
00083   FOREACHfacet_i_(facets) {  /* for each point with facet assignment */
00084     if (facet)
00085       unassigned= False;
00086     else {
00087       unassigned= True;
00088       facet= qh facet_list;
00089     }
00090     point= qh_point(facet_i);
00091     if (point == qh GOODpointp)
00092       continue;
00093     bestfacet= qh_findbest (point, facet, qh_ALL, False, !qh_NOupper,
00094                             &dist, &isoutside, &numpart);
00095     /* occurs after statistics reported */
00096     maximize_(maxdist, dist);
00097     if (dist > maxoutside) {
00098       if (qh ONLYgood && !bestfacet->good 
00099           && !((bestfacet= qh_findgooddist (point, bestfacet, &dist, &facetlist))
00100                && dist > maxoutside))
00101         notgood++;
00102       else {
00103         waserror= True;
00104         fprintf(qh ferr, "qhull precision error: point p%d is outside facet f%d, distance= %6.8g maxoutside= %6.8g\n", 
00105                 facet_i, bestfacet->id, dist, maxoutside);
00106         errfacet2= errfacet1;
00107         errfacet1= bestfacet;               
00108       }
00109     }else if (unassigned && dist < -qh MAXcoplanar)
00110       notverified++;
00111   }
00112   qh_settempfree (&facets);
00113   if (notverified && !qh DELAUNAY && !qh_QUICKhelp && qh PRINTprecision) 
00114     fprintf(qh ferr, "\n%d points were well inside the hull.  If the hull contains\n\
00115 a lens-shaped component, these points were not verified.  Use\n\
00116 options 'Qci Tv' to verify all points.\n", notverified); 
00117   if (maxdist > qh outside_err) {
00118     fprintf( qh ferr, "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",
00119               maxdist, qh outside_err);
00120     qh_errexit2 (qh_ERRprec, errfacet1, errfacet2);
00121   }else if (waserror && qh outside_err > REALmax/2)
00122     qh_errexit2 (qh_ERRprec, errfacet1, errfacet2);
00123   else if (waserror)
00124     ;                       /* the error was logged to qh_errlog() but does not effect the output */
00125   trace0((qh ferr, "qh_check_bestdist: max distance outside %2.2g\n", maxdist));
00126 } /* check_bestdist */

00161                             {
00162   facetT *facet, *bestfacet, *neighbor, **neighborp, *facetlist;
00163   realT dist, maxoutside, minvertex;
00164   pointT *point;
00165   int numpart, facet_i, facet_n, notgood= 0;
00166   setT *facets, *vertices;
00167   vertexT *vertex;
00168 
00169   trace1((qh ferr, "qh_check_maxout: check and update maxoutside for each facet.\n"));
00170   maxoutside= minvertex= 0;
00171   if (qh VERTEXneighbors 
00172   && (qh PRINTsummary || qh KEEPinside || qh KEEPcoplanar 
00173         || qh TRACElevel || qh PRINTstatistics
00174         || qh PRINTout[0] == qh_PRINTsummary || qh PRINTout[0] == qh_PRINTnone)) { 
00175     trace1((qh ferr, "qh_check_maxout: determine actual maxoutside and minvertex\n"));
00176     vertices= qh_pointvertex (/*qh facet_list*/);
00177     FORALLvertices {
00178       FOREACHneighbor_(vertex) {
00179         zinc_(Zdistvertex);  /* distance also computed by main loop below */
00180         qh_distplane (vertex->point, neighbor, &dist);
00181         minimize_(minvertex, dist);
00182         if (-dist > qh TRACEdist || dist > qh TRACEdist 
00183         || neighbor == qh tracefacet || vertex == qh tracevertex)
00184           fprintf (qh ferr, "qh_check_maxout: p%d (v%d) is %.2g from f%d\n",
00185                     qh_pointid (vertex->point), vertex->id, dist, neighbor->id);
00186       }
00187     }
00188     if (qh MERGING) {
00189       wmin_(Wminvertex, qh min_vertex);
00190     }
00191     qh min_vertex= minvertex;
00192     qh_settempfree (&vertices);  
00193   }
00194   facets= qh_pointfacet (/*qh facet_list*/);
00195   FOREACHfacet_i_(facets) {     /* for each point with facet assignment */
00196     if (facet) { 
00197       point= qh_point(facet_i);
00198       if (point == qh GOODpointp)
00199         continue;
00200       zinc_(Ztotcheck);
00201       bestfacet= qh_findbest (point, facet, qh_ALL, False, !qh_NOupper,
00202                                  &dist, NULL, &numpart);
00203       zadd_(Zcheckpart, numpart);
00204       if (bestfacet && dist > maxoutside) {
00205         if (qh ONLYgood && !bestfacet->good 
00206         && !((bestfacet= qh_findgooddist (point, bestfacet, &dist, &facetlist))
00207              && dist > maxoutside))
00208           notgood++;
00209         else
00210           maxoutside= dist;
00211       }
00212       if (dist > qh TRACEdist || (bestfacet && bestfacet == qh tracefacet))
00213         fprintf (qh ferr, "qh_check_maxout: p%d is %.2g above f%d\n",
00214                    qh_pointid (point), dist, bestfacet->id);
00215     }
00216   }
00217   qh_settempfree (&facets);
00218   wval_(Wmaxout)= maxoutside - qh max_outside;
00219   wmax_(Wmaxoutside, qh max_outside);
00220   qh max_outside= maxoutside;
00221   qh_nearcoplanar (/*qh.facet_list*/);
00222   qh maxoutdone= True;
00223   trace1((qh ferr, "qh_check_maxout: maxoutside %2.2g, min_vertex %2.2g, outside of not good %d\n",
00224        maxoutside, qh min_vertex, notgood));
00225 } /* check_maxout */

00237                             {
00238   int i;
00239 
00240   if (qh STOPcone)
00241     return;
00242   if (qh VERIFYoutput | qh IStracing | qh CHECKfrequently) {
00243     qh_checkpolygon (qh facet_list);
00244     qh_checkflipped_all (qh facet_list);
00245     qh_checkconvex (qh facet_list, qh_ALGORITHMfault);
00246   }else if (!qh MERGING && qh_newstats (qhstat precision, &i)) {
00247     qh_checkflipped_all (qh facet_list);
00248     qh_checkconvex (qh facet_list, qh_ALGORITHMfault);
00249   }
00250 } /* check_output */

00260                                                                                                                               {
00261   realT dist;
00262 
00263   /* occurs after statistics reported */
00264   qh_distplane(point, facet, &dist);
00265   if (dist > *maxoutside) {
00266     *errfacet2= *errfacet1;
00267     *errfacet1= facet;
00268     fprintf(qh ferr, "qhull precision error: point p%d is outside facet f%d, distance= %6.8g maxoutside= %6.8g\n", 
00269               qh_pointid(point), facet->id, dist, *maxoutside);
00270   }
00271   maximize_(*maxdist, dist);
00272 } /* qh_check_point */

00297                             {
00298   facetT *facet, *errfacet1= NULL, *errfacet2= NULL;
00299   realT total, maxoutside, maxdist= -REALmax;
00300   pointT *point, **pointp, *pointtemp;
00301   boolT testouter;
00302 
00303   maxoutside= qh_maxouter();
00304   maxoutside += qh DISTround;
00305   /* one more qh.DISTround for check computation */
00306   trace1((qh ferr, "qh_check_points: check all points below %2.2g of all facet planes\n",
00307           maxoutside));
00308   if (qh num_good)   /* miss counts other_points and !good facets */
00309      total= (float) qh num_good * qh num_points;
00310   else
00311      total= (float) qh num_facets * qh num_points;
00312   if (total >= qh_VERIFYdirect && !qh maxoutdone) {
00313     if (!qh_QUICKhelp && qh SKIPcheckmax && qh MERGING)
00314       fprintf (qh ferr, "\n\
00315 qhull input warning: merging without checking outer planes ('Q5').\n\
00316 Verify may report that a point is outside of a facet.\n");
00317     qh_check_bestdist();
00318   }else {
00319     if (qh_MAXoutside && qh maxoutdone)
00320       testouter= True;
00321     else
00322       testouter= False;
00323     if (!qh_QUICKhelp) {
00324       if (qh MERGEexact)
00325         fprintf (qh ferr, "\n\
00326 qhull input warning: exact merge ('Qx').  Verify may report that a point\n\
00327 is outside of a facet.  See qh-optq.htm#Qx\n");
00328       else if (qh SKIPcheckmax || qh NOnearinside)
00329         fprintf (qh ferr, "\n\
00330 qhull input warning: no outer plane check ('Q5') or no processing of\n\
00331 near-inside points ('Q8').  Verify may report that a point is outside\n\
00332 of a facet.\n");
00333     }
00334     if (qh PRINTprecision) {
00335       if (testouter)
00336         fprintf (qh ferr, "\n\
00337 Output completed.  Verifying that all points are below outer planes of\n\
00338 all %sfacets.  Will make %2.0f distance computations.\n", 
00339               (qh ONLYgood ?  "good " : ""), total);
00340       else
00341         fprintf (qh ferr, "\n\
00342 Output completed.  Verifying that all points are below %2.2g of\n\
00343 all %sfacets.  Will make %2.0f distance computations.\n", 
00344               maxoutside, (qh ONLYgood ?  "good " : ""), total);
00345     }
00346     FORALLfacets {
00347       if (!facet->good && qh ONLYgood)
00348         continue;
00349       if (facet->flipped)
00350         continue;
00351       if (testouter) {
00352 #if qh_MAXoutside
00353         maxoutside= facet->maxoutside + 2* qh DISTround;
00354         /* one DISTround to actual point and another to computed point */
00355 #endif
00356       }
00357       FORALLpoints {
00358         if (point != qh GOODpointp)
00359           qh_check_point (point, facet, &maxoutside, &maxdist, &errfacet1, &errfacet2);
00360       }
00361       FOREACHpoint_(qh other_points) {
00362         if (point != qh GOODpointp)
00363           qh_check_point (point, facet, &maxoutside, &maxdist, &errfacet1, &errfacet2);
00364       }
00365     }
00366     if (maxdist > qh outside_err) {
00367       fprintf( qh ferr, "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",
00368                 maxdist, qh outside_err );
00369       qh_errexit2( qh_ERRprec, errfacet1, errfacet2 );
00370     }else if (errfacet1 && qh outside_err > REALmax/2)
00371         qh_errexit2( qh_ERRprec, errfacet1, errfacet2 );
00372     else if (errfacet1)
00373         ;  /* the error was logged to qh.ferr but does not effect the output */
00374     trace0((qh ferr, "qh_check_points: max distance outside %2.2g\n", maxdist));
00375   }
00376 } /* check_points */

00407                                                   {
00408   facetT *facet, *neighbor, **neighborp, *errfacet1=NULL, *errfacet2=NULL;
00409   vertexT *vertex;
00410   realT dist;
00411   pointT *centrum;
00412   boolT waserror= False, tempcentrum= False, allsimplicial;
00413   int neighbor_i;
00414 
00415   trace1((qh ferr, "qh_checkconvex: check all ridges are convex\n"));
00416   if (!qh RERUN) {
00417     zzval_(Zconcaveridges)= 0;
00418     zzval_(Zcoplanarridges)= 0;
00419   }
00420   FORALLfacet_(facetlist) {
00421     if (facet->flipped) {
00422       qh_precision ("flipped facet");
00423       fprintf (qh ferr, "qhull precision error: f%d is flipped (interior point is outside)\n",
00424                facet->id);
00425       errfacet1= facet;
00426       waserror= True;
00427       continue;
00428     }
00429     if (qh MERGING && (!qh ZEROcentrum || !facet->simplicial))
00430       allsimplicial= False;
00431     else {
00432       allsimplicial= True;
00433       neighbor_i= 0;
00434       FOREACHneighbor_(facet) {
00435         vertex= SETelemt_(facet->vertices, neighbor_i++, vertexT);
00436         if (!neighbor->simplicial) {
00437           allsimplicial= False;
00438           continue;
00439         }
00440         qh_distplane (vertex->point, neighbor, &dist);
00441         if (dist > -qh DISTround) {
00442           if (fault == qh_DATAfault) {
00443             qh_precision ("coplanar or concave ridge");
00444             fprintf (qh ferr, "qhull precision error: initial simplex is not convex. Distance=%.2g\n", dist);
00445             qh_errexit(qh_ERRsingular, NULL, NULL);
00446           }
00447           if (dist > qh DISTround) {
00448             zzinc_(Zconcaveridges);
00449             qh_precision ("concave ridge");
00450             fprintf (qh ferr, "qhull precision error: f%d is concave to f%d, since p%d (v%d) is %6.4g above\n",
00451               facet->id, neighbor->id, qh_pointid(vertex->point), vertex->id, dist);
00452             errfacet1= facet;
00453             errfacet2= neighbor;
00454             waserror= True;
00455           }else if (qh ZEROcentrum) {
00456             if (dist > 0) {     /* qh_checkzero checks that dist < - qh DISTround */
00457               zzinc_(Zcoplanarridges); 
00458               qh_precision ("coplanar ridge");
00459               fprintf (qh ferr, "qhull precision error: f%d is clearly not convex to f%d, since p%d (v%d) is %6.4g above\n",
00460                 facet->id, neighbor->id, qh_pointid(vertex->point), vertex->id, dist);
00461               errfacet1= facet;
00462               errfacet2= neighbor;
00463               waserror= True;
00464             }
00465           }else {              
00466             zzinc_(Zcoplanarridges);
00467             qh_precision ("coplanar ridge");
00468             trace0((qh ferr, "qhull precision error: f%d may be coplanar to f%d, since p%d (v%d) is within %6.4g during p%d\n",
00469               facet->id, neighbor->id, qh_pointid(vertex->point), vertex->id, dist, qh furthest_id));
00470           }
00471         }
00472       }
00473     }
00474     if (!allsimplicial) {
00475       if (qh CENTERtype == qh_AScentrum) {
00476         if (!facet->center)
00477           facet->center= qh_getcentrum (facet);
00478         centrum= facet->center;
00479       }else {
00480         centrum= qh_getcentrum(facet);
00481         tempcentrum= True;
00482       }
00483       FOREACHneighbor_(facet) {
00484         if (qh ZEROcentrum && facet->simplicial && neighbor->simplicial)
00485           continue;
00486         zzinc_(Zdistconvex);
00487         qh_distplane (centrum, neighbor, &dist);
00488         if (dist > qh DISTround) {
00489           zzinc_(Zconcaveridges);
00490           qh_precision ("concave ridge");
00491           fprintf (qh ferr, "qhull precision error: f%d is concave to f%d.  Centrum of f%d is %6.4g above f%d\n",
00492             facet->id, neighbor->id, facet->id, dist, neighbor->id);
00493           errfacet1= facet;
00494           errfacet2= neighbor;
00495           waserror= True;
00496         }else if (dist >= 0.0) {   /* if arithmetic always rounds the same,
00497                                      can test against centrum radius instead */
00498           zzinc_(Zcoplanarridges);
00499           qh_precision ("coplanar ridge");
00500           fprintf (qh ferr, "qhull precision error: f%d is coplanar or concave to f%d.  Centrum of f%d is %6.4g above f%d\n",
00501             facet->id, neighbor->id, facet->id, dist, neighbor->id);
00502           errfacet1= facet;
00503           errfacet2= neighbor;
00504           waserror= True;
00505         }
00506       }
00507       if (tempcentrum)
00508         qh_memfree(centrum, qh normal_size);
00509     }
00510   }
00511   if (waserror && !qh FORCEoutput)
00512     qh_errexit2 (qh_ERRprec, errfacet1, errfacet2);
00513 } /* checkconvex */

00553                                                                     {
00554   facetT *neighbor, **neighborp, *errother=NULL;
00555   ridgeT *ridge, **ridgep, *errridge= NULL, *ridge2;
00556   vertexT *vertex, **vertexp;
00557   unsigned previousid= INT_MAX;
00558   int numneighbors, numvertices, numridges=0, numRvertices=0;
00559   boolT waserror= False;
00560   int skipA, skipB, ridge_i, ridge_n, i;
00561   setT *intersection;
00562 
00563   if (facet->visible) {
00564     fprintf (qh ferr, "qhull internal error (qh_checkfacet): facet f%d is on the visible_list\n",
00565       facet->id);
00566     qh_errexit (qh_ERRqhull, facet, NULL);
00567   }
00568   if (!facet->normal) {
00569     fprintf (qh ferr, "qhull internal error (qh_checkfacet): facet f%d does not have  a normal\n",
00570       facet->id);
00571     waserror= True;
00572   }
00573   qh_setcheck (facet->vertices, "vertices for f", facet->id);
00574   qh_setcheck (facet->ridges, "ridges for f", facet->id);
00575   qh_setcheck (facet->outsideset, "outsideset for f", facet->id);
00576   qh_setcheck (facet->coplanarset, "coplanarset for f", facet->id);
00577   qh_setcheck (facet->neighbors, "neighbors for f", facet->id);
00578   FOREACHvertex_(facet->vertices) {
00579     if (vertex->deleted) {
00580       fprintf(qh ferr, "qhull internal error (qh_checkfacet): deleted vertex v%d in f%d\n", vertex->id, facet->id);
00581       qh_errprint ("ERRONEOUS", NULL, NULL, NULL, vertex);
00582       waserror= True;
00583     }
00584     if (vertex->id >= previousid) {
00585       fprintf(qh ferr, "qhull internal error (qh_checkfacet): vertices of f%d are not in descending id order at v%d\n", facet->id, vertex->id);
00586       waserror= True;
00587       break;
00588     }
00589     previousid= vertex->id;
00590   }
00591   numneighbors= qh_setsize(facet->neighbors);
00592   numvertices= qh_setsize(facet->vertices);
00593   numridges= qh_setsize(facet->ridges);
00594   if (facet->simplicial) {
00595     if (numvertices+numneighbors != 2*qh hull_dim 
00596     && !facet->degenerate && !facet->redundant) {
00597       fprintf(qh ferr, "qhull internal error (qh_checkfacet): for simplicial facet f%d, #vertices %d + #neighbors %d != 2*qh hull_dim\n", 
00598                 facet->id, numvertices, numneighbors);
00599       qh_setprint (qh ferr, "", facet->neighbors);
00600       waserror= True;
00601     }
00602   }else { /* non-simplicial */
00603     if (!newmerge 
00604     &&(numvertices < qh hull_dim || numneighbors < qh hull_dim)
00605     && !facet->degenerate && !facet->redundant) {
00606       fprintf(qh ferr, "qhull internal error (qh_checkfacet): for facet f%d, #vertices %d or #neighbors %d < qh hull_dim\n",
00607          facet->id, numvertices, numneighbors);
00608        waserror= True;
00609     }
00610     if (numridges < numneighbors
00611     ||(qh hull_dim == 3 && numvertices != numridges && !qh NEWfacets)
00612     ||(qh hull_dim == 2 && numridges + numvertices + numneighbors != 6)) {
00613       if (!facet->degenerate && !facet->redundant) {
00614         fprintf(qh ferr, "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",
00615             facet->id, numridges, numneighbors, numvertices);
00616         waserror= True;
00617       }
00618     }
00619   }
00620   FOREACHneighbor_(facet) {
00621     if (neighbor == qh_MERGEridge || neighbor == qh_DUPLICATEridge) {
00622       fprintf(qh ferr, "qhull internal error (qh_checkfacet): facet f%d still has a MERGE or DUP neighbor\n", facet->id);
00623       qh_errexit (qh_ERRqhull, facet, NULL);
00624     }
00625     neighbor->seen= True;
00626   }
00627   FOREACHneighbor_(facet) {
00628     if (!qh_setin(neighbor->neighbors, facet)) {
00629       fprintf(qh ferr, "qhull internal error (qh_checkfacet): facet f%d has neighbor f%d, but f%d does not have neighbor f%d\n",
00630               facet->id, neighbor->id, neighbor->id, facet->id);
00631       errother= neighbor;
00632       waserror= True;
00633     }
00634     if (!neighbor->seen) {
00635       fprintf(qh ferr, "qhull internal error (qh_checkfacet): facet f%d has a duplicate neighbor f%d\n",
00636               facet->id, neighbor->id);
00637       errother= neighbor;
00638       waserror= True;
00639     }    
00640     neighbor->seen= False;
00641   }
00642   FOREACHridge_(facet->ridges) {
00643     qh_setcheck (ridge->vertices, "vertices for r", ridge->id);
00644     ridge->seen= False;
00645   }
00646   FOREACHridge_(facet->ridges) {
00647     if (ridge->seen) {
00648       fprintf(qh ferr, "qhull internal error (qh_checkfacet): facet f%d has a duplicate ridge r%d\n",
00649               facet->id, ridge->id);
00650       errridge= ridge;
00651       waserror= True;
00652     }    
00653     ridge->seen= True;
00654     numRvertices= qh_setsize(ridge->vertices);
00655     if (numRvertices != qh hull_dim - 1) {
00656       fprintf(qh ferr, "qhull internal error (qh_checkfacet): ridge between f%d and f%d has %d vertices\n", 
00657                 ridge->top->id, ridge->bottom->id, numRvertices);
00658       errridge= ridge;
00659       waserror= True;
00660     }
00661     neighbor= otherfacet_(ridge, facet);
00662     neighbor->seen= True;
00663     if (!qh_setin(facet->neighbors, neighbor)) {
00664       fprintf(qh ferr, "qhull internal error (qh_checkfacet): for facet f%d, neighbor f%d of ridge r%d not in facet\n",
00665            facet->id, neighbor->id, ridge->id);
00666       errridge= ridge;
00667       waserror= True;
00668     }
00669   }
00670   if (!facet->simplicial) {
00671     FOREACHneighbor_(facet) {
00672       if (!neighbor->seen) {
00673         fprintf(qh ferr, "qhull internal error (qh_checkfacet): facet f%d does not have a ridge for neighbor f%d\n",
00674               facet->id, neighbor->id);
00675         errother= neighbor;
00676         waserror= True;
00677       }
00678       intersection= qh_vertexintersect_new(facet->vertices, neighbor->vertices);
00679       qh_settemppush (intersection);
00680       FOREACHvertex_(facet->vertices) {
00681         vertex->seen= False;
00682         vertex->seen2= False;
00683       }
00684       FOREACHvertex_(intersection)
00685         vertex->seen= True;
00686       FOREACHridge_(facet->ridges) {
00687         if (neighbor != otherfacet_(ridge, facet))
00688             continue;
00689         FOREACHvertex_(ridge->vertices) {
00690           if (!vertex->seen) {
00691             fprintf (qh ferr, "qhull internal error (qh_checkfacet): vertex v%d in r%d not in f%d intersect f%d\n",
00692                   vertex->id, ridge->id, facet->id, neighbor->id);
00693             qh_errexit (qh_ERRqhull, facet, ridge);
00694           }
00695           vertex->seen2= True;
00696         }
00697       }
00698       if (!newmerge) {
00699         FOREACHvertex_(intersection) {
00700           if (!vertex->seen2) {
00701             if (qh IStracing >=3 || !qh MERGING) {
00702               fprintf (qh ferr, "qhull precision error (qh_checkfacet): vertex v%d in f%d intersect f%d but\n\
00703  not in a ridge.  This is ok under merging.  Last point was p%d\n",
00704                      vertex->id, facet->id, neighbor->id, qh furthest_id);
00705               if (!qh FORCEoutput && !qh MERGING) {
00706                 qh_errprint ("ERRONEOUS", facet, neighbor, NULL, vertex);
00707                 if (!qh MERGING)
00708                   qh_errexit (qh_ERRqhull, NULL, NULL);
00709               }
00710             }
00711           }
00712         }
00713       }      
00714       qh_settempfree (&intersection);
00715     }
00716   }else { /* simplicial */
00717     FOREACHneighbor_(facet) {
00718       if (neighbor->simplicial) {    
00719         skipA= SETindex_(facet->neighbors, neighbor);
00720         skipB= qh_setindex (neighbor->neighbors, facet);
00721         if (!qh_setequal_skip (facet->vertices, skipA, neighbor->vertices, skipB)) {
00722           fprintf (qh ferr, "qhull internal error (qh_checkfacet): facet f%d skip %d and neighbor f%d skip %d do not match \n",
00723                    facet->id, skipA, neighbor->id, skipB);
00724           errother= neighbor;
00725           waserror= True;
00726         }
00727       }
00728     }
00729   }
00730   if (qh hull_dim < 5 && (qh IStracing > 2 || qh CHECKfrequently)) {
00731     FOREACHridge_i_(facet->ridges) {           /* expensive */
00732       for (i= ridge_i+1; i < ridge_n; i++) {
00733         ridge2= SETelemt_(facet->ridges, i, ridgeT);
00734         if (qh_setequal (ridge->vertices, ridge2->vertices)) {
00735           fprintf (qh ferr, "qh_checkfacet: ridges r%d and r%d have the same vertices\n",
00736                   ridge->id, ridge2->id);
00737           errridge= ridge;
00738           waserror= True;
00739         }
00740       }
00741     }
00742   }
00743   if (waserror) {
00744     qh_errprint("ERRONEOUS", facet, errother, errridge, NULL);
00745     *waserrorp= True;
00746   }
00747 } /* checkfacet */

00213                                                                     {
00214   realT dist;
00215 
00216   if (facet->flipped && !distp)
00217     return False;
00218   zzinc_(Zdistcheck);
00219   qh_distplane(qh interior_point, facet, &dist);
00220   if (distp)
00221     *distp= dist;
00222   if ((allerror && dist > -qh DISTround)|| (!allerror && dist >= 0.0)) {
00223     facet->flipped= True;
00224     zzinc_(Zflippedfacets);
00225     trace0((qh ferr, "qh_checkflipped: facet f%d is flipped, distance= %6.12g during p%d\n",
00226               facet->id, dist, qh furthest_id));
00227     qh_precision ("flipped facet");
00228     return False;
00229   }
00230   return True;
00231 } /* checkflipped */

00756                                              {
00757   facetT *facet;
00758   boolT waserror= False;
00759   realT dist;
00760 
00761   if (facetlist == qh facet_list)
00762     zzval_(Zflippedfacets)= 0;
00763   FORALLfacet_(facetlist) {
00764     if (facet->normal && !qh_checkflipped (facet, &dist, !qh_ALL)) {
00765       fprintf(qh ferr, "qhull precision error: facet f%d is flipped, distance= %6.12g\n",
00766               facet->id, dist);
00767       if (!qh FORCEoutput) {
00768         qh_errprint("ERRONEOUS", facet, NULL, NULL, NULL);
00769         waserror= True;
00770       }
00771     }
00772   }
00773   if (waserror) {
00774     fprintf (qh ferr, "\n\
00775 A flipped facet occurs when its distance to the interior point is\n\
00776 greater than %2.2g, the maximum roundoff error.\n", -qh DISTround);
00777     qh_errexit(qh_ERRprec, NULL, NULL);
00778   }
00779 } /* checkflipped_all */

00803                                         {
00804   facetT *facet;
00805   vertexT *vertex, **vertexp, *vertexlist;
00806   int numfacets= 0, numvertices= 0, numridges= 0;
00807   int totvneighbors= 0, totvertices= 0;
00808   boolT waserror= False, nextseen= False, visibleseen= False;
00809   
00810   trace1((qh ferr, "qh_checkpolygon: check all facets from f%d\n", facetlist->id));
00811   if (facetlist != qh facet_list || qh ONLYgood)
00812     nextseen= True;
00813   FORALLfacet_(facetlist) {
00814     if (facet == qh visible_list)
00815       visibleseen= True;
00816     if (!facet->visible) {
00817       if (!nextseen) {
00818         if (facet == qh facet_next)
00819           nextseen= True;
00820         else if (qh_setsize (facet->outsideset)
00821         && !(qh NARROWhull && qh CHECKfrequently)) {
00822           fprintf (qh ferr, "qhull internal error (qh_checkpolygon): f%d has outside set before qh facet_next\n",
00823                    facet->id);
00824           qh_errexit (qh_ERRqhull, facet, NULL);
00825         }
00826       }
00827       numfacets++;
00828       qh_checkfacet(facet, False, &waserror);
00829     }
00830   }
00831   if (qh visible_list && !visibleseen && facetlist == qh facet_list) {
00832     fprintf (qh ferr, "qhull internal error (qh_checkpolygon): visible list f%d no longer on facet list\n", qh visible_list->id);
00833     qh_printlists();
00834     qh_errexit (qh_ERRqhull, qh visible_list, NULL);
00835   }
00836   if (facetlist == qh facet_list)
00837     vertexlist= qh vertex_list;
00838   else if (facetlist == qh newfacet_list)
00839     vertexlist= qh newvertex_list;
00840   else
00841     vertexlist= NULL;
00842   FORALLvertex_(vertexlist) {
00843     vertex->seen= False;
00844     vertex->visitid= 0;
00845   }  
00846   FORALLfacet_(facetlist) {
00847     if (facet->visible)
00848       continue;
00849     if (facet->simplicial)
00850       numridges += qh hull_dim;
00851     else
00852       numridges += qh_setsize (facet->ridges);
00853     FOREACHvertex_(facet->vertices) {
00854       vertex->visitid++;
00855       if (!vertex->seen) {
00856         vertex->seen= True;
00857         numvertices++;
00858         if (qh_pointid (vertex->point) == -1) {
00859           fprintf (qh ferr, "qhull internal error (qh_checkpolygon): unknown point %p for vertex v%d first_point %p\n",
00860                    vertex->point, vertex->id, qh first_point);
00861           waserror= True;
00862         }
00863       }
00864     }
00865   }
00866   qh vertex_visit += numfacets;
00867   if (facetlist == qh facet_list) {
00868     if (numfacets != qh num_facets - qh num_visible) {
00869       fprintf(qh ferr, "qhull internal error (qh_checkpolygon): actual number of facets is %d, cumulative facet count is %d\n",
00870               numfacets, qh num_facets- qh num_visible);
00871       waserror= True;
00872     }
00873     qh vertex_visit++;
00874     if (qh VERTEXneighbors) {
00875       FORALLvertices {
00876         qh_setcheck (vertex->neighbors, "neighbors for v", vertex->id);
00877         if (vertex->deleted)
00878           continue;
00879         totvneighbors += qh_setsize (vertex->neighbors);
00880       }
00881       FORALLfacet_(facetlist)
00882         totvertices += qh_setsize (facet->vertices);
00883       if (totvneighbors != totvertices) {
00884         fprintf(qh ferr, "qhull internal error (qh_checkpolygon): vertex neighbors inconsistent.  Totvneighbors %d, totvertices %d\n",
00885                 totvneighbors, totvertices);
00886         waserror= True;
00887       }
00888     }
00889     if (numvertices != qh num_vertices - qh_setsize(qh del_vertices)) {
00890       fprintf(qh ferr, "qhull internal error (qh_checkpolygon): actual number of vertices is %d, cumulative vertex count is %d\n",
00891               numvertices, qh num_vertices - qh_setsize(qh del_vertices));
00892       waserror= True;
00893     }
00894     if (qh hull_dim == 2 && numvertices != numfacets) {
00895       fprintf (qh ferr, "qhull internal error (qh_checkpolygon): #vertices %d != #facets %d\n",
00896         numvertices, numfacets);
00897       waserror= True;
00898     }
00899     if (qh hull_dim == 3 && numvertices + numfacets - numridges/2 != 2) {
00900       fprintf (qh ferr, "qhull internal error (qh_checkpolygon): #vertices %d + #facets %d - #edges %d != 2\n",
00901         numvertices, numfacets, numridges/2);
00902       waserror= True;
00903     }
00904   }
00905   if (waserror) 
00906     qh_errexit(qh_ERRqhull, NULL, NULL);
00907 } /* checkpolygon */

00920                                       {
00921   boolT waserror= False;
00922   facetT *neighbor, **neighborp, *errfacet=NULL;
00923 
00924   if (qh_pointid (vertex->point) == -1) {
00925     fprintf (qh ferr, "qhull internal error (qh_checkvertex): unknown point id %p\n", vertex->point);
00926     waserror= True;
00927   }
00928   if (vertex->id >= qh vertex_id) {
00929     fprintf (qh ferr, "qhull internal error (qh_checkvertex): unknown vertex id %d\n", vertex->id);
00930     waserror= True;
00931   }
00932   if (!waserror && !vertex->deleted) {
00933     if (qh_setsize (vertex->neighbors)) {
00934       FOREACHneighbor_(vertex) {
00935         if (!qh_setin (neighbor->vertices, vertex)) {
00936           fprintf (qh ferr, "qhull internal error (qh_checkvertex): neighbor f%d does not contain v%d\n", neighbor->id, vertex->id);
00937           errfacet= neighbor;
00938           waserror= True;
00939         }
00940       }
00941     }
00942   }
00943   if (waserror) {
00944     qh_errprint ("ERRONEOUS", NULL, NULL, NULL, vertex);
00945     qh_errexit (qh_ERRqhull, errfacet, NULL);
00946   }
00947 } /* checkvertex */

00959                                       {
00960   facetT *facet;
00961   
00962   if (qh CENTERtype != type) {
00963     FORALLfacets {
00964       if (qh CENTERtype == qh_ASvoronoi){
00965         if (facet->center) {
00966           qh_memfree (facet->center, qh center_size);
00967           facet->center= NULL;
00968         }
00969       }else /* qh CENTERtype == qh_AScentrum */ {
00970         if (facet->center) {
00971           qh_memfree (facet->center, qh normal_size);
00972           facet->center= NULL;
00973         }
00974       }
00975     }
00976     qh CENTERtype= type;
00977   }
00978   trace2((qh ferr, "qh_clearcenters: switched to center type %d\n", type));
00979 } /* clearcenters */

00999                                       {
01000   facetT *facet= NULL, *newfacet;
01001   boolT toporient= True;
01002   int vertex_i, vertex_n, nth;
01003   setT *newfacets= qh_settemp (qh hull_dim+1);
01004   vertexT *vertex;
01005   
01006   qh facet_list= qh newfacet_list= qh facet_tail= qh_newfacet();
01007   qh num_facets= qh num_vertices= 0;
01008   qh vertex_list= qh newvertex_list= qh vertex_tail= qh_newvertex(NULL);
01009   FOREACHvertex_i_(vertices) {
01010     newfacet= qh_newfacet();
01011     newfacet->vertices= qh_setnew_delnthsorted (vertices, vertex_n,
01012                                                 vertex_i, 0);
01013     newfacet->toporient= toporient;
01014     qh_appendfacet(newfacet);
01015     newfacet->newfacet= True;
01016     qh_appendvertex (vertex);
01017     qh_setappend (&newfacets, newfacet);
01018     toporient ^= True;
01019   }
01020   FORALLnew_facets {
01021     nth= 0;
01022     FORALLfacet_(qh newfacet_list) {
01023       if (facet != newfacet) 
01024         SETelem_(newfacet->neighbors, nth++)= facet;
01025     }
01026     qh_settruncate (newfacet->neighbors, qh hull_dim);
01027   }
01028   qh_settempfree (&newfacets);
01029   trace1((qh ferr, "qh_createsimplex: created simplex\n"));
01030 } /* createsimplex */

00285                                                  {
00286   facetT *visible, *nextfacet;
00287   vertexT *vertex, **vertexp;
00288   int numvisible= 0, numdel= qh_setsize(qh del_vertices);
00289 
00290   trace1((qh ferr, "qh_deletevisible: delete %d visible facets and %d vertices\n",
00291          qh num_visible, numdel));
00292   for (visible= qh visible_list; visible && visible->visible; 
00293                 visible= nextfacet) { /* deleting current */
00294     nextfacet= visible->next;        
00295     numvisible++;
00296     qh_delfacet(visible);
00297   }
00298   if (numvisible != qh num_visible) {
00299     fprintf (qh ferr, "qhull internal error (qh_deletevisible): qh num_visible %d is not number of visible facets %d\n",
00300              qh num_visible, numvisible);
00301     qh_errexit (qh_ERRqhull, NULL, NULL);
00302   }
00303   qh num_visible= 0;
00304   zadd_(Zvisfacettot, numvisible);
00305   zmax_(Zvisfacetmax, numvisible);
00306   zadd_(Zdelvertextot, numdel);
00307   zmax_(Zdelvertexmax, numdel);
00308   FOREACHvertex_(qh del_vertices) 
00309     qh_delvertex (vertex);
00310   qh_settruncate (qh del_vertices, 0);
00311 } /* deletevisible */

00242                                 {
00243   void **freelistp; /* used !qh_NOmem */
00244 
00245   trace5((qh ferr, "qh_delfacet: delete f%d\n", facet->id));
00246   if (facet == qh tracefacet)
00247     qh tracefacet= NULL;
00248   if (facet == qh GOODclosest)
00249     qh GOODclosest= NULL;
00250   qh_removefacet(facet);
00251   qh_memfree_(facet->normal, qh normal_size, freelistp);
00252   if (qh CENTERtype == qh_ASvoronoi) {   /* uses macro calls */
00253     qh_memfree_(facet->center, qh center_size, freelistp);
00254   }else /* AScentrum */ {
00255     qh_memfree_(facet->center, qh normal_size, freelistp);
00256   }
00257   qh_setfree(&(facet->neighbors));
00258   if (facet->ridges)
00259     qh_setfree(&(facet->ridges));
00260   qh_setfree(&(facet->vertices));
00261   if (facet->outsideset)
00262     qh_setfree(&(facet->outsideset));
00263   if (facet->coplanarset)
00264     qh_setfree(&(facet->coplanarset));
00265   qh_memfree_(facet, sizeof(facetT), freelistp);
00266 } /* delfacet */

01043                                 {
01044   void **freelistp; /* used !qh_NOmem */
01045   
01046   qh_setdel(ridge->top->ridges, ridge);
01047   qh_setdel(ridge->bottom->ridges, ridge);
01048   qh_setfree(&(ridge->vertices));
01049   qh_memfree_(ridge, sizeof(ridgeT), freelistp);
01050 } /* delridge */

01063                                     {
01064 
01065   if (vertex == qh tracevertex)
01066     qh tracevertex= NULL;
01067   qh_removevertex (vertex);
01068   qh_setfree (&vertex->neighbors);
01069   qh_memfree(vertex, sizeof(vertexT));
01070 } /* delvertex */

01086                                       {
01087   ridgeT *ridge, *firstridge;
01088   vertexT *vertex;
01089   int cntvertices, cntprojected=0;
01090   setT *vertices;
01091 
01092   cntvertices= qh_setsize(facet->vertices);
01093   vertices= qh_settemp (cntvertices);
01094   if (facet->simplicial) {
01095     if (cntvertices != 3) {
01096       fprintf (qh ferr, "qhull internal error (qh_facet3vertex): only %d vertices for simplicial facet f%d\n", 
01097                   cntvertices, facet->id);
01098       qh_errexit(qh_ERRqhull, facet, NULL);
01099     }
01100     qh_setappend (&vertices, SETfirst_(facet->vertices));
01101     if (facet->toporient ^ qh_ORIENTclock)
01102       qh_setappend (&vertices, SETsecond_(facet->vertices));
01103     else
01104       qh_setaddnth (&vertices, 0, SETsecond_(facet->vertices));
01105     qh_setappend (&vertices, SETelem_(facet->vertices, 2));
01106   }else {
01107     ridge= firstridge= SETfirstt_(facet->ridges, ridgeT);   /* no infinite */
01108     while ((ridge= qh_nextridge3d (ridge, facet, &vertex))) {
01109       qh_setappend (&vertices, vertex);
01110       if (++cntprojected > cntvertices || ridge == firstridge)
01111         break;
01112     }
01113     if (!ridge || cntprojected != cntvertices) {
01114       fprintf (qh ferr, "qhull internal error (qh_facet3vertex): ridges for facet %d don't match up.  got at least %d\n", 
01115                   facet->id, cntprojected);
01116       qh_errexit(qh_ERRqhull, facet, ridge);
01117     }
01118   }
01119   return vertices;
01120 } /* facet3vertex */

00337                                                              {
00338   setT *intersect;
00339   int dim= qh hull_dim, i, j;
00340   facetT **neighborsA, **neighborsB;
00341 
00342   neighborsA= SETaddr_(facetA->neighbors, facetT);
00343   neighborsB= SETaddr_(facetB->neighbors, facetT);
00344   i= j= 0;
00345   if (facetB == *neighborsA++)
00346     *skipA= 0;
00347   else if (facetB == *neighborsA++)
00348     *skipA= 1;
00349   else if (facetB == *neighborsA++)
00350     *skipA= 2;
00351   else {
00352     for (i= 3; i < dim; i++) {
00353       if (facetB == *neighborsA++) {
00354         *skipA= i;
00355         break;
00356       }
00357     }
00358   }
00359   if (facetA == *neighborsB++)
00360     *skipB= 0;
00361   else if (facetA == *neighborsB++)
00362     *skipB= 1;
00363   else if (facetA == *neighborsB++)
00364     *skipB= 2;
00365   else {
00366     for (j= 3; j < dim; j++) {
00367       if (facetA == *neighborsB++) {
00368         *skipB= j;
00369         break;
00370       }
00371     }
00372   }
00373   if (i >= dim || j >= dim) {
00374     fprintf (qh ferr, "qhull internal error (qh_facetintersect): f%d or f%d not in others neighbors\n",
00375             facetA->id, facetB->id);
00376     qh_errexit2 (qh_ERRqhull, facetA, facetB);
00377   }
00378   intersect= qh_setnew_delnthsorted (facetA->vertices, qh hull_dim, *skipA, prepend);
00379   trace4((qh ferr, "qh_facetintersect: f%d skip %d matches f%d skip %d\n",
00380           facetA->id, *skipA, facetB->id, *skipB));
00381   return(intersect);
00382 } /* facetintersect */

01152                                               {
01153   facetT *bestfacet= NULL;
01154   int numpart, totpart= 0;
01155   
01156   bestfacet= qh_findbest (point, qh facet_list, 
01157                             bestoutside, False, bestoutside,
01158                             bestdist, isoutside, &totpart);
01159   if (!bestfacet) {
01160     fprintf (qh ferr, "qh_findbestfacet: all facets are flipped or upper Delaunay\n");
01161     qh_errexit (qh_ERRqhull, NULL, NULL);
01162   }
01163   if (*bestdist < -qh DISTround) {
01164     bestfacet= qh_findfacet_all (point, bestdist, isoutside, &numpart);
01165     totpart += numpart;
01166     if ((isoutside && bestoutside)
01167     || (!isoutside && bestfacet->upperdelaunay)) {
01168       bestfacet= qh_findbest (point, bestfacet, 
01169                             bestoutside, False, bestoutside,
01170                             bestdist, isoutside, &totpart);
01171       totpart += numpart;
01172     }
01173   }
01174   trace3((qh ferr, "qh_findbestfacet: f%d dist %2.2g isoutside %d totpart %d\n",
01175           bestfacet->id, *bestdist, *isoutside, totpart));
01176   return bestfacet;
01177 } /* findbestfacet */ 

01198                                         {
01199   facetT *bestfacet= NULL, *facet;
01200   realT dist;
01201   int totpart= 0;
01202   
01203   *bestdist= REALmin;
01204   *isoutside= False;
01205   FORALLfacets {
01206     if (facet->flipped || !facet->normal)
01207       continue;
01208     totpart++;
01209     qh_distplane (point, facet, &dist);
01210     if (dist > *bestdist) {
01211       *bestdist= dist;
01212       bestfacet= facet;
01213       if (dist > qh MINoutside) {
01214         *isoutside= True;
01215         break;
01216       }
01217     }
01218   }
01219   *numpart= totpart;
01220   trace3((qh ferr, "qh_findfacet_all: f%d dist %2.2g isoutside %d totpart %d\n",
01221           getid_(bestfacet), *bestdist, *isoutside, totpart));
01222   return bestfacet;
01223 } /* findfacet_all */ 

01257                                                      {
01258   facetT *facet, *bestfacet= NULL;
01259   realT angle, bestangle= REALmax, dist;
01260   int  numgood=0;
01261 
01262   FORALLfacet_(facetlist) {
01263     if (facet->good)
01264       numgood++;
01265   }
01266   if (qh GOODvertex>0 && !qh MERGING) {
01267     FORALLfacet_(facetlist) {
01268       if (!qh_isvertex (qh GOODvertexp, facet->vertices)) {
01269         facet->good= False;
01270         numgood--;
01271       }
01272     }
01273   }
01274   if (qh GOODpoint && numgood) {
01275     FORALLfacet_(facetlist) {
01276       if (facet->good && facet->normal) {
01277         zinc_(Zdistgood);
01278         qh_distplane (qh GOODpointp, facet, &dist);
01279         if ((qh GOODpoint > 0) ^ (dist > 0.0)) {
01280           facet->good= False;
01281           numgood--;
01282         }
01283       }
01284     }
01285   }
01286   if (qh GOODthreshold && (numgood || goodhorizon || qh GOODclosest)) {
01287     FORALLfacet_(facetlist) {
01288       if (facet->good && facet->normal) {
01289         if (!qh_inthresholds (facet->normal, &angle)) {
01290           facet->good= False;
01291           numgood--;
01292           if (angle < bestangle) {
01293             bestangle= angle;
01294             bestfacet= facet;
01295           }
01296         }
01297       }
01298     }
01299     if (!numgood && (!goodhorizon || qh GOODclosest)) {
01300       if (qh GOODclosest) {
01301         if (qh GOODclosest->visible)
01302           qh GOODclosest= NULL;
01303         else {
01304           qh_inthresholds (qh GOODclosest->normal, &angle);
01305           if (angle < bestangle)
01306             bestfacet= qh GOODclosest;
01307         }
01308       }
01309       if (bestfacet && bestfacet != qh GOODclosest) {
01310         if (qh GOODclosest)
01311           qh GOODclosest->good= False;
01312         qh GOODclosest= bestfacet;
01313         bestfacet->good= True;
01314         numgood++;
01315         trace2((qh ferr, "qh_findgood: f%d is closest (%2.2g) to thresholds\n", 
01316            bestfacet->id, bestangle));
01317         return numgood;
01318       }
01319     }else if (qh GOODclosest) { /* numgood > 0 */
01320       qh GOODclosest->good= False;
01321       qh GOODclosest= NULL;
01322     }
01323   }
01324   zadd_(Zgoodfacet, numgood);
01325   trace2((qh ferr, "qh_findgood: found %d good facets with %d good horizon\n",
01326                numgood, goodhorizon));
01327   if (!numgood && qh GOODvertex>0 && !qh MERGING) 
01328     return goodhorizon;
01329   return numgood;
01330 } /* findgood */

01357                                          {
01358   facetT *facet, *bestfacet=NULL;
01359   realT angle, bestangle= REALmax;
01360   int  numgood=0, startgood;
01361 
01362   if (!qh GOODvertex && !qh GOODthreshold && !qh GOODpoint 
01363   && !qh SPLITthresholds)
01364     return;
01365   if (!qh ONLYgood)
01366     qh_findgood (qh facet_list, 0);
01367   FORALLfacet_(facetlist) {
01368     if (facet->good)
01369       numgood++;
01370   }
01371   if (qh GOODvertex <0 || (qh GOODvertex > 0 && qh MERGING)) {
01372     FORALLfacet_(facetlist) {
01373       if (facet->good && ((qh GOODvertex > 0) ^ !!qh_isvertex (qh GOODvertexp, facet->vertices))) {
01374         if (!--numgood) {
01375           if (qh ONLYgood) {
01376             fprintf (qh ferr, "qhull warning: good vertex p%d does not match last good facet f%d.  Ignored.\n",
01377                qh_pointid(qh GOODvertexp), facet->id);
01378             return;
01379           }else if (qh GOODvertex > 0)
01380             fprintf (qh ferr, "qhull warning: point p%d is not a vertex ('QV%d').\n",
01381                 qh GOODvertex-1, qh GOODvertex-1);
01382           else
01383             fprintf (qh ferr, "qhull warning: point p%d is a vertex for every facet ('QV-%d').\n",
01384                 -qh GOODvertex - 1, -qh GOODvertex - 1);
01385         }
01386         facet->good= False;
01387       }
01388     }
01389   }
01390   startgood= numgood;
01391   if (qh SPLITthresholds) {
01392     FORALLfacet_(facetlist) {
01393       if (facet->good) {
01394         if (!qh_inthresholds (facet->normal, &angle)) {
01395           facet->good= False;
01396           numgood--;
01397           if (angle < bestangle) {
01398             bestangle= angle;
01399             bestfacet= facet;
01400           }
01401         }
01402       }
01403     }
01404     if (!numgood && bestfacet) {
01405       bestfacet->good= True;
01406       numgood++;
01407       trace0((qh ferr, "qh_findgood_all: f%d is closest (%2.2g) to thresholds\n", 
01408            bestfacet->id, bestangle));
01409       return;
01410     }
01411   }
01412   qh num_good= numgood;
01413   trace0((qh ferr, "qh_findgood_all: %d good facets remain out of %d facets\n",
01414         numgood, startgood));
01415 } /* findgood_all */

01427                                                 {
01428   facetT *facet, *bestfacet= NULL;
01429   realT dist, bestdist= -REALmax;
01430 
01431   FORALLfacets {
01432     if (facet->outsideset) {
01433 #if qh_COMPUTEfurthest
01434       pointT *furthest;
01435       furthest= (pointT*)qh_setlast (facet->outsideset);
01436       zinc_(Zcomputefurthest);
01437       qh_distplane (furthest, facet, &dist);
01438 #else
01439       dist= facet->furthestdist;
01440 #endif
01441       if (dist > bestdist) {
01442         bestfacet= facet;
01443         bestdist= dist;
01444       }
01445     }
01446   }
01447   if (bestfacet) {
01448     qh_removefacet (bestfacet);
01449     qh_prependfacet (bestfacet, &qh facet_next);
01450     trace1((qh ferr, "qh_furthestnext: made f%d next facet (dist %.2g)\n",
01451             bestfacet->id, bestdist));
01452   }
01453 } /* furthestnext */

01470                                     {
01471   pointT *point, **pointp, *bestpoint= NULL;
01472   realT dist, bestdist= -REALmax;
01473 
01474   FOREACHpoint_(facet->outsideset) {
01475     qh_distplane (point, facet, &dist);
01476     zinc_(Zcomputefurthest);
01477     if (dist > bestdist) {
01478       bestpoint= point;
01479       bestdist= dist;
01480     }
01481   }
01482   if (bestpoint) {
01483     qh_setdel (facet->outsideset, point);
01484     qh_setappend (&facet->outsideset, point);
01485 #if !qh_COMPUTEfurthest
01486     facet->furthestdist= bestdist;
01487 #endif
01488   }
01489   facet->notfurthest= False;
01490   trace3((qh ferr, "qh_furthestout: p%d is furthest outside point of f%d\n",
01491           qh_pointid (point), facet->id));
01492 } /* furthestout */

00397                                                                                         {
00398   void **elemp= SETelemaddr_(set, firstindex, void);
00399   ptr_intT hash = 0, elem;
00400   int i;
00401 
00402   switch (size-firstindex) {
00403   case 1:
00404     hash= (ptr_intT)(*elemp) - (ptr_intT) skipelem;
00405     break;
00406   case 2:
00407     hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] - (ptr_intT) skipelem;
00408     break;
00409   case 3:
00410     hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
00411       - (ptr_intT) skipelem;
00412     break;
00413   case 4:
00414     hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
00415       + (ptr_intT)elemp[3] - (ptr_intT) skipelem;
00416     break;
00417   case 5:
00418     hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
00419       + (ptr_intT)elemp[3] + (ptr_intT)elemp[4] - (ptr_intT) skipelem;
00420     break;
00421   case 6:
00422     hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
00423       + (ptr_intT)elemp[3] + (ptr_intT)elemp[4]+ (ptr_intT)elemp[5]
00424       - (ptr_intT) skipelem;
00425     break;
00426   default:
00427     hash= 0;
00428     i= 3;
00429     do {     /* this is about 10% in 10-d */
00430       if ((elem= (ptr_intT)*elemp++) != (ptr_intT)skipelem) {
00431         hash ^= (elem << i) + (elem >> (32-i));
00432         i += 3;
00433         if (i >= 32)
00434           i -= 32;
00435       }
00436     }while(*elemp);
00437     break;
00438   }
00439   hash %= (ptr_intT) hashsize;
00440   /* hash= 0; for debugging purposes */
00441   return hash;
00442 } /* gethash */

01501                                      {
01502 
01503   fprintf (qh ferr, "qhull internal error (qh_infiniteloop): potential infinite loop detected\n");
01504   qh_errexit (qh_ERRqhull, facet, NULL);
01505 } /* qh_infiniteloop */

01532                          {
01533   setT *maxpoints, *vertices;
01534   facetT *facet;
01535   int i, numpart;
01536   realT dist;
01537   boolT isoutside;
01538 
01539   qh furthest_id= -1;
01540   qh lastreport= 0;
01541   qh facet_id= qh vertex_id= qh ridge_id= 0;
01542   qh visit_id= qh vertex_visit= 0;
01543   qh maxoutdone= False;
01544 
01545   if (qh GOODpoint > 0) 
01546     qh GOODpointp= qh_point (qh GOODpoint-1);
01547   else if (qh GOODpoint < 0) 
01548     qh GOODpointp= qh_point (-qh GOODpoint-1);
01549   if (qh GOODvertex > 0)
01550     qh GOODvertexp= qh_point (qh GOODvertex-1);
01551   else if (qh GOODvertex < 0) 
01552     qh GOODvertexp= qh_point (-qh GOODvertex-1);
01553   if ((qh GOODpoint  
01554        && (qh GOODpointp < qh first_point  /* also catches !GOODpointp */
01555            || qh GOODpointp > qh_point (qh num_points-1)))
01556     || (qh GOODvertex
01557         && (qh GOODvertexp < qh first_point  /* also catches !GOODvertexp */
01558             || qh GOODvertexp > qh_point (qh num_points-1)))) {
01559     fprintf (qh ferr, "qhull input error: either QGn or QVn point is > p%d\n",
01560              qh num_points-1);
01561     qh_errexit (qh_ERRinput, NULL, NULL);
01562   }
01563   maxpoints= qh_maxmin(qh first_point, qh num_points, qh hull_dim);
01564   if (qh SCALElast)
01565     qh_scalelast (qh first_point, qh num_points, qh hull_dim,
01566                qh MINlastcoord, qh MAXlastcoord, qh MAXwidth);
01567   qh_detroundoff();
01568   if (qh DELAUNAY && qh upper_threshold[qh hull_dim-1] > REALmax/2
01569                   && qh lower_threshold[qh hull_dim-1] < -REALmax/2) {
01570     for (i= qh_PRINTEND; i--; ) {
01571       if (qh PRINTout[i] == qh_PRINTgeom && qh DROPdim < 0 
01572           && !qh GOODthreshold && !qh SPLITthresholds)
01573         break;  /* in this case, don't set upper_threshold */
01574     }
01575     if (i < 0) {
01576       if (qh UPPERdelaunay) { /* matches qh.upperdelaunay in qh_setfacetplane */
01577         qh lower_threshold[qh hull_dim-1]= qh ANGLEround * qh_ZEROdelaunay;
01578         qh GOODthreshold= True;
01579       }else { 
01580         qh upper_threshold[qh hull_dim-1]= -qh ANGLEround * qh_ZEROdelaunay;
01581         if (!qh GOODthreshold) 
01582           qh SPLITthresholds= True; /* build upper-convex hull even if Qg */
01583           /* qh_initqhull_globals errors if Qg without Pdk/etc. */
01584       }
01585     }
01586   }
01587   vertices= qh_initialvertices(qh hull_dim, maxpoints, qh first_point, qh num_points); 
01588   qh_initialhull (vertices);  /* initial qh facet_list */
01589   qh_partitionall (vertices, qh first_point, qh num_points);
01590   if (qh PRINToptions1st || qh TRACElevel || qh IStracing) {
01591     if (qh TRACElevel || qh IStracing)
01592       fprintf (qh ferr, "\nTrace level %d for %s | %s\n", 
01593          qh IStracing ? qh IStracing : qh TRACElevel, qh rbox_command, qh qhull_command);
01594     fprintf (qh ferr, "Options selected for Qhull %s:\n%s\n", qh_version, qh qhull_options);
01595   }
01596   qh_resetlists (False /*qh visible_list newvertex_list newfacet_list */);
01597   qh facet_next= qh facet_list;
01598   qh_furthestnext (/* qh facet_list */);
01599   if (qh PREmerge) {
01600     qh cos_max= qh premerge_cos;
01601     qh centrum_radius= qh premerge_centrum;
01602   }
01603   if (qh ONLYgood) {
01604     if (qh GOODvertex > 0 && qh MERGING) {
01605       fprintf (qh ferr, "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");
01606       qh_errexit (qh_ERRinput, NULL, NULL);
01607     }
01608     if (!(qh GOODthreshold || qh GOODpoint
01609          || (!qh MERGEexact && !qh PREmerge && qh GOODvertexp))) {
01610       fprintf (qh ferr, "qhull input error: 'Qg' (ONLYgood) needs a good threshold ('Pd0D0'), a\n\
01611 good point (QGn or QG-n), or a good vertex with 'QJ' or 'Q0' (QVn).\n");
01612       qh_errexit (qh_ERRinput, NULL, NULL);
01613     }
01614     if (qh GOODvertex > 0  && !qh MERGING  /* matches qh_partitionall */
01615         && !qh_isvertex (qh GOODvertexp, vertices)) {
01616       facet= qh_findbestnew (qh GOODvertexp, qh facet_list, 
01617                           &dist, &isoutside, &numpart);
01618       zadd_(Zdistgood, numpart);
01619       if (!isoutside) {
01620         fprintf (qh ferr, "qhull input error: point for QV%d is inside initial simplex.  It can not be made a vertex.\n",
01621                qh_pointid(qh GOODvertexp));
01622         qh_errexit (qh_ERRinput, NULL, NULL);
01623       }
01624       if (!qh_addpoint (qh GOODvertexp, facet, False)) {
01625         qh_settempfree(&vertices);
01626         qh_settempfree(&maxpoints);
01627         return;
01628       }
01629     }
01630     qh_findgood (qh facet_list, 0);
01631   }
01632   qh_settempfree(&vertices);
01633   qh_settempfree(&maxpoints);
01634   trace1((qh ferr, "qh_initbuild: initial hull created and points partitioned\n"));
01635 } /* initbuild */

01651                                     {
01652   facetT *facet, *firstfacet, *neighbor, **neighborp;
01653   realT dist, angle, minangle= REALmax;
01654 #ifndef qh_NOtrace
01655   int k;
01656 #endif
01657 
01658   qh_createsimplex(vertices);  /* qh facet_list */
01659   qh_resetlists (False);
01660   qh facet_next= qh facet_list;      /* advance facet when processed */
01661   qh interior_point= qh_getcenter(vertices);
01662   firstfacet= qh facet_list;
01663   qh_setfacetplane(firstfacet);
01664   zinc_(Znumvisibility); /* needs to be in printsummary */
01665   qh_distplane(qh interior_point, firstfacet, &dist);
01666   if (dist > 0) {  
01667     FORALLfacets
01668       facet->toporient ^= True;
01669   }
01670   FORALLfacets
01671     qh_setfacetplane(facet);
01672   FORALLfacets {
01673     if (!qh_checkflipped (facet, NULL, qh_ALL)) {/* due to axis-parallel facet */
01674       trace1((qh ferr, "qh_initialhull: initial orientation incorrect.  Correct all facets\n"));
01675       facet->flipped= False;
01676       FORALLfacets {
01677         facet->toporient ^= True;
01678         qh_orientoutside (facet);
01679       }
01680       break;
01681     }
01682   }
01683   FORALLfacets {
01684     if (!qh_checkflipped (facet, NULL, !qh_ALL)) {  /* can happen with 'R0.1' */
01685       qh_precision ("initial facet is coplanar with interior point");
01686       fprintf (qh ferr, "qhull precision error: initial facet %d is coplanar with the interior point\n",
01687                    facet->id);
01688       qh_errexit (qh_ERRsingular, facet, NULL);
01689     }
01690     FOREACHneighbor_(facet) {
01691       angle= qh_getangle (facet->normal, neighbor->normal);
01692       minimize_( minangle, angle);
01693     }
01694   }
01695   if (minangle < qh_MAXnarrow) {
01696     realT diff= 1.0 + minangle;
01697 
01698     qh NARROWhull= True;
01699     qh_option ("_narrow-hull", NULL, &diff);
01700     if (minangle < qh_WARNnarrow && !qh RERUN && qh PRINTprecision)
01701       fprintf (qh ferr, "qhull precision warning: \n\
01702 The initial hull is narrow (the cosine of the minimum angle is %.9g).\n\
01703 A coplanar point may lead to a wide facet.  Options 'Qs' (search for best\n\
01704 initial hull), 'QbB' (scale to unit box), or 'Qbb' (scale last coordinate)\n\
01705 may remove this warning.  Use 'Pp' to ignore this warning.\n\
01706 See 'Limitations' in qh-impre.htm.\n",
01707           -minangle);   /* convert from angle between normals to angle between facets */
01708   }
01709   zzval_(Zprocessed)= qh hull_dim+1;
01710   qh_checkpolygon (qh facet_list);
01711   qh_checkconvex(qh facet_list,   qh_DATAfault);
01712 #ifndef qh_NOtrace
01713   if (qh IStracing >= 1) {
01714     fprintf(qh ferr, "qh_initialhull: simplex constructed, interior point:");
01715     for (k=0; k < qh hull_dim; k++) 
01716       fprintf (qh ferr, " %6.4g", qh interior_point[k]);
01717     fprintf (qh ferr, "\n");
01718   }
01719 #endif
01720 } /* initialhull */

01740                                                                                   {
01741   pointT *point, **pointp;
01742   setT *vertices, *simplex, *tested;
01743   realT randr;
01744   int index, point_i, point_n, k;
01745   boolT nearzero= False;
01746   
01747   vertices= qh_settemp (dim + 1);
01748   simplex= qh_settemp (dim+1);
01749   if (qh ALLpoints) 
01750     qh_maxsimplex (dim, NULL, points, numpoints, &simplex);
01751   else if (qh RANDOMoutside) {
01752     while (qh_setsize (simplex) != dim+1) {
01753       randr= qh_RANDOMint;
01754       randr= randr/(qh_RANDOMmax+1);
01755       index= (int)floor(qh num_points * randr);
01756       while (qh_setin (simplex, qh_point (index))) {
01757         index++; /* in case qh_RANDOMint always returns the same value */
01758         index= index < qh num_points ? index : 0;
01759       }
01760       qh_setappend (&simplex, qh_point (index));
01761     }
01762   }else if (qh hull_dim >= qh_INITIALmax) {
01763     tested= qh_settemp (dim+1);
01764     qh_setappend (&simplex, SETfirst_(maxpoints));   /* max and min X coord */
01765     qh_setappend (&simplex, SETsecond_(maxpoints));
01766     qh_maxsimplex (fmin_(qh_INITIALsearch, dim), maxpoints, points, numpoints, &simplex);
01767     k= qh_setsize (simplex);
01768     FOREACHpoint_i_(maxpoints) { 
01769       if (point_i & 0x1) {     /* first pick up max. coord. points */
01770         if (!qh_setin (simplex, point) && !qh_setin (tested, point)){
01771           qh_detsimplex(point, simplex, k, &nearzero);
01772           if (nearzero)
01773             qh_setappend (&tested, point);
01774           else {
01775             qh_setappend (&simplex, point);
01776             if (++k == dim)  /* use search for last point */
01777               break;
01778           }
01779         }
01780       }
01781     }
01782     while (k != dim && (point= (pointT*)qh_setdellast (maxpoints))) {
01783       if (!qh_setin (simplex, point) && !qh_setin (tested, point)){
01784         qh_detsimplex (point, simplex, k, &nearzero);
01785         if (nearzero)
01786           qh_setappend (&tested, point);
01787         else {
01788           qh_setappend (&simplex, point);
01789           k++;
01790         }
01791       }
01792     }
01793     index= 0;
01794     while (k != dim && (point= qh_point (index++))) {
01795       if (!qh_setin (simplex, point) && !qh_setin (tested, point)){
01796         qh_detsimplex (point, simplex, k, &nearzero);
01797         if (!nearzero){
01798           qh_setappend (&simplex, point);
01799           k++;
01800         }
01801       }
01802     }
01803     qh_settempfree (&tested);
01804     qh_maxsimplex (dim, maxpoints, points, numpoints, &simplex);
01805   }else
01806     qh_maxsimplex (dim, maxpoints, points, numpoints, &simplex);
01807   FOREACHpoint_(simplex) 
01808     qh_setaddnth (&vertices, 0, qh_newvertex(point)); /* descending order */
01809   qh_settempfree (&simplex);
01810   return vertices;
01811 } /* initialvertices */

01823                                                      {
01824   vertexT *vertex, **vertexp;
01825 
01826   FOREACHvertex_(vertices) {
01827     if (vertex->point == point)
01828       return vertex;
01829   }
01830   return NULL;
01831 } /* isvertex */

00539                                                                                {
00540   void **freelistp; /* used !qh_NOmem */
00541   ridgeT *ridge, **ridgep;
00542   facetT *neighbor, *newfacet= NULL, *samecycle;
00543   setT *vertices;
00544   boolT toporient;
00545   int ridgeid;
00546 
00547   FOREACHridge_(visible->ridges) {
00548     ridgeid= ridge->id;
00549     neighbor= otherfacet_(ridge, visible);
00550     if (neighbor->visible) {
00551       if (!qh ONLYgood) {
00552         if (neighbor->visitid == qh visit_id) {
00553           qh_setfree (&(ridge->vertices));  /* delete on 2nd visit */
00554           qh_memfree_(ridge, sizeof(ridgeT), freelistp);
00555         }
00556       }
00557     }else {  /* neighbor is an horizon facet */
00558       toporient= (ridge->top == visible);
00559       vertices= qh_setnew (qh hull_dim); /* makes sure this is quick */
00560       qh_setappend (&vertices, apex);
00561       qh_setappend_set (&vertices, ridge->vertices);
00562       newfacet= qh_makenewfacet(vertices, toporient, neighbor);
00563       (*numnew)++;
00564       if (neighbor->coplanar) {
00565         newfacet->mergehorizon= True;
00566         if (!neighbor->seen) {
00567           newfacet->f.samecycle= newfacet;
00568           neighbor->f.newcycle= newfacet;
00569         }else {
00570           samecycle= neighbor->f.newcycle;
00571           newfacet->f.samecycle= samecycle->f.samecycle;
00572           samecycle->f.samecycle= newfacet;
00573         }
00574       }
00575       if (qh ONLYgood) {
00576         if (!neighbor->simplicial)
00577           qh_setappend(&(newfacet->ridges), ridge);
00578       }else {  /* qh_attachnewfacets */
00579         if (neighbor->seen) {
00580           if (neighbor->simplicial) {
00581             fprintf (qh ferr, "qhull internal error (qh_makenew_nonsimplicial): simplicial f%d sharing two ridges with f%d\n", 
00582                    neighbor->id, visible->id);
00583             qh_errexit2 (qh_ERRqhull, neighbor, visible);
00584           }
00585           qh_setappend (&(neighbor->neighbors), newfacet);
00586         }else
00587           qh_setreplace (neighbor->neighbors, visible, newfacet);
00588         if (neighbor->simplicial) {
00589           qh_setdel (neighbor->ridges, ridge);
00590           qh_setfree (&(ridge->vertices)); 
00591           qh_memfree (ridge, sizeof(ridgeT));
00592         }else {
00593           qh_setappend(&(newfacet->ridges), ridge);
00594           if (toporient)
00595             ridge->top= newfacet;
00596           else
00597             ridge->bottom= newfacet;
00598         }
00599       trace4((qh ferr, "qh_makenew_nonsimplicial: created facet f%d from v%d and r%d of horizon f%d\n",
00600             newfacet->id, apex->id, ridgeid, neighbor->id));
00601       }
00602     }
00603     neighbor->seen= True;        
00604   } /* for each ridge */
00605   if (!qh ONLYgood)
00606     SETfirst_(visible->ridges)= NULL;
00607   return newfacet;
00608 } /* makenew_nonsimplicial */

00636                                                                             {
00637   facetT *neighbor, **neighborp, *newfacet= NULL;
00638   setT *vertices;
00639   boolT flip, toporient;
00640   int horizonskip, visibleskip;
00641 
00642   FOREACHneighbor_(visible) {
00643     if (!neighbor->seen && !neighbor->visible) {
00644       vertices= qh_facetintersect(neighbor,visible, &horizonskip, &visibleskip, 1);
00645       SETfirst_(vertices)= apex;
00646       flip= ((horizonskip & 0x1) ^ (visibleskip & 0x1));
00647       if (neighbor->toporient)         
00648         toporient= horizonskip & 0x1;
00649       else
00650         toporient= (horizonskip & 0x1) ^ 0x1;
00651       newfacet= qh_makenewfacet(vertices, toporient, neighbor);
00652       (*numnew)++;
00653       if (neighbor->coplanar && (qh PREmerge || qh MERGEexact)) {
00654 #ifndef qh_NOmerge
00655         newfacet->f.samecycle= newfacet;
00656         newfacet->mergehorizon= True;
00657 #endif
00658       }
00659       if (!qh ONLYgood)
00660         SETelem_(neighbor->neighbors, horizonskip)= newfacet;
00661       trace4((qh ferr, "qh_makenew_simplicial: create facet f%d top %d from v%d and horizon f%d skip %d top %d and visible f%d skip %d, flip? %d\n",
00662             newfacet->id, toporient, apex->id, neighbor->id, horizonskip,
00663               neighbor->toporient, visible->id, visibleskip, flip));
00664     }
00665   }
00666   return newfacet;
00667 } /* makenew_simplicial */

00457                                                                          {
00458   facetT *newfacet;
00459   vertexT *vertex, **vertexp;
00460 
00461   FOREACHvertex_(vertices) {
00462     if (!vertex->newlist) {
00463       qh_removevertex (vertex);
00464       qh_appendvertex (vertex);
00465     }
00466   }
00467   newfacet= qh_newfacet();
00468   newfacet->vertices= vertices;
00469   newfacet->toporient= toporient;
00470   qh_setappend(&(newfacet->neighbors), horizon);
00471   qh_appendfacet(newfacet);
00472   return(newfacet);
00473 } /* makenewfacet */

01859                                                            {
01860   facetT *visible, *newfacet= NULL, *newfacet2= NULL, *neighbor, **neighborp;
01861   vertexT *apex;
01862   int numnew=0;
01863 
01864   qh newfacet_list= qh facet_tail;
01865   qh newvertex_list= qh vertex_tail;
01866   apex= qh_newvertex(point);
01867   qh_appendvertex (apex);  
01868   qh visit_id++;
01869   if (!qh ONLYgood)
01870     qh NEWfacets= True;
01871   FORALLvisible_facets {
01872     FOREACHneighbor_(visible) 
01873       neighbor->seen= False;
01874     if (visible->ridges) {
01875       visible->visitid= qh visit_id;
01876       newfacet2= qh_makenew_nonsimplicial (visible, apex, &numnew);
01877     }
01878     if (visible->simplicial)
01879       newfacet= qh_makenew_simplicial (visible, apex, &numnew);
01880     if (!qh ONLYgood) {
01881       if (newfacet2)  /* newfacet is null if all ridges defined */
01882         newfacet= newfacet2;
01883       if (newfacet)
01884         visible->f.replace= newfacet;
01885       else
01886         zinc_(Zinsidevisible);
01887       SETfirst_(visible->neighbors)= NULL;
01888     }
01889   }
01890   trace1((qh ferr, "qh_makenewfacets: created %d new facets from point p%d to horizon\n",
01891           numnew, qh_pointid(point)));
01892   if (qh IStracing >= 4)
01893     qh_printfacetlist (qh newfacet_list, NULL, qh_ALL);
01894   return apex;
01895 } /* makenewfacets */

00490                                                  {
00491   facetT *newfacet;
00492 
00493   FORALLnew_facets {
00494     if (!newfacet->mergehorizon)
00495       qh_setfacetplane (newfacet);  
00496   }
00497   if (qh JOGGLEmax < REALmax/2)  
00498     minimize_(qh min_vertex, -wwval_(Wnewvertexmax));
00499 } /* makenewplanes */

01923                                                                                     {
01924   boolT same, ismatch;
01925   int hash, scan;
01926   facetT *facet, *newfacet, *maxmatch= NULL, *maxmatch2= NULL, *nextfacet;
01927   int skip, newskip, nextskip= 0, maxskip= 0, maxskip2= 0, makematch;
01928   realT maxdist= -REALmax, mindist, dist2, low, high;
01929 
01930   hash= (int)qh_gethash (hashsize, atfacet->vertices, qh hull_dim, 1, 
01931                      SETelem_(atfacet->vertices, atskip));
01932   trace2((qh ferr, "qh_matchduplicates: find duplicate matches for f%d skip %d hash %d hashcount %d\n",
01933           atfacet->id, atskip, hash, *hashcount));
01934   for (makematch= 0; makematch < 2; makematch++) {
01935     qh visit_id++;
01936     for (newfacet= atfacet, newskip= atskip; newfacet; newfacet= nextfacet, newskip= nextskip) {
01937       zinc_(Zhashlookup);
01938       nextfacet= NULL;
01939       newfacet->visitid= qh visit_id;
01940       for (scan= hash; (facet= SETelemt_(qh hash_table, scan, facetT)); 
01941            scan= (++scan >= hashsize ? 0 : scan)) {
01942         if (!facet->dupridge || facet->visitid == qh visit_id)
01943           continue;
01944         zinc_(Zhashtests);
01945         if (qh_matchvertices (1, newfacet->vertices, newskip, facet->vertices, &skip, &same)) {
01946           ismatch= (same == (newfacet->toporient ^ facet->toporient));
01947           if (SETelemt_(facet->neighbors, skip, facetT) != qh_DUPLICATEridge) {
01948             if (!makematch) {
01949               fprintf (qh ferr, "qhull internal error (qh_matchduplicates): missing dupridge at f%d skip %d for new f%d skip %d hash %d\n",
01950                      facet->id, skip, newfacet->id, newskip, hash);
01951               qh_errexit2 (qh_ERRqhull, facet, newfacet);
01952             }
01953           }else if (ismatch && makematch) {
01954             if (SETelemt_(newfacet->neighbors, newskip, facetT) == qh_DUPLICATEridge) {
01955               SETelem_(facet->neighbors, skip)= newfacet;
01956               SETelem_(newfacet->neighbors, newskip)= qh_MERGEridge;
01957               *hashcount -= 2; /* removed two unmatched facets */
01958               trace4((qh ferr, "qh_matchduplicates: duplicate f%d skip %d matched with new f%d skip %d merge\n",
01959                     facet->id, skip, newfacet->id, newskip));
01960             }
01961           }else if (ismatch) {
01962             mindist= qh_getdistance (facet, newfacet, &low, &high);
01963             dist2= qh_getdistance (newfacet, facet, &low, &high);
01964             minimize_(mindist, dist2);
01965             if (mindist > maxdist) {
01966               maxdist= mindist;
01967               maxmatch= facet;
01968               maxskip= skip;
01969               maxmatch2= newfacet;
01970               maxskip2= newskip;
01971             }
01972             trace3((qh ferr, "qh_matchduplicates: duplicate f%d skip %d new f%d skip %d at dist %2.2g, max is now f%d f%d\n",
01973                     facet->id, skip, newfacet->id, newskip, mindist, 
01974                     maxmatch->id, maxmatch2->id));
01975           }else { /* !ismatch */
01976             nextfacet= facet;
01977             nextskip= skip;
01978           }
01979         }
01980         if (makematch && !facet 
01981         && SETelemt_(facet->neighbors, skip, facetT) == qh_DUPLICATEridge) {
01982           fprintf (qh ferr, "qhull internal error (qh_matchduplicates): no MERGEridge match for duplicate f%d skip %d at hash %d\n",
01983                      newfacet->id, newskip, hash);
01984           qh_errexit (qh_ERRqhull, newfacet, NULL);
01985         }
01986       }
01987     } /* end of for each new facet at hash */
01988     if (!makematch) {
01989       if (!maxmatch) {
01990         fprintf (qh ferr, "qhull internal error (qh_matchduplicates): no maximum match at duplicate f%d skip %d at hash %d\n",
01991                      atfacet->id, atskip, hash);
01992         qh_errexit (qh_ERRqhull, atfacet, NULL);
01993       }
01994       SETelem_(maxmatch->neighbors, maxskip)= maxmatch2;
01995       SETelem_(maxmatch2->neighbors, maxskip2)= maxmatch;
01996       *hashcount -= 2; /* removed two unmatched facets */
01997       zzinc_(Zmultiridge);
01998       trace0((qh ferr, "qh_matchduplicates: duplicate f%d skip %d matched with new f%d skip %d keep\n",
01999               maxmatch->id, maxskip, maxmatch2->id, maxskip2));
02000       qh_precision ("ridge with multiple neighbors");
02001       if (qh IStracing >= 4)
02002         qh_errprint ("DUPLICATED/MATCH", maxmatch, maxmatch2, NULL, NULL);
02003     }
02004   }
02005 } /* matchduplicates */

00700                                                                                     {
00701   boolT newfound= False;   /* True, if new facet is already in hash chain */
00702   boolT same, ismatch;
00703   int hash, scan;
00704   facetT *facet, *matchfacet;
00705   int skip, matchskip;
00706 
00707   hash= (int)qh_gethash (hashsize, newfacet->vertices, qh hull_dim, 1, 
00708                      SETelem_(newfacet->vertices, newskip));
00709   trace4((qh ferr, "qh_matchneighbor: newfacet f%d skip %d hash %d hashcount %d\n",
00710           newfacet->id, newskip, hash, *hashcount));
00711   zinc_(Zhashlookup);
00712   for (scan= hash; (facet= SETelemt_(qh hash_table, scan, facetT)); 
00713        scan= (++scan >= hashsize ? 0 : scan)) {
00714     if (facet == newfacet) {
00715       newfound= True;
00716       continue;
00717     }
00718     zinc_(Zhashtests);
00719     if (qh_matchvertices (1, newfacet->vertices, newskip, facet->vertices, &skip, &same)) {
00720       if (SETelem_(newfacet->vertices, newskip) == 
00721           SETelem_(facet->vertices, skip)) {
00722         qh_precision ("two facets with the same vertices");
00723         fprintf (qh ferr, "qhull precision error: Vertex sets are the same for f%d and f%d.  Can not force output.\n",
00724           facet->id, newfacet->id);
00725         qh_errexit2 (qh_ERRprec, facet, newfacet);
00726       }
00727       ismatch= (same == (newfacet->toporient ^ facet->toporient));
00728       matchfacet= SETelemt_(facet->neighbors, skip, facetT);
00729       if (ismatch && !matchfacet) {
00730         SETelem_(facet->neighbors, skip)= newfacet;
00731         SETelem_(newfacet->neighbors, newskip)= facet;
00732         (*hashcount)--;
00733         trace4((qh ferr, "qh_matchneighbor: f%d skip %d matched with new f%d skip %d\n",
00734            facet->id, skip, newfacet->id, newskip));
00735         return;
00736       }
00737       if (!qh PREmerge && !qh MERGEexact) {
00738         qh_precision ("a ridge with more than two neighbors");
00739         fprintf (qh ferr, "qhull precision error: facets f%d, f%d and f%d meet at a ridge with more than 2 neighbors.  Can not continue.\n",
00740                  facet->id, newfacet->id, getid_(matchfacet));
00741         qh_errexit2 (qh_ERRprec, facet, newfacet);
00742       }
00743       SETelem_(newfacet->neighbors, newskip)= qh_DUPLICATEridge;
00744       newfacet->dupridge= True;
00745       if (!newfacet->normal)
00746         qh_setfacetplane (newfacet);
00747       qh_addhash (newfacet, qh hash_table, hashsize, hash);
00748       (*hashcount)++;
00749       if (!facet->normal)
00750         qh_setfacetplane (facet);
00751       if (matchfacet != qh_DUPLICATEridge) {
00752         SETelem_(facet->neighbors, skip)= qh_DUPLICATEridge;
00753         facet->dupridge= True;
00754         if (!facet->normal)
00755           qh_setfacetplane (facet);
00756         if (matchfacet) {
00757           matchskip= qh_setindex (matchfacet->neighbors, facet);
00758           SETelem_(matchfacet->neighbors, matchskip)= qh_DUPLICATEridge;
00759           matchfacet->dupridge= True;
00760           if (!matchfacet->normal)
00761             qh_setfacetplane (matchfacet);
00762           qh_addhash (matchfacet, qh hash_table, hashsize, hash);
00763           *hashcount += 2;
00764         }
00765       }
00766       trace4((qh ferr, "qh_matchneighbor: new f%d skip %d duplicates ridge for f%d skip %d matching f%d ismatch %d at hash %d\n",
00767            newfacet->id, newskip, facet->id, skip, 
00768            (matchfacet == qh_DUPLICATEridge ? -2 : getid_(matchfacet)), 
00769            ismatch, hash));
00770       return; /* end of duplicate ridge */
00771     }
00772   }
00773   if (!newfound) 
00774     SETelem_(qh hash_table, scan)= newfacet;  /* same as qh_addhash */
00775   (*hashcount)++;
00776   trace4((qh ferr, "qh_matchneighbor: no match for f%d skip %d at hash %d\n",
00777            newfacet->id, newskip, hash));
00778 } /* matchneighbor */

00812                               {
00813   int numnew=0, hashcount=0, newskip;
00814   facetT *newfacet, *neighbor;
00815   int dim= qh hull_dim, hashsize, neighbor_i, neighbor_n;
00816   setT *neighbors;
00817 #ifndef qh_NOtrace
00818   int facet_i, facet_n, numfree= 0;
00819   facetT *facet;
00820 #endif
00821   
00822   trace1((qh ferr, "qh_matchnewfacets: match neighbors for new facets.\n"));
00823   FORALLnew_facets {
00824     numnew++;
00825     {  /* inline qh_setzero (newfacet->neighbors, 1, qh hull_dim); */
00826       neighbors= newfacet->neighbors;
00827       neighbors->e[neighbors->maxsize].i= dim+1; /*may be overwritten*/
00828       memset ((char *)SETelemaddr_(neighbors, 1, void), 0, dim * SETelemsize);
00829     }    
00830   }
00831   qh_newhashtable (numnew*(qh hull_dim-1)); /* twice what is normally needed,
00832                                      but every ridge could be DUPLICATEridge */
00833   hashsize= qh_setsize (qh hash_table);
00834   FORALLnew_facets {
00835     for (newskip=1; newskip<qh hull_dim; newskip++) /* furthest/horizon already matched */
00836       qh_matchneighbor (newfacet, newskip, hashsize, &hashcount);
00837 #if 0   /* use the following to trap hashcount errors */
00838     {
00839       int count= 0, k;
00840       facetT *facet, *neighbor;
00841 
00842       count= 0;
00843       FORALLfacet_(qh newfacet_list) {  /* newfacet already in use */
00844         for (k=1; k < qh hull_dim; k++) {
00845           neighbor= SETelemt_(facet->neighbors, k, facetT);
00846           if (!neighbor || neighbor == qh_DUPLICATEridge)
00847             count++;
00848         }
00849         if (facet == newfacet)
00850           break;
00851       }
00852       if (count != hashcount) {
00853         fprintf (qh ferr, "qh_matchnewfacets: after adding facet %d, hashcount %d != count %d\n",
00854                  newfacet->id, hashcount, count);
00855         qh_errexit (qh_ERRqhull, newfacet, NULL);
00856       }
00857     }
00858 #endif  /* end of trap code */
00859   }
00860   if (hashcount) {
00861     FORALLnew_facets {
00862       if (newfacet->dupridge) {
00863         FOREACHneighbor_i_(newfacet) {
00864           if (neighbor == qh_DUPLICATEridge) {
00865             qh_matchduplicates (newfacet, neighbor_i, hashsize, &hashcount);
00866                     /* this may report MERGEfacet */
00867           }
00868         }
00869       }
00870     }
00871   }
00872   if (hashcount) {
00873     fprintf (qh ferr, "qhull internal error (qh_matchnewfacets): %d neighbors did not match up\n",
00874         hashcount);
00875     qh_printhashtable (qh ferr);
00876     qh_errexit (qh_ERRqhull, NULL, NULL);
00877   }
00878 #ifndef qh_NOtrace
00879   if (qh IStracing >= 2) {
00880     FOREACHfacet_i_(qh hash_table) {
00881       if (!facet)
00882         numfree++;
00883     }
00884     fprintf (qh ferr, "qh_matchnewfacets: %d new facets, %d unused hash entries .  hashsize %d\n",
00885              numnew, numfree, qh_setsize (qh hash_table));
00886   }
00887 #endif /* !qh_NOtrace */
00888   qh_setfree (&qh hash_table);
00889   if (qh PREmerge || qh MERGEexact) {
00890     if (qh IStracing >= 4)
00891       qh_printfacetlist (qh newfacet_list, NULL, qh_ALL);
00892     FORALLnew_facets {
00893       if (newfacet->normal)
00894         qh_checkflipped (newfacet, NULL, qh_ALL);
00895     }
00896   }else if (qh FORCEoutput)
00897     qh_checkflipped_all (qh newfacet_list);  /* prints warnings for flipped */
00898 } /* matchnewfacets */

00922                                                  {
00923   vertexT **elemAp, **elemBp, **skipBp=NULL, **skipAp;
00924 
00925   elemAp= SETelemaddr_(verticesA, firstindex, vertexT);
00926   elemBp= SETelemaddr_(verticesB, firstindex, vertexT);
00927   skipAp= SETelemaddr_(verticesA, skipA, vertexT);
00928   do if (elemAp != skipAp) {
00929     while (*elemAp != *elemBp++) {
00930       if (skipBp)
00931         return False;
00932       skipBp= elemBp;  /* one extra like FOREACH */
00933     }
00934   }while(*(++elemAp));
00935   if (!skipBp)
00936     skipBp= ++elemBp;
00937   *skipB= SETindex_(verticesB, skipB);
00938   *same= !(((ptr_intT)skipA & 0x1) ^ ((ptr_intT)*skipB & 0x1));
00939   trace4((qh ferr, "qh_matchvertices: matched by skip %d (v%d) and skip %d (v%d) same? %d\n",
00940           skipA, (*skipAp)->id, *skipB, (*(skipBp-1))->id, *same));
00941   return (True);
00942 } /* matchvertices */

02030                                                  {
02031   facetT *facet;
02032   pointT *point, **pointp;
02033   int numpart;
02034   realT dist, innerplane;
02035 
02036   if (!qh KEEPcoplanar && !qh KEEPinside) {
02037     FORALLfacets {
02038       if (facet->coplanarset) 
02039         qh_setfree( &facet->coplanarset);
02040     }
02041   }else if (!qh KEEPcoplanar || !qh KEEPinside) {
02042     qh_outerinner (NULL, NULL, &innerplane);
02043     if (qh JOGGLEmax < REALmax/2)
02044       innerplane -= qh JOGGLEmax * sqrt (qh hull_dim);
02045     numpart= 0;
02046     FORALLfacets { 
02047       if (facet->coplanarset) {
02048         FOREACHpoint_(facet->coplanarset) {
02049           numpart++;
02050           qh_distplane (point, facet, &dist); 
02051           if (dist < innerplane) {
02052             if (!qh KEEPinside)
02053               SETref_(point)= NULL;
02054           }else if (!qh KEEPcoplanar)
02055             SETref_(point)= NULL;
02056         }
02057         qh_setcompact (facet->coplanarset);
02058       }
02059     }
02060     zadd_(Zcheckpart, numpart);
02061   }
02062 } /* nearcoplanar */

02077                                                                         {
02078   realT bestdist= REALmax, dist;
02079   vertexT *bestvertex= NULL, *vertex, **vertexp;
02080   int dim= qh hull_dim;
02081 
02082   if (qh DELAUNAY)
02083     dim--;
02084   FOREACHvertex_(facet->vertices) {
02085     dist= qh_pointdist (vertex->point, point, -dim);
02086     if (dist < bestdist) {
02087       bestdist= dist;
02088       bestvertex= vertex;
02089     }
02090   }
02091   *bestdistp= sqrt (bestdist);
02092   return bestvertex;
02093 } /* nearvertex */

00954                           {
00955   facetT *facet;
00956   void **freelistp; /* used !qh_NOmem */
00957   
00958   qh_memalloc_(sizeof(facetT), freelistp, facet, facetT);
00959   memset ((char *)facet, 0, sizeof(facetT));
00960   if (qh facet_id == qh tracefacet_id)
00961     qh tracefacet= facet;
00962   facet->id= qh facet_id++;
00963   facet->neighbors= qh_setnew(qh hull_dim);
00964 #if !qh_COMPUTEfurthest
00965   facet->furthestdist= 0.0;
00966 #endif
00967 #if qh_MAXoutside
00968   if (qh FORCEoutput && qh APPROXhull)
00969     facet->maxoutside= qh MINoutside;
00970   else
00971     facet->maxoutside= qh DISTround;
00972 #endif
00973   facet->simplicial= True;
00974   facet->good= True;
00975   facet->newfacet= True;
00976   trace4((qh ferr, "qh_newfacet: created facet f%d\n", facet->id));
00977   return (facet);
00978 } /* newfacet */

02106                                  {
02107   int size;
02108 
02109   size= ((newsize+1)*qh_HASHfactor) | 0x1;  /* odd number */
02110   while (True) { 
02111     if ((size%3) && (size%5))
02112       break;
02113     size += 2;
02114     /* loop terminates because there is an infinite number of primes */
02115   }
02116   qh hash_table= qh_setnew (size);
02117   qh_setzero (qh hash_table, 0, size);
02118   return size;
02119 } /* newhashtable */

00987                           {
00988   ridgeT *ridge;
00989   void **freelistp;   /* used !qh_NOmem */
00990 
00991   qh_memalloc_(sizeof(ridgeT), freelistp, ridge, ridgeT);
00992   memset ((char *)ridge, 0, sizeof(ridgeT));
00993   zinc_(Ztotridges);
00994   if (qh ridge_id == 0xFFFFFF) {
00995     fprintf(qh ferr, "\
00996 qhull warning: more than %d ridges.  ID field overflows and two ridges\n\
00997 may have the same identifier.  Otherwise output ok.\n", 0xFFFFFF);
00998   }
00999   ridge->id= qh ridge_id++;     
01000   trace4((qh ferr, "qh_newridge: created ridge r%d\n", ridge->id));
01001   return (ridge);
01002 } /* newridge */

02127                                      {
02128   vertexT *vertex;
02129 
02130   zinc_(Ztotvertices);
02131   vertex= (vertexT *)qh_memalloc(sizeof(vertexT));
02132   memset ((char *) vertex, 0, sizeof (vertexT));
02133   if (qh vertex_id == 0xFFFFFF) {
02134     fprintf(qh ferr, "qhull input error: more than %d vertices.  ID field overflows and two vertices\n\
02135 may have the same identifier.  Vertices not sorted correctly.\n", 0xFFFFFF);
02136     qh_errexit(qh_ERRinput, NULL, NULL);
02137   }
02138   if (qh vertex_id == qh tracevertex_id)
02139     qh tracevertex= vertex;
02140   vertex->id= qh vertex_id++;
02141   vertex->point= point;
02142   trace4((qh ferr, "qh_newvertex: vertex p%d (v%d) created\n", qh_pointid(vertex->point), 
02143           vertex->id));
02144   return (vertex);
02145 } /* newvertex */

02162                                                                            {
02163   vertexT *atvertex, *vertex, *othervertex;
02164   ridgeT *ridge, **ridgep;
02165 
02166   if ((atridge->top == facet) ^ qh_ORIENTclock)
02167     atvertex= SETsecondt_(atridge->vertices, vertexT);
02168   else
02169     atvertex= SETfirstt_(atridge->vertices, vertexT);
02170   FOREACHridge_(facet->ridges) {
02171     if (ridge == atridge)
02172       continue;
02173     if ((ridge->top == facet) ^ qh_ORIENTclock) {
02174       othervertex= SETsecondt_(ridge->vertices, vertexT);
02175       vertex= SETfirstt_(ridge->vertices, vertexT);
02176     }else {
02177       vertex= SETsecondt_(ridge->vertices, vertexT);
02178       othervertex= SETfirstt_(ridge->vertices, vertexT);
02179     }
02180     if (vertex == atvertex) {
02181       if (vertexp)
02182         *vertexp= othervertex;
02183       return ridge;
02184     }
02185   }
02186   return NULL;
02187 } /* nextridge3d */

02211                                             {
02212   pointT *point, **pointp;
02213   facetT *facet;
02214   realT dist;
02215 
02216   trace1((qh ferr, "qh_outcoplanar: move outsideset to coplanarset for qh NARROWhull\n"));
02217   FORALLfacets {
02218     FOREACHpoint_(facet->outsideset) {
02219       qh num_outside--;
02220       if (qh KEEPcoplanar || qh KEEPnearinside) {
02221         qh_distplane (point, facet, &dist);
02222         zinc_(Zpartition);
02223         qh_partitioncoplanar (point, facet, &dist);
02224       }
02225     }
02226     qh_setfree (&facet->outsideset);
02227   }
02228 } /* outcoplanar */

02240                           {
02241 
02242   if (id < 0)
02243     return NULL;
02244   if (id < qh num_points)
02245     return qh first_point + id * qh hull_dim;
02246   id -= qh num_points;
02247   if (id < qh_setsize (qh other_points))
02248     return SETelemt_(qh other_points, id, pointT);
02249   return NULL;
02250 } /* point */

02264                                                          {
02265   int id, size;
02266 
02267   SETreturnsize_(set, size);
02268   if ((id= qh_pointid(point)) < 0)
02269     fprintf (qh ferr, "qhull internal warning (point_add): unknown point %p id %d\n", 
02270       point, id);
02271   else if (id >= size) {
02272     fprintf (qh ferr, "qhull internal errror (point_add): point p%d is out of bounds (%d)\n",
02273              id, size);
02274     qh_errexit (qh_ERRqhull, NULL, NULL);
02275   }else
02276     SETelem_(set, id)= elem;
02277 } /* point_add */

02304                                              {
02305   int numpoints= qh num_points + qh_setsize (qh other_points);
02306   setT *facets;
02307   facetT *facet;
02308   vertexT *vertex, **vertexp;
02309   pointT *point, **pointp;
02310   
02311   facets= qh_settemp (numpoints);
02312   qh_setzero (facets, 0, numpoints);
02313   qh vertex_visit++;
02314   FORALLfacets {
02315     FOREACHvertex_(facet->vertices) {
02316       if (vertex->visitid != qh vertex_visit) {
02317         vertex->visitid= qh vertex_visit;
02318         qh_point_add (facets, vertex->point, facet);
02319       }
02320     }
02321     FOREACHpoint_(facet->coplanarset) 
02322       qh_point_add (facets, point, facet);
02323     FOREACHpoint_(facet->outsideset) 
02324       qh_point_add (facets, point, facet);
02325   }
02326   return facets;
02327 } /* pointfacet */

01020                                {
01021   long offset, id;
01022 
01023   if (!point)
01024     id= -3;
01025   else if (point == qh interior_point)
01026     id= -2;
01027   else if (point >= qh first_point
01028   && point < qh first_point + qh num_points * qh hull_dim) {
01029     offset= point - qh first_point;
01030     id= offset / qh hull_dim;
01031   }else if ((id= qh_setindex (qh other_points, point)) != -1)
01032     id += qh num_points;
01033   else
01034     id= -1;
01035   return (int) id;
01036 } /* pointid */

02341                                               {
02342   int numpoints= qh num_points + qh_setsize (qh other_points);
02343   setT *vertices;
02344   vertexT *vertex;
02345   
02346   vertices= qh_settemp (numpoints);
02347   qh_setzero (vertices, 0, numpoints);
02348   FORALLvertices 
02349     qh_point_add (vertices, vertex->point, vertex);
02350   return vertices;
02351 } /* pointvertex */

02368                                                         {
02369   facetT *prevfacet, *list= *facetlist;
02370   
02371 
02372   trace4((qh ferr, "qh_prependfacet: prepend f%d before f%d\n",
02373           facet->id, list->id));
02374   prevfacet= list->previous;
02375   facet->previous= prevfacet;
02376   if (prevfacet)
02377     prevfacet->next= facet;
02378   list->previous= facet;
02379   facet->next= *facetlist;
02380   if (qh facet_list == list)  /* this may change *facetlist */
02381     qh facet_list= facet;
02382   if (qh facet_next == list)
02383     qh facet_next= facet;
02384   *facetlist= facet;
02385   qh num_facets++;
02386 } /* prependfacet */

02404                                  {
02405   facetT *facet, *neighbor;
02406   int id, facet_i, facet_n, neighbor_i= 0, neighbor_n= 0;
02407   vertexT *vertex, **vertexp;
02408 
02409   FOREACHfacet_i_(qh hash_table) {
02410     if (facet) {
02411       FOREACHneighbor_i_(facet) {
02412         if (!neighbor || neighbor == qh_MERGEridge || neighbor == qh_DUPLICATEridge) 
02413           break;
02414       }
02415       if (neighbor_i == neighbor_n)
02416         continue;
02417       fprintf (fp, "hash %d f%d ", facet_i, facet->id);
02418       FOREACHvertex_(facet->vertices)
02419         fprintf (fp, "v%d ", vertex->id);
02420       fprintf (fp, "\n neighbors:");
02421       FOREACHneighbor_i_(facet) {
02422         if (neighbor == qh_MERGEridge)
02423           id= -3;
02424         else if (neighbor == qh_DUPLICATEridge)
02425           id= -2;
02426         else
02427           id= getid_(neighbor);
02428         fprintf (fp, " %d", id);
02429       }
02430       fprintf (fp, "\n");
02431     }
02432   }
02433 } /* printhashtable */

02442                           {
02443   facetT *facet;
02444   vertexT *vertex;
02445   
02446   fprintf (qh ferr, "qh_printlists: facets:");
02447   FORALLfacets 
02448     fprintf (qh ferr, " %d", facet->id);
02449   fprintf (qh ferr, "\n  new facets %d visible facets %d next facet for addpoint %d\n  vertices (new %d):",
02450      getid_(qh newfacet_list), getid_(qh visible_list), getid_(qh facet_next),
02451      getid_(qh newvertex_list));
02452   FORALLvertices
02453     fprintf (qh ferr, " %d", vertex->id);
02454   fprintf (qh ferr, "\n");
02455 } /* printlists */

01048                                    {
01049   facetT *next= facet->next, *previous= facet->previous;
01050   
01051   if (facet == qh newfacet_list)
01052     qh newfacet_list= next;
01053   if (facet == qh facet_next)
01054     qh facet_next= next;
01055   if (facet == qh visible_list)
01056     qh visible_list= next; 
01057   if (previous) {
01058     previous->next= next;
01059     next->previous= previous;
01060   }else {  /* 1st facet in qh facet_list */
01061     qh facet_list= next;
01062     qh facet_list->previous= NULL;
01063   }
01064   qh num_facets--;
01065   trace4((qh ferr, "qh_removefacet: remove f%d from facet_list\n", facet->id));
01066 } /* removefacet */

01079                                       {
01080   vertexT *next= vertex->next, *previous= vertex->previous;
01081   
01082   if (vertex == qh newvertex_list)
01083     qh newvertex_list= next;
01084   if (previous) {
01085     previous->next= next;
01086     next->previous= previous;
01087   }else {  /* 1st vertex in qh vertex_list */
01088     qh vertex_list= vertex->next;
01089     qh vertex_list->previous= NULL;
01090   }
01091   qh num_vertices--;
01092   trace4((qh ferr, "qh_removevertex: remove v%d from vertex_list\n", vertex->id));
01093 } /* removevertex */

02469                                                                                   {
02470   vertexT *vertex;
02471   facetT *newfacet, *visible;
02472   int totnew=0, totver=0;
02473   
02474   if (stats) {
02475     FORALLvertex_(qh newvertex_list)
02476       totver++;
02477     FORALLnew_facets 
02478       totnew++;
02479     zadd_(Zvisvertextot, totver);
02480     zmax_(Zvisvertexmax, totver);
02481     zadd_(Znewfacettot, totnew);
02482     zmax_(Znewfacetmax, totnew);
02483   }
02484   FORALLvertex_(qh newvertex_list)
02485     vertex->newlist= False;
02486   qh newvertex_list= NULL;
02487   FORALLnew_facets
02488     newfacet->newfacet= False;
02489   qh newfacet_list= NULL;
02490   FORALLvisible_facets {
02491     visible->f.replace= NULL;
02492     visible->visible= False;
02493   }
02494   qh visible_list= NULL;
02495   qh num_visible= 0;
02496   qh NEWfacets= False;
02497 } /* resetlists */

02517                               {
02518   facetT *facet;
02519 
02520   qh_clearcenters (qh_ASvoronoi);
02521   qh_vertexneighbors();
02522   
02523   FORALLfacets {
02524     if (!facet->normal || !facet->upperdelaunay || qh UPPERdelaunay) {
02525       if (!facet->center)
02526         facet->center= qh_facetcenter (facet->vertices);
02527     }
02528   }
02529 } /* setvoronoi_all */

01115                               {
01116   facetT *newfacet= NULL, *neighbor, **neighborp, *visible;
01117   vertexT *vertex, **vertexp;
01118 
01119   trace3((qh ferr, "qh_updatevertices: delete interior vertices and update vertex->neighbors\n"));
01120   if (qh VERTEXneighbors) {
01121     FORALLvertex_(qh newvertex_list) {
01122       FOREACHneighbor_(vertex) {
01123         if (neighbor->visible) 
01124           SETref_(neighbor)= NULL;
01125       }
01126       qh_setcompact (vertex->neighbors);
01127     }
01128     FORALLnew_facets {
01129       FOREACHvertex_(newfacet->vertices)
01130         qh_setappend (&vertex->neighbors, newfacet);
01131     }
01132     FORALLvisible_facets {
01133       FOREACHvertex_(visible->vertices) {
01134         if (!vertex->newlist && !vertex->deleted) {
01135           FOREACHneighbor_(vertex) { /* this can happen under merging */
01136             if (!neighbor->visible)
01137               break;
01138           }
01139           if (neighbor)
01140             qh_setdel (vertex->neighbors, visible);
01141           else {
01142             vertex->deleted= True;
01143             qh_setappend (&qh del_vertices, vertex);
01144             trace2((qh ferr, "qh_updatevertices: delete vertex p%d (v%d) in f%d\n",
01145                   qh_pointid(vertex->point), vertex->id, visible->id));
01146           }
01147         }
01148       }
01149     }
01150   }else {  /* !VERTEXneighbors */
01151     FORALLvisible_facets {
01152       FOREACHvertex_(visible->vertices) {
01153         if (!vertex->newlist && !vertex->deleted) {
01154           vertex->deleted= True;
01155           qh_setappend (&qh del_vertices, vertex);
01156           trace2((qh ferr, "qh_updatevertices: delete vertex p%d (v%d) in f%d\n",
01157                   qh_pointid(vertex->point), vertex->id, visible->id));
01158         }
01159       }
01160     }
01161   }
01162 } /* updatevertices */

02544                                                             {
02545   setT *intersection;
02546 
02547   intersection= qh_vertexintersect_new (*vertexsetA, vertexsetB);
02548   qh_settempfree (vertexsetA);
02549   *vertexsetA= intersection;
02550   qh_settemppush (intersection);
02551 } /* vertexintersect */

02562                                                                  {
02563   setT *intersection= qh_setnew (qh hull_dim - 1);
02564   vertexT **vertexA= SETaddr_(vertexsetA, vertexT); 
02565   vertexT **vertexB= SETaddr_(vertexsetB, vertexT); 
02566 
02567   while (*vertexA && *vertexB) {
02568     if (*vertexA  == *vertexB) {
02569       qh_setappend(&intersection, *vertexA);
02570       vertexA++; vertexB++;
02571     }else {
02572       if ((*vertexA)->id > (*vertexB)->id)
02573         vertexA++;
02574       else
02575         vertexB++;
02576     }
02577   }
02578   return intersection;
02579 } /* vertexintersect_new */

02601                                                  {
02602   facetT *facet;
02603   vertexT *vertex, **vertexp;
02604 
02605   if (qh VERTEXneighbors)
02606     return;
02607   trace1((qh ferr, "qh_vertexneighbors: determing neighboring facets for each vertex\n"));
02608   qh vertex_visit++;
02609   FORALLfacets {
02610     if (facet->visible)
02611       continue;
02612     FOREACHvertex_(facet->vertices) {
02613       if (vertex->visitid != qh vertex_visit) {
02614         vertex->visitid= qh vertex_visit;
02615         vertex->neighbors= qh_setnew (qh hull_dim);
02616       }
02617       qh_setappend (&vertex->neighbors, facet);
02618     }
02619   }
02620   qh VERTEXneighbors= True;
02621 } /* vertexneighbors */

02633                                                           {
02634   vertexT **vertexA= (vertexT **) SETaddr_(vertexsetA, vertexT);
02635   vertexT **vertexB= (vertexT **) SETaddr_(vertexsetB, vertexT);
02636 
02637   while (True) {
02638     if (!*vertexA)
02639       return True;
02640     if (!*vertexB)
02641       return False;
02642     if ((*vertexA)->id > (*vertexB)->id)
02643       return False;
02644     if (*vertexA  == *vertexB)
02645       vertexA++;
02646     vertexB++; 
02647   }
02648   return False; /* avoid warnings */
02649 } /* vertexsubset */