?? poly2.c
字號:
/*<html><pre> -<a href="qh-c.htm#poly"
>-------------------------------</a><a name="TOP">-</a>
poly2.c
implements polygons and simplices
see qh-c.htm, poly.h and qhull.h
frequently used code is in poly.c
copyright (c) 1993-1999, The Geometry Center
*/
#include "qhull_a.h"
/*======== functions in alphabetical order ==========*/
/*-<a href="qh-c.htm#poly"
>-------------------------------</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-c.htm#poly"
>-------------------------------</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:
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, isoutside, unassigned;
facetT *facet, *bestfacet, *errfacet1= NULL, *errfacet2= NULL;
facetT *facetlist;
realT dist, maxoutside, maxdist= -REALmax;
pointT *point;
int numpart, 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;
bestfacet= qh_findbest (point, facet, qh_ALL, False, !qh_NOupper,
&dist, &isoutside, &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);
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_errlog() but does not effect the output */
trace0((qh ferr, "qh_check_bestdist: max distance outside %2.2g\n", maxdist));
} /* check_bestdist */
/*-<a href="qh-c.htm#poly"
>-------------------------------</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_findbest()
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;
pointT *point;
int numpart, 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*/);
FOREACHfacet_i_(facets) { /* for each point with facet assignment */
if (facet) {
point= qh_point(facet_i);
if (point == qh GOODpointp)
continue;
zinc_(Ztotcheck);
bestfacet= qh_findbest (point, facet, qh_ALL, False, !qh_NOupper,
&dist, NULL, &numpart);
zadd_(Zcheckpart, 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);
}
}
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-c.htm#poly"
>-------------------------------</a><a name="check_output">-</a>
qh_check_output()
performs the checks at the end of qhull algorithm
*/
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-c.htm#poly"
>-------------------------------</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) {
*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-c.htm#poly"
>-------------------------------</a><a name="check_points">-</a>
qh_check_points()
checks that all points are inside all facets
notes:
uses qh_findbest if lots of points
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').\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 || qh SKIPcheckmax || qh NOnearinside)
fprintf (qh ferr, "\n\
qhull input warning: exact merge ('Qx'), no outer plane check ('Q5'), or\n\
no processing of near-inside points ('Q8'). Verify may report that a point\n\
is outside 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 (testouter) {
#if qh_MAXoutside
maxoutside= facet->maxoutside + 2* qh DISTround;
/* one DISTround to actual point and another to computed point */
#endif
}
FORALLpoints {
if (point != qh GOODpointp)
qh_check_point (point, facet, &maxoutside, &maxdist, &errfacet1, &errfacet2);
}
FOREACHpoint_(qh other_points) {
if (point != qh GOODpointp)
qh_check_point (point, facet, &maxoutside, &maxdist, &errfacet1, &errfacet2);
}
}
if (maxdist > qh outside_err) {
fprintf( qh ferr, "qhull precision error (qh_check_points): 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 (errfacet1 && qh outside_err > REALmax/2)
qh_errexit2( qh_ERRprec, errfacet1, errfacet2 );
else if (errfacet1)
; /* the error was logged to qh.ferr but does not effect the output */
trace0((qh ferr, "qh_check_points: max distance outside %2.2g\n", maxdist));
}
} /* check_points */
/*-<a href="qh-c.htm#poly"
>-------------------------------</a><a name="checkconvex">-</a>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -