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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */