📄 poly2.c
字号:
/*<html><pre> -<a href="qh-poly.htm"
>-------------------------------</a><a name="TOP">-</a>
poly2.c
implements polygons and simplices
see qh-poly.htm, poly.h and qhull.h
frequently used code is in poly.c
copyright (c) 1993-2003, The Geometry Center
*/
#include "qhull_a.h"
/*======== functions in alphabetical order ==========*/
/*-<a href="qh-poly.htm#TOC"
>-------------------------------</a><a name="addhash">-</a>
qh_addhash( newelem, hashtable, hashsize, hash )
add newelem to linear hash table at hash if not already there
*/
void qh_addhash (void* newelem, setT *hashtable, int hashsize, unsigned hash) {
int scan;
void *elem;
for (scan= (int)hash; (elem= SETelem_(hashtable, scan));
scan= (++scan >= hashsize ? 0 : scan)) {
if (elem == newelem)
break;
}
/* loop terminates because qh_HASHfactor >= 1.1 by qh_initbuffers */
if (!elem)
SETelem_(hashtable, scan)= newelem;
} /* addhash */
/*-<a href="qh-poly.htm#TOC"
>-------------------------------</a><a name="check_bestdist">-</a>
qh_check_bestdist()
check that all points are within max_outside of the nearest facet
if qh.ONLYgood,
ignores !good facets
see:
qh_check_maxout(), qh_outerinner()
notes:
only called from qh_check_points()
seldom used since qh.MERGING is almost always set
if notverified>0 at end of routine
some points were well inside the hull. If the hull contains
a lens-shaped component, these points were not verified. Use
options 'Qi Tv' to verify all points. (Exhaustive check also verifies)
design:
determine facet for each point (if any)
for each point
start with the assigned facet or with the first facet
find the best facet for the point and check all coplanar facets
error if point is outside of facet
*/
void qh_check_bestdist (void) {
boolT waserror= False, unassigned;
facetT *facet, *bestfacet, *errfacet1= NULL, *errfacet2= NULL;
facetT *facetlist;
realT dist, maxoutside, maxdist= -REALmax;
pointT *point;
int numpart= 0, facet_i, facet_n, notgood= 0, notverified= 0;
setT *facets;
trace1((qh ferr, "qh_check_bestdist: check points below nearest facet. Facet_list f%d\n",
qh facet_list->id));
maxoutside= qh_maxouter();
maxoutside += qh DISTround;
/* one more qh.DISTround for check computation */
trace1((qh ferr, "qh_check_bestdist: check that all points are within %2.2g of best facet\n", maxoutside));
facets= qh_pointfacet (/*qh facet_list*/);
if (!qh_QUICKhelp && qh PRINTprecision)
fprintf (qh ferr, "\n\
qhull output completed. Verifying that %d points are\n\
below %2.2g of the nearest %sfacet.\n",
qh_setsize(facets), maxoutside, (qh ONLYgood ? "good " : ""));
FOREACHfacet_i_(facets) { /* for each point with facet assignment */
if (facet)
unassigned= False;
else {
unassigned= True;
facet= qh facet_list;
}
point= qh_point(facet_i);
if (point == qh GOODpointp)
continue;
qh_distplane(point, facet, &dist);
numpart++;
bestfacet= qh_findbesthorizon (!qh_IScheckmax, point, facet, qh_NOupper, &dist, &numpart);
/* occurs after statistics reported */
maximize_(maxdist, dist);
if (dist > maxoutside) {
if (qh ONLYgood && !bestfacet->good
&& !((bestfacet= qh_findgooddist (point, bestfacet, &dist, &facetlist))
&& dist > maxoutside))
notgood++;
else {
waserror= True;
fprintf(qh ferr, "qhull precision error: point p%d is outside facet f%d, distance= %6.8g maxoutside= %6.8g\n",
facet_i, bestfacet->id, dist, maxoutside);
if (errfacet1 != bestfacet) {
errfacet2= errfacet1;
errfacet1= bestfacet;
}
}
}else if (unassigned && dist < -qh MAXcoplanar)
notverified++;
}
qh_settempfree (&facets);
if (notverified && !qh DELAUNAY && !qh_QUICKhelp && qh PRINTprecision)
fprintf(qh ferr, "\n%d points were well inside the hull. If the hull contains\n\
a lens-shaped component, these points were not verified. Use\n\
options 'Qci Tv' to verify all points.\n", notverified);
if (maxdist > qh outside_err) {
fprintf( qh ferr, "qhull precision error (qh_check_bestdist): a coplanar point is %6.2g from convex hull. The maximum value (qh.outside_err) is %6.2g\n",
maxdist, qh outside_err);
qh_errexit2 (qh_ERRprec, errfacet1, errfacet2);
}else if (waserror && qh outside_err > REALmax/2)
qh_errexit2 (qh_ERRprec, errfacet1, errfacet2);
else if (waserror)
; /* the error was logged to qh.ferr but does not effect the output */
trace0((qh ferr, "qh_check_bestdist: max distance outside %2.2g\n", maxdist));
} /* check_bestdist */
/*-<a href="qh-poly.htm#TOC"
>-------------------------------</a><a name="check_maxout">-</a>
qh_check_maxout()
updates qh.max_outside by checking all points against bestfacet
if qh.ONLYgood, ignores !good facets
returns:
updates facet->maxoutside via qh_findbesthorizon()
sets qh.maxoutdone
if printing qh.min_vertex (qh_outerinner),
it is updated to the current vertices
removes inside/coplanar points from coplanarset as needed
notes:
defines coplanar as min_vertex instead of MAXcoplanar
may not need to check near-inside points because of qh.MAXcoplanar
and qh.KEEPnearinside (before it was -DISTround)
see also:
qh_check_bestdist()
design:
if qh.min_vertex is needed
for all neighbors of all vertices
test distance from vertex to neighbor
determine facet for each point (if any)
for each point with an assigned facet
find the best facet for the point and check all coplanar facets
(updates outer planes)
remove near-inside points from coplanar sets
*/
#ifndef qh_NOmerge
void qh_check_maxout (void) {
facetT *facet, *bestfacet, *neighbor, **neighborp, *facetlist;
realT dist, maxoutside, minvertex, old_maxoutside;
pointT *point;
int numpart= 0, facet_i, facet_n, notgood= 0;
setT *facets, *vertices;
vertexT *vertex;
trace1((qh ferr, "qh_check_maxout: check and update maxoutside for each facet.\n"));
maxoutside= minvertex= 0;
if (qh VERTEXneighbors
&& (qh PRINTsummary || qh KEEPinside || qh KEEPcoplanar
|| qh TRACElevel || qh PRINTstatistics
|| qh PRINTout[0] == qh_PRINTsummary || qh PRINTout[0] == qh_PRINTnone)) {
trace1((qh ferr, "qh_check_maxout: determine actual maxoutside and minvertex\n"));
vertices= qh_pointvertex (/*qh facet_list*/);
FORALLvertices {
FOREACHneighbor_(vertex) {
zinc_(Zdistvertex); /* distance also computed by main loop below */
qh_distplane (vertex->point, neighbor, &dist);
minimize_(minvertex, dist);
if (-dist > qh TRACEdist || dist > qh TRACEdist
|| neighbor == qh tracefacet || vertex == qh tracevertex)
fprintf (qh ferr, "qh_check_maxout: p%d (v%d) is %.2g from f%d\n",
qh_pointid (vertex->point), vertex->id, dist, neighbor->id);
}
}
if (qh MERGING) {
wmin_(Wminvertex, qh min_vertex);
}
qh min_vertex= minvertex;
qh_settempfree (&vertices);
}
facets= qh_pointfacet (/*qh facet_list*/);
do {
old_maxoutside= fmax_(qh max_outside, maxoutside);
FOREACHfacet_i_(facets) { /* for each point with facet assignment */
if (facet) {
point= qh_point(facet_i);
if (point == qh GOODpointp)
continue;
zinc_(Ztotcheck);
qh_distplane(point, facet, &dist);
numpart++;
bestfacet= qh_findbesthorizon (qh_IScheckmax, point, facet, !qh_NOupper, &dist, &numpart);
if (bestfacet && dist > maxoutside) {
if (qh ONLYgood && !bestfacet->good
&& !((bestfacet= qh_findgooddist (point, bestfacet, &dist, &facetlist))
&& dist > maxoutside))
notgood++;
else
maxoutside= dist;
}
if (dist > qh TRACEdist || (bestfacet && bestfacet == qh tracefacet))
fprintf (qh ferr, "qh_check_maxout: p%d is %.2g above f%d\n",
qh_pointid (point), dist, bestfacet->id);
}
}
}while
(maxoutside > 2*old_maxoutside);
/* if qh.maxoutside increases substantially, qh_SEARCHdist is not valid
e.g., RBOX 5000 s Z1 G1e-13 t1001200614 | qhull */
zzadd_(Zcheckpart, numpart);
qh_settempfree (&facets);
wval_(Wmaxout)= maxoutside - qh max_outside;
wmax_(Wmaxoutside, qh max_outside);
qh max_outside= maxoutside;
qh_nearcoplanar (/*qh.facet_list*/);
qh maxoutdone= True;
trace1((qh ferr, "qh_check_maxout: maxoutside %2.2g, min_vertex %2.2g, outside of not good %d\n",
maxoutside, qh min_vertex, notgood));
} /* check_maxout */
#else /* qh_NOmerge */
void qh_check_maxout (void) {
}
#endif
/*-<a href="qh-poly.htm#TOC"
>-------------------------------</a><a name="check_output">-</a>
qh_check_output()
performs the checks at the end of qhull algorithm
Maybe called after voronoi output. Will recompute otherwise centrums are Voronoi centers instead
*/
void qh_check_output (void) {
int i;
if (qh STOPcone)
return;
if (qh VERIFYoutput | qh IStracing | qh CHECKfrequently) {
qh_checkpolygon (qh facet_list);
qh_checkflipped_all (qh facet_list);
qh_checkconvex (qh facet_list, qh_ALGORITHMfault);
}else if (!qh MERGING && qh_newstats (qhstat precision, &i)) {
qh_checkflipped_all (qh facet_list);
qh_checkconvex (qh facet_list, qh_ALGORITHMfault);
}
} /* check_output */
/*-<a href="qh-poly.htm#TOC"
>-------------------------------</a><a name="check_point">-</a>
qh_check_point( point, facet, maxoutside, maxdist, errfacet1, errfacet2 )
check that point is less than maxoutside from facet
*/
void qh_check_point (pointT *point, facetT *facet, realT *maxoutside, realT *maxdist, facetT **errfacet1, facetT **errfacet2) {
realT dist;
/* occurs after statistics reported */
qh_distplane(point, facet, &dist);
if (dist > *maxoutside) {
if (*errfacet1 != facet) {
*errfacet2= *errfacet1;
*errfacet1= facet;
}
fprintf(qh ferr, "qhull precision error: point p%d is outside facet f%d, distance= %6.8g maxoutside= %6.8g\n",
qh_pointid(point), facet->id, dist, *maxoutside);
}
maximize_(*maxdist, dist);
} /* qh_check_point */
/*-<a href="qh-poly.htm#TOC"
>-------------------------------</a><a name="check_points">-</a>
qh_check_points()
checks that all points are inside all facets
notes:
if many points and qh_check_maxout not called (i.e., !qh.MERGING),
calls qh_findbesthorizon (seldom done).
ignores flipped facets
maxoutside includes 2 qh.DISTrounds
one qh.DISTround for the computed distances in qh_check_points
qh_printafacet and qh_printsummary needs only one qh.DISTround
the computation for qh.VERIFYdirect does not account for qh.other_points
design:
if many points
use qh_check_bestdist()
else
for all facets
for all points
check that point is inside facet
*/
void qh_check_points (void) {
facetT *facet, *errfacet1= NULL, *errfacet2= NULL;
realT total, maxoutside, maxdist= -REALmax;
pointT *point, **pointp, *pointtemp;
boolT testouter;
maxoutside= qh_maxouter();
maxoutside += qh DISTround;
/* one more qh.DISTround for check computation */
trace1((qh ferr, "qh_check_points: check all points below %2.2g of all facet planes\n",
maxoutside));
if (qh num_good) /* miss counts other_points and !good facets */
total= (float) qh num_good * qh num_points;
else
total= (float) qh num_facets * qh num_points;
if (total >= qh_VERIFYdirect && !qh maxoutdone) {
if (!qh_QUICKhelp && qh SKIPcheckmax && qh MERGING)
fprintf (qh ferr, "\n\
qhull input warning: merging without checking outer planes ('Q5' or 'Po').\n\
Verify may report that a point is outside of a facet.\n");
qh_check_bestdist();
}else {
if (qh_MAXoutside && qh maxoutdone)
testouter= True;
else
testouter= False;
if (!qh_QUICKhelp) {
if (qh MERGEexact)
fprintf (qh ferr, "\n\
qhull input warning: exact merge ('Qx'). Verify may report that a point\n\
is outside of a facet. See qh-optq.htm#Qx\n");
else if (qh SKIPcheckmax || qh NOnearinside)
fprintf (qh ferr, "\n\
qhull input warning: no outer plane check ('Q5') or no processing of\n\
near-inside points ('Q8'). Verify may report that a point is outside\n\
of a facet.\n");
}
if (qh PRINTprecision) {
if (testouter)
fprintf (qh ferr, "\n\
Output completed. Verifying that all points are below outer planes of\n\
all %sfacets. Will make %2.0f distance computations.\n",
(qh ONLYgood ? "good " : ""), total);
else
fprintf (qh ferr, "\n\
Output completed. Verifying that all points are below %2.2g of\n\
all %sfacets. Will make %2.0f distance computations.\n",
maxoutside, (qh ONLYgood ? "good " : ""), total);
}
FORALLfacets {
if (!facet->good && qh ONLYgood)
continue;
if (facet->flipped)
continue;
if (!facet->normal) {
fprintf( qh ferr, "qhull warning (qh_check_points): missing normal for facet f%d\n", facet->id);
continue;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -