00052              {  /* in sort order for facet_mergeset */
00053   MRGnone= 0,
00054   MRGcoplanar,          /* centrum coplanar */
00055   MRGanglecoplanar,     /* angle coplanar */
00056                         /* could detect half concave ridges */
00057   MRGconcave,           /* concave ridge */
00058   MRGflip,              /* flipped facet. facet1 == facet2 */
00059   MRGridge,             /* duplicate ridge (qh_MERGEridge) */
00060                         /* degen and redundant go onto degen_mergeset */
00061   MRGdegen,             /* degenerate facet (not enough neighbors) facet1 == facet2 */
00062   MRGredundant,         /* redundant facet (vertex subset) */
00063                         /* merge_degenredundant assumes degen < redundant */
00064   ENDmrg
00065 } mergeType;

00220                                                         {
00221   facetT *facet1, *facet2;
00222   mergeT *merge;
00223   boolT wasmerge= True, isreduce;
00224   void **freelistp;  /* used !qh_NOmem */
00225   vertexT *vertex;
00226   mergeType mergetype;
00227   int numcoplanar=0, numconcave=0, numdegenredun= 0, numnewmerges= 0;
00228   
00229   trace2((qh ferr, "qh_all_merges: starting to merge facets beginning from f%d\n",
00230             getid_(qh newfacet_list)));
00231   while (True) {
00232     wasmerge= False;
00233     while (qh_setsize (qh facet_mergeset)) {
00234       while ((merge= (mergeT*)qh_setdellast(qh facet_mergeset))) {
00235         facet1= merge->facet1;
00236         facet2= merge->facet2;
00237         mergetype= merge->type;
00238         qh_memfree_(merge, sizeof(mergeT), freelistp);
00239         if (facet1->visible || facet2->visible) /*deleted facet*/
00240           continue;  
00241         if ((facet1->newfacet && !facet1->tested)
00242                 || (facet2->newfacet && !facet2->tested)) {
00243           if (qh MERGEindependent && mergetype <= MRGanglecoplanar)
00244             continue;      /* perform independent sets of merges */
00245         }
00246         qh_merge_nonconvex (facet1, facet2, mergetype);
00247         numdegenredun += qh_merge_degenredundant();
00248         numnewmerges++;
00249         wasmerge= True;
00250         if (mergetype == MRGconcave)
00251           numconcave++;
00252         else /* MRGcoplanar or MRGanglecoplanar */
00253           numcoplanar++;
00254       } /* while setdellast */
00255       if (qh POSTmerging && qh hull_dim <= qh_DIMreduceBuild 
00256       && numnewmerges > qh_MAXnewmerges) {
00257         numnewmerges= 0;
00258         qh_reducevertices();  /* otherwise large post merges too slow */
00259       }
00260       qh_getmergeset (qh newfacet_list); /* facet_mergeset */
00261     } /* while mergeset */
00262     if (qh VERTEXneighbors) {
00263       isreduce= False;
00264       if (qh hull_dim >=4 && qh POSTmerging) {
00265         FORALLvertices  
00266           vertex->delridge= True;
00267         isreduce= True;
00268       }
00269       if ((wasmerge || othermerge) && (!qh MERGEexact || qh POSTmerging) 
00270           && qh hull_dim <= qh_DIMreduceBuild) {
00271         othermerge= False;
00272         isreduce= True;
00273       }
00274       if (isreduce) {
00275         if (qh_reducevertices()) {
00276           qh_getmergeset (qh newfacet_list); /* facet_mergeset */
00277           continue;
00278         }
00279       }
00280     }
00281     if (vneighbors && qh_test_vneighbors(/* qh newfacet_list */)) 
00282       continue;
00283     break;
00284   } /* while (True) */
00285   if (qh CHECKfrequently && !qh MERGEexact) {
00286     qh old_randomdist= qh RANDOMdist;
00287     qh RANDOMdist= False;
00288     qh_checkconvex (qh newfacet_list, qh_ALGORITHMfault);
00289     /* qh_checkconnect (); [this is slow and it changes the facet order] */
00290     qh RANDOMdist= qh old_randomdist;
00291   }
00292   trace1((qh ferr, "qh_all_merges: merged %d coplanar facets %d concave facets and %d degen or redundant facets.\n",
00293     numcoplanar, numconcave, numdegenredun));
00294   if (qh IStracing >= 4 && qh num_facets < 50)
00295     qh_printlists ();
00296 } /* all_merges */

00325                                                                                            {
00326   mergeT *merge, *lastmerge;
00327   void **freelistp; /* used !qh_NOmem */
00328 
00329   if (facet->redundant)
00330     return;
00331   if (facet->degenerate && mergetype == MRGdegen)
00332     return;
00333   qh_memalloc_(sizeof(mergeT), freelistp, merge, mergeT);
00334   merge->facet1= facet;
00335   merge->facet2= neighbor;
00336   merge->type= mergetype;
00337   if (angle && qh ANGLEmerge)
00338     merge->angle= *angle;
00339   if (mergetype < MRGdegen)
00340     qh_setappend (&(qh facet_mergeset), merge);
00341   else if (mergetype == MRGdegen) {
00342     facet->degenerate= True;
00343     if (!(lastmerge= (mergeT*)qh_setlast (qh degen_mergeset)) 
00344     || lastmerge->type == MRGdegen)
00345       qh_setappend (&(qh degen_mergeset), merge);
00346     else
00347       qh_setaddnth (&(qh degen_mergeset), 0, merge);
00348   }else { /* mergetype == MRGredundant */
00349     facet->redundant= True;
00350     qh_setappend (&(qh degen_mergeset), merge);
00351   }
00352 } /* appendmergeset */

00375                                           {
00376   facetT *same;
00377   vertexT *apex, *vertex, **vertexp;
00378   setT *vertices= qh_settemp (qh TEMPsize);
00379   
00380   apex= SETfirstt_(samecycle->vertices, vertexT);
00381   apex->visitid= ++qh vertex_visit;
00382   FORALLsame_cycle_(samecycle) {
00383     if (same->mergeridge)
00384       continue;
00385     FOREACHvertex_(same->vertices) {
00386       if (vertex->visitid != qh vertex_visit) {
00387         qh_setappend (&vertices, vertex);
00388         vertex->visitid= qh vertex_visit;
00389         vertex->seen= False;
00390       }
00391     }
00392   }
00393   trace4((qh ferr, "qh_basevertices: found %d vertices\n", 
00394          qh_setsize (vertices)));
00395   return vertices;
00396 } /* basevertices */

00416                                                    {
00417   facetT *facet, *newfacet, *errfacet= NULL, *neighbor, **neighborp;
00418 
00419   facet= qh newfacet_list;
00420   qh_removefacet (facet);
00421   qh_appendfacet (facet);
00422   facet->visitid= ++qh visit_id;
00423   FORALLfacet_(facet) {
00424     FOREACHneighbor_(facet) {
00425       if (neighbor->visitid != qh visit_id) {
00426         qh_removefacet (neighbor);
00427         qh_appendfacet (neighbor);
00428         neighbor->visitid= qh visit_id;
00429       }
00430     }
00431   }
00432   FORALLnew_facets {
00433     if (newfacet->visitid == qh visit_id)
00434       break;
00435     fprintf(qh ferr, "qhull error: f%d is not attached to the new facets\n",
00436          newfacet->id);
00437     errfacet= newfacet;
00438   }
00439   if (errfacet)
00440     qh_errexit (qh_ERRqhull, errfacet, NULL);
00441 } /* checkconnect */

00479                                    {
00480   facetT *facet, *neighbor, **neighborp;
00481   facetT *horizon, *facetlist;
00482   int neighbor_i;
00483   vertexT *vertex, **vertexp;
00484   realT dist;
00485 
00486   if (testall) 
00487     facetlist= qh facet_list;
00488   else {
00489     facetlist= qh newfacet_list;
00490     FORALLfacet_(facetlist) {
00491       horizon= SETfirstt_(facet->neighbors, facetT);
00492       if (!horizon->simplicial)
00493         goto LABELproblem;
00494       if (facet->flipped || facet->dupridge || !facet->normal)
00495         goto LABELproblem;
00496     }
00497     if (qh MERGEexact && qh ZEROall_ok) {
00498       trace2((qh ferr, "qh_checkzero: skip convexity check until first pre-merge\n"));
00499       return True;
00500     }
00501   }
00502   FORALLfacet_(facetlist) {
00503     qh vertex_visit++;
00504     neighbor_i= 0;
00505     horizon= NULL;
00506     FOREACHneighbor_(facet) {
00507       if (!neighbor_i && !testall) {
00508         horizon= neighbor;
00509         neighbor_i++;
00510         continue; /* horizon facet tested in qh_findhorizon */
00511       }
00512       vertex= SETelemt_(facet->vertices, neighbor_i++, vertexT);
00513       vertex->visitid= qh vertex_visit;
00514       zzinc_(Zdistzero);
00515       qh_distplane (vertex->point, neighbor, &dist);
00516       if (dist >= -qh DISTround) {
00517         qh ZEROall_ok= False;
00518         if (!qh MERGEexact || testall || dist > qh DISTround)
00519           goto LABELnonconvex;
00520       }
00521     }
00522     if (!testall) {
00523       FOREACHvertex_(horizon->vertices) {
00524         if (vertex->visitid != qh vertex_visit) {
00525           zzinc_(Zdistzero);
00526           qh_distplane (vertex->point, facet, &dist);
00527           if (dist >= -qh DISTround) {
00528             qh ZEROall_ok= False;
00529             if (!qh MERGEexact || dist > qh DISTround)
00530               goto LABELnonconvex;
00531           }
00532           break;
00533         }
00534       }
00535     }
00536   }
00537   trace2((qh ferr, "qh_checkzero: testall %d, facets are %s\n", testall,
00538         (qh MERGEexact && !testall) ? 
00539            "not concave, flipped, or duplicate ridged" : "clearly convex"));
00540   return True;
00541 
00542  LABELproblem:
00543   qh ZEROall_ok= False;
00544   trace2((qh ferr, "qh_checkzero: facet f%d needs pre-merging\n",
00545        facet->id));
00546   return False;
00547 
00548  LABELnonconvex:
00549   trace2((qh ferr, "qh_checkzero: facet f%d and f%d are not clearly convex.  v%d dist %.2g\n",
00550          facet->id, neighbor->id, vertex->id, dist));
00551   return False;
00552 } /* checkzero */

00604                                         {
00605   facetT *facet, *otherfacet;
00606   ridgeT *ridge, **ridgep;
00607 
00608   facet= atridge->top;
00609   otherfacet= atridge->bottom;
00610   FOREACHridge_(facet->ridges) {
00611     if (otherfacet == otherfacet_(ridge, facet) && ridge != atridge) {
00612       ridge->nonconvex= True;
00613       trace4((qh ferr, "qh_copynonconvex: moved nonconvex flag from r%d to r%d\n",
00614               atridge->id, ridge->id));
00615       break;
00616     }
00617   }
00618 } /* copynonconvex */

00638                                               {
00639   vertexT *vertex, **vertexp;
00640   facetT *neighbor, **neighborp;
00641 
00642   trace4((qh ferr, "qh_degen_redundant_facet: test facet f%d for degen/redundant\n",
00643           facet->id));
00644   FOREACHneighbor_(facet) {
00645     qh vertex_visit++;
00646     FOREACHvertex_(neighbor->vertices)
00647       vertex->visitid= qh vertex_visit;
00648     FOREACHvertex_(facet->vertices) {
00649       if (vertex->visitid != qh vertex_visit)
00650         break;
00651     }
00652     if (!vertex) {
00653       qh_appendmergeset (facet, neighbor, MRGredundant, NULL);
00654       trace2((qh ferr, "qh_degen_redundant_facet: f%d is contained in f%d.  merge\n", facet->id, neighbor->id)); 
00655       return;
00656     }
00657   }
00658   if (qh_setsize (facet->neighbors) < qh hull_dim) {
00659     qh_appendmergeset (facet, facet, MRGdegen, NULL);
00660     trace2((qh ferr, "qh_degen_redundant_neighbors: f%d is degenerate.\n", facet->id));
00661   }
00662 } /* degen_redundant_facet */

00694                                                                     {
00695   vertexT *vertex, **vertexp;
00696   facetT *neighbor, **neighborp;
00697   int size;
00698 
00699   trace4((qh ferr, "qh_degen_redundant_neighbors: test neighbors of f%d with delfacet f%d\n", 
00700           facet->id, getid_(delfacet)));
00701   if ((size= qh_setsize (facet->neighbors)) < qh hull_dim) {
00702     qh_appendmergeset (facet, facet, MRGdegen, NULL);
00703     trace2((qh ferr, "qh_degen_redundant_neighbors: f%d is degenerate with %d neighbors.\n", facet->id, size));
00704   }
00705   if (!delfacet)
00706     delfacet= facet;
00707   qh vertex_visit++;
00708   FOREACHvertex_(facet->vertices)
00709     vertex->visitid= qh vertex_visit;
00710   FOREACHneighbor_(delfacet) {
00711     /* uses early out instead of checking vertex count */
00712     if (neighbor == facet)
00713       continue;
00714     FOREACHvertex_(neighbor->vertices) {
00715       if (vertex->visitid != qh vertex_visit)
00716         break;
00717     }
00718     if (!vertex) {
00719       qh_appendmergeset (neighbor, facet, MRGredundant, NULL);
00720       trace2((qh ferr, "qh_degen_redundant_neighbors: f%d is contained in f%d.  merge\n", neighbor->id, facet->id)); 
00721     }
00722   }
00723   FOREACHneighbor_(delfacet) {   /* redundant merges occur first */
00724     if (neighbor == facet)
00725       continue;
00726     if ((size= qh_setsize (neighbor->neighbors)) < qh hull_dim) {
00727       qh_appendmergeset (neighbor, neighbor, MRGdegen, NULL);
00728       trace2((qh ferr, "qh_degen_redundant_neighbors: f%d is degenerate with %d neighbors.  Neighbor of f%d.\n", neighbor->id, size, facet->id)); 
00729     }
00730   }
00731 } /* degen_redundant_neighbors */

00764                                                                               {
00765   vertexT *vertex, **vertexp;
00766   setT *newridges;
00767   ridgeT *ridge, **ridgep;
00768   int size, hashsize;
00769   int hash;
00770 
00771 #ifndef qh_NOtrace
00772   if (qh IStracing >= 4) {
00773     fprintf (qh ferr, "qh_find_newvertex: find new vertex for v%d from ",
00774              oldvertex->id);
00775     FOREACHvertex_(vertices) 
00776       fprintf (qh ferr, "v%d ", vertex->id);
00777     FOREACHridge_(ridges)
00778       fprintf (qh ferr, "r%d ", ridge->id);
00779     fprintf (qh ferr, "\n");
00780   }
00781 #endif
00782   FOREACHvertex_(vertices) 
00783     vertex->visitid= 0;
00784   FOREACHridge_(ridges) {
00785     FOREACHvertex_(ridge->vertices) 
00786       vertex->visitid++;
00787   }
00788   FOREACHvertex_(vertices) {
00789     if (!vertex->visitid) {
00790       qh_setdelnth (vertices, SETindex_(vertices,vertex));
00791       vertexp--; /* repeat since deleted this vertex */
00792     }
00793   }
00794   qh vertex_visit += qh_setsize (ridges);
00795   if (!qh_setsize (vertices)) {
00796     trace4((qh ferr, "qh_find_newvertex: vertices not in ridges for v%d\n",
00797             oldvertex->id));
00798     return NULL;
00799   }
00800   qsort (SETaddr_(vertices, vertexT), qh_setsize (vertices),
00801                 sizeof (vertexT *), qh_comparevisit);
00802   /* can now use qh vertex_visit */
00803   if (qh PRINTstatistics) {
00804     size= qh_setsize (vertices);
00805     zinc_(Zintersect);
00806     zadd_(Zintersecttot, size);
00807     zmax_(Zintersectmax, size);
00808   }
00809   hashsize= qh_newhashtable (qh_setsize (ridges));
00810   FOREACHridge_(ridges)
00811     qh_hashridge (qh hash_table, hashsize, ridge, oldvertex);
00812   FOREACHvertex_(vertices) {
00813     newridges= qh_vertexridges (vertex);
00814     FOREACHridge_(newridges) {
00815       if (qh_hashridge_find (qh hash_table, hashsize, ridge, vertex, oldvertex, &hash)) {
00816         zinc_(Zdupridge);
00817         break;
00818       }
00819     }
00820     qh_settempfree (&newridges);
00821     if (!ridge)
00822       break;  /* found a rename */
00823   }
00824   if (vertex) {
00825     /* counted in qh_renamevertex */
00826     trace2((qh ferr, "qh_find_newvertex: found v%d for old v%d from %d vertices and %d ridges.\n",
00827       vertex->id, oldvertex->id, qh_setsize (vertices), qh_setsize (ridges)));
00828   }else {
00829     zinc_(Zfindfail);
00830     trace0((qh ferr, "qh_find_newvertex: no vertex for renaming v%d (all duplicated ridges) during p%d\n",
00831       oldvertex->id, qh furthest_id));
00832   }
00833   qh_setfree (&qh hash_table);
00834   return vertex;
00835 } /* find_newvertex */

00852                                                                           {
00853   realT dist, mindist, maxdist;
00854 
00855   if (testcentrum) {
00856     zzinc_(Zbestdist);
00857     qh_distplane(facet->center, neighbor, &dist);
00858     dist *= qh hull_dim; /* estimate furthest vertex */
00859     if (dist < 0) {
00860       maxdist= 0;
00861       mindist= dist;
00862       dist= -dist;
00863     }else
00864       maxdist= dist;
00865   }else
00866     dist= qh_getdistance (facet, neighbor, &mindist, &maxdist);
00867   if (dist < *distp) {
00868     *bestfacet= neighbor;
00869     *mindistp= mindist;
00870     *maxdistp= maxdist;
00871     *distp= dist;
00872   }
00873 } /* findbest_test */

00901                                                                                            {
00902   facetT *neighbor, **neighborp, *bestfacet= NULL;
00903   ridgeT *ridge, **ridgep;
00904   boolT nonconvex= True, testcentrum= False;
00905   int size= qh_setsize (facet->vertices);
00906 
00907   *distp= REALmax;
00908   if (size > qh_BESTcentrum2 * qh hull_dim + qh_BESTcentrum) {
00909     testcentrum= True;
00910     zinc_(Zbestcentrum);
00911     if (!facet->center)
00912        facet->center= qh_getcentrum (facet);
00913   }
00914   if (size > qh hull_dim + qh_BESTnonconvex) {
00915     FOREACHridge_(facet->ridges) {
00916       if (ridge->nonconvex) {
00917         neighbor= otherfacet_(ridge, facet);
00918         qh_findbest_test (testcentrum, facet, neighbor,
00919                           &bestfacet, distp, mindistp, maxdistp);
00920       }
00921     }
00922   }
00923   if (!bestfacet) {     
00924     nonconvex= False;
00925     FOREACHneighbor_(facet)
00926       qh_findbest_test (testcentrum, facet, neighbor,
00927                         &bestfacet, distp, mindistp, maxdistp);
00928   }
00929   if (!bestfacet) {
00930     fprintf (qh ferr, "qhull internal error (qh_findbestneighbor): no neighbors for f%d\n", facet->id);
00931     
00932     qh_errexit (qh_ERRqhull, facet, NULL);
00933   }
00934   if (testcentrum) 
00935     qh_getdistance (facet, bestfacet, mindistp, maxdistp);
00936   trace3((qh ferr, "qh_findbestneighbor: f%d is best neighbor for f%d testcentrum? %d nonconvex? %d dist %2.2g min %2.2g max %2.2g\n",
00937      bestfacet->id, facet->id, testcentrum, nonconvex, *distp, *mindistp, *maxdistp));
00938   return(bestfacet);
00939 } /* findbestneighbor */

00966                                                           {
00967   facetT *facet, *neighbor, *facet1;
00968   realT dist, mindist, maxdist;
00969   mergeT *merge, **mergep;
00970   setT *othermerges;
00971   int nummerge=0;
00972 
00973   trace4((qh ferr, "qh_flippedmerges: begin\n"));
00974   FORALLfacet_(facetlist) {
00975     if (facet->flipped && !facet->visible) 
00976       qh_appendmergeset (facet, facet, MRGflip, NULL);
00977   }
00978   othermerges= qh_settemppop(); /* was facet_mergeset */
00979   qh facet_mergeset= qh_settemp (qh TEMPsize);
00980   qh_settemppush (othermerges);
00981   FOREACHmerge_(othermerges) {
00982     facet1= merge->facet1;
00983     if (merge->type != MRGflip || facet1->visible) 
00984       continue;
00985     if (qh TRACEmerge-1 == zzval_(Ztotmerge))
00986       qhmem.IStracing= qh IStracing= qh TRACElevel;
00987     neighbor= qh_findbestneighbor (facet1, &dist, &mindist, &maxdist);
00988     trace0((qh ferr, "qh_flippedmerges: merge flipped f%d into f%d dist %2.2g during p%d\n",
00989       facet1->id, neighbor->id, dist, qh furthest_id));
00990     qh_mergefacet (facet1, neighbor, &mindist, &maxdist, !qh_MERGEapex);
00991     nummerge++;
00992     if (qh PRINTstatistics) {
00993       zinc_(Zflipped);
00994       wadd_(Wflippedtot, dist);
00995       wmax_(Wflippedmax, dist);
00996     }
00997     qh_merge_degenredundant();
00998   }
00999   FOREACHmerge_(othermerges) {
01000     if (merge->facet1->visible || merge->facet2->visible)
01001       qh_memfree (merge, sizeof(mergeT));
01002     else
01003       qh_setappend (&qh facet_mergeset, merge);
01004   }
01005   qh_settempfree (&othermerges);
01006   if (nummerge)
01007     *wasmerge= True;
01008   trace1((qh ferr, "qh_flippedmerges: merged %d flipped facets into a good neighbor\n", nummerge));
01009 } /* flippedmerges */

01039                                       {
01040   facetT *facet1, *facet2;
01041   mergeT *merge, **mergep;
01042   realT dist1, dist2, mindist1, mindist2, maxdist1, maxdist2;
01043   setT *othermerges;
01044   int nummerge=0, numflip=0;
01045 
01046   if (qh TRACEmerge-1 == zzval_(Ztotmerge))
01047     qhmem.IStracing= qh IStracing= qh TRACElevel;
01048   trace4((qh ferr, "qh_forcedmerges: begin\n"));  
01049   othermerges= qh_settemppop(); /* was facet_mergeset */
01050   qh facet_mergeset= qh_settemp (qh TEMPsize);
01051   qh_settemppush (othermerges);
01052   FOREACHmerge_(othermerges) {
01053     if (merge->type != MRGridge) 
01054         continue;
01055     facet1= merge->facet1;
01056     facet2= merge->facet2;
01057     while (facet1->visible)      /* must exist, no qh_merge_degenredunant */
01058       facet1= facet1->f.replace; /* previously merged facet */
01059     while (facet2->visible)
01060       facet2= facet2->f.replace; /* previously merged facet */
01061     if (facet1 == facet2)
01062       continue;
01063     if (!qh_setin (facet2->neighbors, facet1)) {
01064       fprintf (qh ferr, "qhull internal error (qh_forcedmerges): f%d and f%d had a duplicate ridge but as f%d and f%d they are no longer neighbors\n",
01065                merge->facet1->id, merge->facet2->id, facet1->id, facet2->id);
01066       qh_errexit2 (qh_ERRqhull, facet1, facet2);
01067     }
01068     if (qh TRACEmerge-1 == zzval_(Ztotmerge))
01069       qhmem.IStracing= qh IStracing= qh TRACElevel;
01070     dist1= qh_getdistance (facet1, facet2, &mindist1, &maxdist1);
01071     dist2= qh_getdistance (facet2, facet1, &mindist2, &maxdist2);
01072     trace0((qh ferr, "qh_forcedmerges: duplicate ridge between f%d and f%d, dist %2.2g and reverse dist %2.2g during p%d\n",
01073             facet1->id, facet2->id, dist1, dist2, qh furthest_id));
01074     if (dist1 < dist2) 
01075       qh_mergefacet (facet1, facet2, &mindist1, &maxdist1, !qh_MERGEapex);
01076     else {
01077       qh_mergefacet (facet2, facet1, &mindist2, &maxdist2, !qh_MERGEapex);
01078       dist1= dist2;
01079       facet1= facet2;
01080     }
01081     if (facet1->flipped) {
01082       zinc_(Zmergeflipdup);
01083       numflip++;
01084     }else
01085       nummerge++;
01086     if (qh PRINTstatistics) {
01087       zinc_(Zduplicate);
01088       wadd_(Wduplicatetot, dist1);
01089       wmax_(Wduplicatemax, dist1);
01090     }
01091   }
01092   FOREACHmerge_(othermerges) {
01093     if (merge->type == MRGridge)
01094       qh_memfree (merge, sizeof(mergeT));
01095     else
01096       qh_setappend (&qh facet_mergeset, merge);
01097   }
01098   qh_settempfree (&othermerges);
01099   if (nummerge)
01100     *wasmerge= True;
01101   trace1((qh ferr, "qh_forcedmerges: merged %d facets and %d flipped facets across duplicated ridges\n", 
01102                 nummerge, numflip));
01103 } /* forcedmerges */

01135                                        {
01136   facetT *facet, *neighbor, **neighborp;
01137   ridgeT *ridge, **ridgep;
01138   int nummerges;
01139   
01140   nummerges= qh_setsize (qh facet_mergeset);
01141   trace4((qh ferr, "qh_getmergeset: started.\n"));
01142   qh visit_id++;
01143   FORALLfacet_(facetlist) {
01144     if (facet->tested)
01145       continue;
01146     facet->visitid= qh visit_id;
01147     facet->tested= True;  /* must be non-simplicial due to merge */
01148     FOREACHneighbor_(facet)
01149       neighbor->seen= False;
01150     FOREACHridge_(facet->ridges) {
01151       if (ridge->tested && !ridge->nonconvex)
01152         continue;
01153       /* if tested & nonconvex, need to append merge */
01154       neighbor= otherfacet_(ridge, facet);
01155       if (neighbor->seen) {
01156         ridge->tested= True;
01157         ridge->nonconvex= False;
01158       }else if (neighbor->visitid != qh visit_id) {
01159         ridge->tested= True;
01160         ridge->nonconvex= False;
01161         neighbor->seen= True;      /* only one ridge is marked nonconvex */
01162         if (qh_test_appendmerge (facet, neighbor))
01163           ridge->nonconvex= True;
01164       }
01165     }
01166   }
01167   nummerges= qh_setsize (qh facet_mergeset);
01168   if (qh ANGLEmerge)
01169     qsort(SETaddr_(qh facet_mergeset, mergeT), nummerges,sizeof(mergeT *),qh_compareangle);
01170   else
01171     qsort(SETaddr_(qh facet_mergeset, mergeT), nummerges,sizeof(mergeT *),qh_comparemerge);
01172   if (qh POSTmerging) {
01173     zadd_(Zmergesettot2, nummerges);
01174   }else {
01175     zadd_(Zmergesettot, nummerges);
01176     zmax_(Zmergesetmax, nummerges);
01177   }
01178   trace2((qh ferr, "qh_getmergeset: %d merges found\n", nummerges));
01179 } /* getmergeset */

01208                                                 {
01209   facetT *facet, *neighbor, **neighborp;
01210   ridgeT *ridge, **ridgep;
01211   int nummerges;
01212 
01213   qh visit_id++;
01214   FORALLfacet_(facetlist) {
01215     facet->visitid= qh visit_id;
01216     facet->tested= True;
01217     FOREACHneighbor_(facet) {
01218       if (neighbor->visitid != qh visit_id) {
01219         if (qh_test_appendmerge (facet, neighbor)) {
01220           FOREACHridge_(neighbor->ridges) {
01221             if (facet == otherfacet_(ridge, neighbor)) {
01222               ridge->nonconvex= True;
01223               break;    /* only one ridge is marked nonconvex */
01224             }
01225           }
01226         }
01227       }
01228     }
01229     FOREACHridge_(facet->ridges)
01230       ridge->tested= True;
01231   }
01232   nummerges= qh_setsize (qh facet_mergeset);
01233   if (qh ANGLEmerge)
01234     qsort(SETaddr_(qh facet_mergeset, mergeT), nummerges,sizeof(mergeT *),qh_compareangle);
01235   else
01236     qsort(SETaddr_(qh facet_mergeset, mergeT), nummerges,sizeof(mergeT *),qh_comparemerge);
01237   if (qh POSTmerging) {
01238     zadd_(Zmergeinittot2, nummerges);
01239   }else {
01240     zadd_(Zmergeinittot, nummerges);
01241     zmax_(Zmergeinitmax, nummerges);
01242   }
01243   trace2((qh ferr, "qh_getmergeset_initial: %d merges found\n", nummerges));
01244 } /* getmergeset_initial */

01260                                                                                      {
01261   int hash;
01262   ridgeT *ridgeA;
01263 
01264   hash= (int)qh_gethash (hashsize, ridge->vertices, qh hull_dim-1, 0, oldvertex);
01265   while (True) {
01266     if (!(ridgeA= SETelemt_(hashtable, hash, ridgeT))) {
01267       SETelem_(hashtable, hash)= ridge;
01268       break;
01269     }else if (ridgeA == ridge)
01270       break;
01271     if (++hash == hashsize)
01272       hash= 0;
01273   }
01274 } /* hashridge */

01304                                                                   {
01305   int hash;
01306   ridgeT *ridgeA;
01307 
01308   *hashslot= 0;
01309   zinc_(Zhashridge);
01310   hash= (int)qh_gethash (hashsize, ridge->vertices, qh hull_dim-1, 0, vertex);
01311   while ((ridgeA= SETelemt_(hashtable, hash, ridgeT))) {
01312     if (ridgeA == ridge)
01313       *hashslot= -1;      
01314     else {
01315       zinc_(Zhashridgetest);
01316       if (qh_setequal_except (ridge->vertices, vertex, ridgeA->vertices, oldvertex))
01317         return ridgeA;
01318     }
01319     if (++hash == hashsize)
01320       hash= 0;
01321   }
01322   if (!*hashslot)
01323     *hashslot= hash;
01324   return NULL;
01325 } /* hashridge_find */

01354                                   {
01355   facetT *neighbor, **neighborp;
01356   ridgeT *ridge, **ridgep;
01357   int neighbor_i, neighbor_n;
01358   boolT toporient, mergeridge= False;
01359   
01360   if (!facet->simplicial)
01361     return;
01362   trace4((qh ferr, "qh_makeridges: make ridges for f%d\n", facet->id));
01363   facet->simplicial= False;
01364   FOREACHneighbor_(facet) {
01365     if (neighbor == qh_MERGEridge)
01366       mergeridge= True;
01367     else
01368       neighbor->seen= False;
01369   }
01370   FOREACHridge_(facet->ridges)
01371     otherfacet_(ridge, facet)->seen= True;
01372   FOREACHneighbor_i_(facet) {
01373     if (neighbor == qh_MERGEridge)
01374       continue;  /* fixed by qh_mark_dupridges */
01375     else if (!neighbor->seen) {  /* no current ridges */
01376       ridge= qh_newridge();
01377       ridge->vertices= qh_setnew_delnthsorted (facet->vertices, qh hull_dim,
01378                                                           neighbor_i, 0);
01379       toporient= facet->toporient ^ (neighbor_i & 0x1);
01380       if (toporient) {
01381         ridge->top= facet;
01382         ridge->bottom= neighbor;
01383       }else {
01384         ridge->top= neighbor;
01385         ridge->bottom= facet;
01386       }
01387 #if 0 /* this also works */
01388       flip= (facet->toporient ^ neighbor->toporient)^(skip1 & 0x1) ^ (skip2 & 0x1);
01389       if (facet->toporient ^ (skip1 & 0x1) ^ flip) {
01390         ridge->top= neighbor;
01391         ridge->bottom= facet;
01392       }else {
01393         ridge->top= facet;
01394         ridge->bottom= neighbor;
01395       }
01396 #endif
01397       qh_setappend(&(facet->ridges), ridge);
01398       qh_setappend(&(neighbor->ridges), ridge);
01399     }
01400   }
01401   if (mergeridge) {
01402     while (qh_setdel (facet->neighbors, qh_MERGEridge))
01403       ; /* delete each one */
01404   }
01405 } /* makeridges */

01444                                           {
01445   facetT *facet, *neighbor, **neighborp;
01446   int nummerge=0;
01447   mergeT *merge, **mergep;
01448   
01449 
01450   trace4((qh ferr, "qh_mark_dupridges: identify duplicate ridges\n"));  
01451   FORALLfacet_(facetlist) {
01452     if (facet->dupridge) {
01453       FOREACHneighbor_(facet) {
01454         if (neighbor == qh_MERGEridge) {
01455           facet->mergeridge= True;
01456           continue;
01457         }
01458         if (neighbor->dupridge
01459         && !qh_setin (neighbor->neighbors, facet)) { /* qh_MERGEridge */
01460           qh_appendmergeset (facet, neighbor, MRGridge, NULL);
01461           facet->mergeridge2= True;
01462           facet->mergeridge= True;
01463           nummerge++;
01464         }
01465       }
01466     }
01467   }
01468   if (!nummerge)
01469     return;
01470   FORALLfacet_(facetlist) {            /* gets rid of qh_MERGEridge */
01471     if (facet->mergeridge && !facet->mergeridge2)   
01472       qh_makeridges (facet);
01473   }
01474   FOREACHmerge_(qh facet_mergeset) {   /* restore the missing neighbors */
01475     if (merge->type == MRGridge) {
01476       qh_setappend (&merge->facet2->neighbors, merge->facet1);
01477       qh_makeridges (merge->facet1);   /* and the missing ridges */
01478     }
01479   }
01480   trace1((qh ferr, "qh_mark_dupridges: found %d duplicated ridges\n", 
01481                 nummerge));
01482 } /* mark_dupridges */

01508                                         {
01509   ridgeT *ridge, **ridgep;
01510   realT angledegen= qh_ANGLEdegen;
01511   facetT *neighbor, **neighborp;
01512 
01513   qh visit_id++;
01514   trace4((qh ferr, "qh_maydropneighbor: test f%d for no ridges to a neighbor\n",
01515           facet->id));
01516   FOREACHridge_(facet->ridges) {
01517     ridge->top->visitid= qh visit_id;
01518     ridge->bottom->visitid= qh visit_id;
01519   }
01520   FOREACHneighbor_(facet) {
01521     if (neighbor->visitid != qh visit_id) {
01522       trace0((qh ferr, "qh_maydropneighbor: facets f%d and f%d are no longer neighbors during p%d\n",
01523             facet->id, neighbor->id, qh furthest_id));
01524       zinc_(Zdropneighbor);
01525       qh_setdel (facet->neighbors, neighbor);
01526       neighborp--;  /* repeat, deleted a neighbor */
01527       qh_setdel (neighbor->neighbors, facet);
01528       if (qh_setsize (neighbor->neighbors) < qh hull_dim) {
01529         zinc_(Zdropdegen);
01530         qh_appendmergeset (neighbor, neighbor, MRGdegen, &angledegen);
01531         trace2((qh ferr, "qh_maydropneighbors: f%d is degenerate.\n", neighbor->id));
01532       }
01533     }
01534   }
01535   if (qh_setsize (facet->neighbors) < qh hull_dim) {
01536     zinc_(Zdropdegen);
01537     qh_appendmergeset (facet, facet, MRGdegen, &angledegen);
01538     trace2((qh ferr, "qh_maydropneighbors: f%d is degenerate.\n", facet->id));
01539   }
01540 } /* maydropneighbor */

