merge.c

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

  ridgeT *ridge, **ridgep;

  samevisitid= ++qh visit_id;
  FORALLsame_cycle_(samecycle) {
    if (same->visitid == samevisitid || same->visible)
      qh_infiniteloop (samecycle);
    same->visitid= samevisitid;
  }
  newfacet->visitid= ++qh visit_id;
  trace4((qh ferr, "qh_mergecycle_neighbors: delete shared neighbors from newfacet\n"));  
  FOREACHneighbor_(newfacet) {
    if (neighbor->visitid == samevisitid) {
      SETref_(neighbor)= NULL;  /* samecycle neighbors deleted */
      delneighbors++;
    }else
      neighbor->visitid= qh visit_id;
  }
  qh_setcompact (newfacet->neighbors);

  trace4((qh ferr, "qh_mergecycle_neighbors: update neighbors\n"));  
  FORALLsame_cycle_(samecycle) {
    FOREACHneighbor_(same) {
      if (neighbor->visitid == samevisitid)
	continue;
      if (neighbor->simplicial) {
	if (neighbor->visitid != qh visit_id) {
	  qh_setappend (&newfacet->neighbors, neighbor);
	  qh_setreplace (neighbor->neighbors, same, newfacet);
	  newneighbors++;
	  neighbor->visitid= qh visit_id;
	  FOREACHridge_(neighbor->ridges) { /* update ridge in case of qh_makeridges */
	    if (ridge->top == same) {
	      ridge->top= newfacet;
	      break;
	    }else if (ridge->bottom == same) {
	      ridge->bottom= newfacet;
	      break;
	    }
	  }
	}else {
	  qh_makeridges (neighbor);
	  qh_setdel (neighbor->neighbors, same);
	  /* same can't be horizon facet for neighbor */
	}
      }else { /* non-simplicial neighbor */
        qh_setdel (neighbor->neighbors, same);
        if (neighbor->visitid != qh visit_id) {
          qh_setappend (&neighbor->neighbors, newfacet);
          qh_setappend (&newfacet->neighbors, neighbor);
          neighbor->visitid= qh visit_id;
          newneighbors++;
        } 
      }
    }
  }
  trace2((qh ferr, "qh_mergecycle_neighbors: deleted %d neighbors and added %d\n", 
             delneighbors, newneighbors));
} /* mergecycle_neighbors */

/*-------------------------------------------------
-mergecycle_ridges- add ridges/neighbors for ->f.samecycle to newfacet
  all new/old neighbors of newfacet marked with qh visit_id
    cycle marked with qh visit_id-1
    newfacet marked with qh visit_id
  newfacet has ridges
  ridge already updated for simplicial neighbors of samecycle with a ridge
returns:
  newfacet has merged ridges
notes:
  similar to mergeridges, and makeridges
*/
void qh_mergecycle_ridges(facetT *samecycle, facetT *newfacet) {
  facetT *same, *neighbor= NULL;
  int numold=0, numnew=0;
  int neighbor_i, neighbor_n, samevisitid;
  ridgeT *ridge, **ridgep;
  boolT toporient;
  void **freelistp;

  trace4((qh ferr, "qh_mergecycle_ridges: delete shared ridges from newfacet\n"));  
  samevisitid= qh visit_id -1;
  FOREACHridge_(newfacet->ridges) {
    neighbor= otherfacet_(ridge, newfacet);
    if (neighbor->visitid == samevisitid)
      SETref_(ridge)= NULL; /* ridge free'd below */  
  }
  qh_setcompact (newfacet->ridges);
  
  trace4((qh ferr, "qh_mergecycle_ridges: add ridges to newfacet\n"));  
  FORALLsame_cycle_(samecycle) {
    FOREACHridge_(same->ridges) {
      if (ridge->top == same) {
        ridge->top= newfacet;
	neighbor= ridge->bottom;
      }else if (ridge->bottom == same) {
	ridge->bottom= newfacet;
	neighbor= ridge->top;
      }else if (ridge->top == newfacet || ridge->bottom == newfacet) {
        qh_setappend (&newfacet->ridges, ridge);
        numold++;  /* already set by qh_mergecycle_neighbors */
	continue;  
      }else {
	fprintf (qh ferr, "qhull internal error (qh_mergecycle_ridges): bad ridge r%d\n", ridge->id);
	qh_errexit (qh_ERRqhull, NULL, ridge);
      }
      if (neighbor == newfacet) {
        qh_setfree(&(ridge->vertices)); 
        qh_memfree_(ridge, sizeof(ridgeT), freelistp);
        numold++;
      }else if (neighbor->visitid == samevisitid) {
	qh_setdel (neighbor->ridges, ridge);
	qh_setfree(&(ridge->vertices)); 
	qh_memfree_(ridge, sizeof(ridgeT), freelistp);
	numold++;
      }else {
        qh_setappend (&newfacet->ridges, ridge);
        numold++;
      }
    }
    if (same->ridges)
      qh_settruncate (same->ridges, 0);
    if (!same->simplicial)
      continue;
    FOREACHneighbor_i_(same) {       /* note: !newfact->simplicial */
      if (neighbor->visitid != samevisitid && neighbor->simplicial) {
        ridge= qh_newridge();
        ridge->vertices= qh_setnew_delnthsorted (same->vertices, qh hull_dim,
  					                  neighbor_i, 0);
        toporient= same->toporient ^ (neighbor_i & 0x1);
        if (toporient) {
          ridge->top= newfacet;
          ridge->bottom= neighbor;
        }else {
          ridge->top= neighbor;
          ridge->bottom= newfacet;
        }
        qh_setappend(&(newfacet->ridges), ridge);
        qh_setappend(&(neighbor->ridges), ridge);
        numnew++;
      }
    }
  }

  trace2((qh ferr, "qh_mergecycle_ridges: found %d old ridges and %d new ones\n", 
             numold, numnew));
} /* mergecycle_ridges */

/*-------------------------------------------------
-mergecycle_vneighbors- create vertex neighbors for newfacet
  samecycle with ->visitid == qh visit_id - 1
returns:
  newfacet vertices with updated neighbors
  deletes vertices that are merged away
  sets delridge on all vertices (faster than in mergecycle_ridges)
notes:
  same function as mergevertex_neighbors
*/
void qh_mergecycle_vneighbors (facetT *samecycle, facetT *newfacet) {
  facetT *neighbor, **neighborp;
  int mergeid;
  vertexT *vertex, **vertexp, *apex;
  setT *vertices;
  
  trace4((qh ferr, "qh_mergecycle_vneighbors: update vertex neighbors for newfacet\n"));  
  mergeid= qh visit_id - 1;
  newfacet->visitid= mergeid;
  vertices= qh_basevertices (samecycle); /* temp */
  apex= SETfirst_(samecycle->vertices);
  qh_setappend (&vertices, apex);
  FOREACHvertex_(vertices) {
    vertex->delridge= True;
    FOREACHneighbor_(vertex) {
      if (neighbor->visitid == mergeid)
        SETref_(neighbor)= NULL;
    }
    qh_setcompact (vertex->neighbors);
    qh_setappend (&vertex->neighbors, newfacet);
    if (!SETsecond_(vertex->neighbors)) {
      zinc_(Zcyclevertex);
      trace2((qh ferr, "qh_mergecycle_vneighbors: deleted v%d when merging cycle f%d into f%d\n",
        vertex->id, samecycle->id, newfacet->id));
      qh_setdelsorted (newfacet->vertices, vertex);
      vertex->deleted= True;
      qh_setappend (&qh del_vertices, vertex);
    }
  }
  qh_settempfree (&vertices);
  trace3((qh ferr, "qh_mergecycle_vneighbors: merged vertices from cycle f%d into f%d\n", 
             samecycle->id, newfacet->id));
} /* mergecycle_vneighbors */

/*-------------------------------------------------
-mergefacet- merges facet1 into facet2
  traces merge if fmax_(maxdist,-mindist) > TRACEdist
  mindist/maxdist may be NULL
  max_outside and min_vertex updated
  qh_MERGEapex if new facet into coplanar horizon
  initializes vertex neighbors on first merge
returns:
  facet1 prepended to visible_list for later deletion and partitioning
     facet1->f.replace == facet2
  facet2 moved to end of qh facet_list
    makes facet2 a newfacet
    sets facet2->newmerge set
    clears facet2->center (unless merging into a large facet)
    clears facet2->tested and ridge->tested for facet1
  adds neighboring facets to facet_mergeset if redundant or degenerate
notes: 
  similar to mergecycle
*/
void qh_mergefacet(facetT *facet1, facetT *facet2, realT *mindist, realT *maxdist, boolT mergeapex) {
  boolT traceonce= False;
  vertexT *vertex, **vertexp;
  int tracerestore=0, nummerge;

  if (!qh VERTEXneighbors)
    qh_vertexneighbors();
  zzinc_(Ztotmerge);
  if (qh POSTmerging && zzval_(Ztotmerge) > qh mergereport + qh REPORTfreq2)
    qh_tracemerging();
#ifndef qh_NOtrace 
  if (mindist && (-*mindist > qh TRACEdist || *maxdist > qh TRACEdist)) {
    tracerestore= 0;
    qh IStracing= qh TRACElevel;
    traceonce= True;
    fprintf (qh ferr, "qh_mergefacet: ========= trace wide merge #%d (%2.2g) for f%d into f%d, last point was p%d\n", zzval_(Ztotmerge),
           fmax_(-*mindist, *maxdist), facet1->id, facet2->id, qh furthest_id);
  }else if (facet1 == qh tracefacet || facet2 == qh tracefacet) {
    tracerestore= qh IStracing;
    qh IStracing= 4;
    traceonce= True;
    fprintf (qh ferr, "qh_mergefacet: ========= trace merge #%d involving f%d, furthest is p%d\n",
	       zzval_(Ztotmerge), qh tracefacet_id,  qh furthest_id);
  }
  if (qh IStracing >= 2) {
    realT mergemin= -2;
    realT mergemax= -2;
    
    if (mindist) {
      mergemin= *mindist;
      mergemax= *maxdist;
    }
    fprintf (qh ferr, "qh_mergefacet: #%d merge f%d into f%d, mindist= %2.2g, maxdist= %2.2g\n", 
    zzval_(Ztotmerge), facet1->id, facet2->id, mergemin, mergemax);
  }
#endif /* !qh_NOtrace */
  if (facet1 == facet2 || facet1->visible || facet2->visible) {
    fprintf (qh ferr, "qhull internal error (qh_mergefacet): either f%d and f%d are the same or one is a visible facet\n",
	     facet1->id, facet2->id);
    qh_errexit2 (qh_ERRqhull, facet1, facet2);
  }
  if (qh num_facets - qh num_visible <= qh hull_dim + 1) {
    fprintf(qh ferr, "\n\
qhull precision error: Only %d facets remain.  Can not merge another\n\
pair.  The convexity constraints may be too strong.  Reduce the\n\
magnitude of 'Cn' or increase the magnitude of 'An'.  For example,\n\
try 'C-0.001' instead of 'C-0.1' or 'A-0.999' instead of 'A-0.9'.\n", 
                 qh hull_dim+1);
    if (qh hull_dim >= 5 && !qh MERGEexact)
      fprintf(qh ferr, "Option 'Qx' may avoid this problem.\n");
    qh_errexit(qh_ERRinput, NULL, NULL);
  }
  qh_makeridges(facet1);
  qh_makeridges(facet2);
  if (qh IStracing >=4)
    qh_errprint ("MERGING", facet1, facet2, NULL, NULL);
  if (mindist) {
    maximize_(qh max_outside, *maxdist);
    maximize_(qh max_vertex, *maxdist);
#if qh_MAXoutside
    maximize_(facet2->maxoutside, *maxdist);
#endif
    minimize_(qh min_vertex, *mindist);
    if (!facet2->keepcentrum 
    && (*maxdist > qh WIDEfacet || *mindist < -qh WIDEfacet)) {
      facet2->keepcentrum= True;
      zinc_(Zwidefacet);
    }
  }
  nummerge= facet1->nummerge + facet2->nummerge + 1;
  if (nummerge >= qh_MAXnummerge) 
    facet2->nummerge= qh_MAXnummerge;
  else
    facet2->nummerge= nummerge;
  facet2->newmerge= True;
  facet2->dupridge= False;
  qh_updatetested  (facet1, facet2);
  if (qh_setsize (facet1->vertices) == qh hull_dim)
    qh_mergesimplex (facet1, facet2, mergeapex);
  else {
    qh_mergeneighbors(facet1, facet2);
    qh_mergeridges(facet1, facet2);
    qh vertex_visit++;
    FOREACHvertex_(facet2->vertices)
      vertex->visitid= qh vertex_visit;
    if (qh hull_dim == 2) 
      /* qh_mergevertices2d(facet1->vertices, facet2->vertices);
      RS950202: changes the coordinates of one of the old vertices
      to retain consistency with the existing edges */
      qh_mungevertices2d(facet1, facet2);
    else 
      qh_mergevertices(facet1->vertices, &facet2->vertices);
    qh_mergevertex_neighbors(facet1, facet2);
    if (!facet2->newfacet)
      qh_newvertices (facet2->vertices);
  }
  if (!mergeapex)
    qh_degen_redundant_neighbors (facet2, facet1);
  if (facet2->coplanar || !facet2->newfacet) {
    zinc_(Zmergeintohorizon);
  }else if (!facet1->newfacet && facet2->newfacet) {
    zinc_(Zmergehorizon);
  }else {
    zinc_(Zmergenew);
  }
  qh_willdelete (facet1, facet2);
  qh_removefacet(facet2);  /* append as a newfacet to end of qh facet_list */
  qh_appendfacet(facet2);
  facet2->newfacet= True;
  facet2->tested= False;
  qh_tracemerge (facet1, facet2);
  if (traceonce) {
    fprintf (qh ferr, "qh_mergefacet: end of wide tracing\n");
    qh IStracing= tracerestore;
  }
} /* mergefacet */


