merge.c

关于网格剖分的

      if (vertex->visitid != qh vertex_visit) {
        qh_setappend (&vertices, vertex);
        vertex->visitid= qh vertex_visit;
        vertex->seen= False;
      }
    }
  }
  trace4((qh ferr, "qh_basevertices: found %d vertices\n", 
         qh_setsize (vertices)));
  return vertices;
} /* basevertices */

/*-<a                             href="qh-c.htm#merge"
  >-------------------------------</a><a name="checkconnect">-</a>
  
  qh_checkconnect()
    check that new facets are connected
    new facets are on qh.newfacet_list
    
  notes:
    this is slow and it changes the order of the facets
    uses qh.visit_id

  design:
    move first new facet to end of qh.facet_list
    for all newly appended facets
      append unvisited neighbors to end of qh.facet_list
    for all new facets
      report error if unvisited
*/
void qh_checkconnect (void /* qh newfacet_list */) {
  facetT *facet, *newfacet, *errfacet= NULL, *neighbor, **neighborp;

  facet= qh newfacet_list;
  qh_removefacet (facet);
  qh_appendfacet (facet);
  facet->visitid= ++qh visit_id;
  FORALLfacet_(facet) {
    FOREACHneighbor_(facet) {
      if (neighbor->visitid != qh visit_id) {
        qh_removefacet (neighbor);
        qh_appendfacet (neighbor);
        neighbor->visitid= qh visit_id;
      }
    }
  }
  FORALLnew_facets {
    if (newfacet->visitid == qh visit_id)
      break;
    fprintf(qh ferr, "qhull error: f%d is not attached to the new facets\n",
         newfacet->id);
    errfacet= newfacet;
  }
  if (errfacet)
    qh_errexit (qh_ERRqhull, errfacet, NULL);
} /* checkconnect */

/*-<a                             href="qh-c.htm#merge"
  >-------------------------------</a><a name="checkzero">-</a>
  
  qh_checkzero( testall )
    check that facets are clearly convex for qh.DISTround with qh.MERGEexact

    if testall, 
      test all facets for qh.MERGEexact post-merging
    else 
      test qh.newfacet_list
      
    if qh.MERGEexact, 
      allows coplanar ridges
      skips convexity test while qh.ZEROall_ok

  returns:
    True if all facets !flipped, !dupridge, normal
         if all horizon facets are simplicial
         if all vertices are clearly below neighbor
         if all opposite vertices of horizon are below 
    clears qh.ZEROall_ok if any problems or coplanar facets

  notes:
    uses qh.vertex_visit
    horizon facets may define multiple new facets

  design:
    for all facets in qh.newfacet_list or qh.facet_list
      check for flagged faults (flipped, etc.)
    for all facets in qh.newfacet_list or qh.facet_list
      for each neighbor of facet
        skip horizon facets for qh.newfacet_list
        test the opposite vertex
      if qh.newfacet_list
        test the other vertices in the facet's horizon facet
*/
boolT qh_checkzero (boolT testall) {
  facetT *facet, *neighbor, **neighborp;
  facetT *horizon, *facetlist;
  int neighbor_i;
  vertexT *vertex, **vertexp;
  realT dist;

  if (testall) 
    facetlist= qh facet_list;
  else {
    facetlist= qh newfacet_list;
    FORALLfacet_(facetlist) {
      horizon= SETfirstt_(facet->neighbors, facetT);
      if (!horizon->simplicial)
        goto LABELproblem;
      if (facet->flipped || facet->dupridge || !facet->normal)
        goto LABELproblem;
    }
    if (qh MERGEexact && qh ZEROall_ok) {
      trace2((qh ferr, "qh_checkzero: skip convexity check until first pre-merge\n"));
      return True;
    }
  }
  FORALLfacet_(facetlist) {
    qh vertex_visit++;
    neighbor_i= 0;
    horizon= NULL;
    FOREACHneighbor_(facet) {
      if (!neighbor_i && !testall) {
        horizon= neighbor;
	neighbor_i++;
        continue; /* horizon facet tested in qh_findhorizon */
      }
      vertex= SETelemt_(facet->vertices, neighbor_i++, vertexT);
      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: testall %d, facets are %s\n", testall,
        (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 */

/*-<a                             href="qh-c.htm#merge"
  >-------------------------------</a><a name="compareangle">-</a>
  
  qh_compareangle( angle1, angle2 )
    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 */

/*-<a                             href="qh-c.htm#merge"
  >-------------------------------</a><a name="comparemerge">-</a>
  
  qh_comparemerge( merge1, merge2 )
    used by qsort() to order merges
*/
static int qh_comparemerge(const void *p1, const void *p2) {
  mergeT *a= *((mergeT **)p1), *b= *((mergeT **)p2);
 
  return (a->type - b->type);
} /* comparemerge */

/*-<a                             href="qh-c.htm#merge"
  >-------------------------------</a><a name="comparevisit">-</a>
  
  qh_comparevisit( vertex1, vertex2 )
    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 */

/*-<a                             href="qh-c.htm#merge"
  >-------------------------------</a><a name="copynonconvex">-</a>
  
  qh_copynonconvex( atridge )
    set non-convex flag on other ridges (if any) between same neighbors

  notes:
    may be faster if use smaller ridge set

  design:
    for each ridge of atridge's top facet
      if ridge shares the same neighbor
        set nonconvex flag
*/
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 */

/*-<a                             href="qh-c.htm#merge"
  >-------------------------------</a><a name="degen_redundant_facet">-</a>
  
  qh_degen_redundant_facet( facet )
    check facet for degen. or redundancy

  notes:
    bumps vertex_visit
    called if a facet was redundant but no longer is (qh_merge_degenredundant)
    qh_appendmergeset() only appends first reference to facet (i.e., redundant)

  see:
    qh_degen_redundant_neighbors()

  design:
    test for redundant neighbor
    test for degenerate facet
*/
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 */


/*-<a                             href="qh-c.htm#merge"
  >-------------------------------</a><a name="degen_redundant_neighbors">-</a>
  
  qh_degen_redundant_neighbors( facet, delfacet,  )
    append degenerate and redundant neighbors to facet_mergeset
    if delfacet, 
      only checks neighbors of both delfacet and facet
    also checks current facet for degeneracy

  notes:
    bumps vertex_visit
    called for each qh_mergefacet() and qh_mergecycle()
    merge and statistics occur in merge_nonconvex
    qh_appendmergeset() only appends first reference to facet (i.e., redundant)
      it appends redundant facets after degenerate ones

    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()

  design:
    test for degenerate facet
    test for redundant neighbor
    test for degenerate neighbor
*/
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 with %d neighbors.\n", facet->id, size));
  }
  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 with %d neighbors.  Neighbor of f%d.\n", neighbor->id, size, facet->id)); 
    }
  }
} /* degen_redundant_neighbors */


/*-<a                             href="qh-c.htm#merge"
  >-------------------------------</a><a name="find_newvertex">-</a>
  
  qh_find_newvertex( oldvertex, vertices, ridges )
    locate new vertex for renaming old vertex
    vertices is a set of possible new vertices
      vertices sorted by number of deleted ridges

  returns:
    newvertex or NULL
      each ridge includes both vertex and oldvertex
    vertices sorted by number of deleted ridges
      
  notes:
    modifies vertex->visitid
    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)

  design:
    for each vertex in vertices
      set vertex->visitid to number of references in ridges
    remove unvisited vertices 
    set qh.vertex_visit above all possible values
    sort vertices by number of references in ridges
    add each ridge to qh.hash_table
    for each vertex in vertices
      look for a vertex that would not cause a duplicate ridge after a rename
*/
vertexT *qh_find_newvertex (vertexT *oldvertex, setT *vertices, setT *ridges) {
  vertexT *vertex, **vertexp;
  setT *newridges;
  ridgeT *ridge, **ridgep;
  int size, hashsize;
  int hash;