}      vertex= SETelem_(facet->vertices, neighbor_i++);      vertex->visitid= qh vertex_visit;      zzinc_(Zdistzero);      qh_distplane (vertex->point, neighbor, &dist);      if (dist >= -qh DISTround) {        qh ZEROall_ok= False;        if (!qh MERGEexact || testall || dist > qh DISTround)          goto LABELnonconvex;      }    }    if (!testall) {      FOREACHvertex_(horizon->vertices) {	if (vertex->visitid != qh vertex_visit) {	  zzinc_(Zdistzero);	  qh_distplane (vertex->point, facet, &dist);	  if (dist >= -qh DISTround) {	    qh ZEROall_ok= False;	    if (!qh MERGEexact || dist > qh DISTround)	      goto LABELnonconvex;	  }	  break;	}      }    }  }  trace2((qh ferr, "qh_checkzero: facets are %s\n",        (qh MERGEexact && !testall) ?            "not concave, flipped, or duplicate ridged" : "clearly convex"));  return True; LABELproblem:  qh ZEROall_ok= False;  trace2((qh ferr, "qh_checkzero: facet f%d needs pre-merging\n",       facet->id));  return False; LABELnonconvex:  trace2((qh ferr, "qh_checkzero: facet f%d and f%d are not clearly convex.  v%d dist %.2g\n",         facet->id, neighbor->id, vertex->id, dist));  return False;} /* checkzero *//*--------------------------------------------------compareangle- used by qsort() to order merges by angle*/static int qh_compareangle(const void *p1, const void *p2) {  mergeT *a= *((mergeT **)p1), *b= *((mergeT **)p2);   return ((a->angle > b->angle) ? 1 : -1);} /* compareangle *//*--------------------------------------------------comparemerge- used by qsort() to order merges by type of merge*/static int qh_comparemerge(const void *p1, const void *p2) {  mergeT *a= *((mergeT **)p1), *b= *((mergeT **)p2);   return (a->type - b->type);} /* comparemerge *//*--------------------------------------------------comparevisit- used by qsort() to order vertices by their visitid*/static int qh_comparevisit (const void *p1, const void *p2) {  vertexT *a= *((vertexT **)p1), *b= *((vertexT **)p2);   return (a->visitid - b->visitid);} /* comparevisit *//*-------------------------------------------------copynonconvex- set non-convex flag on another ridge (if any) between same neighbors  may be faster if use smaller ridge set*/void qh_copynonconvex (ridgeT *atridge) {  facetT *facet, *otherfacet;  ridgeT *ridge, **ridgep;  facet= atridge->top;  otherfacet= atridge->bottom;  FOREACHridge_(facet->ridges) {    if (otherfacet == otherfacet_(ridge, facet) && ridge != atridge) {      ridge->nonconvex= True;      trace4((qh ferr, "qh_copynonconvex: moved nonconvex flag from r%d to r%d\n",	      atridge->id, ridge->id));      break;    }  }} /* copynonconvex *//*-------------------------------------------------degen_redundant_facet- check facet for degen. or redundancy  bumps vertex_visit  called if a facet was redundant by no longer is (qh_merge_degenredundant)returns:  appendmergeset() only appends first reference to facet (i.e., redundant)notes:  see  degen_redundant_neighbors*/void qh_degen_redundant_facet (facetT *facet) {  vertexT *vertex, **vertexp;  facetT *neighbor, **neighborp;  trace4((qh ferr, "qh_degen_redundant_facet: test facet f%d for degen/redundant\n",	  facet->id));  FOREACHneighbor_(facet) {    qh vertex_visit++;    FOREACHvertex_(neighbor->vertices)      vertex->visitid= qh vertex_visit;    FOREACHvertex_(facet->vertices) {      if (vertex->visitid != qh vertex_visit)	break;    }    if (!vertex) {      qh_appendmergeset (facet, neighbor, MRGredundant, NULL);      trace2((qh ferr, "qh_degen_redundant_facet: f%d is contained in f%d.  merge\n", facet->id, neighbor->id));       return;    }  }  if (qh_setsize (facet->neighbors) < qh hull_dim) {    qh_appendmergeset (facet, facet, MRGdegen, NULL);    trace2((qh ferr, "qh_degen_redundant_neighbors: f%d is degenerate.\n", facet->id));  }} /* degen_redundant_facet *//*-------------------------------------------------degen_redundant_neighbors- append degen. and redundant neighbors to facet_mergeset  also checks current facet for degeneracy  bumps vertex_visit  called for each mergefacet() and mergecycle()    merge and statistics occur in merge_nonconvex  if delfacet, only checks neighbors of delfacetreturns:  appendmergeset() only appends first reference to facet (i.e., redundant)  it appends redundant facets after degenerate onesnotes:  a degenerate facet has fewer than hull_dim neighbors  a redundant facet's vertices is a subset of its neighbor's vertices  tests for redundant merges first (appendmergeset is nop for others)  in a merge, only needs to test neighbors of merged facet  see qh_merge_degenredundant() and qh_degen_redundant_facet*/void qh_degen_redundant_neighbors (facetT *facet, facetT *delfacet) {  vertexT *vertex, **vertexp;  facetT *neighbor, **neighborp;  int size;  trace4((qh ferr, "qh_degen_redundant_neighbors: test neighbors of f%d with delfacet f%d\n", 	  facet->id, getid_(delfacet)));  if ((size= qh_setsize (facet->neighbors)) < qh hull_dim) {    qh_appendmergeset (facet, facet, MRGdegen, NULL);    trace2((qh ferr, "qh_degen_redundant_neighbors: f%d is degenerate.\n", facet->id));  }  if (!delfacet)    delfacet= facet;  qh vertex_visit++;  FOREACHvertex_(facet->vertices)    vertex->visitid= qh vertex_visit;  FOREACHneighbor_(delfacet) {    /* uses early out instead of checking vertex count */    if (neighbor == facet)      continue;    FOREACHvertex_(neighbor->vertices) {      if (vertex->visitid != qh vertex_visit)        break;    }    if (!vertex) {      qh_appendmergeset (neighbor, facet, MRGredundant, NULL);      trace2((qh ferr, "qh_degen_redundant_neighbors: f%d is contained in f%d.  merge\n", neighbor->id, facet->id));     }  }  FOREACHneighbor_(delfacet) {   /* redundant merges occur first */    if (neighbor == facet)      continue;    if ((size= qh_setsize (neighbor->neighbors)) < qh hull_dim) {      qh_appendmergeset (neighbor, neighbor, MRGdegen, NULL);      trace2((qh ferr, "qh_degen_redundant_neighbors: f%d is degenerate.  Neighbor of f%d.\n", neighbor->id, facet->id));     }  }} /* degen_redundant_neighbors *//*------------------------------------------find_newvertex - locate new vertex for renaming old vertex  each ridge includes oldvertex  vertices consists of possible new verticesreturns:  newvertex or NULL  vertices sorted by number of deleted ridgesnotes:  new vertex is in one of the ridges  renaming will not cause a duplicate ridge  renaming will minimize the number of deleted ridges  newvertex may not be adjacent in the dual (though unlikely)*/vertexT *qh_find_newvertex (vertexT *oldvertex, setT *vertices, setT *ridges) {  vertexT *vertex, **vertexp;  setT *newridges;  ridgeT *ridge, **ridgep, *dupridge;  int size, hashsize;  int hash;#ifndef qh_NOtrace  if (qh IStracing >= 4) {    fprintf (qh ferr, "qh_find_newvertex: find new vertex for v%d from ",	     oldvertex->id);    FOREACHvertex_(vertices)       fprintf (qh ferr, "v%d ", vertex->id);    FOREACHridge_(ridges)      fprintf (qh ferr, "r%d ", ridge->id);    fprintf (qh ferr, "\n");  }#endif  FOREACHvertex_(vertices)     vertex->visitid= 0;  FOREACHridge_(ridges) {    FOREACHvertex_(ridge->vertices)       vertex->visitid++;  }  FOREACHvertex_(vertices) {    if (!vertex->visitid) {      qh_setdelnth (vertices, SETindex_(vertices,vertex));      vertexp--; /* repeat since deleted this vertex */    }  }  qh vertex_visit += qh_setsize (ridges);  if (!qh_setsize (vertices)) {    trace4((qh ferr, "qh_find_newvertex: vertices not in ridges for v%d\n",	    oldvertex->id));    return NULL;  }  qsort (SETaddr_(vertices, vertexT), qh_setsize (vertices),	        sizeof (vertexT *), qh_comparevisit);  /* can now use qh vertex_visit */  if (qh PRINTstatistics) {    size= qh_setsize (vertices);    zinc_(Zintersect);    zadd_(Zintersecttot, size);    zmax_(Zintersectmax, size);  }  hashsize= qh_newhashtable (qh_setsize (ridges));  FOREACHridge_(ridges)    qh_hashridge (qh hash_table, hashsize, ridge, oldvertex);  FOREACHvertex_(vertices) {    newridges= qh_vertexridges (vertex);    FOREACHridge_(newridges) {      if ((dupridge= qh_hashridge_find (qh hash_table, hashsize, ridge, vertex, oldvertex, &hash))) {	zinc_(Zdupridge);	break;      }    }    qh_settempfree (&newridges);    if (!ridge)      break;  /* found a rename */  }  if (vertex) {    /* counted in qh_renamevertex */    trace2((qh ferr, "qh_find_newvertex: found v%d for old v%d from %d vertices and %d ridges.\n",      vertex->id, oldvertex->id, qh_setsize (vertices), qh_setsize (ridges)));  }else {    zinc_(Zfindfail);    trace0((qh ferr, "qh_find_newvertex: no vertex for renaming v%d (all duplicated ridges) during p%d\n",      oldvertex->id, qh furthest_id));  }  qh_setfree (&qh hash_table);  return vertex;} /* find_newvertex *//*--------------------------------------------------findbest_test- test neighbor for findbestneighbor()  either test centrum or vertices  if testcentrum, assumes ->center is defined*/void qh_findbest_test (boolT testcentrum, facetT *facet, facetT *neighbor,      facetT **bestfacet, realT *distp, realT *mindistp, realT *maxdistp) {  realT dist, mindist, maxdist;  if (testcentrum) {    zzinc_(Zbestdist);    qh_distplane(facet->center, neighbor, &dist);    dist *= qh hull_dim; /* estimate furthest vertex */    if (dist < 0) {      maxdist= 0;      mindist= dist;      dist= -dist;    }else      maxdist= dist;  }else    dist= qh_getdistance (facet, neighbor, &mindist, &maxdist);  if (dist < *distp) {    *bestfacet= neighbor;    *mindistp= mindist;    *maxdistp= maxdist;    *distp= dist;  }} /* findbest_test *//*--------------------------------------------------findbestneighbor- finds best neighbor (least dist) of a facet for merging  returns min and max distances and their max absolute value  avoids merging old into new  assumes ridge->nonconvex only set on one ridge between a pair of facetsnotes:  could use an early out predicate but not worth it*/facetT *qh_findbestneighbor(facetT *facet, realT *distp, realT *mindistp, realT *maxdistp) {  facetT *neighbor, **neighborp, *bestfacet= NULL;  ridgeT *ridge, **ridgep;  boolT nonconvex= True, testcentrum= False;  int size= qh_setsize (facet->vertices);  realT dist;     *distp= REALmax;  if (size > qh_BESTcentrum2 * qh hull_dim + qh_BESTcentrum) {    testcentrum= True;    zinc_(Zbestcentrum);    if (!facet->center)       facet->center= qh_getcentrum (facet);  }  if (size > qh hull_dim + qh_BESTnonconvex) {    FOREACHridge_(facet->ridges) {      if (ridge->nonconvex) {        neighbor= otherfacet_(ridge, facet);	qh_findbest_test (testcentrum, facet, neighbor,			  &bestfacet, distp, mindistp, maxdistp);      }    }  }  if (!bestfacet) {         nonconvex= False;    FOREACHneighbor_(facet)      qh_findbest_test (testcentrum, facet, neighbor,			&bestfacet, distp, mindistp, maxdistp);  }  if (!bestfacet) {    fprintf (qh ferr, "qhull internal error (qh_findbestneighbor): no neighbors for f%d\n", facet->id);        qh_errexit (qh_ERRqhull, facet, NULL);  }  if (testcentrum)     dist= qh_getdistance (facet, bestfacet, mindistp, maxdistp);  trace3((qh ferr, "qh_findbestneighbor: f%d is best neighbor for f%d testcentrum? %d nonconvex? %d dist %2.2g min %2.2g max %2.2g\n",     bestfacet->id, facet->id, testcentrum, nonconvex, *distp, *mindistp, *maxdistp));  return(bestfacet);} /* findbestneighbor *//*--------------------------------------------------flippedmerges- merge flipped facets into best neighbor  assumes facet_mergeset at qh_settemppop()returns:  no flipped facets on facetlist    sets wasmerge if merge  degen/redundant merges passed throughnotes:  othermerges not needed since facet_mergeset is empty before & after    keep it in case of change*/void qh_flippedmerges(facetT *facetlist, boolT *wasmerge) {  facetT *facet, *neighbor, *facet1;  realT dist, mindist, maxdist;  mergeT *merge, **mergep;  setT *othermerges;  int nummerge=0;  trace4((qh ferr, "qh_flippedmerges: begin\n"));  FORALLfacet_(facetlist) {    if (facet->flipped && !facet->visible)       qh_appendmergeset (facet, facet, MRGflip, NULL);  }  othermerges= qh_settemppop(); /* was facet_mergeset */  qh facet_mergeset= qh_settemp (qh TEMPsize);  qh_settemppush (othermerges);  FOREACHmerge_(othermerges) {    facet1= merge->facet1;    if (merge->type != MRGflip || facet1->visible)       continue;    if (qh TRACEmerge-1 == zzval_(Ztotmerge))      qhmem.IStracing= qh IStracing= qh TRACElevel;    neighbor= qh_findbestneighbor (facet1, &dist, &mindist, &maxdist);