/*-------------------------------------------------
-mergeneighbors- merges the neighbors of facet1 into facet2
notes:
  similar to mergecycle_neighbors
*/
void qh_mergeneighbors(facetT *facet1, facetT *facet2) {
  facetT *neighbor, **neighborp;

  trace4((qh ferr, "qh_mergeneighbors: merge neighbors of f%d and f%d\n",
	  facet1->id, facet2->id));
  qh visit_id++;
  FOREACHneighbor_(facet2) {
    neighbor->visitid= qh visit_id;
  }
  FOREACHneighbor_(facet1) {
    if (neighbor->visitid == qh visit_id) {
      if (neighbor->simplicial)    /* is degen, needs ridges */
	qh_makeridges (neighbor);
      if (SETfirst_(neighbor->neighbors) != facet1) /*keep newfacet->horizon*/
	qh_setdel (neighbor->neighbors, facet1);
      else {
        qh_setdel(neighbor->neighbors, facet2);
        qh_setreplace(neighbor->neighbors, facet1, facet2);
      }
    }else if (neighbor != facet2) {
      qh_setappend(&(facet2->neighbors), neighbor);
      qh_setreplace(neighbor->neighbors, facet1, facet2);
    }
  }
  qh_setdel(facet1->neighbors, facet2);  /* here for makeridges */
  qh_setdel(facet2->neighbors, facet1);
} /* mergeneighbors */


/*-------------------------------------------------
-mergeridges- merges the ridge set of facet1 into facet2
  may delete all ridges for a vertex
returns:
  sets vertex->delridge on deleted ridges
notes:
  similar to mergecycle_ridges
*/
void qh_mergeridges(facetT *facet1, facetT *facet2) {
  ridgeT *ridge, **ridgep;
  vertexT *vertex, **vertexp;

  trace4((qh ferr, "qh_mergeridges: merge ridges of f%d and f%d\n",
	  facet1->id, facet2->id));
  FOREACHridge_(facet2->ridges) {
    if ((ridge->top == facet1) || (ridge->bottom == facet1))