📄 poly.c
字号:
/*<html><pre> -<a href="qh-c.htm#poly"
>-------------------------------</a><a name="TOP">-</a>
poly.c
implements polygons and simplices
see qh-c.htm, poly.h and qhull.h
infrequent code is in poly2.c
(all but top 50 and their callers 12/3/95)
copyright (c) 1993-1999, The Geometry Center
*/
#include "qhull_a.h"
/*======== functions in alphabetical order ==========*/
/*-<a href="qh-c.htm#poly"
>-------------------------------</a><a name="appendfacet">-</a>
qh_appendfacet( facet )
appends facet to end of qh.facet_list,
returns:
updates qh.facet_list, facet_tail, newfacet_list, facet_next
increments qh.numfacets
notes:
assumes qh.facet_list/facet_tail is defined (createsimplex)
*/
void qh_appendfacet(facetT *facet) {
facetT *tail= qh facet_tail;
if (tail == qh newfacet_list)
qh newfacet_list= facet;
if (tail == qh facet_next)
qh facet_next= facet;
facet->previous= tail->previous;
facet->next= tail;
if (tail->previous)
tail->previous->next= facet;
else
qh facet_list= facet;
tail->previous= facet;
qh num_facets++;
trace4((qh ferr, "qh_appendfacet: append f%d to facet_list\n", facet->id));
} /* appendfacet */
/*-<a href="qh-c.htm#poly"
>-------------------------------</a><a name="appendvertex">-</a>
qh_appendvertex( vertex )
appends vertex to end of qh.vertex_list,
returns:
sets vertex->newlist
updates qh.vertex_list, vertex_tail, newvertex_list
increments qh.num_vertices
notes:
assumes qh.vertex_list/vertex_tail is defined (createsimplex)
*/
void qh_appendvertex (vertexT *vertex) {
vertexT *tail= qh vertex_tail;
if (tail == qh newvertex_list)
qh newvertex_list= vertex;
vertex->newlist= True;
vertex->previous= tail->previous;
vertex->next= tail;
if (tail->previous)
tail->previous->next= vertex;
else
qh vertex_list= vertex;
tail->previous= vertex;
qh num_vertices++;
trace4((qh ferr, "qh_appendvertex: append v%d to vertex_list\n", vertex->id));
} /* appendvertex */
/*-<a href="qh-c.htm#poly"
>-------------------------------</a><a name="attachnewfacets">-</a>
qh_attachnewfacets( )
attach horizon facets to new facets in qh.newfacet_list
newfacets have neighbor and ridge links to horizon but not vice versa
only needed for qh.ONLYgood
returns:
set qh.NEWfacets
horizon facets linked to new facets
ridges changed from visible facets to new facets
simplicial ridges deleted
qh.visible_list, no ridges valid
facet->f.replace is a newfacet (if any)
design:
delete interior ridges and neighbor sets by
for each visible, non-simplicial facet
for each ridge
if last visit or if neighbor is simplicial
if horizon neighbor
delete ridge for horizon's ridge set
delete ridge
erase neighbor set
attach horizon facets and new facets by
for all new facets
if corresponding horizon facet is simplicial
locate corresponding visible facet {may be more than one}
link visible facet to new facet
replace visible facet with new facet in horizon
else it's non-simplicial
for all visible neighbors of the horizon facet
link visible neighbor to new facet
delete visible neighbor from horizon facet
append new facet to horizon's neighbors
the first ridge of the new facet is the horizon ridge
link the new facet into the horizon ridge
*/
void qh_attachnewfacets (void ) {
facetT *newfacet= NULL, *neighbor, **neighborp, *horizon, *visible;
ridgeT *ridge, **ridgep;
qh NEWfacets= True;
trace3((qh ferr, "qh_attachnewfacets: delete interior ridges\n"));
qh visit_id++;
FORALLvisible_facets {
visible->visitid= qh visit_id;
if (visible->ridges) {
FOREACHridge_(visible->ridges) {
neighbor= otherfacet_(ridge, visible);
if (neighbor->visitid == qh visit_id
|| (!neighbor->visible && neighbor->simplicial)) {
if (!neighbor->visible) /* delete ridge for simplicial horizon */
qh_setdel (neighbor->ridges, ridge);
qh_setfree (&(ridge->vertices)); /* delete on 2nd visit */
qh_memfree (ridge, sizeof(ridgeT));
}
}
SETfirst_(visible->ridges)= NULL;
}
SETfirst_(visible->neighbors)= NULL;
}
trace1((qh ferr, "qh_attachnewfacets: attach horizon facets to new facets\n"));
FORALLnew_facets {
horizon= SETfirstt_(newfacet->neighbors, facetT);
if (horizon->simplicial) {
visible= NULL;
FOREACHneighbor_(horizon) { /* may have more than one horizon ridge */
if (neighbor->visible) {
if (visible) {
if (qh_setequal_skip (newfacet->vertices, 0, horizon->vertices,
SETindex_(horizon->neighbors, neighbor))) {
visible= neighbor;
break;
}
}else
visible= neighbor;
}
}
if (visible) {
visible->f.replace= newfacet;
qh_setreplace (horizon->neighbors, visible, newfacet);
}else {
fprintf (qh ferr, "qhull internal error (qh_attachnewfacets): couldn't find visible facet for horizon f%d of newfacet f%d\n",
horizon->id, newfacet->id);
qh_errexit2 (qh_ERRqhull, horizon, newfacet);
}
}else { /* non-simplicial, with a ridge for newfacet */
FOREACHneighbor_(horizon) { /* may hold for many new facets */
if (neighbor->visible) {
neighbor->f.replace= newfacet;
qh_setdelnth (horizon->neighbors,
SETindex_(horizon->neighbors, neighbor));
neighborp--; /* repeat */
}
}
qh_setappend (&horizon->neighbors, newfacet);
ridge= SETfirstt_(newfacet->ridges, ridgeT);
if (ridge->top == horizon)
ridge->bottom= newfacet;
else
ridge->top= newfacet;
}
} /* newfacets */
if (qh PRINTstatistics) {
FORALLvisible_facets {
if (!visible->f.replace)
zinc_(Zinsidevisible);
}
}
} /* attachnewfacets */
/*-<a href="qh-c.htm#poly"
>-------------------------------</a><a name="checkflipped">-</a>
qh_checkflipped( facet, dist, allerror )
checks facet orientation to interior point
if allerror set,
tests against qh.DISTround
else
tests against 0 since tested against DISTround before
returns:
False if it flipped orientation (sets facet->flipped)
distance if non-NULL
*/
boolT qh_checkflipped (facetT *facet, realT *distp, boolT allerror) {
realT dist;
if (facet->flipped && !distp)
return False;
zzinc_(Zdistcheck);
qh_distplane(qh interior_point, facet, &dist);
if (distp)
*distp= dist;
if ((allerror && dist > -qh DISTround)|| (!allerror && dist >= 0.0)) {
facet->flipped= True;
zzinc_(Zflippedfacets);
trace0((qh ferr, "qh_checkflipped: facet f%d is flipped, distance= %6.12g during p%d\n",
facet->id, dist, qh furthest_id));
qh_precision ("flipped facet");
return False;
}
return True;
} /* checkflipped */
/*-<a href="qh-c.htm#poly"
>-------------------------------</a><a name="delfacet">-</a>
qh_delfacet( facet )
removes facet from facet_list and frees up its memory
notes:
assumes vertices and ridges already freed
*/
void qh_delfacet(facetT *facet) {
void **freelistp; /* used !qh_NOmem */
trace5((qh ferr, "qh_delfacet: delete f%d\n", facet->id));
if (facet == qh tracefacet)
qh tracefacet= NULL;
if (facet == qh GOODclosest)
qh GOODclosest= NULL;
qh_removefacet(facet);
qh_memfree_(facet->normal, qh normal_size, freelistp);
if (qh CENTERtype == qh_ASvoronoi) { /* uses macro calls */
qh_memfree_(facet->center, qh center_size, freelistp);
}else /* AScentrum */ {
qh_memfree_(facet->center, qh normal_size, freelistp);
}
qh_setfree(&(facet->neighbors));
if (facet->ridges)
qh_setfree(&(facet->ridges));
qh_setfree(&(facet->vertices));
if (facet->outsideset)
qh_setfree(&(facet->outsideset));
if (facet->coplanarset)
qh_setfree(&(facet->coplanarset));
qh_memfree_(facet, sizeof(facetT), freelistp);
} /* delfacet */
/*-<a href="qh-c.htm#poly"
>-------------------------------</a><a name="deletevisible">-</a>
qh_deletevisible()
delete visible facets and vertices
returns:
deletes each facet and removes from facetlist
at exit, qh.visible_list empty (== qh.newfacet_list)
notes:
ridges already deleted
horizon facets do not reference facets on qh.visible_list
new facets in qh.newfacet_list
uses qh.visit_id;
*/
void qh_deletevisible (void /*qh visible_list*/) {
facetT *visible, *nextfacet;
vertexT *vertex, **vertexp;
int numvisible= 0, numdel= qh_setsize(qh del_vertices);
trace1((qh ferr, "qh_deletevisible: delete %d visible facets and %d vertices\n",
qh num_visible, numdel));
for (visible= qh visible_list; visible && visible->visible;
visible= nextfacet) { /* deleting current */
nextfacet= visible->next;
numvisible++;
qh_delfacet(visible);
}
if (numvisible != qh num_visible) {
fprintf (qh ferr, "qhull internal error (qh_deletevisible): qh num_visible %d is not number of visible facets %d\n",
qh num_visible, numvisible);
qh_errexit (qh_ERRqhull, NULL, NULL);
}
qh num_visible= 0;
zadd_(Zvisfacettot, numvisible);
zmax_(Zvisfacetmax, numvisible);
zadd_(Zdelvertextot, numdel);
zmax_(Zdelvertexmax, numdel);
FOREACHvertex_(qh del_vertices)
qh_delvertex (vertex);
qh_settruncate (qh del_vertices, 0);
} /* deletevisible */
/*-<a href="qh-c.htm#poly"
>-------------------------------</a><a name="facetintersect">-</a>
qh_facetintersect( facetA, facetB, skipa, skipB, prepend )
return vertices for intersection of two simplicial facets
may include 1 prepended entry (if more, need to settemppush)
returns:
returns set of qh.hull_dim-1 + prepend vertices
returns skipped index for each test and checks for exactly one
notes:
does not need settemp since set in quick memory
see also:
qh_vertexintersect and qh_vertexintersect_new
use qh_setnew_delnthsorted to get nth ridge (no skip information)
design:
locate skipped vertex by scanning facet A's neighbors
locate skipped vertex by scanning facet B's neighbors
intersect the vertex sets
*/
setT *qh_facetintersect (facetT *facetA, facetT *facetB,
int *skipA,int *skipB, int prepend) {
setT *intersect;
int dim= qh hull_dim, i, j;
facetT **neighborsA, **neighborsB;
neighborsA= SETaddr_(facetA->neighbors, facetT);
neighborsB= SETaddr_(facetB->neighbors, facetT);
i= j= 0;
if (facetB == *neighborsA++)
*skipA= 0;
else if (facetB == *neighborsA++)
*skipA= 1;
else if (facetB == *neighborsA++)
*skipA= 2;
else {
for (i= 3; i < dim; i++) {
if (facetB == *neighborsA++) {
*skipA= i;
break;
}
}
}
if (facetA == *neighborsB++)
*skipB= 0;
else if (facetA == *neighborsB++)
*skipB= 1;
else if (facetA == *neighborsB++)
*skipB= 2;
else {
for (j= 3; j < dim; j++) {
if (facetA == *neighborsB++) {
*skipB= j;
break;
}
}
}
if (i >= dim || j >= dim) {
fprintf (qh ferr, "qhull internal error (qh_facetintersect): f%d or f%d not in others neighbors\n",
facetA->id, facetB->id);
qh_errexit2 (qh_ERRqhull, facetA, facetB);
}
intersect= qh_setnew_delnthsorted (facetA->vertices, qh hull_dim, *skipA, prepend);
trace4((qh ferr, "qh_facetintersect: f%d skip %d matches f%d skip %d\n",
facetA->id, *skipA, facetB->id, *skipB));
return(intersect);
} /* facetintersect */
/*-<a href="qh-c.htm#poly"
>-------------------------------</a><a name="gethash">-</a>
qh_gethash( hashsize, set, size, firstindex, skipelem )
return hashvalue for a set with firstindex and skipelem
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -