merge.c

这是一个新的用于图像处理的工具箱

      }
      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 delfacet
returns:
  appendmergeset() only appends first reference to facet (i.e., redundant)
  it appends redundant facets after degenerate ones
notes:
  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 vertices
returns:
  newvertex or NULL
  vertices sorted by number of deleted ridges
notes:
  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 facets
notes:
  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 through
notes:
  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);