?? merge.c
字號:
/*<html><pre> -<a href="qh-c.htm#merge"
>-------------------------------</a><a name="TOP">-</a>
merge.c
merges non-convex facets
see qh-c.htm and merge.h
other modules call qh_premerge() and qh_postmerge()
the user may call qh_postmerge() to perform additional merges.
To remove deleted facets and vertices (qhull() in qhull.c):
qh_partitionvisible (!qh_ALL, &numoutside); // visible_list, newfacet_list
qh_deletevisible (); // qh.visible_list
qh_resetlists (False); // qh.visible_list newvertex_list newfacet_list
assumes qh.CENTERtype= centrum
merges occur in qh_mergefacet and in qh_mergecycle
vertex->neighbors not set until the first merge occurs
copyright (c) 1993-1999 The Geometry Center
*/
#include "qhull_a.h"
#ifndef qh_NOmerge
/*=========== internal prototypes =========*/
static int qh_compareangle(const void *p1, const void *p2);
static int qh_comparemerge(const void *p1, const void *p2);
static int qh_comparevisit (const void *p1, const void *p2);
/*===== functions (alphabetical after premerge and postmerge) ======*/
/*-<a href="qh-c.htm#merge"
>-------------------------------</a><a name="premerge">-</a>
qh_premerge( apex, maxcentrum )
pre-merge nonconvex facets in qh.newfacet_list for apex
maxcentrum defines coplanar and concave (qh_test_appendmerge)
returns:
deleted facets added to qh.visible_list with facet->visible set
notes:
uses globals, qh.MERGEexact, qh.PREmerge
design:
mark duplicate ridges in qh.newfacet_list
merge facet cycles in qh.newfacet_list
merge duplicate ridges and concave facets in qh.newfacet_list
check merged facet cycles for degenerate and redundant facets
merge degenerate and redundant facets
collect coplanar and concave facets
merge concave, coplanar, degenerate, and redundant facets
*/
void qh_premerge (vertexT *apex, realT maxcentrum, realT maxangle) {
boolT othermerge= False;
facetT *newfacet;
if (qh ZEROcentrum && qh_checkzero(!qh_ALL))
return;
trace2((qh ferr, "qh_premerge: premerge centrum %2.2g angle %2.2g for apex v%d facetlist f%d\n",
maxcentrum, maxangle, apex->id, getid_(qh newfacet_list)));
if (qh IStracing >= 4 && qh num_facets < 50)
qh_printlists();
qh centrum_radius= maxcentrum;
qh cos_max= maxangle;
qh degen_mergeset= qh_settemp (qh TEMPsize);
qh facet_mergeset= qh_settemp (qh TEMPsize);
if (qh hull_dim >=3) {
qh_mark_dupridges (qh newfacet_list); /* facet_mergeset */
qh_mergecycle_all (qh newfacet_list, &othermerge);
qh_forcedmerges (&othermerge /* qh facet_mergeset */);
FORALLnew_facets { /* test samecycle merges */
if (!newfacet->simplicial && !newfacet->mergeridge)
qh_degen_redundant_neighbors (newfacet, NULL);
}
if (qh_merge_degenredundant())
othermerge= True;
}else /* qh hull_dim == 2 */
qh_mergecycle_all (qh newfacet_list, &othermerge);
qh_flippedmerges (qh newfacet_list, &othermerge);
if (!qh MERGEexact || zzval_(Ztotmerge)) {
zinc_(Zpremergetot);
qh POSTmerging= False;
qh_getmergeset_initial (qh newfacet_list);
qh_all_merges (othermerge, False);
}
qh_settempfree(&qh facet_mergeset);
qh_settempfree(&qh degen_mergeset);
} /* premerge */
/*-<a href="qh-c.htm#merge"
>-------------------------------</a><a name="postmerge">-</a>
qh_postmerge( reason, maxcentrum, maxangle, vneighbors )
post-merge nonconvex facets as defined by maxcentrum and maxangle
'reason' is for reporting progress
if vneighbors,
calls qh_test_vneighbors at end of qh_all_merge
if firstmerge,
calls qh_reducevertices before qh_getmergeset
returns:
if first call (qh.visible_list != qh.facet_list),
builds qh.facet_newlist, qh.newvertex_list
deleted facets added to qh.visible_list with facet->visible
qh.visible_list == qh.facet_list
notes:
design:
if first call
set qh.visible_list and qh.newfacet_list to qh.facet_list
add all facets to qh.newfacet_list
mark non-simplicial facets, facet->newmerge
set qh.newvertext_list to qh.vertex_list
add all vertices to qh.newvertex_list
if a pre-merge occured
set vertex->delridge {will retest the ridge}
if qh.MERGEexact
call qh_reducevertices()
if no pre-merging
merge flipped facets
determine non-convex facets
merge all non-convex facets
*/
void qh_postmerge (char *reason, realT maxcentrum, realT maxangle,
boolT vneighbors) {
facetT *newfacet;
boolT othermerges= False;
vertexT *vertex;
if (qh REPORTfreq || qh IStracing) {
qh_buildtracing (NULL, NULL);
qh_printsummary (qh ferr);
if (qh PRINTstatistics)
qh_printallstatistics (qh ferr, "reason");
fprintf (qh ferr, "\n%s with 'C%.2g' and 'A%.2g'\n",
reason, maxcentrum, maxangle);
}
trace2((qh ferr, "qh_postmerge: postmerge. test vneighbors? %d\n",
vneighbors));
qh centrum_radius= maxcentrum;
qh cos_max= maxangle;
qh POSTmerging= True;
qh degen_mergeset= qh_settemp (qh TEMPsize);
qh facet_mergeset= qh_settemp (qh TEMPsize);
if (qh visible_list != qh facet_list) { /* first call */
qh NEWfacets= True;
qh visible_list= qh newfacet_list= qh facet_list;
FORALLnew_facets {
newfacet->newfacet= True;
if (!newfacet->simplicial)
newfacet->newmerge= True;
zinc_(Zpostfacets);
}
qh newvertex_list= qh vertex_list;
FORALLvertices
vertex->newlist= True;
if (qh VERTEXneighbors) { /* a merge has occurred */
FORALLvertices
vertex->delridge= True; /* test for redundant, needed? */
if (qh MERGEexact) {
if (qh hull_dim <= qh_DIMreduceBuild)
qh_reducevertices(); /* was skipped during pre-merging */
}
}
if (!qh PREmerge && !qh MERGEexact)
qh_flippedmerges (qh newfacet_list, &othermerges);
}
qh_getmergeset_initial (qh newfacet_list);
qh_all_merges (False, vneighbors);
qh_settempfree(&qh facet_mergeset);
qh_settempfree(&qh degen_mergeset);
} /* post_merge */
/*-<a href="qh-c.htm#merge"
>-------------------------------</a><a name="all_merges">-</a>
qh_all_merges( othermerge, vneighbors )
merge all non-convex facets
set othermerge if already merged facets (for qh_reducevertices)
if vneighbors
tests vertex neighbors for convexity at end
qh.facet_mergeset lists the non-convex ridges in qh_newfacet_list
qh.degen_mergeset is defined
if qh.MERGEexact && !qh.POSTmerging,
does not merge coplanar facets
returns:
deleted facets added to qh.visible_list with facet->visible
deleted vertices added qh.delvertex_list with vertex->delvertex
notes:
unless !qh.MERGEindependent,
merges facets in independent sets
uses qh.newfacet_list as argument since merges call qh_removefacet()
design:
while merges occur
for each merge in qh.facet_mergeset
unless one of the facets was already merged in this pass
merge the facets
test merged facets for additional merges
add merges to qh.facet_mergeset
if vertices record neighboring facets
rename redundant vertices
update qh.facet_mergeset
if vneighbors ??
tests vertex neighbors for convexity at end
*/
void qh_all_merges (boolT othermerge, boolT vneighbors) {
facetT *facet1, *facet2;
mergeT *merge;
boolT wasmerge= True, isreduce;
void **freelistp; /* used !qh_NOmem */
vertexT *vertex;
mergeType mergetype;
int numcoplanar=0, numconcave=0, numdegenredun= 0, numnewmerges= 0;
trace2((qh ferr, "qh_all_merges: starting to merge facets beginning from f%d\n",
getid_(qh newfacet_list)));
while (True) {
wasmerge= False;
while (qh_setsize (qh facet_mergeset)) {
while ((merge= (mergeT*)qh_setdellast(qh facet_mergeset))) {
facet1= merge->facet1;
facet2= merge->facet2;
mergetype= merge->type;
qh_memfree_(merge, sizeof(mergeT), freelistp);
if (facet1->visible || facet2->visible) /*deleted facet*/
continue;
if ((facet1->newfacet && !facet1->tested)
|| (facet2->newfacet && !facet2->tested)) {
if (qh MERGEindependent && mergetype <= MRGanglecoplanar)
continue; /* perform independent sets of merges */
}
qh_merge_nonconvex (facet1, facet2, mergetype);
numdegenredun += qh_merge_degenredundant();
numnewmerges++;
wasmerge= True;
if (mergetype == MRGconcave)
numconcave++;
else /* MRGcoplanar or MRGanglecoplanar */
numcoplanar++;
} /* while setdellast */
if (qh POSTmerging && qh hull_dim <= qh_DIMreduceBuild
&& numnewmerges > qh_MAXnewmerges) {
numnewmerges= 0;
qh_reducevertices(); /* otherwise large post merges too slow */
}
qh_getmergeset (qh newfacet_list); /* facet_mergeset */
} /* while mergeset */
if (qh VERTEXneighbors) {
isreduce= False;
if (qh hull_dim >=4 && qh POSTmerging) {
FORALLvertices
vertex->delridge= True;
isreduce= True;
}
if ((wasmerge || othermerge) && (!qh MERGEexact || qh POSTmerging)
&& qh hull_dim <= qh_DIMreduceBuild) {
othermerge= False;
isreduce= True;
}
if (isreduce) {
if (qh_reducevertices()) {
qh_getmergeset (qh newfacet_list); /* facet_mergeset */
continue;
}
}
}
if (vneighbors && qh_test_vneighbors(/* qh newfacet_list */))
continue;
break;
} /* while (True) */
if (qh CHECKfrequently && !qh MERGEexact) {
qh old_randomdist= qh RANDOMdist;
qh RANDOMdist= False;
qh_checkconvex (qh newfacet_list, qh_ALGORITHMfault);
/* qh_checkconnect (); [this is slow and it changes the facet order] */
qh RANDOMdist= qh old_randomdist;
}
trace1((qh ferr, "qh_all_merges: merged %d coplanar facets %d concave facets and %d degen or redundant facets.\n",
numcoplanar, numconcave, numdegenredun));
if (qh IStracing >= 4 && qh num_facets < 50)
qh_printlists ();
} /* all_merges */
/*-<a href="qh-c.htm#merge"
>-------------------------------</a><a name="appendmergeset">-</a>
qh_appendmergeset( facet, neighbor, mergetype, angle )
appends an entry to qh.facet_mergeset or qh.degen_mergeset
angle ignored if NULL or !qh.ANGLEmerge
returns:
merge appended to facet_mergeset or degen_mergeset
sets ->degenerate or ->redundant if degen_mergeset
see:
qh_test_appendmerge()
design:
allocate merge entry
if regular merge
append to qh.facet_mergeset
else if degenerate merge and qh.facet_mergeset is all degenerate
append to qh.degen_mergeset
else if degenerate merge
prepend to qh.degen_mergeset
else if redundant merge
append to qh.degen_mergeset
*/
void qh_appendmergeset(facetT *facet, facetT *neighbor, mergeType mergetype, realT *angle) {
mergeT *merge, *lastmerge;
void **freelistp; /* used !qh_NOmem */
if (facet->redundant)
return;
if (facet->degenerate && mergetype == MRGdegen)
return;
qh_memalloc_(sizeof(mergeT), freelistp, merge, mergeT);
merge->facet1= facet;
merge->facet2= neighbor;
merge->type= mergetype;
if (angle && qh ANGLEmerge)
merge->angle= *angle;
if (mergetype < MRGdegen)
qh_setappend (&(qh facet_mergeset), merge);
else if (mergetype == MRGdegen) {
facet->degenerate= True;
if (!(lastmerge= (mergeT*)qh_setlast (qh degen_mergeset))
|| lastmerge->type == MRGdegen)
qh_setappend (&(qh degen_mergeset), merge);
else
qh_setaddnth (&(qh degen_mergeset), 0, merge);
}else { /* mergetype == MRGredundant */
facet->redundant= True;
qh_setappend (&(qh degen_mergeset), merge);
}
} /* appendmergeset */
/*-<a href="qh-c.htm#merge"
>-------------------------------</a><a name="basevertices">-</a>
qh_basevertices( samecycle )
return temporary set of base vertices for samecycle
samecycle is first facet in the cycle
assumes apex is SETfirst_( samecycle->vertices )
returns:
vertices (settemp)
all ->seen are cleared
notes:
uses qh_vertex_visit;
design:
for each facet in samecycle
for each unseen vertex in facet->vertices
append to result
*/
setT *qh_basevertices (facetT *samecycle) {
facetT *same;
vertexT *apex, *vertex, **vertexp;
setT *vertices= qh_settemp (qh TEMPsize);
apex= SETfirstt_(samecycle->vertices, vertexT);
apex->visitid= ++qh vertex_visit;
FORALLsame_cycle_(samecycle) {
if (same->mergeridge)
continue;
FOREACHvertex_(same->vertices) {
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -