libqhull: poly.c Source File

Go to the documentation of this file.
00001 /*<html><pre>  -<a                             href="qh-poly.htm"
00002   >-------------------------------</a><a name="TOP">-</a>
00003 
00004    poly.c
00005    implements polygons and simplices
00006 
00007    see qh-poly.htm, poly.h and libqhull.h
00008 
00009    infrequent code is in poly2.c
00010    (all but top 50 and their callers 12/3/95)
00011 
00012    Copyright (c) 1993-2011 The Geometry Center.
00013    $Id: //main/2011/qhull/src/libqhull/poly.c#3 $$Change: 1440 $
00014    $DateTime: 2011/11/22 22:22:37 $$Author: bbarber $
00015 */
00016 
00017 #include "qhull_a.h"
00018 
00019 /*======== functions in alphabetical order ==========*/
00020 
00021 /*-<a                             href="qh-poly.htm#TOC"
00022   >-------------------------------</a><a name="appendfacet">-</a>
00023 
00024   qh_appendfacet( facet )
00025     appends facet to end of qh.facet_list,
00026 
00027   returns:
00028     updates qh.newfacet_list, facet_next, facet_list
00029     increments qh.numfacets
00030 
00031   notes:
00032     assumes qh.facet_list/facet_tail is defined (createsimplex)
00033 
00034   see:
00035     qh_removefacet()
00036 
00037 */
00038 void qh_appendfacet(facetT *facet) {
00039   facetT *tail= qh facet_tail;
00040 
00041   if (tail == qh newfacet_list)
00042     qh newfacet_list= facet;
00043   if (tail == qh facet_next)
00044     qh facet_next= facet;
00045   facet->previous= tail->previous;
00046   facet->next= tail;
00047   if (tail->previous)
00048     tail->previous->next= facet;
00049   else
00050     qh facet_list= facet;
00051   tail->previous= facet;
00052   qh num_facets++;
00053   trace4((qh ferr, 4044, "qh_appendfacet: append f%d to facet_list\n", facet->id));
00054 } /* appendfacet */
00055 
00056 
00057 /*-<a                             href="qh-poly.htm#TOC"
00058   >-------------------------------</a><a name="appendvertex">-</a>
00059 
00060   qh_appendvertex( vertex )
00061     appends vertex to end of qh.vertex_list,
00062 
00063   returns:
00064     sets vertex->newlist
00065     updates qh.vertex_list, newvertex_list
00066     increments qh.num_vertices
00067 
00068   notes:
00069     assumes qh.vertex_list/vertex_tail is defined (createsimplex)
00070 
00071 */
00072 void qh_appendvertex(vertexT *vertex) {
00073   vertexT *tail= qh vertex_tail;
00074 
00075   if (tail == qh newvertex_list)
00076     qh newvertex_list= vertex;
00077   vertex->newlist= True;
00078   vertex->previous= tail->previous;
00079   vertex->next= tail;
00080   if (tail->previous)
00081     tail->previous->next= vertex;
00082   else
00083     qh vertex_list= vertex;
00084   tail->previous= vertex;
00085   qh num_vertices++;
00086   trace4((qh ferr, 4045, "qh_appendvertex: append v%d to vertex_list\n", vertex->id));
00087 } /* appendvertex */
00088 
00089 
00090 /*-<a                             href="qh-poly.htm#TOC"
00091   >-------------------------------</a><a name="attachnewfacets">-</a>
00092 
00093   qh_attachnewfacets( )
00094     attach horizon facets to new facets in qh.newfacet_list
00095     newfacets have neighbor and ridge links to horizon but not vice versa
00096     only needed for qh.ONLYgood
00097 
00098   returns:
00099     set qh.NEWfacets
00100     horizon facets linked to new facets
00101       ridges changed from visible facets to new facets
00102       simplicial ridges deleted
00103     qh.visible_list, no ridges valid
00104     facet->f.replace is a newfacet (if any)
00105 
00106   design:
00107     delete interior ridges and neighbor sets by
00108       for each visible, non-simplicial facet
00109         for each ridge
00110           if last visit or if neighbor is simplicial
00111             if horizon neighbor
00112               delete ridge for horizon's ridge set
00113             delete ridge
00114         erase neighbor set
00115     attach horizon facets and new facets by
00116       for all new facets
00117         if corresponding horizon facet is simplicial
00118           locate corresponding visible facet {may be more than one}
00119           link visible facet to new facet
00120           replace visible facet with new facet in horizon
00121         else it's non-simplicial
00122           for all visible neighbors of the horizon facet
00123             link visible neighbor to new facet
00124             delete visible neighbor from horizon facet
00125           append new facet to horizon's neighbors
00126           the first ridge of the new facet is the horizon ridge
00127           link the new facet into the horizon ridge
00128 */
00129 void qh_attachnewfacets(void ) {
00130   facetT *newfacet= NULL, *neighbor, **neighborp, *horizon, *visible;
00131   ridgeT *ridge, **ridgep;
00132 
00133   qh NEWfacets= True;
00134   trace3((qh ferr, 3012, "qh_attachnewfacets: delete interior ridges\n"));
00135   qh visit_id++;
00136   FORALLvisible_facets {
00137     visible->visitid= qh visit_id;
00138     if (visible->ridges) {
00139       FOREACHridge_(visible->ridges) {
00140         neighbor= otherfacet_(ridge, visible);
00141         if (neighbor->visitid == qh visit_id
00142             || (!neighbor->visible && neighbor->simplicial)) {
00143           if (!neighbor->visible)  /* delete ridge for simplicial horizon */
00144             qh_setdel(neighbor->ridges, ridge);
00145           qh_setfree(&(ridge->vertices)); /* delete on 2nd visit */
00146           qh_memfree(ridge, (int)sizeof(ridgeT));
00147         }
00148       }
00149       SETfirst_(visible->ridges)= NULL;
00150     }
00151     SETfirst_(visible->neighbors)= NULL;
00152   }
00153   trace1((qh ferr, 1017, "qh_attachnewfacets: attach horizon facets to new facets\n"));
00154   FORALLnew_facets {
00155     horizon= SETfirstt_(newfacet->neighbors, facetT);
00156     if (horizon->simplicial) {
00157       visible= NULL;
00158       FOREACHneighbor_(horizon) {   /* may have more than one horizon ridge */
00159         if (neighbor->visible) {
00160           if (visible) {
00161             if (qh_setequal_skip(newfacet->vertices, 0, horizon->vertices,
00162                                   SETindex_(horizon->neighbors, neighbor))) {
00163               visible= neighbor;
00164               break;
00165             }
00166           }else
00167             visible= neighbor;
00168         }
00169       }
00170       if (visible) {
00171         visible->f.replace= newfacet;
00172         qh_setreplace(horizon->neighbors, visible, newfacet);
00173       }else {
00174         qh_fprintf(qh ferr, 6102, "qhull internal error (qh_attachnewfacets): couldn't find visible facet for horizon f%d of newfacet f%d\n",
00175                  horizon->id, newfacet->id);
00176         qh_errexit2 (qh_ERRqhull, horizon, newfacet);
00177       }
00178     }else { /* non-simplicial, with a ridge for newfacet */
00179       FOREACHneighbor_(horizon) {    /* may hold for many new facets */
00180         if (neighbor->visible) {
00181           neighbor->f.replace= newfacet;
00182           qh_setdelnth(horizon->neighbors,
00183                         SETindex_(horizon->neighbors, neighbor));
00184           neighborp--; /* repeat */
00185         }
00186       }
00187       qh_setappend(&horizon->neighbors, newfacet);
00188       ridge= SETfirstt_(newfacet->ridges, ridgeT);
00189       if (ridge->top == horizon)
00190         ridge->bottom= newfacet;
00191       else
00192         ridge->top= newfacet;
00193       }
00194   } /* newfacets */
00195   if (qh PRINTstatistics) {
00196     FORALLvisible_facets {
00197       if (!visible->f.replace)
00198         zinc_(Zinsidevisible);
00199     }
00200   }
00201 } /* attachnewfacets */
00202 
00203 /*-<a                             href="qh-poly.htm#TOC"
00204   >-------------------------------</a><a name="checkflipped">-</a>
00205 
00206   qh_checkflipped( facet, dist, allerror )
00207     checks facet orientation to interior point
00208 
00209     if allerror set,
00210       tests against qh.DISTround
00211     else
00212       tests against 0 since tested against DISTround before
00213 
00214   returns:
00215     False if it flipped orientation (sets facet->flipped)
00216     distance if non-NULL
00217 */
00218 boolT qh_checkflipped(facetT *facet, realT *distp, boolT allerror) {
00219   realT dist;
00220 
00221   if (facet->flipped && !distp)
00222     return False;
00223   zzinc_(Zdistcheck);
00224   qh_distplane(qh interior_point, facet, &dist);
00225   if (distp)
00226     *distp= dist;
00227   if ((allerror && dist > -qh DISTround)|| (!allerror && dist >= 0.0)) {
00228     facet->flipped= True;
00229     zzinc_(Zflippedfacets);
00230     trace0((qh ferr, 19, "qh_checkflipped: facet f%d is flipped, distance= %6.12g during p%d\n",
00231               facet->id, dist, qh furthest_id));
00232     qh_precision("flipped facet");
00233     return False;
00234   }
00235   return True;
00236 } /* checkflipped */
00237 
00238 /*-<a                             href="qh-poly.htm#TOC"
00239   >-------------------------------</a><a name="delfacet">-</a>
00240 
00241   qh_delfacet( facet )
00242     removes facet from facet_list and frees up its memory
00243 
00244   notes:
00245     assumes vertices and ridges already freed
00246 */
00247 void qh_delfacet(facetT *facet) {
00248   void **freelistp; /* used !qh_NOmem */
00249 
00250   trace4((qh ferr, 4046, "qh_delfacet: delete f%d\n", facet->id));
00251   if (facet == qh tracefacet)
00252     qh tracefacet= NULL;
00253   if (facet == qh GOODclosest)
00254     qh GOODclosest= NULL;
00255   qh_removefacet(facet);
00256   if (!facet->tricoplanar || facet->keepcentrum) {
00257     qh_memfree_(facet->normal, qh normal_size, freelistp);
00258     if (qh CENTERtype == qh_ASvoronoi) {   /* uses macro calls */
00259       qh_memfree_(facet->center, qh center_size, freelistp);
00260     }else /* AScentrum */ {
00261       qh_memfree_(facet->center, qh normal_size, freelistp);
00262     }
00263   }
00264   qh_setfree(&(facet->neighbors));
00265   if (facet->ridges)
00266     qh_setfree(&(facet->ridges));
00267   qh_setfree(&(facet->vertices));
00268   if (facet->outsideset)
00269     qh_setfree(&(facet->outsideset));
00270   if (facet->coplanarset)
00271     qh_setfree(&(facet->coplanarset));
00272   qh_memfree_(facet, (int)sizeof(facetT), freelistp);
00273 } /* delfacet */
00274 
00275 
00276 /*-<a                             href="qh-poly.htm#TOC"
00277   >-------------------------------</a><a name="deletevisible">-</a>
00278 
00279   qh_deletevisible()
00280     delete visible facets and vertices
00281 
00282   returns:
00283     deletes each facet and removes from facetlist
00284     at exit, qh.visible_list empty (== qh.newfacet_list)
00285 
00286   notes:
00287     ridges already deleted
00288     horizon facets do not reference facets on qh.visible_list
00289     new facets in qh.newfacet_list
00290     uses   qh.visit_id;
00291 */
00292 void qh_deletevisible(void /*qh visible_list*/) {
00293   facetT *visible, *nextfacet;
00294   vertexT *vertex, **vertexp;
00295   int numvisible= 0, numdel= qh_setsize(qh del_vertices);
00296 
00297   trace1((qh ferr, 1018, "qh_deletevisible: delete %d visible facets and %d vertices\n",
00298          qh num_visible, numdel));
00299   for (visible= qh visible_list; visible && visible->visible;
00300                 visible= nextfacet) { /* deleting current */
00301     nextfacet= visible->next;
00302     numvisible++;
00303     qh_delfacet(visible);
00304   }
00305   if (numvisible != qh num_visible) {
00306     qh_fprintf(qh ferr, 6103, "qhull internal error (qh_deletevisible): qh num_visible %d is not number of visible facets %d\n",
00307              qh num_visible, numvisible);
00308     qh_errexit(qh_ERRqhull, NULL, NULL);
00309   }
00310   qh num_visible= 0;
00311   zadd_(Zvisfacettot, numvisible);
00312   zmax_(Zvisfacetmax, numvisible);
00313   zzadd_(Zdelvertextot, numdel);
00314   zmax_(Zdelvertexmax, numdel);
00315   FOREACHvertex_(qh del_vertices)
00316     qh_delvertex(vertex);
00317   qh_settruncate(qh del_vertices, 0);
00318 } /* deletevisible */
00319 
00320 /*-<a                             href="qh-poly.htm#TOC"
00321   >-------------------------------</a><a name="facetintersect">-</a>
00322 
00323   qh_facetintersect( facetA, facetB, skipa, skipB, prepend )
00324     return vertices for intersection of two simplicial facets
00325     may include 1 prepended entry (if more, need to settemppush)
00326 
00327   returns:
00328     returns set of qh.hull_dim-1 + prepend vertices
00329     returns skipped index for each test and checks for exactly one
00330 
00331   notes:
00332     does not need settemp since set in quick memory
00333 
00334   see also:
00335     qh_vertexintersect and qh_vertexintersect_new
00336     use qh_setnew_delnthsorted to get nth ridge (no skip information)
00337 
00338   design:
00339     locate skipped vertex by scanning facet A's neighbors
00340     locate skipped vertex by scanning facet B's neighbors
00341     intersect the vertex sets
00342 */
00343 setT *qh_facetintersect(facetT *facetA, facetT *facetB,
00344                          int *skipA,int *skipB, int prepend) {
00345   setT *intersect;
00346   int dim= qh hull_dim, i, j;
00347   facetT **neighborsA, **neighborsB;
00348 
00349   neighborsA= SETaddr_(facetA->neighbors, facetT);
00350   neighborsB= SETaddr_(facetB->neighbors, facetT);
00351   i= j= 0;
00352   if (facetB == *neighborsA++)
00353     *skipA= 0;
00354   else if (facetB == *neighborsA++)
00355     *skipA= 1;
00356   else if (facetB == *neighborsA++)
00357     *skipA= 2;
00358   else {
00359     for (i=3; i < dim; i++) {
00360       if (facetB == *neighborsA++) {
00361         *skipA= i;
00362         break;
00363       }
00364     }
00365   }
00366   if (facetA == *neighborsB++)
00367     *skipB= 0;
00368   else if (facetA == *neighborsB++)
00369     *skipB= 1;
00370   else if (facetA == *neighborsB++)
00371     *skipB= 2;
00372   else {
00373     for (j=3; j < dim; j++) {
00374       if (facetA == *neighborsB++) {
00375         *skipB= j;
00376         break;
00377       }
00378     }
00379   }
00380   if (i >= dim || j >= dim) {
00381     qh_fprintf(qh ferr, 6104, "qhull internal error (qh_facetintersect): f%d or f%d not in others neighbors\n",
00382             facetA->id, facetB->id);
00383     qh_errexit2 (qh_ERRqhull, facetA, facetB);
00384   }
00385   intersect= qh_setnew_delnthsorted(facetA->vertices, qh hull_dim, *skipA, prepend);
00386   trace4((qh ferr, 4047, "qh_facetintersect: f%d skip %d matches f%d skip %d\n",
00387           facetA->id, *skipA, facetB->id, *skipB));
00388   return(intersect);
00389 } /* facetintersect */
00390 
00391 /*-<a                             href="qh-poly.htm#TOC"
00392   >-------------------------------</a><a name="gethash">-</a>
00393 
00394   qh_gethash( hashsize, set, size, firstindex, skipelem )
00395     return hashvalue for a set with firstindex and skipelem
00396 
00397   notes:
00398     returned hash is in [0,hashsize)
00399     assumes at least firstindex+1 elements
00400     assumes skipelem is NULL, in set, or part of hash
00401 
00402     hashes memory addresses which may change over different runs of the same data
00403     using sum for hash does badly in high d
00404 */
00405 int qh_gethash(int hashsize, setT *set, int size, int firstindex, void *skipelem) {
00406   void **elemp= SETelemaddr_(set, firstindex, void);
00407   ptr_intT hash = 0, elem;
00408   unsigned result;
00409   int i;
00410 #ifdef _MSC_VER                   /* Microsoft Visual C++ -- warn about 64-bit issues */
00411 #pragma warning( push)            /* WARN64 -- ptr_intT holds a 64-bit pointer */
00412 #pragma warning( disable : 4311)  /* 'type cast': pointer truncation from 'void*' to 'ptr_intT' */
00413 #endif
00414 
00415   switch (size-firstindex) {
00416   case 1:
00417     hash= (ptr_intT)(*elemp) - (ptr_intT) skipelem;
00418     break;
00419   case 2:
00420     hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] - (ptr_intT) skipelem;
00421     break;
00422   case 3:
00423     hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
00424       - (ptr_intT) skipelem;
00425     break;
00426   case 4:
00427     hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
00428       + (ptr_intT)elemp[3] - (ptr_intT) skipelem;
00429     break;
00430   case 5:
00431     hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
00432       + (ptr_intT)elemp[3] + (ptr_intT)elemp[4] - (ptr_intT) skipelem;
00433     break;
00434   case 6:
00435     hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
00436       + (ptr_intT)elemp[3] + (ptr_intT)elemp[4]+ (ptr_intT)elemp[5]
00437       - (ptr_intT) skipelem;
00438     break;
00439   default:
00440     hash= 0;
00441     i= 3;
00442     do {     /* this is about 10% in 10-d */
00443       if ((elem= (ptr_intT)*elemp++) != (ptr_intT)skipelem) {
00444         hash ^= (elem << i) + (elem >> (32-i));
00445         i += 3;
00446         if (i >= 32)
00447           i -= 32;
00448       }
00449     }while (*elemp);
00450     break;
00451   }
00452   if (hashsize<0) {
00453     qh_fprintf(qh ferr, 6232, "qhull internal error: negative hashsize %d passed to qh_gethash [poly.c]\n", hashsize);
00454     qh_errexit2 (qh_ERRqhull, NULL, NULL);
00455   }
00456   result= (unsigned)hash;
00457   result %= (unsigned)hashsize;
00458   /* result= 0; for debugging */
00459   return result;
00460 #ifdef _MSC_VER
00461 #pragma warning( pop)
00462 #endif
00463 } /* gethash */
00464 
00465 /*-<a                             href="qh-poly.htm#TOC"
00466   >-------------------------------</a><a name="makenewfacet">-</a>
00467 
00468   qh_makenewfacet( vertices, toporient, horizon )
00469     creates a toporient? facet from vertices
00470 
00471   returns:
00472     returns newfacet
00473       adds newfacet to qh.facet_list
00474       newfacet->vertices= vertices
00475       if horizon
00476         newfacet->neighbor= horizon, but not vice versa
00477     newvertex_list updated with vertices
00478 */
00479 facetT *qh_makenewfacet(setT *vertices, boolT toporient,facetT *horizon) {
00480   facetT *newfacet;
00481   vertexT *vertex, **vertexp;
00482 
00483   FOREACHvertex_(vertices) {
00484     if (!vertex->newlist) {
00485       qh_removevertex(vertex);
00486       qh_appendvertex(vertex);
00487     }
00488   }
00489   newfacet= qh_newfacet();
00490   newfacet->vertices= vertices;
00491   newfacet->toporient= (unsigned char)toporient;
00492   if (horizon)
00493     qh_setappend(&(newfacet->neighbors), horizon);
00494   qh_appendfacet(newfacet);
00495   return(newfacet);
00496 } /* makenewfacet */
00497 
00498 
00499 /*-<a                             href="qh-poly.htm#TOC"
00500   >-------------------------------</a><a name="makenewplanes">-</a>
00501 
00502   qh_makenewplanes()
00503     make new hyperplanes for facets on qh.newfacet_list
00504 
00505   returns:
00506     all facets have hyperplanes or are marked for   merging
00507     doesn't create hyperplane if horizon is coplanar (will merge)
00508     updates qh.min_vertex if qh.JOGGLEmax
00509 
00510   notes:
00511     facet->f.samecycle is defined for facet->mergehorizon facets
00512 */
00513 void qh_makenewplanes(void /* newfacet_list */) {
00514   facetT *newfacet;
00515 
00516   FORALLnew_facets {
00517     if (!newfacet->mergehorizon)
00518       qh_setfacetplane(newfacet);
00519   }
00520   if (qh JOGGLEmax < REALmax/2)
00521     minimize_(qh min_vertex, -wwval_(Wnewvertexmax));
00522 } /* makenewplanes */
00523 
00524 /*-<a                             href="qh-poly.htm#TOC"
00525   >-------------------------------</a><a name="makenew_nonsimplicial">-</a>
00526 
00527   qh_makenew_nonsimplicial( visible, apex, numnew )
00528     make new facets for ridges of a visible facet
00529 
00530   returns:
00531     first newfacet, bumps numnew as needed
00532     attaches new facets if !qh.ONLYgood
00533     marks ridge neighbors for simplicial visible
00534     if (qh.ONLYgood)
00535       ridges on newfacet, horizon, and visible
00536     else
00537       ridge and neighbors between newfacet and   horizon
00538       visible facet's ridges are deleted
00539 
00540   notes:
00541     qh.visit_id if visible has already been processed
00542     sets neighbor->seen for building f.samecycle
00543       assumes all 'seen' flags initially false
00544 
00545   design:
00546     for each ridge of visible facet
00547       get neighbor of visible facet
00548       if neighbor was already processed
00549         delete the ridge (will delete all visible facets later)
00550       if neighbor is a horizon facet
00551         create a new facet
00552         if neighbor coplanar
00553           adds newfacet to f.samecycle for later merging
00554         else
00555           updates neighbor's neighbor set
00556           (checks for non-simplicial facet with multiple ridges to visible facet)
00557         updates neighbor's ridge set
00558         (checks for simplicial neighbor to non-simplicial visible facet)
00559         (deletes ridge if neighbor is simplicial)
00560 
00561 */
00562 #ifndef qh_NOmerge
00563 facetT *qh_makenew_nonsimplicial(facetT *visible, vertexT *apex, int *numnew) {
00564   void **freelistp; /* used !qh_NOmem */
00565   ridgeT *ridge, **ridgep;
00566   facetT *neighbor, *newfacet= NULL, *samecycle;
00567   setT *vertices;
00568   boolT toporient;
00569   int ridgeid;
00570 
00571   FOREACHridge_(visible->ridges) {
00572     ridgeid= ridge->id;
00573     neighbor= otherfacet_(ridge, visible);
00574     if (neighbor->visible) {
00575       if (!qh ONLYgood) {
00576         if (neighbor->visitid == qh visit_id) {
00577           qh_setfree(&(ridge->vertices));  /* delete on 2nd visit */
00578           qh_memfree_(ridge, (int)sizeof(ridgeT), freelistp);
00579         }
00580       }
00581     }else {  /* neighbor is an horizon facet */
00582       toporient= (ridge->top == visible);
00583       vertices= qh_setnew(qh hull_dim); /* makes sure this is quick */
00584       qh_setappend(&vertices, apex);
00585       qh_setappend_set(&vertices, ridge->vertices);
00586       newfacet= qh_makenewfacet(vertices, toporient, neighbor);
00587       (*numnew)++;
00588       if (neighbor->coplanar) {
00589         newfacet->mergehorizon= True;
00590         if (!neighbor->seen) {
00591           newfacet->f.samecycle= newfacet;
00592           neighbor->f.newcycle= newfacet;
00593         }else {
00594           samecycle= neighbor->f.newcycle;
00595           newfacet->f.samecycle= samecycle->f.samecycle;
00596           samecycle->f.samecycle= newfacet;
00597         }
00598       }
00599       if (qh ONLYgood) {
00600         if (!neighbor->simplicial)
00601           qh_setappend(&(newfacet->ridges), ridge);
00602       }else {  /* qh_attachnewfacets */
00603         if (neighbor->seen) {
00604           if (neighbor->simplicial) {
00605             qh_fprintf(qh ferr, 6105, "qhull internal error (qh_makenew_nonsimplicial): simplicial f%d sharing two ridges with f%d\n",
00606                    neighbor->id, visible->id);
00607             qh_errexit2 (qh_ERRqhull, neighbor, visible);
00608           }
00609           qh_setappend(&(neighbor->neighbors), newfacet);
00610         }else
00611           qh_setreplace(neighbor->neighbors, visible, newfacet);
00612         if (neighbor->simplicial) {
00613           qh_setdel(neighbor->ridges, ridge);
00614           qh_setfree(&(ridge->vertices));
00615           qh_memfree(ridge, (int)sizeof(ridgeT));
00616         }else {
00617           qh_setappend(&(newfacet->ridges), ridge);
00618           if (toporient)
00619             ridge->top= newfacet;
00620           else
00621             ridge->bottom= newfacet;
00622         }
00623       trace4((qh ferr, 4048, "qh_makenew_nonsimplicial: created facet f%d from v%d and r%d of horizon f%d\n",
00624             newfacet->id, apex->id, ridgeid, neighbor->id));
00625       }
00626     }
00627     neighbor->seen= True;
00628   } /* for each ridge */
00629   if (!qh ONLYgood)
00630     SETfirst_(visible->ridges)= NULL;
00631   return newfacet;
00632 } /* makenew_nonsimplicial */
00633 #else /* qh_NOmerge */
00634 facetT *qh_makenew_nonsimplicial(facetT *visible, vertexT *apex, int *numnew) {
00635   return NULL;
00636 }
00637 #endif /* qh_NOmerge */
00638 
00639 /*-<a                             href="qh-poly.htm#TOC"
00640   >-------------------------------</a><a name="makenew_simplicial">-</a>
00641 
00642   qh_makenew_simplicial( visible, apex, numnew )
00643     make new facets for simplicial visible facet and apex
00644 
00645   returns:
00646     attaches new facets if (!qh.ONLYgood)
00647       neighbors between newfacet and horizon
00648 
00649   notes:
00650     nop if neighbor->seen or neighbor->visible(see qh_makenew_nonsimplicial)
00651 
00652   design:
00653     locate neighboring horizon facet for visible facet
00654     determine vertices and orientation
00655     create new facet
00656     if coplanar,
00657       add new facet to f.samecycle
00658     update horizon facet's neighbor list
00659 */
00660 facetT *qh_makenew_simplicial(facetT *visible, vertexT *apex, int *numnew) {
00661   facetT *neighbor, **neighborp, *newfacet= NULL;
00662   setT *vertices;
00663   boolT flip, toporient;
00664   int horizonskip, visibleskip;
00665 
00666   FOREACHneighbor_(visible) {
00667     if (!neighbor->seen && !neighbor->visible) {
00668       vertices= qh_facetintersect(neighbor,visible, &horizonskip, &visibleskip, 1);
00669       SETfirst_(vertices)= apex;
00670       flip= ((horizonskip & 0x1) ^ (visibleskip & 0x1));
00671       if (neighbor->toporient)
00672         toporient= horizonskip & 0x1;
00673       else
00674         toporient= (horizonskip & 0x1) ^ 0x1;
00675       newfacet= qh_makenewfacet(vertices, toporient, neighbor);
00676       (*numnew)++;
00677       if (neighbor->coplanar && (qh PREmerge || qh MERGEexact)) {
00678 #ifndef qh_NOmerge
00679         newfacet->f.samecycle= newfacet;
00680         newfacet->mergehorizon= True;
00681 #endif
00682       }
00683       if (!qh ONLYgood)
00684         SETelem_(neighbor->neighbors, horizonskip)= newfacet;
00685       trace4((qh ferr, 4049, "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",
00686             newfacet->id, toporient, apex->id, neighbor->id, horizonskip,
00687               neighbor->toporient, visible->id, visibleskip, flip));
00688     }
00689   }
00690   return newfacet;
00691 } /* makenew_simplicial */
00692 
00693 /*-<a                             href="qh-poly.htm#TOC"
00694   >-------------------------------</a><a name="matchneighbor">-</a>
00695 
00696   qh_matchneighbor( newfacet, newskip, hashsize, hashcount )
00697     either match subridge of newfacet with neighbor or add to hash_table
00698 
00699   returns:
00700     duplicate ridges are unmatched and marked by qh_DUPLICATEridge
00701 
00702   notes:
00703     ridge is newfacet->vertices w/o newskip vertex
00704     do not allocate memory (need to free hash_table cleanly)
00705     uses linear hash chains
00706 
00707   see also:
00708     qh_matchduplicates
00709 
00710   design:
00711     for each possible matching facet in qh.hash_table
00712       if vertices match
00713         set ismatch, if facets have opposite orientation
00714         if ismatch and matching facet doesn't have a match
00715           match the facets by updating their neighbor sets
00716         else
00717           indicate a duplicate ridge
00718           set facet hyperplane for later testing
00719           add facet to hashtable
00720           unless the other facet was already a duplicate ridge
00721             mark both facets with a duplicate ridge
00722             add other facet (if defined) to hash table
00723 */
00724 void qh_matchneighbor(facetT *newfacet, int newskip, int hashsize, int *hashcount) {
00725   boolT newfound= False;   /* True, if new facet is already in hash chain */
00726   boolT same, ismatch;
00727   int hash, scan;
00728   facetT *facet, *matchfacet;
00729   int skip, matchskip;
00730 
00731   hash= qh_gethash(hashsize, newfacet->vertices, qh hull_dim, 1,
00732                      SETelem_(newfacet->vertices, newskip));
00733   trace4((qh ferr, 4050, "qh_matchneighbor: newfacet f%d skip %d hash %d hashcount %d\n",
00734           newfacet->id, newskip, hash, *hashcount));
00735   zinc_(Zhashlookup);
00736   for (scan= hash; (facet= SETelemt_(qh hash_table, scan, facetT));
00737        scan= (++scan >= hashsize ? 0 : scan)) {
00738     if (facet == newfacet) {
00739       newfound= True;
00740       continue;
00741     }
00742     zinc_(Zhashtests);
00743     if (qh_matchvertices(1, newfacet->vertices, newskip, facet->vertices, &skip, &same)) {
00744       if (SETelem_(newfacet->vertices, newskip) ==
00745           SETelem_(facet->vertices, skip)) {
00746         qh_precision("two facets with the same vertices");
00747         qh_fprintf(qh ferr, 6106, "qhull precision error: Vertex sets are the same for f%d and f%d.  Can not force output.\n",
00748           facet->id, newfacet->id);
00749         qh_errexit2 (qh_ERRprec, facet, newfacet);
00750       }
00751       ismatch= (same == (boolT)((newfacet->toporient ^ facet->toporient)));
00752       matchfacet= SETelemt_(facet->neighbors, skip, facetT);
00753       if (ismatch && !matchfacet) {
00754         SETelem_(facet->neighbors, skip)= newfacet;
00755         SETelem_(newfacet->neighbors, newskip)= facet;
00756         (*hashcount)--;
00757         trace4((qh ferr, 4051, "qh_matchneighbor: f%d skip %d matched with new f%d skip %d\n",
00758            facet->id, skip, newfacet->id, newskip));
00759         return;
00760       }
00761       if (!qh PREmerge && !qh MERGEexact) {
00762         qh_precision("a ridge with more than two neighbors");
00763         qh_fprintf(qh ferr, 6107, "qhull precision error: facets f%d, f%d and f%d meet at a ridge with more than 2 neighbors.  Can not continue.\n",
00764                  facet->id, newfacet->id, getid_(matchfacet));
00765         qh_errexit2 (qh_ERRprec, facet, newfacet);
00766       }
00767       SETelem_(newfacet->neighbors, newskip)= qh_DUPLICATEridge;
00768       newfacet->dupridge= True;
00769       if (!newfacet->normal)
00770         qh_setfacetplane(newfacet);
00771       qh_addhash(newfacet, qh hash_table, hashsize, hash);
00772       (*hashcount)++;
00773       if (!facet->normal)
00774         qh_setfacetplane(facet);
00775       if (matchfacet != qh_DUPLICATEridge) {
00776         SETelem_(facet->neighbors, skip)= qh_DUPLICATEridge;
00777         facet->dupridge= True;
00778         if (!facet->normal)
00779           qh_setfacetplane(facet);
00780         if (matchfacet) {
00781           matchskip= qh_setindex(matchfacet->neighbors, facet);
00782           SETelem_(matchfacet->neighbors, matchskip)= qh_DUPLICATEridge;
00783           matchfacet->dupridge= True;
00784           if (!matchfacet->normal)
00785             qh_setfacetplane(matchfacet);
00786           qh_addhash(matchfacet, qh hash_table, hashsize, hash);
00787           *hashcount += 2;
00788         }
00789       }
00790       trace4((qh ferr, 4052, "qh_matchneighbor: new f%d skip %d duplicates ridge for f%d skip %d matching f%d ismatch %d at hash %d\n",
00791            newfacet->id, newskip, facet->id, skip,
00792            (matchfacet == qh_DUPLICATEridge ? -2 : getid_(matchfacet)),
00793            ismatch, hash));
00794       return; /* end of duplicate ridge */
00795     }
00796   }
00797   if (!newfound)
00798     SETelem_(qh hash_table, scan)= newfacet;  /* same as qh_addhash */
00799   (*hashcount)++;
00800   trace4((qh ferr, 4053, "qh_matchneighbor: no match for f%d skip %d at hash %d\n",
00801            newfacet->id, newskip, hash));
00802 } /* matchneighbor */
00803 
00804 
00805 /*-<a                             href="qh-poly.htm#TOC"
00806   >-------------------------------</a><a name="matchnewfacets">-</a>
00807 
00808   qh_matchnewfacets()
00809     match newfacets in qh.newfacet_list to their newfacet neighbors
00810 
00811   returns:
00812     qh.newfacet_list with full neighbor sets
00813       get vertices with nth neighbor by deleting nth vertex
00814     if qh.PREmerge/MERGEexact or qh.FORCEoutput
00815       sets facet->flippped if flipped normal (also prevents point partitioning)
00816     if duplicate ridges and qh.PREmerge/MERGEexact
00817       sets facet->dupridge
00818       missing neighbor links identifies extra ridges to be merging (qh_MERGEridge)
00819 
00820   notes:
00821     newfacets already have neighbor[0] (horizon facet)
00822     assumes qh.hash_table is NULL
00823     vertex->neighbors has not been updated yet
00824     do not allocate memory after qh.hash_table (need to free it cleanly)
00825 
00826   design:
00827     delete neighbor sets for all new facets
00828     initialize a hash table
00829     for all new facets
00830       match facet with neighbors
00831     if unmatched facets (due to duplicate ridges)
00832       for each new facet with a duplicate ridge
00833         match it with a facet
00834     check for flipped facets
00835 */
00836 void qh_matchnewfacets(void /* qh newfacet_list */) {
00837   int numnew=0, hashcount=0, newskip;
00838   facetT *newfacet, *neighbor;
00839   int dim= qh hull_dim, hashsize, neighbor_i, neighbor_n;
00840   setT *neighbors;
00841 #ifndef qh_NOtrace
00842   int facet_i, facet_n, numfree= 0;
00843   facetT *facet;
00844 #endif
00845 
00846   trace1((qh ferr, 1019, "qh_matchnewfacets: match neighbors for new facets.\n"));
00847   FORALLnew_facets {
00848     numnew++;
00849     {  /* inline qh_setzero(newfacet->neighbors, 1, qh hull_dim); */
00850       neighbors= newfacet->neighbors;
00851       neighbors->e[neighbors->maxsize].i= dim+1; /*may be overwritten*/
00852       memset((char *)SETelemaddr_(neighbors, 1, void), 0, dim * SETelemsize);
00853     }
00854   }
00855 
00856   qh_newhashtable(numnew*(qh hull_dim-1)); /* twice what is normally needed,
00857                                      but every ridge could be DUPLICATEridge */
00858   hashsize= qh_setsize(qh hash_table);
00859   FORALLnew_facets {
00860     for (newskip=1; newskip<qh hull_dim; newskip++) /* furthest/horizon already matched */
00861       qh_matchneighbor(newfacet, newskip, hashsize, &hashcount);
00862 #if 0   /* use the following to trap hashcount errors */
00863     {
00864       int count= 0, k;
00865       facetT *facet, *neighbor;
00866 
00867       count= 0;
00868       FORALLfacet_(qh newfacet_list) {  /* newfacet already in use */
00869         for (k=1; k < qh hull_dim; k++) {
00870           neighbor= SETelemt_(facet->neighbors, k, facetT);
00871           if (!neighbor || neighbor == qh_DUPLICATEridge)
00872             count++;
00873         }
00874         if (facet == newfacet)
00875           break;
00876       }
00877       if (count != hashcount) {
00878         qh_fprintf(qh ferr, 8088, "qh_matchnewfacets: after adding facet %d, hashcount %d != count %d\n",
00879                  newfacet->id, hashcount, count);
00880         qh_errexit(qh_ERRqhull, newfacet, NULL);
00881       }
00882     }
00883 #endif  /* end of trap code */
00884   }
00885   if (hashcount) {
00886     FORALLnew_facets {
00887       if (newfacet->dupridge) {
00888         FOREACHneighbor_i_(newfacet) {
00889           if (neighbor == qh_DUPLICATEridge) {
00890             qh_matchduplicates(newfacet, neighbor_i, hashsize, &hashcount);
00891                     /* this may report MERGEfacet */
00892           }
00893         }
00894       }
00895     }
00896   }
00897   if (hashcount) {
00898     qh_fprintf(qh ferr, 6108, "qhull internal error (qh_matchnewfacets): %d neighbors did not match up\n",
00899         hashcount);
00900     qh_printhashtable(qh ferr);
00901     qh_errexit(qh_ERRqhull, NULL, NULL);
00902   }
00903 #ifndef qh_NOtrace
00904   if (qh IStracing >= 2) {
00905     FOREACHfacet_i_(qh hash_table) {
00906       if (!facet)
00907         numfree++;
00908     }
00909     qh_fprintf(qh ferr, 8089, "qh_matchnewfacets: %d new facets, %d unused hash entries .  hashsize %d\n",
00910              numnew, numfree, qh_setsize(qh hash_table));
00911   }
00912 #endif /* !qh_NOtrace */
00913   qh_setfree(&qh hash_table);
00914   if (qh PREmerge || qh MERGEexact) {
00915     if (qh IStracing >= 4)
00916       qh_printfacetlist(qh newfacet_list, NULL, qh_ALL);
00917     FORALLnew_facets {
00918       if (newfacet->normal)
00919         qh_checkflipped(newfacet, NULL, qh_ALL);
00920     }
00921   }else if (qh FORCEoutput)
00922     qh_checkflipped_all(qh newfacet_list);  /* prints warnings for flipped */
00923 } /* matchnewfacets */
00924 
00925 
00926 /*-<a                             href="qh-poly.htm#TOC"
00927   >-------------------------------</a><a name="matchvertices">-</a>
00928 
00929   qh_matchvertices( firstindex, verticesA, skipA, verticesB, skipB, same )
00930     tests whether vertices match with a single skip
00931     starts match at firstindex since all new facets have a common vertex
00932 
00933   returns:
00934     true if matched vertices
00935     skip index for each set
00936     sets same iff vertices have the same orientation
00937 
00938   notes:
00939     assumes skipA is in A and both sets are the same size
00940 
00941   design:
00942     set up pointers
00943     scan both sets checking for a match
00944     test orientation
00945 */
00946 boolT qh_matchvertices(int firstindex, setT *verticesA, int skipA,
00947        setT *verticesB, int *skipB, boolT *same) {
00948   vertexT **elemAp, **elemBp, **skipBp=NULL, **skipAp;
00949 
00950   elemAp= SETelemaddr_(verticesA, firstindex, vertexT);
00951   elemBp= SETelemaddr_(verticesB, firstindex, vertexT);
00952   skipAp= SETelemaddr_(verticesA, skipA, vertexT);
00953   do if (elemAp != skipAp) {
00954     while (*elemAp != *elemBp++) {
00955       if (skipBp)
00956         return False;
00957       skipBp= elemBp;  /* one extra like FOREACH */
00958     }
00959   }while (*(++elemAp));
00960   if (!skipBp)
00961     skipBp= ++elemBp;
00962   *skipB= SETindex_(verticesB, skipB); /* i.e., skipBp - verticesB */
00963   *same= !((skipA & 0x1) ^ (*skipB & 0x1)); /* result is 0 or 1 */
00964   trace4((qh ferr, 4054, "qh_matchvertices: matched by skip %d(v%d) and skip %d(v%d) same? %d\n",
00965           skipA, (*skipAp)->id, *skipB, (*(skipBp-1))->id, *same));
00966   return(True);
00967 } /* matchvertices */
00968 
00969 /*-<a                             href="qh-poly.htm#TOC"
00970   >-------------------------------</a><a name="newfacet">-</a>
00971 
00972   qh_newfacet()
00973     return a new facet
00974 
00975   returns:
00976     all fields initialized or cleared   (NULL)
00977     preallocates neighbors set
00978 */
00979 facetT *qh_newfacet(void) {
00980   facetT *facet;
00981   void **freelistp; /* used !qh_NOmem */
00982 
00983   qh_memalloc_((int)sizeof(facetT), freelistp, facet, facetT);
00984   memset((char *)facet, (size_t)0, sizeof(facetT));
00985   if (qh facet_id == qh tracefacet_id)
00986     qh tracefacet= facet;
00987   facet->id= qh facet_id++;
00988   facet->neighbors= qh_setnew(qh hull_dim);
00989 #if !qh_COMPUTEfurthest
00990   facet->furthestdist= 0.0;
00991 #endif
00992 #if qh_MAXoutside
00993   if (qh FORCEoutput && qh APPROXhull)
00994     facet->maxoutside= qh MINoutside;
00995   else
00996     facet->maxoutside= qh DISTround;
00997 #endif
00998   facet->simplicial= True;
00999   facet->good= True;
01000   facet->newfacet= True;
01001   trace4((qh ferr, 4055, "qh_newfacet: created facet f%d\n", facet->id));
01002   return(facet);
01003 } /* newfacet */
01004 
01005 
01006 /*-<a                             href="qh-poly.htm#TOC"
01007   >-------------------------------</a><a name="newridge">-</a>
01008 
01009   qh_newridge()
01010     return a new ridge
01011 */
01012 ridgeT *qh_newridge(void) {
01013   ridgeT *ridge;
01014   void **freelistp;   /* used !qh_NOmem */
01015 
01016   qh_memalloc_((int)sizeof(ridgeT), freelistp, ridge, ridgeT);
01017   memset((char *)ridge, (size_t)0, sizeof(ridgeT));
01018   zinc_(Ztotridges);
01019   if (qh ridge_id == 0xFFFFFF) {
01020     qh_fprintf(qh ferr, 7074, "\
01021 qhull warning: more than %d ridges.  ID field overflows and two ridges\n\
01022 may have the same identifier.  Otherwise output ok.\n", 0xFFFFFF);
01023   }
01024   ridge->id= qh ridge_id++;
01025   trace4((qh ferr, 4056, "qh_newridge: created ridge r%d\n", ridge->id));
01026   return(ridge);
01027 } /* newridge */
01028 
01029 
01030 /*-<a                             href="qh-poly.htm#TOC"
01031   >-------------------------------</a><a name="pointid">-</a>
01032 
01033   qh_pointid(  )
01034     return id for a point,
01035     returns -3 if null, -2 if interior, or -1 if not known
01036 
01037   alternative code:
01038     unsigned long id;
01039     id= ((unsigned long)point - (unsigned long)qh.first_point)/qh.normal_size;
01040 
01041   notes:
01042     WARN64 -- id truncated to 32-bits, at most 2G points
01043     NOerrors returned (QhullPoint::id)
01044     if point not in point array
01045       the code does a comparison of unrelated pointers.
01046 */
01047 int qh_pointid(pointT *point) {
01048   ptr_intT offset, id;
01049 
01050   if (!point)
01051     return -3;
01052   else if (point == qh interior_point)
01053     return -2;
01054   else if (point >= qh first_point
01055   && point < qh first_point + qh num_points * qh hull_dim) {
01056     offset= (ptr_intT)(point - qh first_point);
01057     id= offset / qh hull_dim;
01058   }else if ((id= qh_setindex(qh other_points, point)) != -1)
01059     id += qh num_points;
01060   else
01061     return -1;
01062   return (int)id;
01063 } /* pointid */
01064 
01065 /*-<a                             href="qh-poly.htm#TOC"
01066   >-------------------------------</a><a name="removefacet">-</a>
01067 
01068   qh_removefacet( facet )
01069     unlinks facet from qh.facet_list,
01070 
01071   returns:
01072     updates qh.facet_list .newfacet_list .facet_next visible_list
01073     decrements qh.num_facets
01074 
01075   see:
01076     qh_appendfacet
01077 */
01078 void qh_removefacet(facetT *facet) {
01079   facetT *next= facet->next, *previous= facet->previous;
01080 
01081   if (facet == qh newfacet_list)
01082     qh newfacet_list= next;
01083   if (facet == qh facet_next)
01084     qh facet_next= next;
01085   if (facet == qh visible_list)
01086     qh visible_list= next;
01087   if (previous) {
01088     previous->next= next;
01089     next->previous= previous;
01090   }else {  /* 1st facet in qh facet_list */
01091     qh facet_list= next;
01092     qh facet_list->previous= NULL;
01093   }
01094   qh num_facets--;
01095   trace4((qh ferr, 4057, "qh_removefacet: remove f%d from facet_list\n", facet->id));
01096 } /* removefacet */
01097 
01098 
01099 /*-<a                             href="qh-poly.htm#TOC"
01100   >-------------------------------</a><a name="removevertex">-</a>
01101 
01102   qh_removevertex( vertex )
01103     unlinks vertex from qh.vertex_list,
01104 
01105   returns:
01106     updates qh.vertex_list .newvertex_list
01107     decrements qh.num_vertices
01108 */
01109 void qh_removevertex(vertexT *vertex) {
01110   vertexT *next= vertex->next, *previous= vertex->previous;
01111 
01112   if (vertex == qh newvertex_list)
01113     qh newvertex_list= next;
01114   if (previous) {
01115     previous->next= next;
01116     next->previous= previous;
01117   }else {  /* 1st vertex in qh vertex_list */
01118     qh vertex_list= vertex->next;
01119     qh vertex_list->previous= NULL;
01120   }
01121   qh num_vertices--;
01122   trace4((qh ferr, 4058, "qh_removevertex: remove v%d from vertex_list\n", vertex->id));
01123 } /* removevertex */
01124 
01125 
01126 /*-<a                             href="qh-poly.htm#TOC"
01127   >-------------------------------</a><a name="updatevertices">-</a>
01128 
01129   qh_updatevertices()
01130     update vertex neighbors and delete interior vertices
01131 
01132   returns:
01133     if qh.VERTEXneighbors, updates neighbors for each vertex
01134       if qh.newvertex_list,
01135          removes visible neighbors  from vertex neighbors
01136       if qh.newfacet_list
01137          adds new facets to vertex neighbors
01138     if qh.visible_list
01139        interior vertices added to qh.del_vertices for later partitioning
01140 
01141   design:
01142     if qh.VERTEXneighbors
01143       deletes references to visible facets from vertex neighbors
01144       appends new facets to the neighbor list for each vertex
01145       checks all vertices of visible facets
01146         removes visible facets from neighbor lists
01147         marks unused vertices for deletion
01148 */
01149 void qh_updatevertices(void /*qh newvertex_list, newfacet_list, visible_list*/) {
01150   facetT *newfacet= NULL, *neighbor, **neighborp, *visible;
01151   vertexT *vertex, **vertexp;
01152 
01153   trace3((qh ferr, 3013, "qh_updatevertices: delete interior vertices and update vertex->neighbors\n"));
01154   if (qh VERTEXneighbors) {
01155     FORALLvertex_(qh newvertex_list) {
01156       FOREACHneighbor_(vertex) {
01157         if (neighbor->visible)
01158           SETref_(neighbor)= NULL;
01159       }
01160       qh_setcompact(vertex->neighbors);
01161     }
01162     FORALLnew_facets {
01163       FOREACHvertex_(newfacet->vertices)
01164         qh_setappend(&vertex->neighbors, newfacet);
01165     }
01166     FORALLvisible_facets {
01167       FOREACHvertex_(visible->vertices) {
01168         if (!vertex->newlist && !vertex->deleted) {
01169           FOREACHneighbor_(vertex) { /* this can happen under merging */
01170             if (!neighbor->visible)
01171               break;
01172           }
01173           if (neighbor)
01174             qh_setdel(vertex->neighbors, visible);
01175           else {
01176             vertex->deleted= True;
01177             qh_setappend(&qh del_vertices, vertex);
01178             trace2((qh ferr, 2041, "qh_updatevertices: delete vertex p%d(v%d) in f%d\n",
01179                   qh_pointid(vertex->point), vertex->id, visible->id));
01180           }
01181         }
01182       }
01183     }
01184   }else {  /* !VERTEXneighbors */
01185     FORALLvisible_facets {
01186       FOREACHvertex_(visible->vertices) {
01187         if (!vertex->newlist && !vertex->deleted) {
01188           vertex->deleted= True;
01189           qh_setappend(&qh del_vertices, vertex);
01190           trace2((qh ferr, 2042, "qh_updatevertices: delete vertex p%d(v%d) in f%d\n",
01191                   qh_pointid(vertex->point), vertex->id, visible->id));
01192         }
01193       }
01194     }
01195   }
01196 } /* updatevertices */
01197 
01198 
01199