01568                                    {
01569   int size;
01570   mergeT *merge;
01571   facetT *bestneighbor, *facet1, *facet2;
01572   realT dist, mindist, maxdist;
01573   vertexT *vertex, **vertexp;
01574   int nummerges= 0;
01575   mergeType mergetype;
01576 
01577   while ((merge= (mergeT*)qh_setdellast (qh degen_mergeset))) {
01578     facet1= merge->facet1;
01579     facet2= merge->facet2;
01580     mergetype= merge->type;
01581     qh_memfree (merge, sizeof(mergeT));
01582     if (facet1->visible)
01583       continue;
01584     facet1->degenerate= False; 
01585     facet1->redundant= False; 
01586     if (qh TRACEmerge-1 == zzval_(Ztotmerge))
01587       qhmem.IStracing= qh IStracing= qh TRACElevel;
01588     if (mergetype == MRGredundant) {
01589       zinc_(Zneighbor);
01590       while (facet2->visible) {
01591         if (!facet2->f.replace) {
01592           fprintf (qh ferr, "qhull internal error (qh_merge_degenredunant): f%d redundant but f%d has no replacement\n",
01593                facet1->id, facet2->id);
01594           qh_errexit2 (qh_ERRqhull, facet1, facet2);
01595         }
01596         facet2= facet2->f.replace;
01597       }
01598       if (facet1 == facet2) {
01599         qh_degen_redundant_facet (facet1); /* in case of others */
01600         continue;
01601       }
01602       trace2((qh ferr, "qh_merge_degenredundant: facet f%d is contained in f%d, will merge\n",
01603             facet1->id, facet2->id));
01604       qh_mergefacet(facet1, facet2, NULL, NULL, !qh_MERGEapex);
01605       /* merge distance is already accounted for */
01606       nummerges++;
01607     }else {  /* mergetype == MRGdegen, other merges may have fixed */
01608       if (!(size= qh_setsize (facet1->neighbors))) {
01609         zinc_(Zdelfacetdup);
01610         trace2((qh ferr, "qh_merge_degenredundant: facet f%d has no neighbors.  Deleted\n", facet1->id));
01611         qh_willdelete (facet1, NULL);
01612         FOREACHvertex_(facet1->vertices) {
01613           qh_setdel (vertex->neighbors, facet1);
01614           if (!SETfirst_(vertex->neighbors)) {
01615             zinc_(Zdegenvertex);
01616             trace2((qh ferr, "qh_merge_degenredundant: deleted v%d because f%d has no neighbors\n",
01617                  vertex->id, facet1->id));
01618             vertex->deleted= True;
01619             qh_setappend (&qh del_vertices, vertex);
01620           }
01621         }
01622         nummerges++;
01623       }else if (size < qh hull_dim) {
01624         bestneighbor= qh_findbestneighbor(facet1, &dist, &mindist, &maxdist);
01625         trace2((qh ferr, "qh_merge_degenredundant: facet f%d has %d neighbors, merge into f%d dist %2.2g\n",
01626               facet1->id, size, bestneighbor->id, dist));
01627         qh_mergefacet(facet1, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
01628         nummerges++;
01629         if (qh PRINTstatistics) {
01630           zinc_(Zdegen);
01631           wadd_(Wdegentot, dist);
01632           wmax_(Wdegenmax, dist);
01633         }
01634       } /* else, another merge fixed the degeneracy and redundancy tested */
01635     }
01636   }
01637   return nummerges;
01638 } /* merge_degenredundant */

01657                                                                               {
01658   facetT *bestfacet, *bestneighbor, *neighbor;
01659   realT dist, dist2, mindist, mindist2, maxdist, maxdist2;
01660 
01661   if (qh TRACEmerge-1 == zzval_(Ztotmerge))
01662     qhmem.IStracing= qh IStracing= qh TRACElevel;
01663   trace3((qh ferr, "qh_merge_nonconvex: merge #%d for f%d and f%d type %d\n",
01664       zzval_(Ztotmerge) + 1, facet1->id, facet2->id, mergetype));
01665   /* concave or coplanar */
01666   if (!facet1->newfacet) {
01667     bestfacet= facet2;   /* avoid merging old facet if new is ok */
01668     facet2= facet1;
01669     facet1= bestfacet;
01670   }else
01671     bestfacet= facet1;
01672   bestneighbor= qh_findbestneighbor(bestfacet, &dist, &mindist, &maxdist);
01673   neighbor= qh_findbestneighbor(facet2, &dist2, &mindist2, &maxdist2);
01674   if (dist < dist2) {
01675     qh_mergefacet(bestfacet, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
01676   }else if (qh AVOIDold && !facet2->newfacet
01677   && ((mindist >= -qh MAXcoplanar && maxdist <= qh max_outside)
01678        || dist * 1.5 < dist2)) {
01679     zinc_(Zavoidold);
01680     wadd_(Wavoidoldtot, dist);
01681     wmax_(Wavoidoldmax, dist);
01682     trace2((qh ferr, "qh_merge_nonconvex: avoid merging old facet f%d dist %2.2g.  Use f%d dist %2.2g instead\n",
01683            facet2->id, dist2, facet1->id, dist2));
01684     qh_mergefacet(bestfacet, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
01685   }else {
01686     qh_mergefacet(facet2, neighbor, &mindist2, &maxdist2, !qh_MERGEapex);
01687     dist= dist2;
01688   }
01689   if (qh PRINTstatistics) {
01690     if (mergetype == MRGanglecoplanar) {
01691       zinc_(Zacoplanar);
01692       wadd_(Wacoplanartot, dist);
01693       wmax_(Wacoplanarmax, dist);
01694     }else if (mergetype == MRGconcave) {
01695       zinc_(Zconcave);
01696       wadd_(Wconcavetot, dist);
01697       wmax_(Wconcavemax, dist);
01698     }else { /* MRGcoplanar */
01699       zinc_(Zcoplanar);
01700       wadd_(Wcoplanartot, dist);
01701       wmax_(Wcoplanarmax, dist);
01702     }
01703   }
01704 } /* merge_nonconvex */

01735                                                          {
01736   int traceonce= False, tracerestore= 0;
01737   vertexT *apex;
01738 #ifndef qh_NOtrace
01739   facetT *same;
01740 #endif
01741 
01742   if (!qh VERTEXneighbors)
01743     qh_vertexneighbors();
01744   zzinc_(Ztotmerge);
01745   if (qh REPORTfreq2 && qh POSTmerging) {
01746     if (zzval_(Ztotmerge) > qh mergereport + qh REPORTfreq2)
01747       qh_tracemerging();
01748   }
01749 #ifndef qh_NOtrace
01750   if (qh TRACEmerge == zzval_(Ztotmerge))
01751     qhmem.IStracing= qh IStracing= qh TRACElevel;
01752   trace2((qh ferr, "qh_mergecycle: merge #%d for facets from cycle f%d into coplanar horizon f%d\n", 
01753         zzval_(Ztotmerge), samecycle->id, newfacet->id));
01754   if (newfacet == qh tracefacet) {
01755     tracerestore= qh IStracing;
01756     qh IStracing= 4;
01757     fprintf (qh ferr, "qh_mergecycle: ========= trace merge %d of samecycle %d into trace f%d, furthest is p%d\n",
01758                zzval_(Ztotmerge), samecycle->id, newfacet->id,  qh furthest_id);
01759     traceonce= True;
01760   }
01761   if (qh IStracing >=4) {
01762     fprintf (qh ferr, "  same cycle:");
01763     FORALLsame_cycle_(samecycle)
01764       fprintf(qh ferr, " f%d", same->id);
01765     fprintf (qh ferr, "\n");
01766   }
01767   if (qh IStracing >=4)
01768     qh_errprint ("MERGING CYCLE", samecycle, newfacet, NULL, NULL);
01769 #endif /* !qh_NOtrace */
01770   apex= SETfirstt_(samecycle->vertices, vertexT);
01771   qh_makeridges (newfacet);
01772   qh_mergecycle_neighbors (samecycle, newfacet);
01773   qh_mergecycle_ridges (samecycle, newfacet);
01774   qh_mergecycle_vneighbors (samecycle, newfacet);
01775   if (SETfirstt_(newfacet->vertices, vertexT) != apex) 
01776     qh_setaddnth (&newfacet->vertices, 0, apex);  /* apex has last id */
01777   if (!newfacet->newfacet)
01778     qh_newvertices (newfacet->vertices);
01779   qh_mergecycle_facets (samecycle, newfacet);
01780   qh_tracemerge (samecycle, newfacet);
01781   /* check for degen_redundant_neighbors after qh_forcedmerges() */
01782   if (traceonce) {
01783     fprintf (qh ferr, "qh_mergecycle: end of trace facet\n");
01784     qh IStracing= tracerestore;
01785   }
01786 } /* mergecycle */

01817                                                             {
01818   facetT *facet, *same, *prev, *horizon;
01819   facetT *samecycle= NULL, *nextfacet, *nextsame;
01820   vertexT *apex, *vertex, **vertexp;
01821   int cycles=0, total=0, facets, nummerge;
01822 
01823   trace2((qh ferr, "qh_mergecycle_all: begin\n"));
01824   for (facet= facetlist; facet && (nextfacet= facet->next); facet= nextfacet) {
01825     if (facet->normal)
01826       continue;
01827     if (!facet->mergehorizon) {
01828       fprintf (qh ferr, "qh_mergecycle_all: f%d without normal\n", facet->id);
01829       qh_errexit (qh_ERRqhull, facet, NULL);
01830     }
01831     horizon= SETfirstt_(facet->neighbors, facetT);
01832     if (facet->f.samecycle == facet) {
01833       zinc_(Zonehorizon);  
01834       /* merge distance done in qh_findhorizon */
01835       apex= SETfirstt_(facet->vertices, vertexT);
01836       FOREACHvertex_(facet->vertices) {
01837         if (vertex != apex)
01838           vertex->delridge= True;
01839       }
01840       horizon->f.newcycle= NULL;
01841       qh_mergefacet (facet, horizon, NULL, NULL, qh_MERGEapex);
01842     }else {
01843       samecycle= facet;
01844       facets= 0;
01845       prev= facet;
01846       for (same= facet->f.samecycle; same;  /* FORALLsame_cycle_(facet) */
01847            same= (same == facet ? NULL :nextsame)) { /* ends at facet */
01848         nextsame= same->f.samecycle;
01849         if (same->cycledone || same->visible)
01850           qh_infiniteloop (same);
01851         same->cycledone= True;
01852         if (same->normal) { 
01853           prev->f.samecycle= same->f.samecycle; /* unlink ->mergeridge */
01854           same->f.samecycle= NULL;
01855         }else {
01856           prev= same;
01857           facets++;
01858         }
01859       }
01860       while (nextfacet && nextfacet->cycledone)  /* will delete samecycle */
01861         nextfacet= nextfacet->next;
01862       horizon->f.newcycle= NULL;
01863       qh_mergecycle (samecycle, horizon);
01864       nummerge= horizon->nummerge + facets;
01865       if (nummerge > qh_MAXnummerge) 
01866         horizon->nummerge= qh_MAXnummerge;
01867       else
01868         horizon->nummerge= nummerge;
01869       zzinc_(Zcyclehorizon);
01870       total += facets;
01871       zzadd_(Zcyclefacettot, facets);
01872       zmax_(Zcyclefacetmax, facets);
01873     }
01874     cycles++;
01875   }
01876   if (cycles)
01877     *wasmerge= True;
01878   trace1((qh ferr, "qh_mergecycle_all: merged %d same cycles or facets into coplanar horizons\n", cycles));
01879 } /* mergecycle_all */

01905                                                                 {
01906   facetT *same, *next;
01907   
01908   trace4((qh ferr, "qh_mergecycle_facets: make newfacet new and samecycle deleted\n"));  
01909   qh_removefacet(newfacet);  /* append as a newfacet to end of qh facet_list */
01910   qh_appendfacet(newfacet);
01911   newfacet->newfacet= True;
01912   newfacet->simplicial= False;
01913   newfacet->newmerge= True;
01914   
01915   for (same= samecycle->f.samecycle; same; same= (same == samecycle ?  NULL : next)) {
01916     next= same->f.samecycle;  /* reused by willdelete */
01917     qh_willdelete (same, newfacet);
01918   }
01919   if (newfacet->center 
01920       && qh_setsize (newfacet->vertices) <= qh hull_dim + qh_MAXnewcentrum) {
01921     qh_memfree (newfacet->center, qh normal_size);
01922     newfacet->center= NULL;
01923   }
01924   trace3((qh ferr, "qh_mergecycle_facets: merged facets from cycle f%d into f%d\n", 
01925              samecycle->id, newfacet->id));
01926 } /* mergecycle_facets */

01963                                                                   {
01964   facetT *same, *neighbor, **neighborp;
01965   int delneighbors= 0, newneighbors= 0;
01966   unsigned int samevisitid;
01967   ridgeT *ridge, **ridgep;
01968 
01969   samevisitid= ++qh visit_id;
01970   FORALLsame_cycle_(samecycle) {
01971     if (same->visitid == samevisitid || same->visible)
01972       qh_infiniteloop (samecycle);
01973     same->visitid= samevisitid;
01974   }
01975   newfacet->visitid= ++qh visit_id;
01976   trace4((qh ferr, "qh_mergecycle_neighbors: delete shared neighbors from newfacet\n"));  
01977   FOREACHneighbor_(newfacet) {
01978     if (neighbor->visitid == samevisitid) {
01979       SETref_(neighbor)= NULL;  /* samecycle neighbors deleted */
01980       delneighbors++;
01981     }else
01982       neighbor->visitid= qh visit_id;
01983   }
01984   qh_setcompact (newfacet->neighbors);
01985 
01986   trace4((qh ferr, "qh_mergecycle_neighbors: update neighbors\n"));  
01987   FORALLsame_cycle_(samecycle) {
01988     FOREACHneighbor_(same) {
01989       if (neighbor->visitid == samevisitid)
01990         continue;
01991       if (neighbor->simplicial) {
01992         if (neighbor->visitid != qh visit_id) {
01993           qh_setappend (&newfacet->neighbors, neighbor);
01994           qh_setreplace (neighbor->neighbors, same, newfacet);
01995           newneighbors++;
01996           neighbor->visitid= qh visit_id;
01997           FOREACHridge_(neighbor->ridges) { /* update ridge in case of qh_makeridges */
01998             if (ridge->top == same) {
01999               ridge->top= newfacet;
02000               break;
02001             }else if (ridge->bottom == same) {
02002               ridge->bottom= newfacet;
02003               break;
02004             }
02005           }
02006         }else {
02007           qh_makeridges (neighbor);
02008           qh_setdel (neighbor->neighbors, same);
02009           /* same can't be horizon facet for neighbor */
02010         }
02011       }else { /* non-simplicial neighbor */
02012         qh_setdel (neighbor->neighbors, same);
02013         if (neighbor->visitid != qh visit_id) {
02014           qh_setappend (&neighbor->neighbors, newfacet);
02015           qh_setappend (&newfacet->neighbors, neighbor);
02016           neighbor->visitid= qh visit_id;
02017           newneighbors++;
02018         } 
02019       }
02020     }
02021   }
02022   trace2((qh ferr, "qh_mergecycle_neighbors: deleted %d neighbors and added %d\n", 
02023              delneighbors, newneighbors));
02024 } /* mergecycle_neighbors */

02060                                                                {
02061   facetT *same, *neighbor= NULL;
02062   int numold=0, numnew=0;
02063   int neighbor_i, neighbor_n;
02064   unsigned int samevisitid;
02065   ridgeT *ridge, **ridgep;
02066   boolT toporient;
02067   void **freelistp; /* used !qh_NOmem */
02068 
02069   trace4((qh ferr, "qh_mergecycle_ridges: delete shared ridges from newfacet\n"));  
02070   samevisitid= qh visit_id -1;
02071   FOREACHridge_(newfacet->ridges) {
02072     neighbor= otherfacet_(ridge, newfacet);
02073     if (neighbor->visitid == samevisitid)
02074       SETref_(ridge)= NULL; /* ridge free'd below */  
02075   }
02076   qh_setcompact (newfacet->ridges);
02077   
02078   trace4((qh ferr, "qh_mergecycle_ridges: add ridges to newfacet\n"));  
02079   FORALLsame_cycle_(samecycle) {
02080     FOREACHridge_(same->ridges) {
02081       if (ridge->top == same) {
02082         ridge->top= newfacet;
02083         neighbor= ridge->bottom;
02084       }else if (ridge->bottom == same) {
02085         ridge->bottom= newfacet;
02086         neighbor= ridge->top;
02087       }else if (ridge->top == newfacet || ridge->bottom == newfacet) {
02088         qh_setappend (&newfacet->ridges, ridge);
02089         numold++;  /* already set by qh_mergecycle_neighbors */
02090         continue;  
02091       }else {
02092         fprintf (qh ferr, "qhull internal error (qh_mergecycle_ridges): bad ridge r%d\n", ridge->id);
02093         qh_errexit (qh_ERRqhull, NULL, ridge);
02094       }
02095       if (neighbor == newfacet) {
02096         qh_setfree(&(ridge->vertices)); 
02097         qh_memfree_(ridge, sizeof(ridgeT), freelistp);
02098         numold++;
02099       }else if (neighbor->visitid == samevisitid) {
02100         qh_setdel (neighbor->ridges, ridge);
02101         qh_setfree(&(ridge->vertices)); 
02102         qh_memfree_(ridge, sizeof(ridgeT), freelistp);
02103         numold++;
02104       }else {
02105         qh_setappend (&newfacet->ridges, ridge);
02106         numold++;
02107       }
02108     }
02109     if (same->ridges)
02110       qh_settruncate (same->ridges, 0);
02111     if (!same->simplicial)
02112       continue;
02113     FOREACHneighbor_i_(same) {       /* note: !newfact->simplicial */
02114       if (neighbor->visitid != samevisitid && neighbor->simplicial) {
02115         ridge= qh_newridge();
02116         ridge->vertices= qh_setnew_delnthsorted (same->vertices, qh hull_dim,
02117                                                           neighbor_i, 0);
02118         toporient= same->toporient ^ (neighbor_i & 0x1);
02119         if (toporient) {
02120           ridge->top= newfacet;
02121           ridge->bottom= neighbor;
02122         }else {
02123           ridge->top= neighbor;
02124           ridge->bottom= newfacet;
02125         }
02126         qh_setappend(&(newfacet->ridges), ridge);
02127         qh_setappend(&(neighbor->ridges), ridge);
02128         numnew++;
02129       }
02130     }
02131   }
02132 
02133   trace2((qh ferr, "qh_mergecycle_ridges: found %d old ridges and %d new ones\n", 
02134              numold, numnew));
02135 } /* mergecycle_ridges */

02162                                                                     {
02163   facetT *neighbor, **neighborp;
02164   unsigned int mergeid;
02165   vertexT *vertex, **vertexp, *apex;
02166   setT *vertices;
02167   
02168   trace4((qh ferr, "qh_mergecycle_vneighbors: update vertex neighbors for newfacet\n"));  
02169   mergeid= qh visit_id - 1;
02170   newfacet->visitid= mergeid;
02171   vertices= qh_basevertices (samecycle); /* temp */
02172   apex= SETfirstt_(samecycle->vertices, vertexT);
02173   qh_setappend (&vertices, apex);
02174   FOREACHvertex_(vertices) {
02175     vertex->delridge= True;
02176     FOREACHneighbor_(vertex) {
02177       if (neighbor->visitid == mergeid)
02178         SETref_(neighbor)= NULL;
02179     }
02180     qh_setcompact (vertex->neighbors);
02181     qh_setappend (&vertex->neighbors, newfacet);
02182     if (!SETsecond_(vertex->neighbors)) {
02183       zinc_(Zcyclevertex);
02184       trace2((qh ferr, "qh_mergecycle_vneighbors: deleted v%d when merging cycle f%d into f%d\n",
02185         vertex->id, samecycle->id, newfacet->id));
02186       qh_setdelsorted (newfacet->vertices, vertex);
02187       vertex->deleted= True;
02188       qh_setappend (&qh del_vertices, vertex);
02189     }
02190   }
02191   qh_settempfree (&vertices);
02192   trace3((qh ferr, "qh_mergecycle_vneighbors: merged vertices from cycle f%d into f%d\n", 
02193              samecycle->id, newfacet->id));
02194 } /* mergecycle_vneighbors */

02247                                                                                                     {
02248   boolT traceonce= False;
02249   vertexT *vertex, **vertexp;
02250   int tracerestore=0, nummerge;
02251 
02252   zzinc_(Ztotmerge);
02253   if (qh REPORTfreq2 && qh POSTmerging) {
02254     if (zzval_(Ztotmerge) > qh mergereport + qh REPORTfreq2)
02255       qh_tracemerging();
02256   }
02257 #ifndef qh_NOtrace
02258   if (qh build_cnt >= qh RERUN) {
02259     if (mindist && (-*mindist > qh TRACEdist || *maxdist > qh TRACEdist)) {
02260       tracerestore= 0;
02261       qh IStracing= qh TRACElevel;
02262       traceonce= True;
02263       fprintf (qh ferr, "qh_mergefacet: ========= trace wide merge #%d (%2.2g) for f%d into f%d, last point was p%d\n", zzval_(Ztotmerge),
02264              fmax_(-*mindist, *maxdist), facet1->id, facet2->id, qh furthest_id);
02265     }else if (facet1 == qh tracefacet || facet2 == qh tracefacet) {
02266       tracerestore= qh IStracing;
02267       qh IStracing= 4;
02268       traceonce= True;
02269       fprintf (qh ferr, "qh_mergefacet: ========= trace merge #%d involving f%d, furthest is p%d\n",
02270                  zzval_(Ztotmerge), qh tracefacet_id,  qh furthest_id);
02271     }
02272   }
02273   if (qh IStracing >= 2) {
02274     realT mergemin= -2;
02275     realT mergemax= -2;
02276     
02277     if (mindist) {
02278       mergemin= *mindist;
02279       mergemax= *maxdist;
02280     }
02281     fprintf (qh ferr, "qh_mergefacet: #%d merge f%d into f%d, mindist= %2.2g, maxdist= %2.2g\n", 
02282     zzval_(Ztotmerge), facet1->id, facet2->id, mergemin, mergemax);
02283   }
02284 #endif /* !qh_NOtrace */
02285   if (facet1 == facet2 || facet1->visible || facet2->visible) {
02286     fprintf (qh ferr, "qhull internal error (qh_mergefacet): either f%d and f%d are the same or one is a visible facet\n",
02287              facet1->id, facet2->id);
02288     qh_errexit2 (qh_ERRqhull, facet1, facet2);
02289   }
02290   if (qh num_facets - qh num_visible <= qh hull_dim + 1) {
02291     fprintf(qh ferr, "\n\
02292 qhull precision error: Only %d facets remain.  Can not merge another\n\
02293 pair.  The convexity constraints may be too strong.  Reduce the\n\
02294 magnitude of 'Cn' or increase the magnitude of 'An'.  For example,\n\
02295 try 'C-0.001' instead of 'C-0.1' or 'A-0.999' instead of 'A-0.9'.\n", 
02296                  qh hull_dim+1);
02297     if (qh hull_dim >= 5 && !qh MERGEexact)
02298       fprintf(qh ferr, "Option 'Qx' may avoid this problem.\n");
02299     qh_errexit(qh_ERRinput, NULL, NULL);
02300   }
02301   if (!qh VERTEXneighbors)
02302     qh_vertexneighbors();
02303   qh_makeridges(facet1);
02304   qh_makeridges(facet2);
02305   if (qh IStracing >=4)
02306     qh_errprint ("MERGING", facet1, facet2, NULL, NULL);
02307   if (mindist) {
02308     maximize_(qh max_outside, *maxdist);
02309     maximize_(qh max_vertex, *maxdist);
02310 #if qh_MAXoutside
02311     maximize_(facet2->maxoutside, *maxdist);
02312 #endif
02313     minimize_(qh min_vertex, *mindist);
02314     if (!facet2->keepcentrum 
02315     && (*maxdist > qh WIDEfacet || *mindist < -qh WIDEfacet)) {
02316       facet2->keepcentrum= True;
02317       zinc_(Zwidefacet);
02318     }
02319   }
02320   nummerge= facet1->nummerge + facet2->nummerge + 1;
02321   if (nummerge >= qh_MAXnummerge) 
02322     facet2->nummerge= qh_MAXnummerge;
02323   else
02324     facet2->nummerge= nummerge;
02325   facet2->newmerge= True;
02326   facet2->dupridge= False;
02327   qh_updatetested  (facet1, facet2);
02328   if (qh hull_dim > 2 && qh_setsize (facet1->vertices) == qh hull_dim)
02329     qh_mergesimplex (facet1, facet2, mergeapex);
02330   else {
02331     qh vertex_visit++;
02332     FOREACHvertex_(facet2->vertices)
02333       vertex->visitid= qh vertex_visit;
02334     if (qh hull_dim == 2) 
02335       qh_mergefacet2d(facet1, facet2);
02336     else {
02337       qh_mergeneighbors(facet1, facet2);
02338       qh_mergevertices(facet1->vertices, &facet2->vertices);
02339     }
02340     qh_mergeridges(facet1, facet2);
02341     qh_mergevertex_neighbors(facet1, facet2);
02342     if (!facet2->newfacet)
02343       qh_newvertices (facet2->vertices);
02344   }
02345   if (!mergeapex)
02346     qh_degen_redundant_neighbors (facet2, facet1);
02347   if (facet2->coplanar || !facet2->newfacet) {
02348     zinc_(Zmergeintohorizon);
02349   }else if (!facet1->newfacet && facet2->newfacet) {
02350     zinc_(Zmergehorizon);
02351   }else {
02352     zinc_(Zmergenew);
02353   }
02354   qh_willdelete (facet1, facet2);
02355   qh_removefacet(facet2);  /* append as a newfacet to end of qh facet_list */
02356   qh_appendfacet(facet2);
02357   facet2->newfacet= True;
02358   facet2->tested= False;
02359   qh_tracemerge (facet1, facet2);
02360   if (traceonce) {
02361     fprintf (qh ferr, "qh_mergefacet: end of wide tracing\n");
02362     qh IStracing= tracerestore;
02363   }
02364 } /* mergefacet */

02390                                                       {
02391   vertexT *vertex1A, *vertex1B, *vertex2A, *vertex2B, *vertexA, *vertexB;
02392   facetT *neighbor1A, *neighbor1B, *neighbor2A, *neighbor2B, *neighborA, *neighborB;
02393 
02394   vertex1A= SETfirstt_(facet1->vertices, vertexT);
02395   vertex1B= SETsecondt_(facet1->vertices, vertexT);
02396   vertex2A= SETfirstt_(facet2->vertices, vertexT);
02397   vertex2B= SETsecondt_(facet2->vertices, vertexT);
02398   neighbor1A= SETfirstt_(facet1->neighbors, facetT);
02399   neighbor1B= SETsecondt_(facet1->neighbors, facetT);
02400   neighbor2A= SETfirstt_(facet2->neighbors, facetT);
02401   neighbor2B= SETsecondt_(facet2->neighbors, facetT);
02402   if (vertex1A == vertex2A) {
02403     vertexA= vertex1B;
02404     vertexB= vertex2B;
02405     neighborA= neighbor2A;
02406     neighborB= neighbor1A;
02407   }else if (vertex1A == vertex2B) {
02408     vertexA= vertex1B;
02409     vertexB= vertex2A;
02410     neighborA= neighbor2B;
02411     neighborB= neighbor1A;
02412   }else if (vertex1B == vertex2A) {
02413     vertexA= vertex1A;
02414     vertexB= vertex2B;
02415     neighborA= neighbor2A;
02416     neighborB= neighbor1B;
02417   }else { /* 1B == 2B */
02418     vertexA= vertex1A;
02419     vertexB= vertex2A;
02420     neighborA= neighbor2B;
02421     neighborB= neighbor1B;
02422   }
02423   /* vertexB always from facet2, neighborB always from facet1 */
02424   if (vertexA->id > vertexB->id) {
02425     SETfirst_(facet2->vertices)= vertexA;
02426     SETsecond_(facet2->vertices)= vertexB;
02427     if (vertexB == vertex2A)
02428       facet2->toporient= !facet2->toporient;
02429     SETfirst_(facet2->neighbors)= neighborA;
02430     SETsecond_(facet2->neighbors)= neighborB;
02431   }else {
02432     SETfirst_(facet2->vertices)= vertexB;
02433     SETsecond_(facet2->vertices)= vertexA;
02434     if (vertexB == vertex2B)
02435       facet2->toporient= !facet2->toporient;
02436     SETfirst_(facet2->neighbors)= neighborB;
02437     SETsecond_(facet2->neighbors)= neighborA;
02438   }
02439   qh_makeridges (neighborB);
02440   qh_setreplace(neighborB->neighbors, facet1, facet2);
02441   trace4((qh ferr, "qh_mergefacet2d: merged v%d and neighbor f%d of f%d into f%d\n",
02442        vertexA->id, neighborB->id, facet1->id, facet2->id));
02443 } /* mergefacet2d */

02465                                                        {
02466   facetT *neighbor, **neighborp;
02467 
02468   trace4((qh ferr, "qh_mergeneighbors: merge neighbors of f%d and f%d\n",
02469           facet1->id, facet2->id));
02470   qh visit_id++;
02471   FOREACHneighbor_(facet2) {
02472     neighbor->visitid= qh visit_id;
02473   }
02474   FOREACHneighbor_(facet1) {
02475     if (neighbor->visitid == qh visit_id) {
02476       if (neighbor->simplicial)    /* is degen, needs ridges */
02477         qh_makeridges (neighbor);
02478       if (SETfirstt_(neighbor->neighbors, facetT) != facet1) /*keep newfacet->horizon*/
02479         qh_setdel (neighbor->neighbors, facet1);
02480       else {
02481         qh_setdel(neighbor->neighbors, facet2);
02482         qh_setreplace(neighbor->neighbors, facet1, facet2);
02483       }
02484     }else if (neighbor != facet2) {
02485       qh_setappend(&(facet2->neighbors), neighbor);
02486       qh_setreplace(neighbor->neighbors, facet1, facet2);
02487     }
02488   }
02489   qh_setdel(facet1->neighbors, facet2);  /* here for makeridges */
02490   qh_setdel(facet2->neighbors, facet1);
02491 } /* mergeneighbors */

02513                                                     {
02514   ridgeT *ridge, **ridgep;
02515   vertexT *vertex, **vertexp;
02516 
02517   trace4((qh ferr, "qh_mergeridges: merge ridges of f%d and f%d\n",
02518           facet1->id, facet2->id));
02519   FOREACHridge_(facet2->ridges) {
02520     if ((ridge->top == facet1) || (ridge->bottom == facet1)) {
02521       FOREACHvertex_(ridge->vertices)
02522         vertex->delridge= True;
02523       qh_delridge(ridge);  /* expensive in high-d, could rebuild */
02524       ridgep--; /*repeat*/
02525     }
02526   }
02527   FOREACHridge_(facet1->ridges) {
02528     if (ridge->top == facet1)
02529       ridge->top= facet2;
02530     else
02531       ridge->bottom= facet2;
02532     qh_setappend(&(facet2->ridges), ridge);
02533   }
02534 } /* mergeridges */

02580                                                                       {
02581   vertexT *vertex, **vertexp, *apex;
02582   ridgeT *ridge, **ridgep;
02583   boolT issubset= False;
02584   int vertex_i= -1, vertex_n;
02585   facetT *neighbor, **neighborp, *otherfacet;
02586 
02587   if (mergeapex) {
02588     if (!facet2->newfacet)
02589       qh_newvertices (facet2->vertices);  /* apex is new */
02590     apex= SETfirstt_(facet1->vertices, vertexT);
02591     if (SETfirstt_(facet2->vertices, vertexT) != apex) 
02592       qh_setaddnth (&facet2->vertices, 0, apex);  /* apex has last id */
02593     else
02594       issubset= True;
02595   }else {
02596     zinc_(Zmergesimplex);
02597     FOREACHvertex_(facet1->vertices)
02598       vertex->seen= False;
02599     FOREACHridge_(facet1->ridges) {
02600       if (otherfacet_(ridge, facet1) == facet2) {
02601         FOREACHvertex_(ridge->vertices) {
02602           vertex->seen= True;
02603           vertex->delridge= True;
02604         }
02605         break;
02606       }
02607     }
02608     FOREACHvertex_(facet1->vertices) {
02609       if (!vertex->seen)
02610         break;  /* must occur */
02611     }
02612     apex= vertex;
02613     trace4((qh ferr, "qh_mergesimplex: merge apex v%d of f%d into facet f%d\n",
02614           apex->id, facet1->id, facet2->id));
02615     FOREACHvertex_i_(facet2->vertices) {
02616       if (vertex->id < apex->id) {
02617         break;
02618       }else if (vertex->id == apex->id) {
02619         issubset= True;
02620         break;
02621       }
02622     }
02623     if (!issubset)
02624       qh_setaddnth (&facet2->vertices, vertex_i, apex);
02625     if (!facet2->newfacet)
02626       qh_newvertices (facet2->vertices);
02627     else if (!apex->newlist) {
02628       qh_removevertex (apex);
02629       qh_appendvertex (apex);
02630     }
02631   }
02632   trace4((qh ferr, "qh_mergesimplex: update vertex neighbors of f%d\n",
02633           facet1->id));
02634   FOREACHvertex_(facet1->vertices) {
02635     if (vertex == apex && !issubset)
02636       qh_setreplace (vertex->neighbors, facet1, facet2);
02637     else {
02638       qh_setdel (vertex->neighbors, facet1);
02639       if (!SETsecond_(vertex->neighbors))
02640         qh_mergevertex_del (vertex, facet1, facet2);
02641     }
02642   }
02643   trace4((qh ferr, "qh_mergesimplex: merge ridges and neighbors of f%d into f%d\n",
02644           facet1->id, facet2->id));
02645   qh visit_id++;
02646   FOREACHneighbor_(facet2)
02647     neighbor->visitid= qh visit_id;
02648   FOREACHridge_(facet1->ridges) {
02649     otherfacet= otherfacet_(ridge, facet1);
02650     if (otherfacet == facet2) {
02651       qh_setdel (facet2->ridges, ridge);
02652       qh_setfree(&(ridge->vertices)); 
02653       qh_memfree (ridge, sizeof(ridgeT));
02654       qh_setdel (facet2->neighbors, facet1);
02655     }else {
02656       qh_setappend (&facet2->ridges, ridge);
02657       if (otherfacet->visitid != qh visit_id) {
02658         qh_setappend (&facet2->neighbors, otherfacet);
02659         qh_setreplace (otherfacet->neighbors, facet1, facet2);
02660         otherfacet->visitid= qh visit_id;
02661       }else {
02662         if (otherfacet->simplicial)    /* is degen, needs ridges */
02663           qh_makeridges (otherfacet);
02664         if (SETfirstt_(otherfacet->neighbors, facetT) != facet1)
02665           qh_setdel (otherfacet->neighbors, facet1);
02666         else {   /*keep newfacet->neighbors->horizon*/
02667           qh_setdel(otherfacet->neighbors, facet2);
02668           qh_setreplace(otherfacet->neighbors, facet1, facet2);
02669         }
02670       }
02671       if (ridge->top == facet1) /* wait until after qh_makeridges */
02672         ridge->top= facet2;
02673       else 
02674         ridge->bottom= facet2;
02675     }
02676   }
02677   SETfirst_(facet1->ridges)= NULL; /* it will be deleted */
02678   trace3((qh ferr, "qh_mergesimplex: merged simplex f%d apex v%d into facet f%d\n",
02679           facet1->id, getid_(apex), facet2->id));
02680 } /* mergesimplex */

02692                                                                           {
02693 
02694   zinc_(Zmergevertex);
02695   trace2((qh ferr, "qh_mergevertex_del: deleted v%d when merging f%d into f%d\n",
02696           vertex->id, facet1->id, facet2->id));
02697   qh_setdelsorted (facet2->vertices, vertex);
02698   vertex->deleted= True;
02699   qh_setappend (&qh del_vertices, vertex);
02700 } /* mergevertex_del */

02718                                                               {
02719   vertexT *vertex, **vertexp;
02720 
02721   trace4((qh ferr, "qh_mergevertex_neighbors: merge vertex neighbors of f%d and f%d\n",
02722           facet1->id, facet2->id));
02723   if (qh tracevertex) {
02724     fprintf (qh ferr, "qh_mergevertex_neighbors: of f%d and f%d at furthest p%d f0= %p\n",
02725              facet1->id, facet2->id, qh furthest_id, qh tracevertex->neighbors->e[0].p);
02726     qh_errprint ("TRACE", NULL, NULL, NULL, qh tracevertex);
02727   }
02728   FOREACHvertex_(facet1->vertices) {
02729     if (vertex->visitid != qh vertex_visit) 
02730       qh_setreplace(vertex->neighbors, facet1, facet2);
02731     else {
02732       qh_setdel(vertex->neighbors, facet1);
02733       if (!SETsecond_(vertex->neighbors))
02734         qh_mergevertex_del (vertex, facet1, facet2);
02735     }
02736   }
02737   if (qh tracevertex) 
02738     qh_errprint ("TRACE", NULL, NULL, NULL, qh tracevertex);
02739 } /* mergevertex_neighbors */

02756                                                          {
02757   int newsize= qh_setsize(vertices1)+qh_setsize(*vertices2) - qh hull_dim + 1;
02758   setT *mergedvertices;
02759   vertexT *vertex, **vertexp, **vertex2= SETaddr_(*vertices2, vertexT);
02760 
02761   mergedvertices= qh_settemp (newsize);
02762   FOREACHvertex_(vertices1) {
02763     if (!*vertex2 || vertex->id > (*vertex2)->id)
02764       qh_setappend (&mergedvertices, vertex);
02765     else {
02766       while (*vertex2 && (*vertex2)->id > vertex->id)
02767         qh_setappend (&mergedvertices, *vertex2++);
02768       if (!*vertex2 || (*vertex2)->id < vertex->id)
02769         qh_setappend (&mergedvertices, vertex);
02770       else
02771         qh_setappend (&mergedvertices, *vertex2++);
02772     }
02773   }
02774   while (*vertex2)
02775     qh_setappend (&mergedvertices, *vertex2++);
02776   if (newsize < qh_setsize (mergedvertices)) {
02777     fprintf (qh ferr, "qhull internal error (qh_mergevertices): facets did not share a ridge\n");
02778     qh_errexit (qh_ERRqhull, NULL, NULL);
02779   }
02780   qh_setfree(vertices2);
02781   *vertices2= mergedvertices;
02782   qh_settemppop ();
02783 } /* mergevertices */

02809                                                   {
02810   facetT *neighbor, **neighborp, *neighborA, *neighborB;
02811   setT *intersect;
02812   int neighbor_i, neighbor_n;
02813 
02814   FOREACHneighbor_(vertex) {
02815     if (neighbor->simplicial)
02816       return NULL;
02817   }
02818   neighborA= SETfirstt_(vertex->neighbors, facetT);
02819   neighborB= SETsecondt_(vertex->neighbors, facetT);
02820   zinc_(Zintersectnum);
02821   if (!neighborA)
02822     return NULL;
02823   if (!neighborB)
02824     intersect= qh_setcopy (neighborA->vertices, 0);
02825   else
02826     intersect= qh_vertexintersect_new (neighborA->vertices, neighborB->vertices);
02827   qh_settemppush (intersect);
02828   qh_setdelsorted (intersect, vertex);
02829   FOREACHneighbor_i_(vertex) {
02830     if (neighbor_i >= 2) {
02831       zinc_(Zintersectnum);
02832       qh_vertexintersect (&intersect, neighbor->vertices);
02833       if (!SETfirst_(intersect)) {
02834         zinc_(Zintersectfail);
02835         qh_settempfree (&intersect);
02836         return NULL;
02837       }
02838     }
02839   }
02840   trace3((qh ferr, "qh_neighbor_intersections: %d vertices in neighbor intersection of v%d\n", 
02841           qh_setsize (intersect), vertex->id));
02842   return intersect;
02843 } /* neighbor_intersections */

02855                                      {
02856   vertexT *vertex, **vertexp;
02857 
02858   FOREACHvertex_(vertices) {
02859     if (!vertex->newlist) {
02860       qh_removevertex (vertex);
02861       qh_appendvertex (vertex);
02862     }
02863   }
02864 } /* newvertices */

00135                                         {
00136   facetT *newfacet;
00137   boolT othermerges= False;
00138   vertexT *vertex;
00139 
00140   if (qh REPORTfreq || qh IStracing) {
00141     qh_buildtracing (NULL, NULL);
00142     qh_printsummary (qh ferr);
00143     if (qh PRINTstatistics) 
00144       qh_printallstatistics (qh ferr, "reason");
00145     fprintf (qh ferr, "\n%s with 'C%.2g' and 'A%.2g'\n", 
00146         reason, maxcentrum, maxangle);
00147   }
00148   trace2((qh ferr, "qh_postmerge: postmerge.  test vneighbors? %d\n",
00149             vneighbors));
00150   qh centrum_radius= maxcentrum;
00151   qh cos_max= maxangle;
00152   qh POSTmerging= True;
00153   qh degen_mergeset= qh_settemp (qh TEMPsize);
00154   qh facet_mergeset= qh_settemp (qh TEMPsize);
00155   if (qh visible_list != qh facet_list) {  /* first call */
00156     qh NEWfacets= True;
00157     qh visible_list= qh newfacet_list= qh facet_list;
00158     FORALLnew_facets {
00159       newfacet->newfacet= True;
00160        if (!newfacet->simplicial)
00161         newfacet->newmerge= True;
00162      zinc_(Zpostfacets);
00163     }
00164     qh newvertex_list= qh vertex_list;
00165     FORALLvertices
00166       vertex->newlist= True;
00167     if (qh VERTEXneighbors) { /* a merge has occurred */
00168       FORALLvertices
00169         vertex->delridge= True; /* test for redundant, needed? */
00170       if (qh MERGEexact) {
00171         if (qh hull_dim <= qh_DIMreduceBuild)
00172           qh_reducevertices(); /* was skipped during pre-merging */
00173       }
00174     }
00175     if (!qh PREmerge && !qh MERGEexact) 
00176       qh_flippedmerges (qh newfacet_list, &othermerges);
00177   }
00178   qh_getmergeset_initial (qh newfacet_list);
00179   qh_all_merges (False, vneighbors);
00180   qh_settempfree(&qh facet_mergeset);
00181   qh_settempfree(&qh degen_mergeset);
00182 } /* post_merge */

00061                                                                    {
00062   boolT othermerge= False;
00063   facetT *newfacet;
00064   
00065   if (qh ZEROcentrum && qh_checkzero(!qh_ALL))
00066     return;    
00067   trace2((qh ferr, "qh_premerge: premerge centrum %2.2g angle %2.2g for apex v%d facetlist f%d\n",
00068             maxcentrum, maxangle, apex->id, getid_(qh newfacet_list)));
00069   if (qh IStracing >= 4 && qh num_facets < 50)
00070     qh_printlists();
00071   qh centrum_radius= maxcentrum;
00072   qh cos_max= maxangle;
00073   qh degen_mergeset= qh_settemp (qh TEMPsize);
00074   qh facet_mergeset= qh_settemp (qh TEMPsize);
00075   if (qh hull_dim >=3) { 
00076     qh_mark_dupridges (qh newfacet_list); /* facet_mergeset */
00077     qh_mergecycle_all (qh newfacet_list, &othermerge);
00078     qh_forcedmerges (&othermerge /* qh facet_mergeset */); 
00079     FORALLnew_facets {  /* test samecycle merges */
00080       if (!newfacet->simplicial && !newfacet->mergeridge)
00081         qh_degen_redundant_neighbors (newfacet, NULL);
00082     }
00083     if (qh_merge_degenredundant())
00084       othermerge= True;
00085   }else /* qh hull_dim == 2 */
00086     qh_mergecycle_all (qh newfacet_list, &othermerge);
00087   qh_flippedmerges (qh newfacet_list, &othermerge);
00088   if (!qh MERGEexact || zzval_(Ztotmerge)) {
00089     zinc_(Zpremergetot);
00090     qh POSTmerging= False;
00091     qh_getmergeset_initial (qh newfacet_list);
00092     qh_all_merges (othermerge, False);
00093   }
00094   qh_settempfree(&qh facet_mergeset);
00095   qh_settempfree(&qh degen_mergeset);
00096 } /* premerge */

02893                                {
02894   int numshare=0, numrename= 0;
02895   boolT degenredun= False;
02896   facetT *newfacet;
02897   vertexT *vertex, **vertexp;
02898 
02899   if (qh hull_dim == 2) 
02900     return False;
02901   if (qh_merge_degenredundant())
02902     degenredun= True;
02903  LABELrestart:
02904   FORALLnew_facets {
02905     if (newfacet->newmerge) { 
02906       if (!qh MERGEvertices)
02907         newfacet->newmerge= False;
02908       qh_remove_extravertices (newfacet);
02909     }
02910   }
02911   if (!qh MERGEvertices)
02912     return False;
02913   FORALLnew_facets {
02914     if (newfacet->newmerge) {
02915       newfacet->newmerge= False;
02916       FOREACHvertex_(newfacet->vertices) {
02917         if (vertex->delridge) {
02918           if (qh_rename_sharedvertex (vertex, newfacet)) {
02919             numshare++;
02920             vertexp--; /* repeat since deleted vertex */
02921           }
02922         }
02923       }
02924     }
02925   }
02926   FORALLvertex_(qh newvertex_list) {
02927     if (vertex->delridge && !vertex->deleted) {
02928       vertex->delridge= False;
02929       if (qh hull_dim >= 4 && qh_redundant_vertex (vertex)) {
02930         numrename++;
02931         if (qh_merge_degenredundant()) {
02932           degenredun= True;
02933           goto LABELrestart;
02934         }
02935       }
02936     }
02937   }
02938   trace1((qh ferr, "qh_reducevertices: renamed %d shared vertices and %d redundant vertices. Degen? %d\n",
02939           numshare, numrename, degenredun));
02940   return degenredun;
02941 } /* reducevertices */

02965                                                {
02966   vertexT *newvertex= NULL;
02967   setT *vertices, *ridges;
02968 
02969   trace3((qh ferr, "qh_redundant_vertex: check if v%d can be renamed\n", vertex->id));  
02970   if ((vertices= qh_neighbor_intersections (vertex))) {
02971     ridges= qh_vertexridges (vertex);
02972     if ((newvertex= qh_find_newvertex (vertex, vertices, ridges)))
02973       qh_renamevertex (vertex, newvertex, ridges, NULL, NULL);
02974     qh_settempfree (&ridges);
02975     qh_settempfree (&vertices);
02976   }
02977   return newvertex;
02978 } /* redundant_vertex */

02997                                               {
02998   ridgeT *ridge, **ridgep;
02999   vertexT *vertex, **vertexp;
03000   boolT foundrem= False;
03001 
03002   trace4((qh ferr, "qh_remove_extravertices: test f%d for extra vertices\n",
03003           facet->id));
03004   FOREACHvertex_(facet->vertices)
03005     vertex->seen= False;
03006   FOREACHridge_(facet->ridges) { 
03007     FOREACHvertex_(ridge->vertices)
03008       vertex->seen= True;
03009   }
03010   FOREACHvertex_(facet->vertices) {
03011     if (!vertex->seen) {
03012       foundrem= True;
03013       zinc_(Zremvertex);
03014       qh_setdelsorted (facet->vertices, vertex);
03015       qh_setdel (vertex->neighbors, facet);
03016       if (!qh_setsize (vertex->neighbors)) {
03017         vertex->deleted= True;
03018         qh_setappend (&qh del_vertices, vertex);
03019         zinc_(Zremvertexdel);
03020         trace2((qh ferr, "qh_remove_extravertices: v%d deleted because it's lost all ridges\n", vertex->id));
03021       }else
03022         trace3((qh ferr, "qh_remove_extravertices: v%d removed from f%d because it's lost all ridges\n", vertex->id, facet->id));
03023       vertexp--; /*repeat*/
03024     }
03025   }
03026   return foundrem;
03027 } /* remove_extravertices */

03056                                                                  {
03057   facetT *neighbor, **neighborp, *neighborA= NULL;
03058   setT *vertices, *ridges;
03059   vertexT *newvertex;
03060 
03061   if (qh_setsize (vertex->neighbors) == 2) {
03062     neighborA= SETfirstt_(vertex->neighbors, facetT);
03063     if (neighborA == facet)
03064       neighborA= SETsecondt_(vertex->neighbors, facetT);
03065   }else if (qh hull_dim == 3)
03066     return NULL;
03067   else {
03068     qh visit_id++;
03069     FOREACHneighbor_(facet)
03070       neighbor->visitid= qh visit_id;
03071     FOREACHneighbor_(vertex) {
03072       if (neighbor->visitid == qh visit_id) {
03073         if (neighborA)
03074           return NULL;
03075         neighborA= neighbor;
03076       }
03077     }
03078     if (!neighborA) {
03079       fprintf (qh ferr, "qhull internal error (qh_rename_sharedvertex): v%d's neighbors not in f%d\n",
03080         vertex->id, facet->id);
03081       qh_errprint ("ERRONEOUS", facet, NULL, NULL, vertex);
03082       qh_errexit (qh_ERRqhull, NULL, NULL);
03083     }
03084   }
03085   /* the vertex is shared by facet and neighborA */
03086   ridges= qh_settemp (qh TEMPsize);
03087   neighborA->visitid= ++qh visit_id;
03088   qh_vertexridges_facet (vertex, facet, &ridges);
03089   trace2((qh ferr, "qh_rename_sharedvertex: p%d (v%d) is shared by f%d (%d ridges) and f%d\n",
03090     qh_pointid(vertex->point), vertex->id, facet->id, qh_setsize (ridges), neighborA->id));
03091   zinc_(Zintersectnum);
03092   vertices= qh_vertexintersect_new (facet->vertices, neighborA->vertices);
03093   qh_setdel (vertices, vertex);
03094   qh_settemppush (vertices);
03095   if ((newvertex= qh_find_newvertex (vertex, vertices, ridges))) 
03096     qh_renamevertex (vertex, newvertex, ridges, facet, neighborA);
03097   qh_settempfree (&vertices);
03098   qh_settempfree (&ridges);
03099   return newvertex;
03100 } /* rename_sharedvertex */

03119                                                                                  {
03120   int nth= 0, oldnth;
03121   facetT *temp;
03122   vertexT *vertex, **vertexp;
03123 
03124   oldnth= qh_setindex (ridge->vertices, oldvertex);
03125   qh_setdelnthsorted (ridge->vertices, oldnth);
03126   FOREACHvertex_(ridge->vertices) {
03127     if (vertex == newvertex) {
03128       zinc_(Zdelridge);
03129       if (ridge->nonconvex) /* only one ridge has nonconvex set */
03130         qh_copynonconvex (ridge);
03131       qh_delridge (ridge);
03132       trace2((qh ferr, "qh_renameridgevertex: ridge r%d deleted.  It contained both v%d and v%d\n",
03133         ridge->id, oldvertex->id, newvertex->id));
03134       return;
03135     }
03136     if (vertex->id < newvertex->id)
03137       break;
03138     nth++;
03139   }
03140   qh_setaddnth(&ridge->vertices, nth, newvertex);
03141   if (abs(oldnth - nth)%2) {
03142     trace3((qh ferr, "qh_renameridgevertex: swapped the top and bottom of ridge r%d\n", 
03143             ridge->id));
03144     temp= ridge->top;
03145     ridge->top= ridge->bottom;
03146     ridge->bottom= temp;
03147   }
03148 } /* renameridgevertex */

03181                                                                                                                 {
03182   facetT *neighbor, **neighborp;
03183   ridgeT *ridge, **ridgep;
03184   boolT istrace= False;
03185 
03186   if (qh IStracing >= 2 || oldvertex->id == qh tracevertex_id ||
03187         newvertex->id == qh tracevertex_id)
03188     istrace= True;
03189   FOREACHridge_(ridges) 
03190     qh_renameridgevertex (ridge, oldvertex, newvertex);
03191   if (!oldfacet) {
03192     zinc_(Zrenameall);
03193     if (istrace)
03194       fprintf (qh ferr, "qh_renamevertex: renamed v%d to v%d in several facets\n",
03195                oldvertex->id, newvertex->id);
03196     FOREACHneighbor_(oldvertex) {
03197       qh_maydropneighbor (neighbor);
03198       qh_setdelsorted (neighbor->vertices, oldvertex);
03199       if (qh_remove_extravertices (neighbor))
03200         neighborp--; /* neighbor may be deleted */
03201     }
03202     if (!oldvertex->deleted) {
03203       oldvertex->deleted= True;
03204       qh_setappend (&qh del_vertices, oldvertex);
03205     }
03206   }else if (qh_setsize (oldvertex->neighbors) == 2) {
03207     zinc_(Zrenameshare);
03208     if (istrace)
03209       fprintf (qh ferr, "qh_renamevertex: renamed v%d to v%d in oldfacet f%d\n", 
03210                oldvertex->id, newvertex->id, oldfacet->id);
03211     FOREACHneighbor_(oldvertex)
03212       qh_setdelsorted (neighbor->vertices, oldvertex);
03213     oldvertex->deleted= True;
03214     qh_setappend (&qh del_vertices, oldvertex);
03215   }else {
03216     zinc_(Zrenamepinch);
03217     if (istrace || qh IStracing)
03218       fprintf (qh ferr, "qh_renamevertex: renamed pinched v%d to v%d between f%d and f%d\n", 
03219                oldvertex->id, newvertex->id, oldfacet->id, neighborA->id);
03220     qh_setdelsorted (oldfacet->vertices, oldvertex);
03221     qh_setdel (oldvertex->neighbors, oldfacet);
03222     qh_remove_extravertices (neighborA);
03223   }
03224 } /* renamevertex */

03261                                                             {
03262   realT dist, dist2= -REALmax, angle= -REALmax;
03263   boolT isconcave= False, iscoplanar= False, okangle= False;
03264 
03265   if (qh SKIPconvex && !qh POSTmerging)
03266     return False;
03267   if ((!qh MERGEexact || qh POSTmerging) && qh cos_max < REALmax/2) {
03268     angle= qh_getangle(facet->normal, neighbor->normal);
03269     zinc_(Zangletests);
03270     if (angle > qh cos_max) {
03271       zinc_(Zcoplanarangle);
03272       qh_appendmergeset(facet, neighbor, MRGanglecoplanar, &angle);
03273       trace2((qh ferr, "qh_test_appendmerge: coplanar angle %4.4g between f%d and f%d\n",
03274          angle, facet->id, neighbor->id));
03275       return True;
03276     }else
03277       okangle= True;
03278   }
03279   if (!facet->center)
03280     facet->center= qh_getcentrum (facet);
03281   zzinc_(Zcentrumtests);
03282   qh_distplane(facet->center, neighbor, &dist);
03283   if (dist > qh centrum_radius)
03284     isconcave= True;
03285   else {
03286     if (dist > -qh centrum_radius)
03287       iscoplanar= True;
03288     if (!neighbor->center)
03289       neighbor->center= qh_getcentrum (neighbor);
03290     zzinc_(Zcentrumtests);
03291     qh_distplane(neighbor->center, facet, &dist2);
03292     if (dist2 > qh centrum_radius)
03293       isconcave= True;
03294     else if (!iscoplanar && dist2 > -qh centrum_radius)
03295       iscoplanar= True;
03296   }
03297   if (!isconcave && (!iscoplanar || (qh MERGEexact && !qh POSTmerging)))
03298     return False;
03299   if (!okangle && qh ANGLEmerge) {
03300     angle= qh_getangle(facet->normal, neighbor->normal);
03301     zinc_(Zangletests);
03302   }
03303   if (isconcave) {
03304     zinc_(Zconcaveridge);
03305     if (qh ANGLEmerge)
03306       angle += qh_ANGLEconcave + 0.5;
03307     qh_appendmergeset(facet, neighbor, MRGconcave, &angle);
03308     trace0((qh ferr, "qh_test_appendmerge: concave f%d to f%d dist %4.4g and reverse dist %4.4g angle %4.4g during p%d\n",
03309            facet->id, neighbor->id, dist, dist2, angle, qh furthest_id));
03310   }else /* iscoplanar */ {
03311     zinc_(Zcoplanarcentrum);
03312     qh_appendmergeset(facet, neighbor, MRGcoplanar, &angle);
03313     trace2((qh ferr, "qh_test_appendmerge: coplanar f%d to f%d dist %4.4g, reverse dist %4.4g angle %4.4g\n",
03314               facet->id, neighbor->id, dist, dist2, angle));
03315   }
03316   return True;
03317 } /* test_appendmerge */

03344                                                        {
03345   facetT *newfacet, *neighbor, **neighborp;
03346   vertexT *vertex, **vertexp;
03347   int nummerges= 0;
03348 
03349   trace1((qh ferr, "qh_test_vneighbors: testing vertex neighbors for convexity\n"));
03350   if (!qh VERTEXneighbors)
03351     qh_vertexneighbors();
03352   FORALLnew_facets 
03353     newfacet->seen= False;
03354   FORALLnew_facets {
03355     newfacet->seen= True;
03356     newfacet->visitid= qh visit_id++;
03357     FOREACHneighbor_(newfacet)
03358       newfacet->visitid= qh visit_id;
03359     FOREACHvertex_(newfacet->vertices) {
03360       FOREACHneighbor_(vertex) {
03361         if (neighbor->seen || neighbor->visitid == qh visit_id)
03362           continue;
03363         if (qh_test_appendmerge (newfacet, neighbor))
03364           nummerges++;
03365       }
03366     }
03367   }
03368   zadd_(Ztestvneighbor, nummerges);
03369   trace1((qh ferr, "qh_test_vneighbors: found %d non-convex, vertex neighbors\n",
03370            nummerges));
03371   return (nummerges > 0);    
03372 } /* test_vneighbors */

03380                                                     {
03381   boolT waserror= False;
03382 
03383 #ifndef qh_NOtrace
03384   if (qh IStracing >= 4) 
03385     qh_errprint ("MERGED", facet2, NULL, NULL, NULL);
03386   if (facet2 == qh tracefacet || (qh tracevertex && qh tracevertex->newlist)) {
03387     fprintf (qh ferr, "qh_tracemerge: trace facet and vertex after merge of f%d and f%d, furthest p%d\n", facet1->id, facet2->id, qh furthest_id);
03388     if (facet2 != qh tracefacet)
03389       qh_errprint ("TRACE", qh tracefacet, 
03390         (qh tracevertex && qh tracevertex->neighbors) ? 
03391            SETfirstt_(qh tracevertex->neighbors, facetT) : NULL,
03392         NULL, qh tracevertex);      
03393   }
03394   if (qh tracevertex) {
03395     if (qh tracevertex->deleted)
03396       fprintf (qh ferr, "qh_tracemerge: trace vertex deleted at furthest p%d\n",
03397             qh furthest_id);
03398     else
03399       qh_checkvertex (qh tracevertex);
03400   }
03401   if (qh tracefacet) {
03402     qh_checkfacet (qh tracefacet, True, &waserror);
03403     if (waserror)
03404       qh_errexit (qh_ERRqhull, qh tracefacet, NULL);
03405   }
03406 #endif /* !qh_NOtrace */
03407   if (qh CHECKfrequently || qh IStracing >= 4) { /* can't check polygon here */
03408     qh_checkfacet (facet2, True, &waserror);
03409     if (waserror)
03410       qh_errexit(qh_ERRqhull, NULL, NULL);
03411   }
03412 } /* tracemerge */

03429                             {
03430   realT cpu;
03431   int total;
03432   time_t timedata;
03433   struct tm *tp;
03434 
03435   qh mergereport= zzval_(Ztotmerge);
03436   time (&timedata);
03437   tp= localtime (&timedata);
03438   cpu= qh_CPUclock;
03439   cpu /= qh_SECticks;
03440   total= zzval_(Ztotmerge) - zzval_(Zcyclehorizon) + zzval_(Zcyclefacettot);
03441   fprintf (qh ferr, "\n\
03442 At %d:%d:%d & %2.5g CPU secs, qhull has merged %d facets.  The hull\n\
03443   contains %d facets and %d vertices.\n",
03444       tp->tm_hour, tp->tm_min, tp->tm_sec, cpu,
03445       total, qh num_facets - qh num_visible,
03446       qh num_vertices-qh_setsize (qh del_vertices));
03447 } /* tracemerging */

03471                                                       {
03472   ridgeT *ridge, **ridgep;
03473   int size;
03474   
03475   facet2->tested= False;
03476   FOREACHridge_(facet1->ridges)
03477     ridge->tested= False;
03478   if (!facet2->center)
03479     return;
03480   size= qh_setsize (facet2->vertices);
03481   if (!facet2->keepcentrum) {
03482     if (size > qh hull_dim + qh_MAXnewcentrum) {
03483       facet2->keepcentrum= True;
03484       zinc_(Zwidevertices);
03485     }
03486   }else if (size <= qh hull_dim + qh_MAXnewcentrum) {
03487     /* center and keepcentrum was set */
03488     if (size == qh hull_dim || qh POSTmerging)
03489       facet2->keepcentrum= False; /* if many merges need to recompute centrum */
03490   }
03491   if (!facet2->keepcentrum) {
03492     qh_memfree (facet2->center, qh normal_size);
03493     facet2->center= NULL;
03494     FOREACHridge_(facet2->ridges)
03495       ridge->tested= False;
03496   }
03497 } /* updatetested */

03514                                         {
03515   facetT *neighbor, **neighborp;
03516   setT *ridges= qh_settemp (qh TEMPsize);
03517   int size;
03518 
03519   qh visit_id++;
03520   FOREACHneighbor_(vertex)
03521     neighbor->visitid= qh visit_id;
03522   FOREACHneighbor_(vertex) {
03523     if (*neighborp)   /* no new ridges in last neighbor */
03524       qh_vertexridges_facet (vertex, neighbor, &ridges);
03525   }
03526   if (qh PRINTstatistics || qh IStracing) {
03527     size= qh_setsize (ridges);
03528     zinc_(Zvertexridge);
03529     zadd_(Zvertexridgetot, size);
03530     zmax_(Zvertexridgemax, size);
03531     trace3((qh ferr, "qh_vertexridges: found %d ridges for v%d\n",
03532              size, vertex->id));
03533   }
03534   return ridges;
03535 } /* vertexridges */

03555                                                                            {
03556   ridgeT *ridge, **ridgep;
03557   facetT *neighbor;
03558 
03559   FOREACHridge_(facet->ridges) {
03560     neighbor= otherfacet_(ridge, facet);
03561     if (neighbor->visitid == qh visit_id 
03562     && qh_setin (ridge->vertices, vertex))
03563       qh_setappend (ridges, ridge);
03564   }
03565   facet->visitid= qh visit_id-1;
03566 } /* vertexridges_facet */

03578                                                     {
03579 
03580   qh_removefacet(facet);
03581   qh_prependfacet (facet, &qh visible_list);
03582   qh num_visible++;
03583   facet->visible= True;
03584   facet->f.replace= replace;
03585 } /* willdelete */