merge.c
Go to the documentation of this file.
00001 /*<html><pre>  -<a                             href="qh-merge.htm#TOC"
00002   >-------------------------------</a><a name="TOP">-</a>
00003 
00004    merge.c
00005    merges non-convex facets
00006 
00007    see qh-merge.htm and merge.h
00008 
00009    other modules call qh_premerge() and qh_postmerge()
00010 
00011    the user may call qh_postmerge() to perform additional merges.
00012 
00013    To remove deleted facets and vertices (qhull() in libqhull.c):
00014      qh_partitionvisible(!qh_ALL, &numoutside);  // visible_list, newfacet_list
00015      qh_deletevisible();         // qh.visible_list
00016      qh_resetlists(False, qh_RESETvisible);       // qh.visible_list newvertex_list newfacet_list
00017 
00018    assumes qh.CENTERtype= centrum
00019 
00020    merges occur in qh_mergefacet and in qh_mergecycle
00021    vertex->neighbors not set until the first merge occurs
00022 
00023    Copyright (c) 1993-2011 C.B. Barber.
00024    $Id: //main/2011/qhull/src/libqhull/merge.c#2 $$Change: 1342 $
00025    $DateTime: 2011/03/07 21:55:47 $$Author: bbarber $
00026 */
00027 
00028 #include "qhull_a.h"
00029 
00030 #ifndef qh_NOmerge
00031 
00032 /*===== functions(alphabetical after premerge and postmerge) ======*/
00033 
00034 /*-<a                             href="qh-merge.htm#TOC"
00035   >-------------------------------</a><a name="premerge">-</a>
00036 
00037   qh_premerge( apex, maxcentrum )
00038     pre-merge nonconvex facets in qh.newfacet_list for apex
00039     maxcentrum defines coplanar and concave (qh_test_appendmerge)
00040 
00041   returns:
00042     deleted facets added to qh.visible_list with facet->visible set
00043 
00044   notes:
00045     uses globals, qh.MERGEexact, qh.PREmerge
00046 
00047   design:
00048     mark duplicate ridges in qh.newfacet_list
00049     merge facet cycles in qh.newfacet_list
00050     merge duplicate ridges and concave facets in qh.newfacet_list
00051     check merged facet cycles for degenerate and redundant facets
00052     merge degenerate and redundant facets
00053     collect coplanar and concave facets
00054     merge concave, coplanar, degenerate, and redundant facets
00055 */
00056 void qh_premerge(vertexT *apex, realT maxcentrum, realT maxangle) {
00057   boolT othermerge= False;
00058   facetT *newfacet;
00059 
00060   if (qh ZEROcentrum && qh_checkzero(!qh_ALL))
00061     return;
00062   trace2((qh ferr, 2008, "qh_premerge: premerge centrum %2.2g angle %2.2g for apex v%d facetlist f%d\n",
00063             maxcentrum, maxangle, apex->id, getid_(qh newfacet_list)));
00064   if (qh IStracing >= 4 && qh num_facets < 50)
00065     qh_printlists();
00066   qh centrum_radius= maxcentrum;
00067   qh cos_max= maxangle;
00068   qh degen_mergeset= qh_settemp(qh TEMPsize);
00069   qh facet_mergeset= qh_settemp(qh TEMPsize);
00070   if (qh hull_dim >=3) {
00071     qh_mark_dupridges(qh newfacet_list); /* facet_mergeset */
00072     qh_mergecycle_all(qh newfacet_list, &othermerge);
00073     qh_forcedmerges(&othermerge /* qh facet_mergeset */);
00074     FORALLnew_facets {  /* test samecycle merges */
00075       if (!newfacet->simplicial && !newfacet->mergeridge)
00076         qh_degen_redundant_neighbors(newfacet, NULL);
00077     }
00078     if (qh_merge_degenredundant())
00079       othermerge= True;
00080   }else /* qh hull_dim == 2 */
00081     qh_mergecycle_all(qh newfacet_list, &othermerge);
00082   qh_flippedmerges(qh newfacet_list, &othermerge);
00083   if (!qh MERGEexact || zzval_(Ztotmerge)) {
00084     zinc_(Zpremergetot);
00085     qh POSTmerging= False;
00086     qh_getmergeset_initial(qh newfacet_list);
00087     qh_all_merges(othermerge, False);
00088   }
00089   qh_settempfree(&qh facet_mergeset);
00090   qh_settempfree(&qh degen_mergeset);
00091 } /* premerge */
00092 
00093 /*-<a                             href="qh-merge.htm#TOC"
00094   >-------------------------------</a><a name="postmerge">-</a>
00095 
00096   qh_postmerge( reason, maxcentrum, maxangle, vneighbors )
00097     post-merge nonconvex facets as defined by maxcentrum and maxangle
00098     'reason' is for reporting progress
00099     if vneighbors,
00100       calls qh_test_vneighbors at end of qh_all_merge
00101     if firstmerge,
00102       calls qh_reducevertices before qh_getmergeset
00103 
00104   returns:
00105     if first call (qh.visible_list != qh.facet_list),
00106       builds qh.facet_newlist, qh.newvertex_list
00107     deleted facets added to qh.visible_list with facet->visible
00108     qh.visible_list == qh.facet_list
00109 
00110   notes:
00111 
00112 
00113   design:
00114     if first call
00115       set qh.visible_list and qh.newfacet_list to qh.facet_list
00116       add all facets to qh.newfacet_list
00117       mark non-simplicial facets, facet->newmerge
00118       set qh.newvertext_list to qh.vertex_list
00119       add all vertices to qh.newvertex_list
00120       if a pre-merge occured
00121         set vertex->delridge {will retest the ridge}
00122         if qh.MERGEexact
00123           call qh_reducevertices()
00124       if no pre-merging
00125         merge flipped facets
00126     determine non-convex facets
00127     merge all non-convex facets
00128 */
00129 void qh_postmerge(const char *reason, realT maxcentrum, realT maxangle,
00130                       boolT vneighbors) {
00131   facetT *newfacet;
00132   boolT othermerges= False;
00133   vertexT *vertex;
00134 
00135   if (qh REPORTfreq || qh IStracing) {
00136     qh_buildtracing(NULL, NULL);
00137     qh_printsummary(qh ferr);
00138     if (qh PRINTstatistics)
00139       qh_printallstatistics(qh ferr, "reason");
00140     qh_fprintf(qh ferr, 8062, "\n%s with 'C%.2g' and 'A%.2g'\n",
00141         reason, maxcentrum, maxangle);
00142   }
00143   trace2((qh ferr, 2009, "qh_postmerge: postmerge.  test vneighbors? %d\n",
00144             vneighbors));
00145   qh centrum_radius= maxcentrum;
00146   qh cos_max= maxangle;
00147   qh POSTmerging= True;
00148   qh degen_mergeset= qh_settemp(qh TEMPsize);
00149   qh facet_mergeset= qh_settemp(qh TEMPsize);
00150   if (qh visible_list != qh facet_list) {  /* first call */
00151     qh NEWfacets= True;
00152     qh visible_list= qh newfacet_list= qh facet_list;
00153     FORALLnew_facets {
00154       newfacet->newfacet= True;
00155        if (!newfacet->simplicial)
00156         newfacet->newmerge= True;
00157      zinc_(Zpostfacets);
00158     }
00159     qh newvertex_list= qh vertex_list;
00160     FORALLvertices
00161       vertex->newlist= True;
00162     if (qh VERTEXneighbors) { /* a merge has occurred */
00163       FORALLvertices
00164         vertex->delridge= True; /* test for redundant, needed? */
00165       if (qh MERGEexact) {
00166         if (qh hull_dim <= qh_DIMreduceBuild)
00167           qh_reducevertices(); /* was skipped during pre-merging */
00168       }
00169     }
00170     if (!qh PREmerge && !qh MERGEexact)
00171       qh_flippedmerges(qh newfacet_list, &othermerges);
00172   }
00173   qh_getmergeset_initial(qh newfacet_list);
00174   qh_all_merges(False, vneighbors);
00175   qh_settempfree(&qh facet_mergeset);
00176   qh_settempfree(&qh degen_mergeset);
00177 } /* post_merge */
00178 
00179 /*-<a                             href="qh-merge.htm#TOC"
00180   >-------------------------------</a><a name="all_merges">-</a>
00181 
00182   qh_all_merges( othermerge, vneighbors )
00183     merge all non-convex facets
00184 
00185     set othermerge if already merged facets (for qh_reducevertices)
00186     if vneighbors
00187       tests vertex neighbors for convexity at end
00188     qh.facet_mergeset lists the non-convex ridges in qh_newfacet_list
00189     qh.degen_mergeset is defined
00190     if qh.MERGEexact && !qh.POSTmerging,
00191       does not merge coplanar facets
00192 
00193   returns:
00194     deleted facets added to qh.visible_list with facet->visible
00195     deleted vertices added qh.delvertex_list with vertex->delvertex
00196 
00197   notes:
00198     unless !qh.MERGEindependent,
00199       merges facets in independent sets
00200     uses qh.newfacet_list as argument since merges call qh_removefacet()
00201 
00202   design:
00203     while merges occur
00204       for each merge in qh.facet_mergeset
00205         unless one of the facets was already merged in this pass
00206           merge the facets
00207         test merged facets for additional merges
00208         add merges to qh.facet_mergeset
00209       if vertices record neighboring facets
00210         rename redundant vertices
00211           update qh.facet_mergeset
00212     if vneighbors ??
00213       tests vertex neighbors for convexity at end
00214 */
00215 void qh_all_merges(boolT othermerge, boolT vneighbors) {
00216   facetT *facet1, *facet2;
00217   mergeT *merge;
00218   boolT wasmerge= True, isreduce;
00219   void **freelistp;  /* used !qh_NOmem */
00220   vertexT *vertex;
00221   mergeType mergetype;
00222   int numcoplanar=0, numconcave=0, numdegenredun= 0, numnewmerges= 0;
00223 
00224   trace2((qh ferr, 2010, "qh_all_merges: starting to merge facets beginning from f%d\n",
00225             getid_(qh newfacet_list)));
00226   while (True) {
00227     wasmerge= False;
00228     while (qh_setsize(qh facet_mergeset)) {
00229       while ((merge= (mergeT*)qh_setdellast(qh facet_mergeset))) {
00230         facet1= merge->facet1;
00231         facet2= merge->facet2;
00232         mergetype= merge->type;
00233         qh_memfree_(merge, (int)sizeof(mergeT), freelistp);
00234         if (facet1->visible || facet2->visible) /*deleted facet*/
00235           continue;
00236         if ((facet1->newfacet && !facet1->tested)
00237                 || (facet2->newfacet && !facet2->tested)) {
00238           if (qh MERGEindependent && mergetype <= MRGanglecoplanar)
00239             continue;      /* perform independent sets of merges */
00240         }
00241         qh_merge_nonconvex(facet1, facet2, mergetype);
00242         numdegenredun += qh_merge_degenredundant();
00243         numnewmerges++;
00244         wasmerge= True;
00245         if (mergetype == MRGconcave)
00246           numconcave++;
00247         else /* MRGcoplanar or MRGanglecoplanar */
00248           numcoplanar++;
00249       } /* while setdellast */
00250       if (qh POSTmerging && qh hull_dim <= qh_DIMreduceBuild
00251       && numnewmerges > qh_MAXnewmerges) {
00252         numnewmerges= 0;
00253         qh_reducevertices();  /* otherwise large post merges too slow */
00254       }
00255       qh_getmergeset(qh newfacet_list); /* facet_mergeset */
00256     } /* while mergeset */
00257     if (qh VERTEXneighbors) {
00258       isreduce= False;
00259       if (qh hull_dim >=4 && qh POSTmerging) {
00260         FORALLvertices
00261           vertex->delridge= True;
00262         isreduce= True;
00263       }
00264       if ((wasmerge || othermerge) && (!qh MERGEexact || qh POSTmerging)
00265           && qh hull_dim <= qh_DIMreduceBuild) {
00266         othermerge= False;
00267         isreduce= True;
00268       }
00269       if (isreduce) {
00270         if (qh_reducevertices()) {
00271           qh_getmergeset(qh newfacet_list); /* facet_mergeset */
00272           continue;
00273         }
00274       }
00275     }
00276     if (vneighbors && qh_test_vneighbors(/* qh newfacet_list */))
00277       continue;
00278     break;
00279   } /* while (True) */
00280   if (qh CHECKfrequently && !qh MERGEexact) {
00281     qh old_randomdist= qh RANDOMdist;
00282     qh RANDOMdist= False;
00283     qh_checkconvex(qh newfacet_list, qh_ALGORITHMfault);
00284     /* qh_checkconnect(); [this is slow and it changes the facet order] */
00285     qh RANDOMdist= qh old_randomdist;
00286   }
00287   trace1((qh ferr, 1009, "qh_all_merges: merged %d coplanar facets %d concave facets and %d degen or redundant facets.\n",
00288     numcoplanar, numconcave, numdegenredun));
00289   if (qh IStracing >= 4 && qh num_facets < 50)
00290     qh_printlists();
00291 } /* all_merges */
00292 
00293 
00294 /*-<a                             href="qh-merge.htm#TOC"
00295   >-------------------------------</a><a name="appendmergeset">-</a>
00296 
00297   qh_appendmergeset( facet, neighbor, mergetype, angle )
00298     appends an entry to qh.facet_mergeset or qh.degen_mergeset
00299 
00300     angle ignored if NULL or !qh.ANGLEmerge
00301 
00302   returns:
00303     merge appended to facet_mergeset or degen_mergeset
00304       sets ->degenerate or ->redundant if degen_mergeset
00305 
00306   see:
00307     qh_test_appendmerge()
00308 
00309   design:
00310     allocate merge entry
00311     if regular merge
00312       append to qh.facet_mergeset
00313     else if degenerate merge and qh.facet_mergeset is all degenerate
00314       append to qh.degen_mergeset
00315     else if degenerate merge
00316       prepend to qh.degen_mergeset
00317     else if redundant merge
00318       append to qh.degen_mergeset
00319 */
00320 void qh_appendmergeset(facetT *facet, facetT *neighbor, mergeType mergetype, realT *angle) {
00321   mergeT *merge, *lastmerge;
00322   void **freelistp; /* used !qh_NOmem */
00323 
00324   if (facet->redundant)
00325     return;
00326   if (facet->degenerate && mergetype == MRGdegen)
00327     return;
00328   qh_memalloc_((int)sizeof(mergeT), freelistp, merge, mergeT);
00329   merge->facet1= facet;
00330   merge->facet2= neighbor;
00331   merge->type= mergetype;
00332   if (angle && qh ANGLEmerge)
00333     merge->angle= *angle;
00334   if (mergetype < MRGdegen)
00335     qh_setappend(&(qh facet_mergeset), merge);
00336   else if (mergetype == MRGdegen) {
00337     facet->degenerate= True;
00338     if (!(lastmerge= (mergeT*)qh_setlast(qh degen_mergeset))
00339     || lastmerge->type == MRGdegen)
00340       qh_setappend(&(qh degen_mergeset), merge);
00341     else
00342       qh_setaddnth(&(qh degen_mergeset), 0, merge);
00343   }else if (mergetype == MRGredundant) {
00344     facet->redundant= True;
00345     qh_setappend(&(qh degen_mergeset), merge);
00346   }else /* mergetype == MRGmirror */ {
00347     if (facet->redundant || neighbor->redundant) {
00348       qh_fprintf(qh ferr, 6092, "qhull error (qh_appendmergeset): facet f%d or f%d is already a mirrored facet\n",
00349            facet->id, neighbor->id);
00350       qh_errexit2 (qh_ERRqhull, facet, neighbor);
00351     }
00352     if (!qh_setequal(facet->vertices, neighbor->vertices)) {
00353       qh_fprintf(qh ferr, 6093, "qhull error (qh_appendmergeset): mirrored facets f%d and f%d do not have the same vertices\n",
00354            facet->id, neighbor->id);
00355       qh_errexit2 (qh_ERRqhull, facet, neighbor);
00356     }
00357     facet->redundant= True;
00358     neighbor->redundant= True;
00359     qh_setappend(&(qh degen_mergeset), merge);
00360   }
00361 } /* appendmergeset */
00362 
00363 
00364 /*-<a                             href="qh-merge.htm#TOC"
00365   >-------------------------------</a><a name="basevertices">-</a>
00366 
00367   qh_basevertices( samecycle )
00368     return temporary set of base vertices for samecycle
00369     samecycle is first facet in the cycle
00370     assumes apex is SETfirst_( samecycle->vertices )
00371 
00372   returns:
00373     vertices(settemp)
00374     all ->seen are cleared
00375 
00376   notes:
00377     uses qh_vertex_visit;
00378 
00379   design:
00380     for each facet in samecycle
00381       for each unseen vertex in facet->vertices
00382         append to result
00383 */
00384 setT *qh_basevertices(facetT *samecycle) {
00385   facetT *same;
00386   vertexT *apex, *vertex, **vertexp;
00387   setT *vertices= qh_settemp(qh TEMPsize);
00388 
00389   apex= SETfirstt_(samecycle->vertices, vertexT);
00390   apex->visitid= ++qh vertex_visit;
00391   FORALLsame_cycle_(samecycle) {
00392     if (same->mergeridge)
00393       continue;
00394     FOREACHvertex_(same->vertices) {
00395       if (vertex->visitid != qh vertex_visit) {
00396         qh_setappend(&vertices, vertex);
00397         vertex->visitid= qh vertex_visit;
00398         vertex->seen= False;
00399       }
00400     }
00401   }
00402   trace4((qh ferr, 4019, "qh_basevertices: found %d vertices\n",
00403          qh_setsize(vertices)));
00404   return vertices;
00405 } /* basevertices */
00406 
00407 /*-<a                             href="qh-merge.htm#TOC"
00408   >-------------------------------</a><a name="checkconnect">-</a>
00409 
00410   qh_checkconnect()
00411     check that new facets are connected
00412     new facets are on qh.newfacet_list
00413 
00414   notes:
00415     this is slow and it changes the order of the facets
00416     uses qh.visit_id
00417 
00418   design:
00419     move first new facet to end of qh.facet_list
00420     for all newly appended facets
00421       append unvisited neighbors to end of qh.facet_list
00422     for all new facets
00423       report error if unvisited
00424 */
00425 void qh_checkconnect(void /* qh newfacet_list */) {
00426   facetT *facet, *newfacet, *errfacet= NULL, *neighbor, **neighborp;
00427 
00428   facet= qh newfacet_list;
00429   qh_removefacet(facet);
00430   qh_appendfacet(facet);
00431   facet->visitid= ++qh visit_id;
00432   FORALLfacet_(facet) {
00433     FOREACHneighbor_(facet) {
00434       if (neighbor->visitid != qh visit_id) {
00435         qh_removefacet(neighbor);
00436         qh_appendfacet(neighbor);
00437         neighbor->visitid= qh visit_id;
00438       }
00439     }
00440   }
00441   FORALLnew_facets {
00442     if (newfacet->visitid == qh visit_id)
00443       break;
00444     qh_fprintf(qh ferr, 6094, "qhull error: f%d is not attached to the new facets\n",
00445          newfacet->id);
00446     errfacet= newfacet;
00447   }
00448   if (errfacet)
00449     qh_errexit(qh_ERRqhull, errfacet, NULL);
00450 } /* checkconnect */
00451 
00452 /*-<a                             href="qh-merge.htm#TOC"
00453   >-------------------------------</a><a name="checkzero">-</a>
00454 
00455   qh_checkzero( testall )
00456     check that facets are clearly convex for qh.DISTround with qh.MERGEexact
00457 
00458     if testall,
00459       test all facets for qh.MERGEexact post-merging
00460     else
00461       test qh.newfacet_list
00462 
00463     if qh.MERGEexact,
00464       allows coplanar ridges
00465       skips convexity test while qh.ZEROall_ok
00466 
00467   returns:
00468     True if all facets !flipped, !dupridge, normal
00469          if all horizon facets are simplicial
00470          if all vertices are clearly below neighbor
00471          if all opposite vertices of horizon are below
00472     clears qh.ZEROall_ok if any problems or coplanar facets
00473 
00474   notes:
00475     uses qh.vertex_visit
00476     horizon facets may define multiple new facets
00477 
00478   design:
00479     for all facets in qh.newfacet_list or qh.facet_list
00480       check for flagged faults (flipped, etc.)
00481     for all facets in qh.newfacet_list or qh.facet_list
00482       for each neighbor of facet
00483         skip horizon facets for qh.newfacet_list
00484         test the opposite vertex
00485       if qh.newfacet_list
00486         test the other vertices in the facet's horizon facet
00487 */
00488 boolT qh_checkzero(boolT testall) {
00489   facetT *facet, *neighbor, **neighborp;
00490   facetT *horizon, *facetlist;
00491   int neighbor_i;
00492   vertexT *vertex, **vertexp;
00493   realT dist;
00494 
00495   if (testall)
00496     facetlist= qh facet_list;
00497   else {
00498     facetlist= qh newfacet_list;
00499     FORALLfacet_(facetlist) {
00500       horizon= SETfirstt_(facet->neighbors, facetT);
00501       if (!horizon->simplicial)
00502         goto LABELproblem;
00503       if (facet->flipped || facet->dupridge || !facet->normal)
00504         goto LABELproblem;
00505     }
00506     if (qh MERGEexact && qh ZEROall_ok) {
00507       trace2((qh ferr, 2011, "qh_checkzero: skip convexity check until first pre-merge\n"));
00508       return True;
00509     }
00510   }
00511   FORALLfacet_(facetlist) {
00512     qh vertex_visit++;
00513     neighbor_i= 0;
00514     horizon= NULL;
00515     FOREACHneighbor_(facet) {
00516       if (!neighbor_i && !testall) {
00517         horizon= neighbor;
00518         neighbor_i++;
00519         continue; /* horizon facet tested in qh_findhorizon */
00520       }
00521       vertex= SETelemt_(facet->vertices, neighbor_i++, vertexT);
00522       vertex->visitid= qh vertex_visit;
00523       zzinc_(Zdistzero);
00524       qh_distplane(vertex->point, neighbor, &dist);
00525       if (dist >= -qh DISTround) {
00526         qh ZEROall_ok= False;
00527         if (!qh MERGEexact || testall || dist > qh DISTround)
00528           goto LABELnonconvex;
00529       }
00530     }
00531     if (!testall) {
00532       FOREACHvertex_(horizon->vertices) {
00533         if (vertex->visitid != qh vertex_visit) {
00534           zzinc_(Zdistzero);
00535           qh_distplane(vertex->point, facet, &dist);
00536           if (dist >= -qh DISTround) {
00537             qh ZEROall_ok= False;
00538             if (!qh MERGEexact || dist > qh DISTround)
00539               goto LABELnonconvex;
00540           }
00541           break;
00542         }
00543       }
00544     }
00545   }
00546   trace2((qh ferr, 2012, "qh_checkzero: testall %d, facets are %s\n", testall,
00547         (qh MERGEexact && !testall) ?
00548            "not concave, flipped, or duplicate ridged" : "clearly convex"));
00549   return True;
00550 
00551  LABELproblem:
00552   qh ZEROall_ok= False;
00553   trace2((qh ferr, 2013, "qh_checkzero: facet f%d needs pre-merging\n",
00554        facet->id));
00555   return False;
00556 
00557  LABELnonconvex:
00558   trace2((qh ferr, 2014, "qh_checkzero: facet f%d and f%d are not clearly convex.  v%d dist %.2g\n",
00559          facet->id, neighbor->id, vertex->id, dist));
00560   return False;
00561 } /* checkzero */
00562 
00563 /*-<a                             href="qh-merge.htm#TOC"
00564   >-------------------------------</a><a name="compareangle">-</a>
00565 
00566   qh_compareangle( angle1, angle2 )
00567     used by qsort() to order merges by angle
00568 */
00569 int qh_compareangle(const void *p1, const void *p2) {
00570   const mergeT *a= *((mergeT *const*)p1), *b= *((mergeT *const*)p2);
00571 
00572   return((a->angle > b->angle) ? 1 : -1);
00573 } /* compareangle */
00574 
00575 /*-<a                             href="qh-merge.htm#TOC"
00576   >-------------------------------</a><a name="comparemerge">-</a>
00577 
00578   qh_comparemerge( merge1, merge2 )
00579     used by qsort() to order merges
00580 */
00581 int qh_comparemerge(const void *p1, const void *p2) {
00582   const mergeT *a= *((mergeT *const*)p1), *b= *((mergeT *const*)p2);
00583 
00584   return(a->type - b->type);
00585 } /* comparemerge */
00586 
00587 /*-<a                             href="qh-merge.htm#TOC"
00588   >-------------------------------</a><a name="comparevisit">-</a>
00589 
00590   qh_comparevisit( vertex1, vertex2 )
00591     used by qsort() to order vertices by their visitid
00592 */
00593 int qh_comparevisit(const void *p1, const void *p2) {
00594   const vertexT *a= *((vertexT *const*)p1), *b= *((vertexT *const*)p2);
00595 
00596   return(a->visitid - b->visitid);
00597 } /* comparevisit */
00598 
00599 /*-<a                             href="qh-merge.htm#TOC"
00600   >-------------------------------</a><a name="copynonconvex">-</a>
00601 
00602   qh_copynonconvex( atridge )
00603     set non-convex flag on other ridges (if any) between same neighbors
00604 
00605   notes:
00606     may be faster if use smaller ridge set
00607 
00608   design:
00609     for each ridge of atridge's top facet
00610       if ridge shares the same neighbor
00611         set nonconvex flag
00612 */
00613 void qh_copynonconvex(ridgeT *atridge) {
00614   facetT *facet, *otherfacet;
00615   ridgeT *ridge, **ridgep;
00616 
00617   facet= atridge->top;
00618   otherfacet= atridge->bottom;
00619   FOREACHridge_(facet->ridges) {
00620     if (otherfacet == otherfacet_(ridge, facet) && ridge != atridge) {
00621       ridge->nonconvex= True;
00622       trace4((qh ferr, 4020, "qh_copynonconvex: moved nonconvex flag from r%d to r%d\n",
00623               atridge->id, ridge->id));
00624       break;
00625     }
00626   }
00627 } /* copynonconvex */
00628 
00629 /*-<a                             href="qh-merge.htm#TOC"
00630   >-------------------------------</a><a name="degen_redundant_facet">-</a>
00631 
00632   qh_degen_redundant_facet( facet )
00633     check facet for degen. or redundancy
00634 
00635   notes:
00636     bumps vertex_visit
00637     called if a facet was redundant but no longer is (qh_merge_degenredundant)
00638     qh_appendmergeset() only appends first reference to facet (i.e., redundant)
00639 
00640   see:
00641     qh_degen_redundant_neighbors()
00642 
00643   design:
00644     test for redundant neighbor
00645     test for degenerate facet
00646 */
00647 void qh_degen_redundant_facet(facetT *facet) {
00648   vertexT *vertex, **vertexp;
00649   facetT *neighbor, **neighborp;
00650 
00651   trace4((qh ferr, 4021, "qh_degen_redundant_facet: test facet f%d for degen/redundant\n",
00652           facet->id));
00653   FOREACHneighbor_(facet) {
00654     qh vertex_visit++;
00655     FOREACHvertex_(neighbor->vertices)
00656       vertex->visitid= qh vertex_visit;
00657     FOREACHvertex_(facet->vertices) {
00658       if (vertex->visitid != qh vertex_visit)
00659         break;
00660     }
00661     if (!vertex) {
00662       qh_appendmergeset(facet, neighbor, MRGredundant, NULL);
00663       trace2((qh ferr, 2015, "qh_degen_redundant_facet: f%d is contained in f%d.  merge\n", facet->id, neighbor->id));
00664       return;
00665     }
00666   }
00667   if (qh_setsize(facet->neighbors) < qh hull_dim) {
00668     qh_appendmergeset(facet, facet, MRGdegen, NULL);
00669     trace2((qh ferr, 2016, "qh_degen_redundant_neighbors: f%d is degenerate.\n", facet->id));
00670   }
00671 } /* degen_redundant_facet */
00672 
00673 
00674 /*-<a                             href="qh-merge.htm#TOC"
00675   >-------------------------------</a><a name="degen_redundant_neighbors">-</a>
00676 
00677   qh_degen_redundant_neighbors( facet, delfacet,  )
00678     append degenerate and redundant neighbors to facet_mergeset
00679     if delfacet,
00680       only checks neighbors of both delfacet and facet
00681     also checks current facet for degeneracy
00682 
00683   notes:
00684     bumps vertex_visit
00685     called for each qh_mergefacet() and qh_mergecycle()
00686     merge and statistics occur in merge_nonconvex
00687     qh_appendmergeset() only appends first reference to facet (i.e., redundant)
00688       it appends redundant facets after degenerate ones
00689 
00690     a degenerate facet has fewer than hull_dim neighbors
00691     a redundant facet's vertices is a subset of its neighbor's vertices
00692     tests for redundant merges first (appendmergeset is nop for others)
00693     in a merge, only needs to test neighbors of merged facet
00694 
00695   see:
00696     qh_merge_degenredundant() and qh_degen_redundant_facet()
00697 
00698   design:
00699     test for degenerate facet
00700     test for redundant neighbor
00701     test for degenerate neighbor
00702 */
00703 void qh_degen_redundant_neighbors(facetT *facet, facetT *delfacet) {
00704   vertexT *vertex, **vertexp;
00705   facetT *neighbor, **neighborp;
00706   int size;
00707 
00708   trace4((qh ferr, 4022, "qh_degen_redundant_neighbors: test neighbors of f%d with delfacet f%d\n",
00709           facet->id, getid_(delfacet)));
00710   if ((size= qh_setsize(facet->neighbors)) < qh hull_dim) {
00711     qh_appendmergeset(facet, facet, MRGdegen, NULL);
00712     trace2((qh ferr, 2017, "qh_degen_redundant_neighbors: f%d is degenerate with %d neighbors.\n", facet->id, size));
00713   }
00714   if (!delfacet)
00715     delfacet= facet;
00716   qh vertex_visit++;
00717   FOREACHvertex_(facet->vertices)
00718     vertex->visitid= qh vertex_visit;
00719   FOREACHneighbor_(delfacet) {
00720     /* uses early out instead of checking vertex count */
00721     if (neighbor == facet)
00722       continue;
00723     FOREACHvertex_(neighbor->vertices) {
00724       if (vertex->visitid != qh vertex_visit)
00725         break;
00726     }
00727     if (!vertex) {
00728       qh_appendmergeset(neighbor, facet, MRGredundant, NULL);
00729       trace2((qh ferr, 2018, "qh_degen_redundant_neighbors: f%d is contained in f%d.  merge\n", neighbor->id, facet->id));
00730     }
00731   }
00732   FOREACHneighbor_(delfacet) {   /* redundant merges occur first */
00733     if (neighbor == facet)
00734       continue;
00735     if ((size= qh_setsize(neighbor->neighbors)) < qh hull_dim) {
00736       qh_appendmergeset(neighbor, neighbor, MRGdegen, NULL);
00737       trace2((qh ferr, 2019, "qh_degen_redundant_neighbors: f%d is degenerate with %d neighbors.  Neighbor of f%d.\n", neighbor->id, size, facet->id));
00738     }
00739   }
00740 } /* degen_redundant_neighbors */
00741 
00742 
00743 /*-<a                             href="qh-merge.htm#TOC"
00744   >-------------------------------</a><a name="find_newvertex">-</a>
00745 
00746   qh_find_newvertex( oldvertex, vertices, ridges )
00747     locate new vertex for renaming old vertex
00748     vertices is a set of possible new vertices
00749       vertices sorted by number of deleted ridges
00750 
00751   returns:
00752     newvertex or NULL
00753       each ridge includes both vertex and oldvertex
00754     vertices sorted by number of deleted ridges
00755 
00756   notes:
00757     modifies vertex->visitid
00758     new vertex is in one of the ridges
00759     renaming will not cause a duplicate ridge
00760     renaming will minimize the number of deleted ridges
00761     newvertex may not be adjacent in the dual (though unlikely)
00762 
00763   design:
00764     for each vertex in vertices
00765       set vertex->visitid to number of references in ridges
00766     remove unvisited vertices
00767     set qh.vertex_visit above all possible values
00768     sort vertices by number of references in ridges
00769     add each ridge to qh.hash_table
00770     for each vertex in vertices
00771       look for a vertex that would not cause a duplicate ridge after a rename
00772 */
00773 vertexT *qh_find_newvertex(vertexT *oldvertex, setT *vertices, setT *ridges) {
00774   vertexT *vertex, **vertexp;
00775   setT *newridges;
00776   ridgeT *ridge, **ridgep;
00777   int size, hashsize;
00778   int hash;
00779 
00780 #ifndef qh_NOtrace
00781   if (qh IStracing >= 4) {
00782     qh_fprintf(qh ferr, 8063, "qh_find_newvertex: find new vertex for v%d from ",
00783              oldvertex->id);
00784     FOREACHvertex_(vertices)
00785       qh_fprintf(qh ferr, 8064, "v%d ", vertex->id);
00786     FOREACHridge_(ridges)
00787       qh_fprintf(qh ferr, 8065, "r%d ", ridge->id);
00788     qh_fprintf(qh ferr, 8066, "\n");
00789   }
00790 #endif
00791   FOREACHvertex_(vertices)
00792     vertex->visitid= 0;
00793   FOREACHridge_(ridges) {
00794     FOREACHvertex_(ridge->vertices)
00795       vertex->visitid++;
00796   }
00797   FOREACHvertex_(vertices) {
00798     if (!vertex->visitid) {
00799       qh_setdelnth(vertices, SETindex_(vertices,vertex));
00800       vertexp--; /* repeat since deleted this vertex */
00801     }
00802   }
00803   qh vertex_visit += (unsigned int)qh_setsize(ridges);
00804   if (!qh_setsize(vertices)) {
00805     trace4((qh ferr, 4023, "qh_find_newvertex: vertices not in ridges for v%d\n",
00806             oldvertex->id));
00807     return NULL;
00808   }
00809   qsort(SETaddr_(vertices, vertexT), (size_t)qh_setsize(vertices),
00810                 sizeof(vertexT *), qh_comparevisit);
00811   /* can now use qh vertex_visit */
00812   if (qh PRINTstatistics) {
00813     size= qh_setsize(vertices);
00814     zinc_(Zintersect);
00815     zadd_(Zintersecttot, size);
00816     zmax_(Zintersectmax, size);
00817   }
00818   hashsize= qh_newhashtable(qh_setsize(ridges));
00819   FOREACHridge_(ridges)
00820     qh_hashridge(qh hash_table, hashsize, ridge, oldvertex);
00821   FOREACHvertex_(vertices) {
00822     newridges= qh_vertexridges(vertex);
00823     FOREACHridge_(newridges) {
00824       if (qh_hashridge_find(qh hash_table, hashsize, ridge, vertex, oldvertex, &hash)) {
00825         zinc_(Zdupridge);
00826         break;
00827       }
00828     }
00829     qh_settempfree(&newridges);
00830     if (!ridge)
00831       break;  /* found a rename */
00832   }
00833   if (vertex) {
00834     /* counted in qh_renamevertex */
00835     trace2((qh ferr, 2020, "qh_find_newvertex: found v%d for old v%d from %d vertices and %d ridges.\n",
00836       vertex->id, oldvertex->id, qh_setsize(vertices), qh_setsize(ridges)));
00837   }else {
00838     zinc_(Zfindfail);
00839     trace0((qh ferr, 14, "qh_find_newvertex: no vertex for renaming v%d(all duplicated ridges) during p%d\n",
00840       oldvertex->id, qh furthest_id));
00841   }
00842   qh_setfree(&qh hash_table);
00843   return vertex;
00844 } /* find_newvertex */
00845 
00846 /*-<a                             href="qh-merge.htm#TOC"
00847   >-------------------------------</a><a name="findbest_test">-</a>
00848 
00849   qh_findbest_test( testcentrum, facet, neighbor, bestfacet, dist, mindist, maxdist )
00850     test neighbor of facet for qh_findbestneighbor()
00851     if testcentrum,
00852       tests centrum (assumes it is defined)
00853     else
00854       tests vertices
00855 
00856   returns:
00857     if a better facet (i.e., vertices/centrum of facet closer to neighbor)
00858       updates bestfacet, dist, mindist, and maxdist
00859 */
00860 void qh_findbest_test(boolT testcentrum, facetT *facet, facetT *neighbor,
00861       facetT **bestfacet, realT *distp, realT *mindistp, realT *maxdistp) {
00862   realT dist, mindist, maxdist;
00863 
00864   if (testcentrum) {
00865     zzinc_(Zbestdist);
00866     qh_distplane(facet->center, neighbor, &dist);
00867     dist *= qh hull_dim; /* estimate furthest vertex */
00868     if (dist < 0) {
00869       maxdist= 0;
00870       mindist= dist;
00871       dist= -dist;
00872     }else {
00873       mindist= 0;
00874       maxdist= dist;
00875     }
00876   }else
00877     dist= qh_getdistance(facet, neighbor, &mindist, &maxdist);
00878   if (dist < *distp) {
00879     *bestfacet= neighbor;
00880     *mindistp= mindist;
00881     *maxdistp= maxdist;
00882     *distp= dist;
00883   }
00884 } /* findbest_test */
00885 
00886 /*-<a                             href="qh-merge.htm#TOC"
00887   >-------------------------------</a><a name="findbestneighbor">-</a>
00888 
00889   qh_findbestneighbor( facet, dist, mindist, maxdist )
00890     finds best neighbor (least dist) of a facet for merging
00891 
00892   returns:
00893     returns min and max distances and their max absolute value
00894 
00895   notes:
00896     avoids merging old into new
00897     assumes ridge->nonconvex only set on one ridge between a pair of facets
00898     could use an early out predicate but not worth it
00899 
00900   design:
00901     if a large facet
00902       will test centrum
00903     else
00904       will test vertices
00905     if a large facet
00906       test nonconvex neighbors for best merge
00907     else
00908       test all neighbors for the best merge
00909     if testing centrum
00910       get distance information
00911 */
00912 facetT *qh_findbestneighbor(facetT *facet, realT *distp, realT *mindistp, realT *maxdistp) {
00913   facetT *neighbor, **neighborp, *bestfacet= NULL;
00914   ridgeT *ridge, **ridgep;
00915   boolT nonconvex= True, testcentrum= False;
00916   int size= qh_setsize(facet->vertices);
00917 
00918   *distp= REALmax;
00919   if (size > qh_BESTcentrum2 * qh hull_dim + qh_BESTcentrum) {
00920     testcentrum= True;
00921     zinc_(Zbestcentrum);
00922     if (!facet->center)
00923        facet->center= qh_getcentrum(facet);
00924   }
00925   if (size > qh hull_dim + qh_BESTnonconvex) {
00926     FOREACHridge_(facet->ridges) {
00927       if (ridge->nonconvex) {
00928         neighbor= otherfacet_(ridge, facet);
00929         qh_findbest_test(testcentrum, facet, neighbor,
00930                           &bestfacet, distp, mindistp, maxdistp);
00931       }
00932     }
00933   }
00934   if (!bestfacet) {
00935     nonconvex= False;
00936     FOREACHneighbor_(facet)
00937       qh_findbest_test(testcentrum, facet, neighbor,
00938                         &bestfacet, distp, mindistp, maxdistp);
00939   }
00940   if (!bestfacet) {
00941     qh_fprintf(qh ferr, 6095, "qhull internal error (qh_findbestneighbor): no neighbors for f%d\n", facet->id);
00942 
00943     qh_errexit(qh_ERRqhull, facet, NULL);
00944   }
00945   if (testcentrum)
00946     qh_getdistance(facet, bestfacet, mindistp, maxdistp);
00947   trace3((qh ferr, 3002, "qh_findbestneighbor: f%d is best neighbor for f%d testcentrum? %d nonconvex? %d dist %2.2g min %2.2g max %2.2g\n",
00948      bestfacet->id, facet->id, testcentrum, nonconvex, *distp, *mindistp, *maxdistp));
00949   return(bestfacet);
00950 } /* findbestneighbor */
00951 
00952 
00953 /*-<a                             href="qh-merge.htm#TOC"
00954   >-------------------------------</a><a name="flippedmerges">-</a>
00955 
00956   qh_flippedmerges( facetlist, wasmerge )
00957     merge flipped facets into best neighbor
00958     assumes qh.facet_mergeset at top of temporary stack
00959 
00960   returns:
00961     no flipped facets on facetlist
00962     sets wasmerge if merge occurred
00963     degen/redundant merges passed through
00964 
00965   notes:
00966     othermerges not needed since qh.facet_mergeset is empty before & after
00967       keep it in case of change
00968 
00969   design:
00970     append flipped facets to qh.facetmergeset
00971     for each flipped merge
00972       find best neighbor
00973       merge facet into neighbor
00974       merge degenerate and redundant facets
00975     remove flipped merges from qh.facet_mergeset
00976 */
00977 void qh_flippedmerges(facetT *facetlist, boolT *wasmerge) {
00978   facetT *facet, *neighbor, *facet1;
00979   realT dist, mindist, maxdist;
00980   mergeT *merge, **mergep;
00981   setT *othermerges;
00982   int nummerge=0;
00983 
00984   trace4((qh ferr, 4024, "qh_flippedmerges: begin\n"));
00985   FORALLfacet_(facetlist) {
00986     if (facet->flipped && !facet->visible)
00987       qh_appendmergeset(facet, facet, MRGflip, NULL);
00988   }
00989   othermerges= qh_settemppop(); /* was facet_mergeset */
00990   qh facet_mergeset= qh_settemp(qh TEMPsize);
00991   qh_settemppush(othermerges);
00992   FOREACHmerge_(othermerges) {
00993     facet1= merge->facet1;
00994     if (merge->type != MRGflip || facet1->visible)
00995       continue;
00996     if (qh TRACEmerge-1 == zzval_(Ztotmerge))
00997       qhmem.IStracing= qh IStracing= qh TRACElevel;
00998     neighbor= qh_findbestneighbor(facet1, &dist, &mindist, &maxdist);
00999     trace0((qh ferr, 15, "qh_flippedmerges: merge flipped f%d into f%d dist %2.2g during p%d\n",
01000       facet1->id, neighbor->id, dist, qh furthest_id));
01001     qh_mergefacet(facet1, neighbor, &mindist, &maxdist, !qh_MERGEapex);
01002     nummerge++;
01003     if (qh PRINTstatistics) {
01004       zinc_(Zflipped);
01005       wadd_(Wflippedtot, dist);
01006       wmax_(Wflippedmax, dist);
01007     }
01008     qh_merge_degenredundant();
01009   }
01010   FOREACHmerge_(othermerges) {
01011     if (merge->facet1->visible || merge->facet2->visible)
01012       qh_memfree(merge, (int)sizeof(mergeT));
01013     else
01014       qh_setappend(&qh facet_mergeset, merge);
01015   }
01016   qh_settempfree(&othermerges);
01017   if (nummerge)
01018     *wasmerge= True;
01019   trace1((qh ferr, 1010, "qh_flippedmerges: merged %d flipped facets into a good neighbor\n", nummerge));
01020 } /* flippedmerges */
01021 
01022 
01023 /*-<a                             href="qh-merge.htm#TOC"
01024   >-------------------------------</a><a name="forcedmerges">-</a>
01025 
01026   qh_forcedmerges( wasmerge )
01027     merge duplicated ridges
01028 
01029   returns:
01030     removes all duplicate ridges on facet_mergeset
01031     wasmerge set if merge
01032     qh.facet_mergeset may include non-forced merges(none for now)
01033     qh.degen_mergeset includes degen/redun merges
01034 
01035   notes:
01036     duplicate ridges occur when the horizon is pinched,
01037         i.e. a subridge occurs in more than two horizon ridges.
01038      could rename vertices that pinch the horizon
01039     assumes qh_merge_degenredundant() has not be called
01040     othermerges isn't needed since facet_mergeset is empty afterwards
01041       keep it in case of change
01042 
01043   design:
01044     for each duplicate ridge
01045       find current facets by chasing f.replace links
01046       determine best direction for facet
01047       merge one facet into the other
01048       remove duplicate ridges from qh.facet_mergeset
01049 */
01050 void qh_forcedmerges(boolT *wasmerge) {
01051   facetT *facet1, *facet2;
01052   mergeT *merge, **mergep;
01053   realT dist1, dist2, mindist1, mindist2, maxdist1, maxdist2;
01054   setT *othermerges;
01055   int nummerge=0, numflip=0;
01056 
01057   if (qh TRACEmerge-1 == zzval_(Ztotmerge))
01058     qhmem.IStracing= qh IStracing= qh TRACElevel;
01059   trace4((qh ferr, 4025, "qh_forcedmerges: begin\n"));
01060   othermerges= qh_settemppop(); /* was facet_mergeset */
01061   qh facet_mergeset= qh_settemp(qh TEMPsize);
01062   qh_settemppush(othermerges);
01063   FOREACHmerge_(othermerges) {
01064     if (merge->type != MRGridge)
01065         continue;
01066     facet1= merge->facet1;
01067     facet2= merge->facet2;
01068     while (facet1->visible)      /* must exist, no qh_merge_degenredunant */
01069       facet1= facet1->f.replace; /* previously merged facet */
01070     while (facet2->visible)
01071       facet2= facet2->f.replace; /* previously merged facet */
01072     if (facet1 == facet2)
01073       continue;
01074     if (!qh_setin(facet2->neighbors, facet1)) {
01075       qh_fprintf(qh ferr, 6096, "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",
01076                merge->facet1->id, merge->facet2->id, facet1->id, facet2->id);
01077       qh_errexit2 (qh_ERRqhull, facet1, facet2);
01078     }
01079     if (qh TRACEmerge-1 == zzval_(Ztotmerge))
01080       qhmem.IStracing= qh IStracing= qh TRACElevel;
01081     dist1= qh_getdistance(facet1, facet2, &mindist1, &maxdist1);
01082     dist2= qh_getdistance(facet2, facet1, &mindist2, &maxdist2);
01083     trace0((qh ferr, 16, "qh_forcedmerges: duplicate ridge between f%d and f%d, dist %2.2g and reverse dist %2.2g during p%d\n",
01084             facet1->id, facet2->id, dist1, dist2, qh furthest_id));
01085     if (dist1 < dist2)
01086       qh_mergefacet(facet1, facet2, &mindist1, &maxdist1, !qh_MERGEapex);
01087     else {
01088       qh_mergefacet(facet2, facet1, &mindist2, &maxdist2, !qh_MERGEapex);
01089       dist1= dist2;
01090       facet1= facet2;
01091     }
01092     if (facet1->flipped) {
01093       zinc_(Zmergeflipdup);
01094       numflip++;
01095     }else
01096       nummerge++;
01097     if (qh PRINTstatistics) {
01098       zinc_(Zduplicate);
01099       wadd_(Wduplicatetot, dist1);
01100       wmax_(Wduplicatemax, dist1);
01101     }
01102   }
01103   FOREACHmerge_(othermerges) {
01104     if (merge->type == MRGridge)
01105       qh_memfree(merge, (int)sizeof(mergeT));
01106     else
01107       qh_setappend(&qh facet_mergeset, merge);
01108   }
01109   qh_settempfree(&othermerges);
01110   if (nummerge)
01111     *wasmerge= True;
01112   trace1((qh ferr, 1011, "qh_forcedmerges: merged %d facets and %d flipped facets across duplicated ridges\n",
01113                 nummerge, numflip));
01114 } /* forcedmerges */
01115 
01116 
01117 /*-<a                             href="qh-merge.htm#TOC"
01118   >-------------------------------</a><a name="getmergeset">-</a>
01119 
01120   qh_getmergeset( facetlist )
01121     determines nonconvex facets on facetlist
01122     tests !tested ridges and nonconvex ridges of !tested facets
01123 
01124   returns:
01125     returns sorted qh.facet_mergeset of facet-neighbor pairs to be merged
01126     all ridges tested
01127 
01128   notes:
01129     assumes no nonconvex ridges with both facets tested
01130     uses facet->tested/ridge->tested to prevent duplicate tests
01131     can not limit tests to modified ridges since the centrum changed
01132     uses qh.visit_id
01133 
01134   see:
01135     qh_getmergeset_initial()
01136 
01137   design:
01138     for each facet on facetlist
01139       for each ridge of facet
01140         if untested ridge
01141           test ridge for convexity
01142           if non-convex
01143             append ridge to qh.facet_mergeset
01144     sort qh.facet_mergeset by angle
01145 */
01146 void qh_getmergeset(facetT *facetlist) {
01147   facetT *facet, *neighbor, **neighborp;
01148   ridgeT *ridge, **ridgep;
01149   int nummerges;
01150 
01151   nummerges= qh_setsize(qh facet_mergeset);
01152   trace4((qh ferr, 4026, "qh_getmergeset: started.\n"));
01153   qh visit_id++;
01154   FORALLfacet_(facetlist) {
01155     if (facet->tested)
01156       continue;
01157     facet->visitid= qh visit_id;
01158     facet->tested= True;  /* must be non-simplicial due to merge */
01159     FOREACHneighbor_(facet)
01160       neighbor->seen= False;
01161     FOREACHridge_(facet->ridges) {
01162       if (ridge->tested && !ridge->nonconvex)
01163         continue;
01164       /* if tested & nonconvex, need to append merge */
01165       neighbor= otherfacet_(ridge, facet);
01166       if (neighbor->seen) {
01167         ridge->tested= True;
01168         ridge->nonconvex= False;
01169       }else if (neighbor->visitid != qh visit_id) {
01170         ridge->tested= True;
01171         ridge->nonconvex= False;
01172         neighbor->seen= True;      /* only one ridge is marked nonconvex */
01173         if (qh_test_appendmerge(facet, neighbor))
01174           ridge->nonconvex= True;
01175       }
01176     }
01177   }
01178   nummerges= qh_setsize(qh facet_mergeset);
01179   if (qh ANGLEmerge)
01180     qsort(SETaddr_(qh facet_mergeset, mergeT), (size_t)nummerges, sizeof(mergeT *), qh_compareangle);
01181   else
01182     qsort(SETaddr_(qh facet_mergeset, mergeT), (size_t)nummerges, sizeof(mergeT *), qh_comparemerge);
01183   if (qh POSTmerging) {
01184     zadd_(Zmergesettot2, nummerges);
01185   }else {
01186     zadd_(Zmergesettot, nummerges);
01187     zmax_(Zmergesetmax, nummerges);
01188   }
01189   trace2((qh ferr, 2021, "qh_getmergeset: %d merges found\n", nummerges));
01190 } /* getmergeset */
01191 
01192 
01193 /*-<a                             href="qh-merge.htm#TOC"
01194   >-------------------------------</a><a name="getmergeset_initial">-</a>
01195 
01196   qh_getmergeset_initial( facetlist )
01197     determine initial qh.facet_mergeset for facets
01198     tests all facet/neighbor pairs on facetlist
01199 
01200   returns:
01201     sorted qh.facet_mergeset with nonconvex ridges
01202     sets facet->tested, ridge->tested, and ridge->nonconvex
01203 
01204   notes:
01205     uses visit_id, assumes ridge->nonconvex is False
01206 
01207   see:
01208     qh_getmergeset()
01209 
01210   design:
01211     for each facet on facetlist
01212       for each untested neighbor of facet
01213         test facet and neighbor for convexity
01214         if non-convex
01215           append merge to qh.facet_mergeset
01216           mark one of the ridges as nonconvex
01217     sort qh.facet_mergeset by angle
01218 */
01219 void qh_getmergeset_initial(facetT *facetlist) {
01220   facetT *facet, *neighbor, **neighborp;
01221   ridgeT *ridge, **ridgep;
01222   int nummerges;
01223 
01224   qh visit_id++;
01225   FORALLfacet_(facetlist) {
01226     facet->visitid= qh visit_id;
01227     facet->tested= True;
01228     FOREACHneighbor_(facet) {
01229       if (neighbor->visitid != qh visit_id) {
01230         if (qh_test_appendmerge(facet, neighbor)) {
01231           FOREACHridge_(neighbor->ridges) {
01232             if (facet == otherfacet_(ridge, neighbor)) {
01233               ridge->nonconvex= True;
01234               break;    /* only one ridge is marked nonconvex */
01235             }
01236           }
01237         }
01238       }
01239     }
01240     FOREACHridge_(facet->ridges)
01241       ridge->tested= True;
01242   }
01243   nummerges= qh_setsize(qh facet_mergeset);
01244   if (qh ANGLEmerge)
01245     qsort(SETaddr_(qh facet_mergeset, mergeT), (size_t)nummerges, sizeof(mergeT *), qh_compareangle);
01246   else
01247     qsort(SETaddr_(qh facet_mergeset, mergeT), (size_t)nummerges, sizeof(mergeT *), qh_comparemerge);
01248   if (qh POSTmerging) {
01249     zadd_(Zmergeinittot2, nummerges);
01250   }else {
01251     zadd_(Zmergeinittot, nummerges);
01252     zmax_(Zmergeinitmax, nummerges);
01253   }
01254   trace2((qh ferr, 2022, "qh_getmergeset_initial: %d merges found\n", nummerges));
01255 } /* getmergeset_initial */
01256 
01257 
01258 /*-<a                             href="qh-merge.htm#TOC"
01259   >-------------------------------</a><a name="hashridge">-</a>
01260 
01261   qh_hashridge( hashtable, hashsize, ridge, oldvertex )
01262     add ridge to hashtable without oldvertex
01263 
01264   notes:
01265     assumes hashtable is large enough
01266 
01267   design:
01268     determine hash value for ridge without oldvertex
01269     find next empty slot for ridge
01270 */
01271 void qh_hashridge(setT *hashtable, int hashsize, ridgeT *ridge, vertexT *oldvertex) {
01272   int hash;
01273   ridgeT *ridgeA;
01274 
01275   hash= qh_gethash(hashsize, ridge->vertices, qh hull_dim-1, 0, oldvertex);
01276   while (True) {
01277     if (!(ridgeA= SETelemt_(hashtable, hash, ridgeT))) {
01278       SETelem_(hashtable, hash)= ridge;
01279       break;
01280     }else if (ridgeA == ridge)
01281       break;
01282     if (++hash == hashsize)
01283       hash= 0;
01284   }
01285 } /* hashridge */
01286 
01287 
01288 /*-<a                             href="qh-merge.htm#TOC"
01289   >-------------------------------</a><a name="hashridge_find">-</a>
01290 
01291   qh_hashridge_find( hashtable, hashsize, ridge, vertex, oldvertex, hashslot )
01292     returns matching ridge without oldvertex in hashtable
01293       for ridge without vertex
01294     if oldvertex is NULL
01295       matches with any one skip
01296 
01297   returns:
01298     matching ridge or NULL
01299     if no match,
01300       if ridge already in   table
01301         hashslot= -1
01302       else
01303         hashslot= next NULL index
01304 
01305   notes:
01306     assumes hashtable is large enough
01307     can't match ridge to itself
01308 
01309   design:
01310     get hash value for ridge without vertex
01311     for each hashslot
01312       return match if ridge matches ridgeA without oldvertex
01313 */
01314 ridgeT *qh_hashridge_find(setT *hashtable, int hashsize, ridgeT *ridge,
01315               vertexT *vertex, vertexT *oldvertex, int *hashslot) {
01316   int hash;
01317   ridgeT *ridgeA;
01318 
01319   *hashslot= 0;
01320   zinc_(Zhashridge);
01321   hash= qh_gethash(hashsize, ridge->vertices, qh hull_dim-1, 0, vertex);
01322   while ((ridgeA= SETelemt_(hashtable, hash, ridgeT))) {
01323     if (ridgeA == ridge)
01324       *hashslot= -1;
01325     else {
01326       zinc_(Zhashridgetest);
01327       if (qh_setequal_except(ridge->vertices, vertex, ridgeA->vertices, oldvertex))
01328         return ridgeA;
01329     }
01330     if (++hash == hashsize)
01331       hash= 0;
01332   }
01333   if (!*hashslot)
01334     *hashslot= hash;
01335   return NULL;
01336 } /* hashridge_find */
01337 
01338 
01339 /*-<a                             href="qh-merge.htm#TOC"
01340   >-------------------------------</a><a name="makeridges">-</a>
01341 
01342   qh_makeridges( facet )
01343     creates explicit ridges between simplicial facets
01344 
01345   returns:
01346     facet with ridges and without qh_MERGEridge
01347     ->simplicial is False
01348 
01349   notes:
01350     allows qh_MERGEridge flag
01351     uses existing ridges
01352     duplicate neighbors ok if ridges already exist (qh_mergecycle_ridges)
01353 
01354   see:
01355     qh_mergecycle_ridges()
01356 
01357   design:
01358     look for qh_MERGEridge neighbors
01359     mark neighbors that already have ridges
01360     for each unprocessed neighbor of facet
01361       create a ridge for neighbor and facet
01362     if any qh_MERGEridge neighbors
01363       delete qh_MERGEridge flags (already handled by qh_mark_dupridges)
01364 */
01365 void qh_makeridges(facetT *facet) {
01366   facetT *neighbor, **neighborp;
01367   ridgeT *ridge, **ridgep;
01368   int neighbor_i, neighbor_n;
01369   boolT toporient, mergeridge= False;
01370 
01371   if (!facet->simplicial)
01372     return;
01373   trace4((qh ferr, 4027, "qh_makeridges: make ridges for f%d\n", facet->id));
01374   facet->simplicial= False;
01375   FOREACHneighbor_(facet) {
01376     if (neighbor == qh_MERGEridge)
01377       mergeridge= True;
01378     else
01379       neighbor->seen= False;
01380   }
01381   FOREACHridge_(facet->ridges)
01382     otherfacet_(ridge, facet)->seen= True;
01383   FOREACHneighbor_i_(facet) {
01384     if (neighbor == qh_MERGEridge)
01385       continue;  /* fixed by qh_mark_dupridges */
01386     else if (!neighbor->seen) {  /* no current ridges */
01387       ridge= qh_newridge();
01388       ridge->vertices= qh_setnew_delnthsorted(facet->vertices, qh hull_dim,
01389                                                           neighbor_i, 0);
01390       toporient= facet->toporient ^ (neighbor_i & 0x1);
01391       if (toporient) {
01392         ridge->top= facet;
01393         ridge->bottom= neighbor;
01394       }else {
01395         ridge->top= neighbor;
01396         ridge->bottom= facet;
01397       }
01398 #if 0 /* this also works */
01399       flip= (facet->toporient ^ neighbor->toporient)^(skip1 & 0x1) ^ (skip2 & 0x1);
01400       if (facet->toporient ^ (skip1 & 0x1) ^ flip) {
01401         ridge->top= neighbor;
01402         ridge->bottom= facet;
01403       }else {
01404         ridge->top= facet;
01405         ridge->bottom= neighbor;
01406       }
01407 #endif
01408       qh_setappend(&(facet->ridges), ridge);
01409       qh_setappend(&(neighbor->ridges), ridge);
01410     }
01411   }
01412   if (mergeridge) {
01413     while (qh_setdel(facet->neighbors, qh_MERGEridge))
01414       ; /* delete each one */
01415   }
01416 } /* makeridges */
01417 
01418 
01419 /*-<a                             href="qh-merge.htm#TOC"
01420   >-------------------------------</a><a name="mark_dupridges">-</a>
01421 
01422   qh_mark_dupridges( facetlist )
01423     add duplicated ridges to qh.facet_mergeset
01424     facet->dupridge is true
01425 
01426   returns:
01427     duplicate ridges on qh.facet_mergeset
01428     ->mergeridge/->mergeridge2 set
01429     duplicate ridges marked by qh_MERGEridge and both sides facet->dupridge
01430     no MERGEridges in neighbor sets
01431 
01432   notes:
01433     duplicate ridges occur when the horizon is pinched,
01434         i.e. a subridge occurs in more than two horizon ridges.
01435     could rename vertices that pinch the horizon
01436     uses qh.visit_id
01437 
01438   design:
01439     for all facets on facetlist
01440       if facet contains a duplicate ridge
01441         for each neighbor of facet
01442           if neighbor marked qh_MERGEridge (one side of the merge)
01443             set facet->mergeridge
01444           else
01445             if neighbor contains a duplicate ridge
01446             and the back link is qh_MERGEridge
01447               append duplicate ridge to qh.facet_mergeset
01448    for each duplicate ridge
01449      make ridge sets in preparation for merging
01450      remove qh_MERGEridge from neighbor set
01451    for each duplicate ridge
01452      restore the missing neighbor from the neighbor set that was qh_MERGEridge
01453      add the missing ridge for this neighbor
01454 */
01455 void qh_mark_dupridges(facetT *facetlist) {
01456   facetT *facet, *neighbor, **neighborp;
01457   int nummerge=0;
01458   mergeT *merge, **mergep;
01459 
01460 
01461   trace4((qh ferr, 4028, "qh_mark_dupridges: identify duplicate ridges\n"));
01462   FORALLfacet_(facetlist) {
01463     if (facet->dupridge) {
01464       FOREACHneighbor_(facet) {
01465         if (neighbor == qh_MERGEridge) {
01466           facet->mergeridge= True;
01467           continue;
01468         }
01469         if (neighbor->dupridge
01470         && !qh_setin(neighbor->neighbors, facet)) { /* qh_MERGEridge */
01471           qh_appendmergeset(facet, neighbor, MRGridge, NULL);
01472           facet->mergeridge2= True;
01473           facet->mergeridge= True;
01474           nummerge++;
01475         }
01476       }
01477     }
01478   }
01479   if (!nummerge)
01480     return;
01481   FORALLfacet_(facetlist) {            /* gets rid of qh_MERGEridge */
01482     if (facet->mergeridge && !facet->mergeridge2)
01483       qh_makeridges(facet);
01484   }
01485   FOREACHmerge_(qh facet_mergeset) {   /* restore the missing neighbors */
01486     if (merge->type == MRGridge) {
01487       qh_setappend(&merge->facet2->neighbors, merge->facet1);
01488       qh_makeridges(merge->facet1);   /* and the missing ridges */
01489     }
01490   }
01491   trace1((qh ferr, 1012, "qh_mark_dupridges: found %d duplicated ridges\n",
01492                 nummerge));
01493 } /* mark_dupridges */
01494 
01495 /*-<a                             href="qh-merge.htm#TOC"
01496   >-------------------------------</a><a name="maydropneighbor">-</a>
01497 
01498   qh_maydropneighbor( facet )
01499     drop neighbor relationship if no ridge between facet and neighbor
01500 
01501   returns:
01502     neighbor sets updated
01503     appends degenerate facets to qh.facet_mergeset
01504 
01505   notes:
01506     won't cause redundant facets since vertex inclusion is the same
01507     may drop vertex and neighbor if no ridge
01508     uses qh.visit_id
01509 
01510   design:
01511     visit all neighbors with ridges
01512     for each unvisited neighbor of facet
01513       delete neighbor and facet from the neighbor sets
01514       if neighbor becomes degenerate
01515         append neighbor to qh.degen_mergeset
01516     if facet is degenerate
01517       append facet to qh.degen_mergeset
01518 */
01519 void qh_maydropneighbor(facetT *facet) {
01520   ridgeT *ridge, **ridgep;
01521   realT angledegen= qh_ANGLEdegen;
01522   facetT *neighbor, **neighborp;
01523 
01524   qh visit_id++;
01525   trace4((qh ferr, 4029, "qh_maydropneighbor: test f%d for no ridges to a neighbor\n",
01526           facet->id));
01527   FOREACHridge_(facet->ridges) {
01528     ridge->top->visitid= qh visit_id;
01529     ridge->bottom->visitid= qh visit_id;
01530   }
01531   FOREACHneighbor_(facet) {
01532     if (neighbor->visitid != qh visit_id) {
01533       trace0((qh ferr, 17, "qh_maydropneighbor: facets f%d and f%d are no longer neighbors during p%d\n",
01534             facet->id, neighbor->id, qh furthest_id));
01535       zinc_(Zdropneighbor);
01536       qh_setdel(facet->neighbors, neighbor);
01537       neighborp--;  /* repeat, deleted a neighbor */
01538       qh_setdel(neighbor->neighbors, facet);
01539       if (qh_setsize(neighbor->neighbors) < qh hull_dim) {
01540         zinc_(Zdropdegen);
01541         qh_appendmergeset(neighbor, neighbor, MRGdegen, &angledegen);
01542         trace2((qh ferr, 2023, "qh_maydropneighbors: f%d is degenerate.\n", neighbor->id));
01543       }
01544     }
01545   }
01546   if (qh_setsize(facet->neighbors) < qh hull_dim) {
01547     zinc_(Zdropdegen);
01548     qh_appendmergeset(facet, facet, MRGdegen, &angledegen);
01549     trace2((qh ferr, 2024, "qh_maydropneighbors: f%d is degenerate.\n", facet->id));
01550   }
01551 } /* maydropneighbor */
01552 
01553 
01554 /*-<a                             href="qh-merge.htm#TOC"
01555   >-------------------------------</a><a name="merge_degenredundant">-</a>
01556 
01557   qh_merge_degenredundant()
01558     merge all degenerate and redundant facets
01559     qh.degen_mergeset contains merges from qh_degen_redundant_neighbors()
01560 
01561   returns:
01562     number of merges performed
01563     resets facet->degenerate/redundant
01564     if deleted (visible) facet has no neighbors
01565       sets ->f.replace to NULL
01566 
01567   notes:
01568     redundant merges happen before degenerate ones
01569     merging and renaming vertices can result in degen/redundant facets
01570 
01571   design:
01572     for each merge on qh.degen_mergeset
01573       if redundant merge
01574         if non-redundant facet merged into redundant facet
01575           recheck facet for redundancy
01576         else
01577           merge redundant facet into other facet
01578 */
01579 int qh_merge_degenredundant(void) {
01580   int size;
01581   mergeT *merge;
01582   facetT *bestneighbor, *facet1, *facet2;
01583   realT dist, mindist, maxdist;
01584   vertexT *vertex, **vertexp;
01585   int nummerges= 0;
01586   mergeType mergetype;
01587 
01588   while ((merge= (mergeT*)qh_setdellast(qh degen_mergeset))) {
01589     facet1= merge->facet1;
01590     facet2= merge->facet2;
01591     mergetype= merge->type;
01592     qh_memfree(merge, (int)sizeof(mergeT));
01593     if (facet1->visible)
01594       continue;
01595     facet1->degenerate= False;
01596     facet1->redundant= False;
01597     if (qh TRACEmerge-1 == zzval_(Ztotmerge))
01598       qhmem.IStracing= qh IStracing= qh TRACElevel;
01599     if (mergetype == MRGredundant) {
01600       zinc_(Zneighbor);
01601       while (facet2->visible) {
01602         if (!facet2->f.replace) {
01603           qh_fprintf(qh ferr, 6097, "qhull internal error (qh_merge_degenredunant): f%d redundant but f%d has no replacement\n",
01604                facet1->id, facet2->id);
01605           qh_errexit2 (qh_ERRqhull, facet1, facet2);
01606         }
01607         facet2= facet2->f.replace;
01608       }
01609       if (facet1 == facet2) {
01610         qh_degen_redundant_facet(facet1); /* in case of others */
01611         continue;
01612       }
01613       trace2((qh ferr, 2025, "qh_merge_degenredundant: facet f%d is contained in f%d, will merge\n",
01614             facet1->id, facet2->id));
01615       qh_mergefacet(facet1, facet2, NULL, NULL, !qh_MERGEapex);
01616       /* merge distance is already accounted for */
01617       nummerges++;
01618     }else {  /* mergetype == MRGdegen, other merges may have fixed */
01619       if (!(size= qh_setsize(facet1->neighbors))) {
01620         zinc_(Zdelfacetdup);
01621         trace2((qh ferr, 2026, "qh_merge_degenredundant: facet f%d has no neighbors.  Deleted\n", facet1->id));
01622         qh_willdelete(facet1, NULL);
01623         FOREACHvertex_(facet1->vertices) {
01624           qh_setdel(vertex->neighbors, facet1);
01625           if (!SETfirst_(vertex->neighbors)) {
01626             zinc_(Zdegenvertex);
01627             trace2((qh ferr, 2027, "qh_merge_degenredundant: deleted v%d because f%d has no neighbors\n",
01628                  vertex->id, facet1->id));
01629             vertex->deleted= True;
01630             qh_setappend(&qh del_vertices, vertex);
01631           }
01632         }
01633         nummerges++;
01634       }else if (size < qh hull_dim) {
01635         bestneighbor= qh_findbestneighbor(facet1, &dist, &mindist, &maxdist);
01636         trace2((qh ferr, 2028, "qh_merge_degenredundant: facet f%d has %d neighbors, merge into f%d dist %2.2g\n",
01637               facet1->id, size, bestneighbor->id, dist));
01638         qh_mergefacet(facet1, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
01639         nummerges++;
01640         if (qh PRINTstatistics) {
01641           zinc_(Zdegen);
01642           wadd_(Wdegentot, dist);
01643           wmax_(Wdegenmax, dist);
01644         }
01645       } /* else, another merge fixed the degeneracy and redundancy tested */
01646     }
01647   }
01648   return nummerges;
01649 } /* merge_degenredundant */
01650 
01651 /*-<a                             href="qh-merge.htm#TOC"
01652   >-------------------------------</a><a name="merge_nonconvex">-</a>
01653 
01654   qh_merge_nonconvex( facet1, facet2, mergetype )
01655     remove non-convex ridge between facet1 into facet2
01656     mergetype gives why the facet's are non-convex
01657 
01658   returns:
01659     merges one of the facets into the best neighbor
01660 
01661   design:
01662     if one of the facets is a new facet
01663       prefer merging new facet into old facet
01664     find best neighbors for both facets
01665     merge the nearest facet into its best neighbor
01666     update the statistics
01667 */
01668 void qh_merge_nonconvex(facetT *facet1, facetT *facet2, mergeType mergetype) {
01669   facetT *bestfacet, *bestneighbor, *neighbor;
01670   realT dist, dist2, mindist, mindist2, maxdist, maxdist2;
01671 
01672   if (qh TRACEmerge-1 == zzval_(Ztotmerge))
01673     qhmem.IStracing= qh IStracing= qh TRACElevel;
01674   trace3((qh ferr, 3003, "qh_merge_nonconvex: merge #%d for f%d and f%d type %d\n",
01675       zzval_(Ztotmerge) + 1, facet1->id, facet2->id, mergetype));
01676   /* concave or coplanar */
01677   if (!facet1->newfacet) {
01678     bestfacet= facet2;   /* avoid merging old facet if new is ok */
01679     facet2= facet1;
01680     facet1= bestfacet;
01681   }else
01682     bestfacet= facet1;
01683   bestneighbor= qh_findbestneighbor(bestfacet, &dist, &mindist, &maxdist);
01684   neighbor= qh_findbestneighbor(facet2, &dist2, &mindist2, &maxdist2);
01685   if (dist < dist2) {
01686     qh_mergefacet(bestfacet, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
01687   }else if (qh AVOIDold && !facet2->newfacet
01688   && ((mindist >= -qh MAXcoplanar && maxdist <= qh max_outside)
01689        || dist * 1.5 < dist2)) {
01690     zinc_(Zavoidold);
01691     wadd_(Wavoidoldtot, dist);
01692     wmax_(Wavoidoldmax, dist);
01693     trace2((qh ferr, 2029, "qh_merge_nonconvex: avoid merging old facet f%d dist %2.2g.  Use f%d dist %2.2g instead\n",
01694            facet2->id, dist2, facet1->id, dist2));
01695     qh_mergefacet(bestfacet, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
01696   }else {
01697     qh_mergefacet(facet2, neighbor, &mindist2, &maxdist2, !qh_MERGEapex);
01698     dist= dist2;
01699   }
01700   if (qh PRINTstatistics) {
01701     if (mergetype == MRGanglecoplanar) {
01702       zinc_(Zacoplanar);
01703       wadd_(Wacoplanartot, dist);
01704       wmax_(Wacoplanarmax, dist);
01705     }else if (mergetype == MRGconcave) {
01706       zinc_(Zconcave);
01707       wadd_(Wconcavetot, dist);
01708       wmax_(Wconcavemax, dist);
01709     }else { /* MRGcoplanar */
01710       zinc_(Zcoplanar);
01711       wadd_(Wcoplanartot, dist);
01712       wmax_(Wcoplanarmax, dist);
01713     }
01714   }
01715 } /* merge_nonconvex */
01716 
01717 /*-<a                             href="qh-merge.htm#TOC"
01718   >-------------------------------</a><a name="mergecycle">-</a>
01719 
01720   qh_mergecycle( samecycle, newfacet )
01721     merge a cycle of facets starting at samecycle into a newfacet
01722     newfacet is a horizon facet with ->normal
01723     samecycle facets are simplicial from an apex
01724 
01725   returns:
01726     initializes vertex neighbors on first merge
01727     samecycle deleted (placed on qh.visible_list)
01728     newfacet at end of qh.facet_list
01729     deleted vertices on qh.del_vertices
01730 
01731   see:
01732     qh_mergefacet()
01733     called by qh_mergecycle_all() for multiple, same cycle facets
01734 
01735   design:
01736     make vertex neighbors if necessary
01737     make ridges for newfacet
01738     merge neighbor sets of samecycle into newfacet
01739     merge ridges of samecycle into newfacet
01740     merge vertex neighbors of samecycle into newfacet
01741     make apex of samecycle the apex of newfacet
01742     if newfacet wasn't a new facet
01743       add its vertices to qh.newvertex_list
01744     delete samecycle facets a make newfacet a newfacet
01745 */
01746 void qh_mergecycle(facetT *samecycle, facetT *newfacet) {
01747   int traceonce= False, tracerestore= 0;
01748   vertexT *apex;
01749 #ifndef qh_NOtrace
01750   facetT *same;
01751 #endif
01752 
01753   if (newfacet->tricoplanar) {
01754     if (!qh TRInormals) {
01755       qh_fprintf(qh ferr, 6224, "Qhull internal error (qh_mergecycle): does not work for tricoplanar facets.  Use option 'Q11'\n");
01756       qh_errexit(qh_ERRqhull, newfacet, NULL);
01757     }
01758     newfacet->tricoplanar= False;
01759     newfacet->keepcentrum= False;
01760   }
01761   if (!qh VERTEXneighbors)
01762     qh_vertexneighbors();
01763   zzinc_(Ztotmerge);
01764   if (qh REPORTfreq2 && qh POSTmerging) {
01765     if (zzval_(Ztotmerge) > qh mergereport + qh REPORTfreq2)
01766       qh_tracemerging();
01767   }
01768 #ifndef qh_NOtrace
01769   if (qh TRACEmerge == zzval_(Ztotmerge))
01770     qhmem.IStracing= qh IStracing= qh TRACElevel;
01771   trace2((qh ferr, 2030, "qh_mergecycle: merge #%d for facets from cycle f%d into coplanar horizon f%d\n",
01772         zzval_(Ztotmerge), samecycle->id, newfacet->id));
01773   if (newfacet == qh tracefacet) {
01774     tracerestore= qh IStracing;
01775     qh IStracing= 4;
01776     qh_fprintf(qh ferr, 8068, "qh_mergecycle: ========= trace merge %d of samecycle %d into trace f%d, furthest is p%d\n",
01777                zzval_(Ztotmerge), samecycle->id, newfacet->id,  qh furthest_id);
01778     traceonce= True;
01779   }
01780   if (qh IStracing >=4) {
01781     qh_fprintf(qh ferr, 8069, "  same cycle:");
01782     FORALLsame_cycle_(samecycle)
01783       qh_fprintf(qh ferr, 8070, " f%d", same->id);
01784     qh_fprintf(qh ferr, 8071, "\n");
01785   }
01786   if (qh IStracing >=4)
01787     qh_errprint("MERGING CYCLE", samecycle, newfacet, NULL, NULL);
01788 #endif /* !qh_NOtrace */
01789   apex= SETfirstt_(samecycle->vertices, vertexT);
01790   qh_makeridges(newfacet);
01791   qh_mergecycle_neighbors(samecycle, newfacet);
01792   qh_mergecycle_ridges(samecycle, newfacet);
01793   qh_mergecycle_vneighbors(samecycle, newfacet);
01794   if (SETfirstt_(newfacet->vertices, vertexT) != apex)
01795     qh_setaddnth(&newfacet->vertices, 0, apex);  /* apex has last id */
01796   if (!newfacet->newfacet)
01797     qh_newvertices(newfacet->vertices);
01798   qh_mergecycle_facets(samecycle, newfacet);
01799   qh_tracemerge(samecycle, newfacet);
01800   /* check for degen_redundant_neighbors after qh_forcedmerges() */
01801   if (traceonce) {
01802     qh_fprintf(qh ferr, 8072, "qh_mergecycle: end of trace facet\n");
01803     qh IStracing= tracerestore;
01804   }
01805 } /* mergecycle */
01806 
01807 /*-<a                             href="qh-merge.htm#TOC"
01808   >-------------------------------</a><a name="mergecycle_all">-</a>
01809 
01810   qh_mergecycle_all( facetlist, wasmerge )
01811     merge all samecycles of coplanar facets into horizon
01812     don't merge facets with ->mergeridge (these already have ->normal)
01813     all facets are simplicial from apex
01814     all facet->cycledone == False
01815 
01816   returns:
01817     all newfacets merged into coplanar horizon facets
01818     deleted vertices on  qh.del_vertices
01819     sets wasmerge if any merge
01820 
01821   see:
01822     calls qh_mergecycle for multiple, same cycle facets
01823 
01824   design:
01825     for each facet on facetlist
01826       skip facets with duplicate ridges and normals
01827       check that facet is in a samecycle (->mergehorizon)
01828       if facet only member of samecycle
01829         sets vertex->delridge for all vertices except apex
01830         merge facet into horizon
01831       else
01832         mark all facets in samecycle
01833         remove facets with duplicate ridges from samecycle
01834         merge samecycle into horizon (deletes facets from facetlist)
01835 */
01836 void qh_mergecycle_all(facetT *facetlist, boolT *wasmerge) {
01837   facetT *facet, *same, *prev, *horizon;
01838   facetT *samecycle= NULL, *nextfacet, *nextsame;
01839   vertexT *apex, *vertex, **vertexp;
01840   int cycles=0, total=0, facets, nummerge;
01841 
01842   trace2((qh ferr, 2031, "qh_mergecycle_all: begin\n"));
01843   for (facet= facetlist; facet && (nextfacet= facet->next); facet= nextfacet) {
01844     if (facet->normal)
01845       continue;
01846     if (!facet->mergehorizon) {
01847       qh_fprintf(qh ferr, 6225, "Qhull internal error (qh_mergecycle_all): f%d without normal\n", facet->id);
01848       qh_errexit(qh_ERRqhull, facet, NULL);
01849     }
01850     horizon= SETfirstt_(facet->neighbors, facetT);
01851     if (facet->f.samecycle == facet) {
01852       zinc_(Zonehorizon);
01853       /* merge distance done in qh_findhorizon */
01854       apex= SETfirstt_(facet->vertices, vertexT);
01855       FOREACHvertex_(facet->vertices) {
01856         if (vertex != apex)
01857           vertex->delridge= True;
01858       }
01859       horizon->f.newcycle= NULL;
01860       qh_mergefacet(facet, horizon, NULL, NULL, qh_MERGEapex);
01861     }else {
01862       samecycle= facet;
01863       facets= 0;
01864       prev= facet;
01865       for (same= facet->f.samecycle; same;  /* FORALLsame_cycle_(facet) */
01866            same= (same == facet ? NULL :nextsame)) { /* ends at facet */
01867         nextsame= same->f.samecycle;
01868         if (same->cycledone || same->visible)
01869           qh_infiniteloop(same);
01870         same->cycledone= True;
01871         if (same->normal) {
01872           prev->f.samecycle= same->f.samecycle; /* unlink ->mergeridge */
01873           same->f.samecycle= NULL;
01874         }else {
01875           prev= same;
01876           facets++;
01877         }
01878       }
01879       while (nextfacet && nextfacet->cycledone)  /* will delete samecycle */
01880         nextfacet= nextfacet->next;
01881       horizon->f.newcycle= NULL;
01882       qh_mergecycle(samecycle, horizon);
01883       nummerge= horizon->nummerge + facets;
01884       if (nummerge > qh_MAXnummerge)
01885         horizon->nummerge= qh_MAXnummerge;
01886       else
01887         horizon->nummerge= (short unsigned int)nummerge;
01888       zzinc_(Zcyclehorizon);
01889       total += facets;
01890       zzadd_(Zcyclefacettot, facets);
01891       zmax_(Zcyclefacetmax, facets);
01892     }
01893     cycles++;
01894   }
01895   if (cycles)
01896     *wasmerge= True;
01897   trace1((qh ferr, 1013, "qh_mergecycle_all: merged %d same cycles or facets into coplanar horizons\n", cycles));
01898 } /* mergecycle_all */
01899 
01900 /*-<a                             href="qh-merge.htm#TOC"
01901   >-------------------------------</a><a name="mergecycle_facets">-</a>
01902 
01903   qh_mergecycle_facets( samecycle, newfacet )
01904     finish merge of samecycle into newfacet
01905 
01906   returns:
01907     samecycle prepended to visible_list for later deletion and partitioning
01908       each facet->f.replace == newfacet
01909 
01910     newfacet moved to end of qh.facet_list
01911       makes newfacet a newfacet (get's facet1->id if it was old)
01912       sets newfacet->newmerge
01913       clears newfacet->center (unless merging into a large facet)
01914       clears newfacet->tested and ridge->tested for facet1
01915 
01916     adds neighboring facets to facet_mergeset if redundant or degenerate
01917 
01918   design:
01919     make newfacet a new facet and set its flags
01920     move samecycle facets to qh.visible_list for later deletion
01921     unless newfacet is large
01922       remove its centrum
01923 */
01924 void qh_mergecycle_facets(facetT *samecycle, facetT *newfacet) {
01925   facetT *same, *next;
01926 
01927   trace4((qh ferr, 4030, "qh_mergecycle_facets: make newfacet new and samecycle deleted\n"));
01928   qh_removefacet(newfacet);  /* append as a newfacet to end of qh facet_list */
01929   qh_appendfacet(newfacet);
01930   newfacet->newfacet= True;
01931   newfacet->simplicial= False;
01932   newfacet->newmerge= True;
01933 
01934   for (same= samecycle->f.samecycle; same; same= (same == samecycle ?  NULL : next)) {
01935     next= same->f.samecycle;  /* reused by willdelete */
01936     qh_willdelete(same, newfacet);
01937   }
01938   if (newfacet->center
01939       && qh_setsize(newfacet->vertices) <= qh hull_dim + qh_MAXnewcentrum) {
01940     qh_memfree(newfacet->center, qh normal_size);
01941     newfacet->center= NULL;
01942   }
01943   trace3((qh ferr, 3004, "qh_mergecycle_facets: merged facets from cycle f%d into f%d\n",
01944              samecycle->id, newfacet->id));
01945 } /* mergecycle_facets */
01946 
01947 /*-<a                             href="qh-merge.htm#TOC"
01948   >-------------------------------</a><a name="mergecycle_neighbors">-</a>
01949 
01950   qh_mergecycle_neighbors( samecycle, newfacet )
01951     add neighbors for samecycle facets to newfacet
01952 
01953   returns:
01954     newfacet with updated neighbors and vice-versa
01955     newfacet has ridges
01956     all neighbors of newfacet marked with qh.visit_id
01957     samecycle facets marked with qh.visit_id-1
01958     ridges updated for simplicial neighbors of samecycle with a ridge
01959 
01960   notes:
01961     assumes newfacet not in samecycle
01962     usually, samecycle facets are new, simplicial facets without internal ridges
01963       not so if horizon facet is coplanar to two different samecycles
01964 
01965   see:
01966     qh_mergeneighbors()
01967 
01968   design:
01969     check samecycle
01970     delete neighbors from newfacet that are also in samecycle
01971     for each neighbor of a facet in samecycle
01972       if neighbor is simplicial
01973         if first visit
01974           move the neighbor relation to newfacet
01975           update facet links for its ridges
01976         else
01977           make ridges for neighbor
01978           remove samecycle reference
01979       else
01980         update neighbor sets
01981 */
01982 void qh_mergecycle_neighbors(facetT *samecycle, facetT *newfacet) {
01983   facetT *same, *neighbor, **neighborp;
01984   int delneighbors= 0, newneighbors= 0;
01985   unsigned int samevisitid;
01986   ridgeT *ridge, **ridgep;
01987 
01988   samevisitid= ++qh visit_id;
01989   FORALLsame_cycle_(samecycle) {
01990     if (same->visitid == samevisitid || same->visible)
01991       qh_infiniteloop(samecycle);
01992     same->visitid= samevisitid;
01993   }
01994   newfacet->visitid= ++qh visit_id;
01995   trace4((qh ferr, 4031, "qh_mergecycle_neighbors: delete shared neighbors from newfacet\n"));
01996   FOREACHneighbor_(newfacet) {
01997     if (neighbor->visitid == samevisitid) {
01998       SETref_(neighbor)= NULL;  /* samecycle neighbors deleted */
01999       delneighbors++;
02000     }else
02001       neighbor->visitid= qh visit_id;
02002   }
02003   qh_setcompact(newfacet->neighbors);
02004 
02005   trace4((qh ferr, 4032, "qh_mergecycle_neighbors: update neighbors\n"));
02006   FORALLsame_cycle_(samecycle) {
02007     FOREACHneighbor_(same) {
02008       if (neighbor->visitid == samevisitid)
02009         continue;
02010       if (neighbor->simplicial) {
02011         if (neighbor->visitid != qh visit_id) {
02012           qh_setappend(&newfacet->neighbors, neighbor);
02013           qh_setreplace(neighbor->neighbors, same, newfacet);
02014           newneighbors++;
02015           neighbor->visitid= qh visit_id;
02016           FOREACHridge_(neighbor->ridges) { /* update ridge in case of qh_makeridges */
02017             if (ridge->top == same) {
02018               ridge->top= newfacet;
02019               break;
02020             }else if (ridge->bottom == same) {
02021               ridge->bottom= newfacet;
02022               break;
02023             }
02024           }
02025         }else {
02026           qh_makeridges(neighbor);
02027           qh_setdel(neighbor->neighbors, same);
02028           /* same can't be horizon facet for neighbor */
02029         }
02030       }else { /* non-simplicial neighbor */
02031         qh_setdel(neighbor->neighbors, same);
02032         if (neighbor->visitid != qh visit_id) {
02033           qh_setappend(&neighbor->neighbors, newfacet);
02034           qh_setappend(&newfacet->neighbors, neighbor);
02035           neighbor->visitid= qh visit_id;
02036           newneighbors++;
02037         }
02038       }
02039     }
02040   }
02041   trace2((qh ferr, 2032, "qh_mergecycle_neighbors: deleted %d neighbors and added %d\n",
02042              delneighbors, newneighbors));
02043 } /* mergecycle_neighbors */
02044 
02045 /*-<a                             href="qh-merge.htm#TOC"
02046   >-------------------------------</a><a name="mergecycle_ridges">-</a>
02047 
02048   qh_mergecycle_ridges( samecycle, newfacet )
02049     add ridges/neighbors for facets in samecycle to newfacet
02050     all new/old neighbors of newfacet marked with qh.visit_id
02051     facets in samecycle marked with qh.visit_id-1
02052     newfacet marked with qh.visit_id
02053 
02054   returns:
02055     newfacet has merged ridges
02056 
02057   notes:
02058     ridge already updated for simplicial neighbors of samecycle with a ridge
02059 
02060   see:
02061     qh_mergeridges()
02062     qh_makeridges()
02063 
02064   design:
02065     remove ridges between newfacet and samecycle
02066     for each facet in samecycle
02067       for each ridge in facet
02068         update facet pointers in ridge
02069         skip ridges processed in qh_mergecycle_neighors
02070         free ridges between newfacet and samecycle
02071         free ridges between facets of samecycle (on 2nd visit)
02072         append remaining ridges to newfacet
02073       if simpilicial facet
02074         for each neighbor of facet
02075           if simplicial facet
02076           and not samecycle facet or newfacet
02077             make ridge between neighbor and newfacet
02078 */
02079 void qh_mergecycle_ridges(facetT *samecycle, facetT *newfacet) {
02080   facetT *same, *neighbor= NULL;
02081   int numold=0, numnew=0;
02082   int neighbor_i, neighbor_n;
02083   unsigned int samevisitid;
02084   ridgeT *ridge, **ridgep;
02085   boolT toporient;
02086   void **freelistp; /* used !qh_NOmem */
02087 
02088   trace4((qh ferr, 4033, "qh_mergecycle_ridges: delete shared ridges from newfacet\n"));
02089   samevisitid= qh visit_id -1;
02090   FOREACHridge_(newfacet->ridges) {
02091     neighbor= otherfacet_(ridge, newfacet);
02092     if (neighbor->visitid == samevisitid)
02093       SETref_(ridge)= NULL; /* ridge free'd below */
02094   }
02095   qh_setcompact(newfacet->ridges);
02096 
02097   trace4((qh ferr, 4034, "qh_mergecycle_ridges: add ridges to newfacet\n"));
02098   FORALLsame_cycle_(samecycle) {
02099     FOREACHridge_(same->ridges) {
02100       if (ridge->top == same) {
02101         ridge->top= newfacet;
02102         neighbor= ridge->bottom;
02103       }else if (ridge->bottom == same) {
02104         ridge->bottom= newfacet;
02105         neighbor= ridge->top;
02106       }else if (ridge->top == newfacet || ridge->bottom == newfacet) {
02107         qh_setappend(&newfacet->ridges, ridge);
02108         numold++;  /* already set by qh_mergecycle_neighbors */
02109         continue;
02110       }else {
02111         qh_fprintf(qh ferr, 6098, "qhull internal error (qh_mergecycle_ridges): bad ridge r%d\n", ridge->id);
02112         qh_errexit(qh_ERRqhull, NULL, ridge);
02113       }
02114       if (neighbor == newfacet) {
02115         qh_setfree(&(ridge->vertices));
02116         qh_memfree_(ridge, (int)sizeof(ridgeT), freelistp);
02117         numold++;
02118       }else if (neighbor->visitid == samevisitid) {
02119         qh_setdel(neighbor->ridges, ridge);
02120         qh_setfree(&(ridge->vertices));
02121         qh_memfree_(ridge, (int)sizeof(ridgeT), freelistp);
02122         numold++;
02123       }else {
02124         qh_setappend(&newfacet->ridges, ridge);
02125         numold++;
02126       }
02127     }
02128     if (same->ridges)
02129       qh_settruncate(same->ridges, 0);
02130     if (!same->simplicial)
02131       continue;
02132     FOREACHneighbor_i_(same) {       /* note: !newfact->simplicial */
02133       if (neighbor->visitid != samevisitid && neighbor->simplicial) {
02134         ridge= qh_newridge();
02135         ridge->vertices= qh_setnew_delnthsorted(same->vertices, qh hull_dim,
02136                                                           neighbor_i, 0);
02137         toporient= same->toporient ^ (neighbor_i & 0x1);
02138         if (toporient) {
02139           ridge->top= newfacet;
02140           ridge->bottom= neighbor;
02141         }else {
02142           ridge->top= neighbor;
02143           ridge->bottom= newfacet;
02144         }
02145         qh_setappend(&(newfacet->ridges), ridge);
02146         qh_setappend(&(neighbor->ridges), ridge);
02147         numnew++;
02148       }
02149     }
02150   }
02151 
02152   trace2((qh ferr, 2033, "qh_mergecycle_ridges: found %d old ridges and %d new ones\n",
02153              numold, numnew));
02154 } /* mergecycle_ridges */
02155 
02156 /*-<a                             href="qh-merge.htm#TOC"
02157   >-------------------------------</a><a name="mergecycle_vneighbors">-</a>
02158 
02159   qh_mergecycle_vneighbors( samecycle, newfacet )
02160     create vertex neighbors for newfacet from vertices of facets in samecycle
02161     samecycle marked with visitid == qh.visit_id - 1
02162 
02163   returns:
02164     newfacet vertices with updated neighbors
02165     marks newfacet with qh.visit_id-1
02166     deletes vertices that are merged away
02167     sets delridge on all vertices (faster here than in mergecycle_ridges)
02168 
02169   see:
02170     qh_mergevertex_neighbors()
02171 
02172   design:
02173     for each vertex of samecycle facet
02174       set vertex->delridge
02175       delete samecycle facets from vertex neighbors
02176       append newfacet to vertex neighbors
02177       if vertex only in newfacet
02178         delete it from newfacet
02179         add it to qh.del_vertices for later deletion
02180 */
02181 void qh_mergecycle_vneighbors(facetT *samecycle, facetT *newfacet) {
02182   facetT *neighbor, **neighborp;
02183   unsigned int mergeid;
02184   vertexT *vertex, **vertexp, *apex;
02185   setT *vertices;
02186 
02187   trace4((qh ferr, 4035, "qh_mergecycle_vneighbors: update vertex neighbors for newfacet\n"));
02188   mergeid= qh visit_id - 1;
02189   newfacet->visitid= mergeid;
02190   vertices= qh_basevertices(samecycle); /* temp */
02191   apex= SETfirstt_(samecycle->vertices, vertexT);
02192   qh_setappend(&vertices, apex);
02193   FOREACHvertex_(vertices) {
02194     vertex->delridge= True;
02195     FOREACHneighbor_(vertex) {
02196       if (neighbor->visitid == mergeid)
02197         SETref_(neighbor)= NULL;
02198     }
02199     qh_setcompact(vertex->neighbors);
02200     qh_setappend(&vertex->neighbors, newfacet);
02201     if (!SETsecond_(vertex->neighbors)) {
02202       zinc_(Zcyclevertex);
02203       trace2((qh ferr, 2034, "qh_mergecycle_vneighbors: deleted v%d when merging cycle f%d into f%d\n",
02204         vertex->id, samecycle->id, newfacet->id));
02205       qh_setdelsorted(newfacet->vertices, vertex);
02206       vertex->deleted= True;
02207       qh_setappend(&qh del_vertices, vertex);
02208     }
02209   }
02210   qh_settempfree(&vertices);
02211   trace3((qh ferr, 3005, "qh_mergecycle_vneighbors: merged vertices from cycle f%d into f%d\n",
02212              samecycle->id, newfacet->id));
02213 } /* mergecycle_vneighbors */
02214 
02215 /*-<a                             href="qh-merge.htm#TOC"
02216   >-------------------------------</a><a name="mergefacet">-</a>
02217 
02218   qh_mergefacet( facet1, facet2, mindist, maxdist, mergeapex )
02219     merges facet1 into facet2
02220     mergeapex==qh_MERGEapex if merging new facet into coplanar horizon
02221 
02222   returns:
02223     qh.max_outside and qh.min_vertex updated
02224     initializes vertex neighbors on first merge
02225 
02226   returns:
02227     facet2 contains facet1's vertices, neighbors, and ridges
02228       facet2 moved to end of qh.facet_list
02229       makes facet2 a newfacet
02230       sets facet2->newmerge set
02231       clears facet2->center (unless merging into a large facet)
02232       clears facet2->tested and ridge->tested for facet1
02233 
02234     facet1 prepended to visible_list for later deletion and partitioning
02235       facet1->f.replace == facet2
02236 
02237     adds neighboring facets to facet_mergeset if redundant or degenerate
02238 
02239   notes:
02240     mindist/maxdist may be NULL (only if both NULL)
02241     traces merge if fmax_(maxdist,-mindist) > TRACEdist
02242 
02243   see:
02244     qh_mergecycle()
02245 
02246   design:
02247     trace merge and check for degenerate simplex
02248     make ridges for both facets
02249     update qh.max_outside, qh.max_vertex, qh.min_vertex
02250     update facet2->maxoutside and keepcentrum
02251     update facet2->nummerge
02252     update tested flags for facet2
02253     if facet1 is simplicial
02254       merge facet1 into facet2
02255     else
02256       merge facet1's neighbors into facet2
02257       merge facet1's ridges into facet2
02258       merge facet1's vertices into facet2
02259       merge facet1's vertex neighbors into facet2
02260       add facet2's vertices to qh.new_vertexlist
02261       unless qh_MERGEapex
02262         test facet2 for degenerate or redundant neighbors
02263       move facet1 to qh.visible_list for later deletion
02264       move facet2 to end of qh.newfacet_list
02265 */
02266 void qh_mergefacet(facetT *facet1, facetT *facet2, realT *mindist, realT *maxdist, boolT mergeapex) {
02267   boolT traceonce= False;
02268   vertexT *vertex, **vertexp;
02269   int tracerestore=0, nummerge;
02270 
02271   if (facet1->tricoplanar || facet2->tricoplanar) {
02272     if (!qh TRInormals) {
02273       qh_fprintf(qh ferr, 6226, "Qhull internal error (qh_mergefacet): does not work for tricoplanar facets.  Use option 'Q11'\n");
02274       qh_errexit2 (qh_ERRqhull, facet1, facet2);
02275     }
02276     if (facet2->tricoplanar) {
02277       facet2->tricoplanar= False;
02278       facet2->keepcentrum= False;
02279     }
02280   }
02281   zzinc_(Ztotmerge);
02282   if (qh REPORTfreq2 && qh POSTmerging) {
02283     if (zzval_(Ztotmerge) > qh mergereport + qh REPORTfreq2)
02284       qh_tracemerging();
02285   }
02286 #ifndef qh_NOtrace
02287   if (qh build_cnt >= qh RERUN) {
02288     if (mindist && (-*mindist > qh TRACEdist || *maxdist > qh TRACEdist)) {
02289       tracerestore= 0;
02290       qh IStracing= qh TRACElevel;
02291       traceonce= True;
02292       qh_fprintf(qh ferr, 8075, "qh_mergefacet: ========= trace wide merge #%d(%2.2g) for f%d into f%d, last point was p%d\n", zzval_(Ztotmerge),
02293              fmax_(-*mindist, *maxdist), facet1->id, facet2->id, qh furthest_id);
02294     }else if (facet1 == qh tracefacet || facet2 == qh tracefacet) {
02295       tracerestore= qh IStracing;
02296       qh IStracing= 4;
02297       traceonce= True;
02298       qh_fprintf(qh ferr, 8076, "qh_mergefacet: ========= trace merge #%d involving f%d, furthest is p%d\n",
02299                  zzval_(Ztotmerge), qh tracefacet_id,  qh furthest_id);
02300     }
02301   }
02302   if (qh IStracing >= 2) {
02303     realT mergemin= -2;
02304     realT mergemax= -2;
02305 
02306     if (mindist) {
02307       mergemin= *mindist;
02308       mergemax= *maxdist;
02309     }
02310     qh_fprintf(qh ferr, 8077, "qh_mergefacet: #%d merge f%d into f%d, mindist= %2.2g, maxdist= %2.2g\n",
02311     zzval_(Ztotmerge), facet1->id, facet2->id, mergemin, mergemax);
02312   }
02313 #endif /* !qh_NOtrace */
02314   if (facet1 == facet2 || facet1->visible || facet2->visible) {
02315     qh_fprintf(qh ferr, 6099, "qhull internal error (qh_mergefacet): either f%d and f%d are the same or one is a visible facet\n",
02316              facet1->id, facet2->id);
02317     qh_errexit2 (qh_ERRqhull, facet1, facet2);
02318   }
02319   if (qh num_facets - qh num_visible <= qh hull_dim + 1) {
02320     qh_fprintf(qh ferr, 6227, "\n\
02321 qhull precision error: Only %d facets remain.  Can not merge another\n\
02322 pair.  The input is too degenerate or the convexity constraints are\n\
02323 too strong.\n", qh hull_dim+1);
02324     if (qh hull_dim >= 5 && !qh MERGEexact)
02325       qh_fprintf(qh ferr, 8079, "Option 'Qx' may avoid this problem.\n");
02326     qh_errexit(qh_ERRinput, NULL, NULL);
02327   }
02328   if (!qh VERTEXneighbors)
02329     qh_vertexneighbors();
02330   qh_makeridges(facet1);
02331   qh_makeridges(facet2);
02332   if (qh IStracing >=4)
02333     qh_errprint("MERGING", facet1, facet2, NULL, NULL);
02334   if (mindist) {
02335     maximize_(qh max_outside, *maxdist);
02336     maximize_(qh max_vertex, *maxdist);
02337 #if qh_MAXoutside
02338     maximize_(facet2->maxoutside, *maxdist);
02339 #endif
02340     minimize_(qh min_vertex, *mindist);
02341     if (!facet2->keepcentrum
02342     && (*maxdist > qh WIDEfacet || *mindist < -qh WIDEfacet)) {
02343       facet2->keepcentrum= True;
02344       zinc_(Zwidefacet);
02345     }
02346   }
02347   nummerge= facet1->nummerge + facet2->nummerge + 1;
02348   if (nummerge >= qh_MAXnummerge)
02349     facet2->nummerge= qh_MAXnummerge;
02350   else
02351     facet2->nummerge= (short unsigned int)nummerge;
02352   facet2->newmerge= True;
02353   facet2->dupridge= False;
02354   qh_updatetested  (facet1, facet2);
02355   if (qh hull_dim > 2 && qh_setsize(facet1->vertices) == qh hull_dim)
02356     qh_mergesimplex(facet1, facet2, mergeapex);
02357   else {
02358     qh vertex_visit++;
02359     FOREACHvertex_(facet2->vertices)
02360       vertex->visitid= qh vertex_visit;
02361     if (qh hull_dim == 2)
02362       qh_mergefacet2d(facet1, facet2);
02363     else {
02364       qh_mergeneighbors(facet1, facet2);
02365       qh_mergevertices(facet1->vertices, &facet2->vertices);
02366     }
02367     qh_mergeridges(facet1, facet2);
02368     qh_mergevertex_neighbors(facet1, facet2);
02369     if (!facet2->newfacet)
02370       qh_newvertices(facet2->vertices);
02371   }
02372   if (!mergeapex)
02373     qh_degen_redundant_neighbors(facet2, facet1);
02374   if (facet2->coplanar || !facet2->newfacet) {
02375     zinc_(Zmergeintohorizon);
02376   }else if (!facet1->newfacet && facet2->newfacet) {
02377     zinc_(Zmergehorizon);
02378   }else {
02379     zinc_(Zmergenew);
02380   }
02381   qh_willdelete(facet1, facet2);
02382   qh_removefacet(facet2);  /* append as a newfacet to end of qh facet_list */
02383   qh_appendfacet(facet2);
02384   facet2->newfacet= True;
02385   facet2->tested= False;
02386   qh_tracemerge(facet1, facet2);
02387   if (traceonce) {
02388     qh_fprintf(qh ferr, 8080, "qh_mergefacet: end of wide tracing\n");
02389     qh IStracing= tracerestore;
02390   }
02391 } /* mergefacet */
02392 
02393 
02394 /*-<a                             href="qh-merge.htm#TOC"
02395   >-------------------------------</a><a name="mergefacet2d">-</a>
02396 
02397   qh_mergefacet2d( facet1, facet2 )
02398     in 2d, merges neighbors and vertices of facet1 into facet2
02399 
02400   returns:
02401     build ridges for neighbors if necessary
02402     facet2 looks like a simplicial facet except for centrum, ridges
02403       neighbors are opposite the corresponding vertex
02404       maintains orientation of facet2
02405 
02406   notes:
02407     qh_mergefacet() retains non-simplicial structures
02408       they are not needed in 2d, but later routines may use them
02409     preserves qh.vertex_visit for qh_mergevertex_neighbors()
02410 
02411   design:
02412     get vertices and neighbors
02413     determine new vertices and neighbors
02414     set new vertices and neighbors and adjust orientation
02415     make ridges for new neighbor if needed
02416 */
02417 void qh_mergefacet2d(facetT *facet1, facetT *facet2) {
02418   vertexT *vertex1A, *vertex1B, *vertex2A, *vertex2B, *vertexA, *vertexB;
02419   facetT *neighbor1A, *neighbor1B, *neighbor2A, *neighbor2B, *neighborA, *neighborB;
02420 
02421   vertex1A= SETfirstt_(facet1->vertices, vertexT);
02422   vertex1B= SETsecondt_(facet1->vertices, vertexT);
02423   vertex2A= SETfirstt_(facet2->vertices, vertexT);
02424   vertex2B= SETsecondt_(facet2->vertices, vertexT);
02425   neighbor1A= SETfirstt_(facet1->neighbors, facetT);
02426   neighbor1B= SETsecondt_(facet1->neighbors, facetT);
02427   neighbor2A= SETfirstt_(facet2->neighbors, facetT);
02428   neighbor2B= SETsecondt_(facet2->neighbors, facetT);
02429   if (vertex1A == vertex2A) {
02430     vertexA= vertex1B;
02431     vertexB= vertex2B;
02432     neighborA= neighbor2A;
02433     neighborB= neighbor1A;
02434   }else if (vertex1A == vertex2B) {
02435     vertexA= vertex1B;
02436     vertexB= vertex2A;
02437     neighborA= neighbor2B;
02438     neighborB= neighbor1A;
02439   }else if (vertex1B == vertex2A) {
02440     vertexA= vertex1A;
02441     vertexB= vertex2B;
02442     neighborA= neighbor2A;
02443     neighborB= neighbor1B;
02444   }else { /* 1B == 2B */
02445     vertexA= vertex1A;
02446     vertexB= vertex2A;
02447     neighborA= neighbor2B;
02448     neighborB= neighbor1B;
02449   }
02450   /* vertexB always from facet2, neighborB always from facet1 */
02451   if (vertexA->id > vertexB->id) {
02452     SETfirst_(facet2->vertices)= vertexA;
02453     SETsecond_(facet2->vertices)= vertexB;
02454     if (vertexB == vertex2A)
02455       facet2->toporient= !facet2->toporient;
02456     SETfirst_(facet2->neighbors)= neighborA;
02457     SETsecond_(facet2->neighbors)= neighborB;
02458   }else {
02459     SETfirst_(facet2->vertices)= vertexB;
02460     SETsecond_(facet2->vertices)= vertexA;
02461     if (vertexB == vertex2B)
02462       facet2->toporient= !facet2->toporient;
02463     SETfirst_(facet2->neighbors)= neighborB;
02464     SETsecond_(facet2->neighbors)= neighborA;
02465   }
02466   qh_makeridges(neighborB);
02467   qh_setreplace(neighborB->neighbors, facet1, facet2);
02468   trace4((qh ferr, 4036, "qh_mergefacet2d: merged v%d and neighbor f%d of f%d into f%d\n",
02469        vertexA->id, neighborB->id, facet1->id, facet2->id));
02470 } /* mergefacet2d */
02471 
02472 
02473 /*-<a                             href="qh-merge.htm#TOC"
02474   >-------------------------------</a><a name="mergeneighbors">-</a>
02475 
02476   qh_mergeneighbors( facet1, facet2 )
02477     merges the neighbors of facet1 into facet2
02478 
02479   see:
02480     qh_mergecycle_neighbors()
02481 
02482   design:
02483     for each neighbor of facet1
02484       if neighbor is also a neighbor of facet2
02485         if neighbor is simpilicial
02486           make ridges for later deletion as a degenerate facet
02487         update its neighbor set
02488       else
02489         move the neighbor relation to facet2
02490     remove the neighbor relation for facet1 and facet2
02491 */
02492 void qh_mergeneighbors(facetT *facet1, facetT *facet2) {
02493   facetT *neighbor, **neighborp;
02494 
02495   trace4((qh ferr, 4037, "qh_mergeneighbors: merge neighbors of f%d and f%d\n",
02496           facet1->id, facet2->id));
02497   qh visit_id++;
02498   FOREACHneighbor_(facet2) {
02499     neighbor->visitid= qh visit_id;
02500   }
02501   FOREACHneighbor_(facet1) {
02502     if (neighbor->visitid == qh visit_id) {
02503       if (neighbor->simplicial)    /* is degen, needs ridges */
02504         qh_makeridges(neighbor);
02505       if (SETfirstt_(neighbor->neighbors, facetT) != facet1) /*keep newfacet->horizon*/
02506         qh_setdel(neighbor->neighbors, facet1);
02507       else {
02508         qh_setdel(neighbor->neighbors, facet2);
02509         qh_setreplace(neighbor->neighbors, facet1, facet2);
02510       }
02511     }else if (neighbor != facet2) {
02512       qh_setappend(&(facet2->neighbors), neighbor);
02513       qh_setreplace(neighbor->neighbors, facet1, facet2);
02514     }
02515   }
02516   qh_setdel(facet1->neighbors, facet2);  /* here for makeridges */
02517   qh_setdel(facet2->neighbors, facet1);
02518 } /* mergeneighbors */
02519 
02520 
02521 /*-<a                             href="qh-merge.htm#TOC"
02522   >-------------------------------</a><a name="mergeridges">-</a>
02523 
02524   qh_mergeridges( facet1, facet2 )
02525     merges the ridge set of facet1 into facet2
02526 
02527   returns:
02528     may delete all ridges for a vertex
02529     sets vertex->delridge on deleted ridges
02530 
02531   see:
02532     qh_mergecycle_ridges()
02533 
02534   design:
02535     delete ridges between facet1 and facet2
02536       mark (delridge) vertices on these ridges for later testing
02537     for each remaining ridge
02538       rename facet1 to facet2
02539 */
02540 void qh_mergeridges(facetT *facet1, facetT *facet2) {
02541   ridgeT *ridge, **ridgep;
02542   vertexT *vertex, **vertexp;
02543 
02544   trace4((qh ferr, 4038, "qh_mergeridges: merge ridges of f%d and f%d\n",
02545           facet1->id, facet2->id));
02546   FOREACHridge_(facet2->ridges) {
02547     if ((ridge->top == facet1) || (ridge->bottom == facet1)) {
02548       FOREACHvertex_(ridge->vertices)
02549         vertex->delridge= True;
02550       qh_delridge(ridge);  /* expensive in high-d, could rebuild */
02551       ridgep--; /*repeat*/
02552     }
02553   }
02554   FOREACHridge_(facet1->ridges) {
02555     if (ridge->top == facet1)
02556       ridge->top= facet2;
02557     else
02558       ridge->bottom= facet2;
02559     qh_setappend(&(facet2->ridges), ridge);
02560   }
02561 } /* mergeridges */
02562 
02563 
02564 /*-<a                             href="qh-merge.htm#TOC"
02565   >-------------------------------</a><a name="mergesimplex">-</a>
02566 
02567   qh_mergesimplex( facet1, facet2, mergeapex )
02568     merge simplicial facet1 into facet2
02569     mergeapex==qh_MERGEapex if merging samecycle into horizon facet
02570       vertex id is latest (most recently created)
02571     facet1 may be contained in facet2
02572     ridges exist for both facets
02573 
02574   returns:
02575     facet2 with updated vertices, ridges, neighbors
02576     updated neighbors for facet1's vertices
02577     facet1 not deleted
02578     sets vertex->delridge on deleted ridges
02579 
02580   notes:
02581     special case code since this is the most common merge
02582     called from qh_mergefacet()
02583 
02584   design:
02585     if qh_MERGEapex
02586       add vertices of facet2 to qh.new_vertexlist if necessary
02587       add apex to facet2
02588     else
02589       for each ridge between facet1 and facet2
02590         set vertex->delridge
02591       determine the apex for facet1 (i.e., vertex to be merged)
02592       unless apex already in facet2
02593         insert apex into vertices for facet2
02594       add vertices of facet2 to qh.new_vertexlist if necessary
02595       add apex to qh.new_vertexlist if necessary
02596       for each vertex of facet1
02597         if apex
02598           rename facet1 to facet2 in its vertex neighbors
02599         else
02600           delete facet1 from vertex neighors
02601           if only in facet2
02602             add vertex to qh.del_vertices for later deletion
02603       for each ridge of facet1
02604         delete ridges between facet1 and facet2
02605         append other ridges to facet2 after renaming facet to facet2
02606 */
02607 void qh_mergesimplex(facetT *facet1, facetT *facet2, boolT mergeapex) {
02608   vertexT *vertex, **vertexp, *apex;
02609   ridgeT *ridge, **ridgep;
02610   boolT issubset= False;
02611   int vertex_i= -1, vertex_n;
02612   facetT *neighbor, **neighborp, *otherfacet;
02613 
02614   if (mergeapex) {
02615     if (!facet2->newfacet)
02616       qh_newvertices(facet2->vertices);  /* apex is new */
02617     apex= SETfirstt_(facet1->vertices, vertexT);
02618     if (SETfirstt_(facet2->vertices, vertexT) != apex)
02619       qh_setaddnth(&facet2->vertices, 0, apex);  /* apex has last id */
02620     else
02621       issubset= True;
02622   }else {
02623     zinc_(Zmergesimplex);
02624     FOREACHvertex_(facet1->vertices)
02625       vertex->seen= False;
02626     FOREACHridge_(facet1->ridges) {
02627       if (otherfacet_(ridge, facet1) == facet2) {
02628         FOREACHvertex_(ridge->vertices) {
02629           vertex->seen= True;
02630           vertex->delridge= True;
02631         }
02632         break;
02633       }
02634     }
02635     FOREACHvertex_(facet1->vertices) {
02636       if (!vertex->seen)
02637         break;  /* must occur */
02638     }
02639     apex= vertex;
02640     trace4((qh ferr, 4039, "qh_mergesimplex: merge apex v%d of f%d into facet f%d\n",
02641           apex->id, facet1->id, facet2->id));
02642     FOREACHvertex_i_(facet2->vertices) {
02643       if (vertex->id < apex->id) {
02644         break;
02645       }else if (vertex->id == apex->id) {
02646         issubset= True;
02647         break;
02648       }
02649     }
02650     if (!issubset)
02651       qh_setaddnth(&facet2->vertices, vertex_i, apex);
02652     if (!facet2->newfacet)
02653       qh_newvertices(facet2->vertices);
02654     else if (!apex->newlist) {
02655       qh_removevertex(apex);
02656       qh_appendvertex(apex);
02657     }
02658   }
02659   trace4((qh ferr, 4040, "qh_mergesimplex: update vertex neighbors of f%d\n",
02660           facet1->id));
02661   FOREACHvertex_(facet1->vertices) {
02662     if (vertex == apex && !issubset)
02663       qh_setreplace(vertex->neighbors, facet1, facet2);
02664     else {
02665       qh_setdel(vertex->neighbors, facet1);
02666       if (!SETsecond_(vertex->neighbors))
02667         qh_mergevertex_del(vertex, facet1, facet2);
02668     }
02669   }
02670   trace4((qh ferr, 4041, "qh_mergesimplex: merge ridges and neighbors of f%d into f%d\n",
02671           facet1->id, facet2->id));
02672   qh visit_id++;
02673   FOREACHneighbor_(facet2)
02674     neighbor->visitid= qh visit_id;
02675   FOREACHridge_(facet1->ridges) {
02676     otherfacet= otherfacet_(ridge, facet1);
02677     if (otherfacet == facet2) {
02678       qh_setdel(facet2->ridges, ridge);
02679       qh_setfree(&(ridge->vertices));
02680       qh_memfree(ridge, (int)sizeof(ridgeT));
02681       qh_setdel(facet2->neighbors, facet1);
02682     }else {
02683       qh_setappend(&facet2->ridges, ridge);
02684       if (otherfacet->visitid != qh visit_id) {
02685         qh_setappend(&facet2->neighbors, otherfacet);
02686         qh_setreplace(otherfacet->neighbors, facet1, facet2);
02687         otherfacet->visitid= qh visit_id;
02688       }else {
02689         if (otherfacet->simplicial)    /* is degen, needs ridges */
02690           qh_makeridges(otherfacet);
02691         if (SETfirstt_(otherfacet->neighbors, facetT) != facet1)
02692           qh_setdel(otherfacet->neighbors, facet1);
02693         else {   /*keep newfacet->neighbors->horizon*/
02694           qh_setdel(otherfacet->neighbors, facet2);
02695           qh_setreplace(otherfacet->neighbors, facet1, facet2);
02696         }
02697       }
02698       if (ridge->top == facet1) /* wait until after qh_makeridges */
02699         ridge->top= facet2;
02700       else
02701         ridge->bottom= facet2;
02702     }
02703   }
02704   SETfirst_(facet1->ridges)= NULL; /* it will be deleted */
02705   trace3((qh ferr, 3006, "qh_mergesimplex: merged simplex f%d apex v%d into facet f%d\n",
02706           facet1->id, getid_(apex), facet2->id));
02707 } /* mergesimplex */
02708 
02709 /*-<a                             href="qh-merge.htm#TOC"
02710   >-------------------------------</a><a name="mergevertex_del">-</a>
02711 
02712   qh_mergevertex_del( vertex, facet1, facet2 )
02713     delete a vertex because of merging facet1 into facet2
02714 
02715   returns:
02716     deletes vertex from facet2
02717     adds vertex to qh.del_vertices for later deletion
02718 */
02719 void qh_mergevertex_del(vertexT *vertex, facetT *facet1, facetT *facet2) {
02720 
02721   zinc_(Zmergevertex);
02722   trace2((qh ferr, 2035, "qh_mergevertex_del: deleted v%d when merging f%d into f%d\n",
02723           vertex->id, facet1->id, facet2->id));
02724   qh_setdelsorted(facet2->vertices, vertex);
02725   vertex->deleted= True;
02726   qh_setappend(&qh del_vertices, vertex);
02727 } /* mergevertex_del */
02728 
02729 /*-<a                             href="qh-merge.htm#TOC"
02730   >-------------------------------</a><a name="mergevertex_neighbors">-</a>
02731 
02732   qh_mergevertex_neighbors( facet1, facet2 )
02733     merge the vertex neighbors of facet1 to facet2
02734 
02735   returns:
02736     if vertex is current qh.vertex_visit
02737       deletes facet1 from vertex->neighbors
02738     else
02739       renames facet1 to facet2 in vertex->neighbors
02740     deletes vertices if only one neighbor
02741 
02742   notes:
02743     assumes vertex neighbor sets are good
02744 */
02745 void qh_mergevertex_neighbors(facetT *facet1, facetT *facet2) {
02746   vertexT *vertex, **vertexp;
02747 
02748   trace4((qh ferr, 4042, "qh_mergevertex_neighbors: merge vertex neighbors of f%d and f%d\n",
02749           facet1->id, facet2->id));
02750   if (qh tracevertex) {
02751     qh_fprintf(qh ferr, 8081, "qh_mergevertex_neighbors: of f%d and f%d at furthest p%d f0= %p\n",
02752              facet1->id, facet2->id, qh furthest_id, qh tracevertex->neighbors->e[0].p);
02753     qh_errprint("TRACE", NULL, NULL, NULL, qh tracevertex);
02754   }
02755   FOREACHvertex_(facet1->vertices) {
02756     if (vertex->visitid != qh vertex_visit)
02757       qh_setreplace(vertex->neighbors, facet1, facet2);
02758     else {
02759       qh_setdel(vertex->neighbors, facet1);
02760       if (!SETsecond_(vertex->neighbors))
02761         qh_mergevertex_del(vertex, facet1, facet2);
02762     }
02763   }
02764   if (qh tracevertex)
02765     qh_errprint("TRACE", NULL, NULL, NULL, qh tracevertex);
02766 } /* mergevertex_neighbors */
02767 
02768 
02769 /*-<a                             href="qh-merge.htm#TOC"
02770   >-------------------------------</a><a name="mergevertices">-</a>
02771 
02772   qh_mergevertices( vertices1, vertices2 )
02773     merges the vertex set of facet1 into facet2
02774 
02775   returns:
02776     replaces vertices2 with merged set
02777     preserves vertex_visit for qh_mergevertex_neighbors
02778     updates qh.newvertex_list
02779 
02780   design:
02781     create a merged set of both vertices (in inverse id order)
02782 */
02783 void qh_mergevertices(setT *vertices1, setT **vertices2) {
02784   int newsize= qh_setsize(vertices1)+qh_setsize(*vertices2) - qh hull_dim + 1;
02785   setT *mergedvertices;
02786   vertexT *vertex, **vertexp, **vertex2= SETaddr_(*vertices2, vertexT);
02787 
02788   mergedvertices= qh_settemp(newsize);
02789   FOREACHvertex_(vertices1) {
02790     if (!*vertex2 || vertex->id > (*vertex2)->id)
02791       qh_setappend(&mergedvertices, vertex);
02792     else {
02793       while (*vertex2 && (*vertex2)->id > vertex->id)
02794         qh_setappend(&mergedvertices, *vertex2++);
02795       if (!*vertex2 || (*vertex2)->id < vertex->id)
02796         qh_setappend(&mergedvertices, vertex);
02797       else
02798         qh_setappend(&mergedvertices, *vertex2++);
02799     }
02800   }
02801   while (*vertex2)
02802     qh_setappend(&mergedvertices, *vertex2++);
02803   if (newsize < qh_setsize(mergedvertices)) {
02804     qh_fprintf(qh ferr, 6100, "qhull internal error (qh_mergevertices): facets did not share a ridge\n");
02805     qh_errexit(qh_ERRqhull, NULL, NULL);
02806   }
02807   qh_setfree(vertices2);
02808   *vertices2= mergedvertices;
02809   qh_settemppop();
02810 } /* mergevertices */
02811 
02812 
02813 /*-<a                             href="qh-merge.htm#TOC"
02814   >-------------------------------</a><a name="neighbor_intersections">-</a>
02815 
02816   qh_neighbor_intersections( vertex )
02817     return intersection of all vertices in vertex->neighbors except for vertex
02818 
02819   returns:
02820     returns temporary set of vertices
02821     does not include vertex
02822     NULL if a neighbor is simplicial
02823     NULL if empty set
02824 
02825   notes:
02826     used for renaming vertices
02827 
02828   design:
02829     initialize the intersection set with vertices of the first two neighbors
02830     delete vertex from the intersection
02831     for each remaining neighbor
02832       intersect its vertex set with the intersection set
02833       return NULL if empty
02834     return the intersection set
02835 */
02836 setT *qh_neighbor_intersections(vertexT *vertex) {
02837   facetT *neighbor, **neighborp, *neighborA, *neighborB;
02838   setT *intersect;
02839   int neighbor_i, neighbor_n;
02840 
02841   FOREACHneighbor_(vertex) {
02842     if (neighbor->simplicial)
02843       return NULL;
02844   }
02845   neighborA= SETfirstt_(vertex->neighbors, facetT);
02846   neighborB= SETsecondt_(vertex->neighbors, facetT);
02847   zinc_(Zintersectnum);
02848   if (!neighborA)
02849     return NULL;
02850   if (!neighborB)
02851     intersect= qh_setcopy(neighborA->vertices, 0);
02852   else
02853     intersect= qh_vertexintersect_new(neighborA->vertices, neighborB->vertices);
02854   qh_settemppush(intersect);
02855   qh_setdelsorted(intersect, vertex);
02856   FOREACHneighbor_i_(vertex) {
02857     if (neighbor_i >= 2) {
02858       zinc_(Zintersectnum);
02859       qh_vertexintersect(&intersect, neighbor->vertices);
02860       if (!SETfirst_(intersect)) {
02861         zinc_(Zintersectfail);
02862         qh_settempfree(&intersect);
02863         return NULL;
02864       }
02865     }
02866   }
02867   trace3((qh ferr, 3007, "qh_neighbor_intersections: %d vertices in neighbor intersection of v%d\n",
02868           qh_setsize(intersect), vertex->id));
02869   return intersect;
02870 } /* neighbor_intersections */
02871 
02872 /*-<a                             href="qh-merge.htm#TOC"
02873   >-------------------------------</a><a name="newvertices">-</a>
02874 
02875   qh_newvertices( vertices )
02876     add vertices to end of qh.vertex_list (marks as new vertices)
02877 
02878   returns:
02879     vertices on qh.newvertex_list
02880     vertex->newlist set
02881 */
02882 void qh_newvertices(setT *vertices) {
02883   vertexT *vertex, **vertexp;
02884 
02885   FOREACHvertex_(vertices) {
02886     if (!vertex->newlist) {
02887       qh_removevertex(vertex);
02888       qh_appendvertex(vertex);
02889     }
02890   }
02891 } /* newvertices */
02892 
02893 /*-<a                             href="qh-merge.htm#TOC"
02894   >-------------------------------</a><a name="reducevertices">-</a>
02895 
02896   qh_reducevertices()
02897     reduce extra vertices, shared vertices, and redundant vertices
02898     facet->newmerge is set if merged since last call
02899     if !qh.MERGEvertices, only removes extra vertices
02900 
02901   returns:
02902     True if also merged degen_redundant facets
02903     vertices are renamed if possible
02904     clears facet->newmerge and vertex->delridge
02905 
02906   notes:
02907     ignored if 2-d
02908 
02909   design:
02910     merge any degenerate or redundant facets
02911     for each newly merged facet
02912       remove extra vertices
02913     if qh.MERGEvertices
02914       for each newly merged facet
02915         for each vertex
02916           if vertex was on a deleted ridge
02917             rename vertex if it is shared
02918       remove delridge flag from new vertices
02919 */
02920 boolT qh_reducevertices(void) {
02921   int numshare=0, numrename= 0;
02922   boolT degenredun= False;
02923   facetT *newfacet;
02924   vertexT *vertex, **vertexp;
02925 
02926   if (qh hull_dim == 2)
02927     return False;
02928   if (qh_merge_degenredundant())
02929     degenredun= True;
02930  LABELrestart:
02931   FORALLnew_facets {
02932     if (newfacet->newmerge) {
02933       if (!qh MERGEvertices)
02934         newfacet->newmerge= False;
02935       qh_remove_extravertices(newfacet);
02936     }
02937   }
02938   if (!qh MERGEvertices)
02939     return False;
02940   FORALLnew_facets {
02941     if (newfacet->newmerge) {
02942       newfacet->newmerge= False;
02943       FOREACHvertex_(newfacet->vertices) {
02944         if (vertex->delridge) {
02945           if (qh_rename_sharedvertex(vertex, newfacet)) {
02946             numshare++;
02947             vertexp--; /* repeat since deleted vertex */
02948           }
02949         }
02950       }
02951     }
02952   }
02953   FORALLvertex_(qh newvertex_list) {
02954     if (vertex->delridge && !vertex->deleted) {
02955       vertex->delridge= False;
02956       if (qh hull_dim >= 4 && qh_redundant_vertex(vertex)) {
02957         numrename++;
02958         if (qh_merge_degenredundant()) {
02959           degenredun= True;
02960           goto LABELrestart;
02961         }
02962       }
02963     }
02964   }
02965   trace1((qh ferr, 1014, "qh_reducevertices: renamed %d shared vertices and %d redundant vertices. Degen? %d\n",
02966           numshare, numrename, degenredun));
02967   return degenredun;
02968 } /* reducevertices */
02969 
02970 /*-<a                             href="qh-merge.htm#TOC"
02971   >-------------------------------</a><a name="redundant_vertex">-</a>
02972 
02973   qh_redundant_vertex( vertex )
02974     detect and rename a redundant vertex
02975     vertices have full vertex->neighbors
02976 
02977   returns:
02978     returns true if find a redundant vertex
02979       deletes vertex(vertex->deleted)
02980 
02981   notes:
02982     only needed if vertex->delridge and hull_dim >= 4
02983     may add degenerate facets to qh.facet_mergeset
02984     doesn't change vertex->neighbors or create redundant facets
02985 
02986   design:
02987     intersect vertices of all facet neighbors of vertex
02988     determine ridges for these vertices
02989     if find a new vertex for vertex amoung these ridges and vertices
02990       rename vertex to the new vertex
02991 */
02992 vertexT *qh_redundant_vertex(vertexT *vertex) {
02993   vertexT *newvertex= NULL;
02994   setT *vertices, *ridges;
02995 
02996   trace3((qh ferr, 3008, "qh_redundant_vertex: check if v%d can be renamed\n", vertex->id));
02997   if ((vertices= qh_neighbor_intersections(vertex))) {
02998     ridges= qh_vertexridges(vertex);
02999     if ((newvertex= qh_find_newvertex(vertex, vertices, ridges)))
03000       qh_renamevertex(vertex, newvertex, ridges, NULL, NULL);
03001     qh_settempfree(&ridges);
03002     qh_settempfree(&vertices);
03003   }
03004   return newvertex;
03005 } /* redundant_vertex */
03006 
03007 /*-<a                             href="qh-merge.htm#TOC"
03008   >-------------------------------</a><a name="remove_extravertices">-</a>
03009 
03010   qh_remove_extravertices( facet )
03011     remove extra vertices from non-simplicial facets
03012 
03013   returns:
03014     returns True if it finds them
03015 
03016   design:
03017     for each vertex in facet
03018       if vertex not in a ridge (i.e., no longer used)
03019         delete vertex from facet
03020         delete facet from vertice's neighbors
03021         unless vertex in another facet
03022           add vertex to qh.del_vertices for later deletion
03023 */
03024 boolT qh_remove_extravertices(facetT *facet) {
03025   ridgeT *ridge, **ridgep;
03026   vertexT *vertex, **vertexp;
03027   boolT foundrem= False;
03028 
03029   trace4((qh ferr, 4043, "qh_remove_extravertices: test f%d for extra vertices\n",
03030           facet->id));
03031   FOREACHvertex_(facet->vertices)
03032     vertex->seen= False;
03033   FOREACHridge_(facet->ridges) {
03034     FOREACHvertex_(ridge->vertices)
03035       vertex->seen= True;
03036   }
03037   FOREACHvertex_(facet->vertices) {
03038     if (!vertex->seen) {
03039       foundrem= True;
03040       zinc_(Zremvertex);
03041       qh_setdelsorted(facet->vertices, vertex);
03042       qh_setdel(vertex->neighbors, facet);
03043       if (!qh_setsize(vertex->neighbors)) {
03044         vertex->deleted= True;
03045         qh_setappend(&qh del_vertices, vertex);
03046         zinc_(Zremvertexdel);
03047         trace2((qh ferr, 2036, "qh_remove_extravertices: v%d deleted because it's lost all ridges\n", vertex->id));
03048       }else
03049         trace3((qh ferr, 3009, "qh_remove_extravertices: v%d removed from f%d because it's lost all ridges\n", vertex->id, facet->id));
03050       vertexp--; /*repeat*/
03051     }
03052   }
03053   return foundrem;
03054 } /* remove_extravertices */
03055 
03056 /*-<a                             href="qh-merge.htm#TOC"
03057   >-------------------------------</a><a name="rename_sharedvertex">-</a>
03058 
03059   qh_rename_sharedvertex( vertex, facet )
03060     detect and rename if shared vertex in facet
03061     vertices have full ->neighbors
03062 
03063   returns:
03064     newvertex or NULL
03065     the vertex may still exist in other facets (i.e., a neighbor was pinched)
03066     does not change facet->neighbors
03067     updates vertex->neighbors
03068 
03069   notes:
03070     a shared vertex for a facet is only in ridges to one neighbor
03071     this may undo a pinched facet
03072 
03073     it does not catch pinches involving multiple facets.  These appear
03074       to be difficult to detect, since an exhaustive search is too expensive.
03075 
03076   design:
03077     if vertex only has two neighbors
03078       determine the ridges that contain the vertex
03079       determine the vertices shared by both neighbors
03080       if can find a new vertex in this set
03081         rename the vertex to the new vertex
03082 */
03083 vertexT *qh_rename_sharedvertex(vertexT *vertex, facetT *facet) {
03084   facetT *neighbor, **neighborp, *neighborA= NULL;
03085   setT *vertices, *ridges;
03086   vertexT *newvertex;
03087 
03088   if (qh_setsize(vertex->neighbors) == 2) {
03089     neighborA= SETfirstt_(vertex->neighbors, facetT);
03090     if (neighborA == facet)
03091       neighborA= SETsecondt_(vertex->neighbors, facetT);
03092   }else if (qh hull_dim == 3)
03093     return NULL;
03094   else {
03095     qh visit_id++;
03096     FOREACHneighbor_(facet)
03097       neighbor->visitid= qh visit_id;
03098     FOREACHneighbor_(vertex) {
03099       if (neighbor->visitid == qh visit_id) {
03100         if (neighborA)
03101           return NULL;
03102         neighborA= neighbor;
03103       }
03104     }
03105     if (!neighborA) {
03106       qh_fprintf(qh ferr, 6101, "qhull internal error (qh_rename_sharedvertex): v%d's neighbors not in f%d\n",
03107         vertex->id, facet->id);
03108       qh_errprint("ERRONEOUS", facet, NULL, NULL, vertex);
03109       qh_errexit(qh_ERRqhull, NULL, NULL);
03110     }
03111   }
03112   /* the vertex is shared by facet and neighborA */
03113   ridges= qh_settemp(qh TEMPsize);
03114   neighborA->visitid= ++qh visit_id;
03115   qh_vertexridges_facet(vertex, facet, &ridges);
03116   trace2((qh ferr, 2037, "qh_rename_sharedvertex: p%d(v%d) is shared by f%d(%d ridges) and f%d\n",
03117     qh_pointid(vertex->point), vertex->id, facet->id, qh_setsize(ridges), neighborA->id));
03118   zinc_(Zintersectnum);
03119   vertices= qh_vertexintersect_new(facet->vertices, neighborA->vertices);
03120   qh_setdel(vertices, vertex);
03121   qh_settemppush(vertices);
03122   if ((newvertex= qh_find_newvertex(vertex, vertices, ridges)))
03123     qh_renamevertex(vertex, newvertex, ridges, facet, neighborA);
03124   qh_settempfree(&vertices);
03125   qh_settempfree(&ridges);
03126   return newvertex;
03127 } /* rename_sharedvertex */
03128 
03129 /*-<a                             href="qh-merge.htm#TOC"
03130   >-------------------------------</a><a name="renameridgevertex">-</a>
03131 
03132   qh_renameridgevertex( ridge, oldvertex, newvertex )
03133     renames oldvertex as newvertex in ridge
03134 
03135   returns:
03136 
03137   design:
03138     delete oldvertex from ridge
03139     if newvertex already in ridge
03140       copy ridge->noconvex to another ridge if possible
03141       delete the ridge
03142     else
03143       insert newvertex into the ridge
03144       adjust the ridge's orientation
03145 */
03146 void qh_renameridgevertex(ridgeT *ridge, vertexT *oldvertex, vertexT *newvertex) {
03147   int nth= 0, oldnth;
03148   facetT *temp;
03149   vertexT *vertex, **vertexp;
03150 
03151   oldnth= qh_setindex(ridge->vertices, oldvertex);
03152   qh_setdelnthsorted(ridge->vertices, oldnth);
03153   FOREACHvertex_(ridge->vertices) {
03154     if (vertex == newvertex) {
03155       zinc_(Zdelridge);
03156       if (ridge->nonconvex) /* only one ridge has nonconvex set */
03157         qh_copynonconvex(ridge);
03158       qh_delridge(ridge);
03159       trace2((qh ferr, 2038, "qh_renameridgevertex: ridge r%d deleted.  It contained both v%d and v%d\n",
03160         ridge->id, oldvertex->id, newvertex->id));
03161       return;
03162     }
03163     if (vertex->id < newvertex->id)
03164       break;
03165     nth++;
03166   }
03167   qh_setaddnth(&ridge->vertices, nth, newvertex);
03168   if (abs(oldnth - nth)%2) {
03169     trace3((qh ferr, 3010, "qh_renameridgevertex: swapped the top and bottom of ridge r%d\n",
03170             ridge->id));
03171     temp= ridge->top;
03172     ridge->top= ridge->bottom;
03173     ridge->bottom= temp;
03174   }
03175 } /* renameridgevertex */
03176 
03177 
03178 /*-<a                             href="qh-merge.htm#TOC"
03179   >-------------------------------</a><a name="renamevertex">-</a>
03180 
03181   qh_renamevertex( oldvertex, newvertex, ridges, oldfacet, neighborA )
03182     renames oldvertex as newvertex in ridges
03183     gives oldfacet/neighborA if oldvertex is shared between two facets
03184 
03185   returns:
03186     oldvertex may still exist afterwards
03187 
03188 
03189   notes:
03190     can not change neighbors of newvertex (since it's a subset)
03191 
03192   design:
03193     for each ridge in ridges
03194       rename oldvertex to newvertex and delete degenerate ridges
03195     if oldfacet not defined
03196       for each neighbor of oldvertex
03197         delete oldvertex from neighbor's vertices
03198         remove extra vertices from neighbor
03199       add oldvertex to qh.del_vertices
03200     else if oldvertex only between oldfacet and neighborA
03201       delete oldvertex from oldfacet and neighborA
03202       add oldvertex to qh.del_vertices
03203     else oldvertex is in oldfacet and neighborA and other facets (i.e., pinched)
03204       delete oldvertex from oldfacet
03205       delete oldfacet from oldvertice's neighbors
03206       remove extra vertices (e.g., oldvertex) from neighborA
03207 */
03208 void qh_renamevertex(vertexT *oldvertex, vertexT *newvertex, setT *ridges, facetT *oldfacet, facetT *neighborA) {
03209   facetT *neighbor, **neighborp;
03210   ridgeT *ridge, **ridgep;
03211   boolT istrace= False;
03212 
03213   if (qh IStracing >= 2 || oldvertex->id == qh tracevertex_id ||
03214         newvertex->id == qh tracevertex_id)
03215     istrace= True;
03216   FOREACHridge_(ridges)
03217     qh_renameridgevertex(ridge, oldvertex, newvertex);
03218   if (!oldfacet) {
03219     zinc_(Zrenameall);
03220     if (istrace)
03221       qh_fprintf(qh ferr, 8082, "qh_renamevertex: renamed v%d to v%d in several facets\n",
03222                oldvertex->id, newvertex->id);
03223     FOREACHneighbor_(oldvertex) {
03224       qh_maydropneighbor(neighbor);
03225       qh_setdelsorted(neighbor->vertices, oldvertex);
03226       if (qh_remove_extravertices(neighbor))
03227         neighborp--; /* neighbor may be deleted */
03228     }
03229     if (!oldvertex->deleted) {
03230       oldvertex->deleted= True;
03231       qh_setappend(&qh del_vertices, oldvertex);
03232     }
03233   }else if (qh_setsize(oldvertex->neighbors) == 2) {
03234     zinc_(Zrenameshare);
03235     if (istrace)
03236       qh_fprintf(qh ferr, 8083, "qh_renamevertex: renamed v%d to v%d in oldfacet f%d\n",
03237                oldvertex->id, newvertex->id, oldfacet->id);
03238     FOREACHneighbor_(oldvertex)
03239       qh_setdelsorted(neighbor->vertices, oldvertex);
03240     oldvertex->deleted= True;
03241     qh_setappend(&qh del_vertices, oldvertex);
03242   }else {
03243     zinc_(Zrenamepinch);
03244     if (istrace || qh IStracing)
03245       qh_fprintf(qh ferr, 8084, "qh_renamevertex: renamed pinched v%d to v%d between f%d and f%d\n",
03246                oldvertex->id, newvertex->id, oldfacet->id, neighborA->id);
03247     qh_setdelsorted(oldfacet->vertices, oldvertex);
03248     qh_setdel(oldvertex->neighbors, oldfacet);
03249     qh_remove_extravertices(neighborA);
03250   }
03251 } /* renamevertex */
03252 
03253 
03254 /*-<a                             href="qh-merge.htm#TOC"
03255   >-------------------------------</a><a name="test_appendmerge">-</a>
03256 
03257   qh_test_appendmerge( facet, neighbor )
03258     tests facet/neighbor for convexity
03259     appends to mergeset if non-convex
03260     if pre-merging,
03261       nop if qh.SKIPconvex, or qh.MERGEexact and coplanar
03262 
03263   returns:
03264     true if appends facet/neighbor to mergeset
03265     sets facet->center as needed
03266     does not change facet->seen
03267 
03268   design:
03269     if qh.cos_max is defined
03270       if the angle between facet normals is too shallow
03271         append an angle-coplanar merge to qh.mergeset
03272         return True
03273     make facet's centrum if needed
03274     if facet's centrum is above the neighbor
03275       set isconcave
03276     else
03277       if facet's centrum is not below the neighbor
03278         set iscoplanar
03279       make neighbor's centrum if needed
03280       if neighbor's centrum is above the facet
03281         set isconcave
03282       else if neighbor's centrum is not below the facet
03283         set iscoplanar
03284    if isconcave or iscoplanar
03285      get angle if needed
03286      append concave or coplanar merge to qh.mergeset
03287 */
03288 boolT qh_test_appendmerge(facetT *facet, facetT *neighbor) {
03289   realT dist, dist2= -REALmax, angle= -REALmax;
03290   boolT isconcave= False, iscoplanar= False, okangle= False;
03291 
03292   if (qh SKIPconvex && !qh POSTmerging)
03293     return False;
03294   if ((!qh MERGEexact || qh POSTmerging) && qh cos_max < REALmax/2) {
03295     angle= qh_getangle(facet->normal, neighbor->normal);
03296     zinc_(Zangletests);
03297     if (angle > qh cos_max) {
03298       zinc_(Zcoplanarangle);
03299       qh_appendmergeset(facet, neighbor, MRGanglecoplanar, &angle);
03300       trace2((qh ferr, 2039, "qh_test_appendmerge: coplanar angle %4.4g between f%d and f%d\n",
03301          angle, facet->id, neighbor->id));
03302       return True;
03303     }else
03304       okangle= True;
03305   }
03306   if (!facet->center)
03307     facet->center= qh_getcentrum(facet);
03308   zzinc_(Zcentrumtests);
03309   qh_distplane(facet->center, neighbor, &dist);
03310   if (dist > qh centrum_radius)
03311     isconcave= True;
03312   else {
03313     if (dist > -qh centrum_radius)
03314       iscoplanar= True;
03315     if (!neighbor->center)
03316       neighbor->center= qh_getcentrum(neighbor);
03317     zzinc_(Zcentrumtests);
03318     qh_distplane(neighbor->center, facet, &dist2);
03319     if (dist2 > qh centrum_radius)
03320       isconcave= True;
03321     else if (!iscoplanar && dist2 > -qh centrum_radius)
03322       iscoplanar= True;
03323   }
03324   if (!isconcave && (!iscoplanar || (qh MERGEexact && !qh POSTmerging)))
03325     return False;
03326   if (!okangle && qh ANGLEmerge) {
03327     angle= qh_getangle(facet->normal, neighbor->normal);
03328     zinc_(Zangletests);
03329   }
03330   if (isconcave) {
03331     zinc_(Zconcaveridge);
03332     if (qh ANGLEmerge)
03333       angle += qh_ANGLEconcave + 0.5;
03334     qh_appendmergeset(facet, neighbor, MRGconcave, &angle);
03335     trace0((qh ferr, 18, "qh_test_appendmerge: concave f%d to f%d dist %4.4g and reverse dist %4.4g angle %4.4g during p%d\n",
03336            facet->id, neighbor->id, dist, dist2, angle, qh furthest_id));
03337   }else /* iscoplanar */ {
03338     zinc_(Zcoplanarcentrum);
03339     qh_appendmergeset(facet, neighbor, MRGcoplanar, &angle);
03340     trace2((qh ferr, 2040, "qh_test_appendmerge: coplanar f%d to f%d dist %4.4g, reverse dist %4.4g angle %4.4g\n",
03341               facet->id, neighbor->id, dist, dist2, angle));
03342   }
03343   return True;
03344 } /* test_appendmerge */
03345 
03346 /*-<a                             href="qh-merge.htm#TOC"
03347   >-------------------------------</a><a name="test_vneighbors">-</a>
03348 
03349   qh_test_vneighbors()
03350     test vertex neighbors for convexity
03351     tests all facets on qh.newfacet_list
03352 
03353   returns:
03354     true if non-convex vneighbors appended to qh.facet_mergeset
03355     initializes vertex neighbors if needed
03356 
03357   notes:
03358     assumes all facet neighbors have been tested
03359     this can be expensive
03360     this does not guarantee that a centrum is below all facets
03361       but it is unlikely
03362     uses qh.visit_id
03363 
03364   design:
03365     build vertex neighbors if necessary
03366     for all new facets
03367       for all vertices
03368         for each unvisited facet neighbor of the vertex
03369           test new facet and neighbor for convexity
03370 */
03371 boolT qh_test_vneighbors(void /* qh newfacet_list */) {
03372   facetT *newfacet, *neighbor, **neighborp;
03373   vertexT *vertex, **vertexp;
03374   int nummerges= 0;
03375 
03376   trace1((qh ferr, 1015, "qh_test_vneighbors: testing vertex neighbors for convexity\n"));
03377   if (!qh VERTEXneighbors)
03378     qh_vertexneighbors();
03379   FORALLnew_facets
03380     newfacet->seen= False;
03381   FORALLnew_facets {
03382     newfacet->seen= True;
03383     newfacet->visitid= qh visit_id++;
03384     FOREACHneighbor_(newfacet)
03385       newfacet->visitid= qh visit_id;
03386     FOREACHvertex_(newfacet->vertices) {
03387       FOREACHneighbor_(vertex) {
03388         if (neighbor->seen || neighbor->visitid == qh visit_id)
03389           continue;
03390         if (qh_test_appendmerge(newfacet, neighbor))
03391           nummerges++;
03392       }
03393     }
03394   }
03395   zadd_(Ztestvneighbor, nummerges);
03396   trace1((qh ferr, 1016, "qh_test_vneighbors: found %d non-convex, vertex neighbors\n",
03397            nummerges));
03398   return (nummerges > 0);
03399 } /* test_vneighbors */
03400 
03401 /*-<a                             href="qh-merge.htm#TOC"
03402   >-------------------------------</a><a name="tracemerge">-</a>
03403 
03404   qh_tracemerge( facet1, facet2 )
03405     print trace message after merge
03406 */
03407 void qh_tracemerge(facetT *facet1, facetT *facet2) {
03408   boolT waserror= False;
03409 
03410 #ifndef qh_NOtrace
03411   if (qh IStracing >= 4)
03412     qh_errprint("MERGED", facet2, NULL, NULL, NULL);
03413   if (facet2 == qh tracefacet || (qh tracevertex && qh tracevertex->newlist)) {
03414     qh_fprintf(qh ferr, 8085, "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);
03415     if (facet2 != qh tracefacet)
03416       qh_errprint("TRACE", qh tracefacet,
03417         (qh tracevertex && qh tracevertex->neighbors) ?
03418            SETfirstt_(qh tracevertex->neighbors, facetT) : NULL,
03419         NULL, qh tracevertex);
03420   }
03421   if (qh tracevertex) {
03422     if (qh tracevertex->deleted)
03423       qh_fprintf(qh ferr, 8086, "qh_tracemerge: trace vertex deleted at furthest p%d\n",
03424             qh furthest_id);
03425     else
03426       qh_checkvertex(qh tracevertex);
03427   }
03428   if (qh tracefacet) {
03429     qh_checkfacet(qh tracefacet, True, &waserror);
03430     if (waserror)
03431       qh_errexit(qh_ERRqhull, qh tracefacet, NULL);
03432   }
03433 #endif /* !qh_NOtrace */
03434   if (qh CHECKfrequently || qh IStracing >= 4) { /* can't check polygon here */
03435     qh_checkfacet(facet2, True, &waserror);
03436     if (waserror)
03437       qh_errexit(qh_ERRqhull, NULL, NULL);
03438   }
03439 } /* tracemerge */
03440 
03441 /*-<a                             href="qh-merge.htm#TOC"
03442   >-------------------------------</a><a name="tracemerging">-</a>
03443 
03444   qh_tracemerging()
03445     print trace message during POSTmerging
03446 
03447   returns:
03448     updates qh.mergereport
03449 
03450   notes:
03451     called from qh_mergecycle() and qh_mergefacet()
03452 
03453   see:
03454     qh_buildtracing()
03455 */
03456 void qh_tracemerging(void) {
03457   realT cpu;
03458   int total;
03459   time_t timedata;
03460   struct tm *tp;
03461 
03462   qh mergereport= zzval_(Ztotmerge);
03463   time(&timedata);
03464   tp= localtime(&timedata);
03465   cpu= qh_CPUclock;
03466   cpu /= qh_SECticks;
03467   total= zzval_(Ztotmerge) - zzval_(Zcyclehorizon) + zzval_(Zcyclefacettot);
03468   qh_fprintf(qh ferr, 8087, "\n\
03469 At %d:%d:%d & %2.5g CPU secs, qhull has merged %d facets.  The hull\n\
03470   contains %d facets and %d vertices.\n",
03471       tp->tm_hour, tp->tm_min, tp->tm_sec, cpu,
03472       total, qh num_facets - qh num_visible,
03473       qh num_vertices-qh_setsize(qh del_vertices));
03474 } /* tracemerging */
03475 
03476 /*-<a                             href="qh-merge.htm#TOC"
03477   >-------------------------------</a><a name="updatetested">-</a>
03478 
03479   qh_updatetested( facet1, facet2 )
03480     clear facet2->tested and facet1->ridge->tested for merge
03481 
03482   returns:
03483     deletes facet2->center unless it's already large
03484       if so, clears facet2->ridge->tested
03485 
03486   design:
03487     clear facet2->tested
03488     clear ridge->tested for facet1's ridges
03489     if facet2 has a centrum
03490       if facet2 is large
03491         set facet2->keepcentrum
03492       else if facet2 has 3 vertices due to many merges, or not large and post merging
03493         clear facet2->keepcentrum
03494       unless facet2->keepcentrum
03495         clear facet2->center to recompute centrum later
03496         clear ridge->tested for facet2's ridges
03497 */
03498 void qh_updatetested(facetT *facet1, facetT *facet2) {
03499   ridgeT *ridge, **ridgep;
03500   int size;
03501 
03502   facet2->tested= False;
03503   FOREACHridge_(facet1->ridges)
03504     ridge->tested= False;
03505   if (!facet2->center)
03506     return;
03507   size= qh_setsize(facet2->vertices);
03508   if (!facet2->keepcentrum) {
03509     if (size > qh hull_dim + qh_MAXnewcentrum) {
03510       facet2->keepcentrum= True;
03511       zinc_(Zwidevertices);
03512     }
03513   }else if (size <= qh hull_dim + qh_MAXnewcentrum) {
03514     /* center and keepcentrum was set */
03515     if (size == qh hull_dim || qh POSTmerging)
03516       facet2->keepcentrum= False; /* if many merges need to recompute centrum */
03517   }
03518   if (!facet2->keepcentrum) {
03519     qh_memfree(facet2->center, qh normal_size);
03520     facet2->center= NULL;
03521     FOREACHridge_(facet2->ridges)
03522       ridge->tested= False;
03523   }
03524 } /* updatetested */
03525 
03526 /*-<a                             href="qh-merge.htm#TOC"
03527   >-------------------------------</a><a name="vertexridges">-</a>
03528 
03529   qh_vertexridges( vertex )
03530     return temporary set of ridges adjacent to a vertex
03531     vertex->neighbors defined
03532 
03533   ntoes:
03534     uses qh.visit_id
03535     does not include implicit ridges for simplicial facets
03536 
03537   design:
03538     for each neighbor of vertex
03539       add ridges that include the vertex to ridges
03540 */
03541 setT *qh_vertexridges(vertexT *vertex) {
03542   facetT *neighbor, **neighborp;
03543   setT *ridges= qh_settemp(qh TEMPsize);
03544   int size;
03545 
03546   qh visit_id++;
03547   FOREACHneighbor_(vertex)
03548     neighbor->visitid= qh visit_id;
03549   FOREACHneighbor_(vertex) {
03550     if (*neighborp)   /* no new ridges in last neighbor */
03551       qh_vertexridges_facet(vertex, neighbor, &ridges);
03552   }
03553   if (qh PRINTstatistics || qh IStracing) {
03554     size= qh_setsize(ridges);
03555     zinc_(Zvertexridge);
03556     zadd_(Zvertexridgetot, size);
03557     zmax_(Zvertexridgemax, size);
03558     trace3((qh ferr, 3011, "qh_vertexridges: found %d ridges for v%d\n",
03559              size, vertex->id));
03560   }
03561   return ridges;
03562 } /* vertexridges */
03563 
03564 /*-<a                             href="qh-merge.htm#TOC"
03565   >-------------------------------</a><a name="vertexridges_facet">-</a>
03566 
03567   qh_vertexridges_facet( vertex, facet, ridges )
03568     add adjacent ridges for vertex in facet
03569     neighbor->visitid==qh.visit_id if it hasn't been visited
03570 
03571   returns:
03572     ridges updated
03573     sets facet->visitid to qh.visit_id-1
03574 
03575   design:
03576     for each ridge of facet
03577       if ridge of visited neighbor (i.e., unprocessed)
03578         if vertex in ridge
03579           append ridge to vertex
03580     mark facet processed
03581 */
03582 void qh_vertexridges_facet(vertexT *vertex, facetT *facet, setT **ridges) {
03583   ridgeT *ridge, **ridgep;
03584   facetT *neighbor;
03585 
03586   FOREACHridge_(facet->ridges) {
03587     neighbor= otherfacet_(ridge, facet);
03588     if (neighbor->visitid == qh visit_id
03589     && qh_setin(ridge->vertices, vertex))
03590       qh_setappend(ridges, ridge);
03591   }
03592   facet->visitid= qh visit_id-1;
03593 } /* vertexridges_facet */
03594 
03595 /*-<a                             href="qh-merge.htm#TOC"
03596   >-------------------------------</a><a name="willdelete">-</a>
03597 
03598   qh_willdelete( facet, replace )
03599     moves facet to visible list
03600     sets facet->f.replace to replace (may be NULL)
03601 
03602   returns:
03603     bumps qh.num_visible
03604 */
03605 void qh_willdelete(facetT *facet, facetT *replace) {
03606 
03607   qh_removefacet(facet);
03608   qh_prependfacet(facet, &qh visible_list);
03609   qh num_visible++;
03610   facet->visible= True;
03611   facet->f.replace= replace;
03612 } /* willdelete */
03613 
03614 #else /* qh_NOmerge */
03615 void qh_premerge(vertexT *apex, realT maxcentrum, realT maxangle) {
03616 }
03617 void qh_postmerge(const char *reason, realT maxcentrum, realT maxangle,
03618                       boolT vneighbors) {
03619 }
03620 boolT qh_checkzero(boolT testall) {
03621    }
03622 #endif /* qh_NOmerge */
03623 


libqhull-ours
Author(s): Robert Krug
autogenerated on Mon Jan 6 2014 11:32:10