/* poly.h -- header file for poly.c and poly2.c see README, qhull.h and poly.c copyright (c) 1993, 1997, The Geometry Center */ #ifndef qhDEFpoly #define qhDEFpoly 1 /*----------------------------------------------- -constants- for calling checkconvex() -ALGORITHMfault flag for checkconvex for error during buildhull -DATAfault flag for checkconvex for error during initialhull set by matchneighbor, used by matchmatch and mark_dupridge -DUPLICATEridge flag in facet->neighbors to indicate duplicated ridge -MERGEridge flag in facet->neighbors to indicate merged ridge */ #define qh_ALGORITHMfault 0 #define qh_DATAfault 1 #define qh_DUPLICATEridge (facetT *) 1 #define qh_MERGEridge (facetT *) 2 /* ============ -structures- ==================== */ /* ---------------------------------------------- -hashentryT- hash table entry for matching sub-ridges in makecone() */ typedef struct hashentryT hashentryT; struct hashentryT { facetT *facet; /* facet */ hashentryT *next; /* next hash table entry for this bucket */ unsigned skipindex; /* skipped vertex in facet, for orientation */ }; /* =========== -macros- ========================= */ /* ---------------------------------------------- -FOREACH... and FORALL... -- standard for loops see qhull.h for notes */ #define FORALLfacet_(facetlist) if (facetlist) for(facet=(facetlist);facet && facet->next;facet=facet->next) #define FORALLnew_facets for(newfacet=qh newfacet_list;newfacet && newfacet->next;newfacet=newfacet->next) #define FORALLvertex_(vertexlist) for (vertex=(vertexlist);vertex && vertex->next;vertex= vertex->next) #define FORALLvisible_facets for (visible=qh visible_list; visible && visible->visible; visible= visible->next) /* FORALLsame - only for newfacets, same_cycle includes facet */ #define FORALLsame_(newfacet) for (same= newfacet->f.samecycle; same != newfacet; same= same->f.samecycle) /* FORALLsame_cycle_ - only for newfacets, last same is newfacet */ #define FORALLsame_cycle_(newfacet) \ for (same= newfacet->f.samecycle; \ same; same= (same == newfacet ? NULL : same->f.samecycle)) #define FOREACHentry_(entries) FOREACHsetelement_(hashentryT, entries, entry) #define FOREACHvisible_(facets) FOREACHsetelement_(facetT, facets, visible) #define FOREACHnewfacet_(facets) FOREACHsetelement_(facetT, facets, newfacet) #define FOREACHvertexA_(vertices) FOREACHsetelement_(vertexT, vertices, vertexA) #define FOREACHvertexreverse12_(vertices) FOREACHsetelementreverse12_(vertexT, vertices, vertex) /* ======= -functions =========== see poly.c for definitions Facetlist functions -appendfacet appends facet to end of qh facet_list, -prependfacet prepends facet to start of facetlist -removefacet unlinks facet from qh facet_list, -resetlists reset newvertex_list, newfacet_list, visible_list -initialhull construct the initial hull as a simplex of vertices -setvoronoi_all compute Voronoi centers for all facets -findfacet find facet that is furthest below a point -findgood identify good facets for qh ONLYgood -findgood_all identify good facets for qh PRINTgood -furthestnext move facet with furthest of furthest points to facet_next Facet functions -createsimplex creates a simplex of facets from a set of vertices -makenewfacet creates a toporient? facet from vertices and apex -makenewfacets make new facets from point, horizon facets, and visible facets -makenewplanes make new hyperplanes for facets -makenew_nonsimplicial make new facets for ridges of visible facets -makenew_simplicial make new facets for horizon neighbors -attachnewfacets attach new facets in qh newfacet_list to the horizon -makeadjacencies make adjacencies for non-simplicial facets -furthestout make furthest outside point the last point of outsideset -outcoplanar move points from outsideset to coplanarset Vertex, ridge, and point functions -appendvertex appends vertex to end of qh vertex_list, -removevertex unlinks vertex from qh vertex_list, -point return point for a point id, or NULL if unknown -pointid return id for a point, or -1 if not known -nearvertex return nearest vertex to point -vertexintersect intersects two vertex sets -vertexintersect_new intersects two vertex sets -facetintersect intersect simplicial facets -isvertex true if point is in the vertex set -vertexsubset returns True if vertexsetA is a subset of vertexsetB -nextridge3d iterate each ridge and vertex for a 3d facet -facet3vertex return oriented vertex set for 3-d facet -vertexneighhbors for each vertex in hull, determine facet neighbors -pointfacet return temporary set of facets indexed by point id -pointvertex return temporary set of vertices indexed by point id -initialvertices return non-singular set of initial vertices -updatevertices update vertex neighbors and delete interior vertices Hashtable functions -addhash add hash element to linear hash table if not already there -newhashtable allocates a new qh hash_table -gethash return hashvalue for a set with firstindex -matchduplicates match duplicate ridges in hashtable -matchnewfacets match newfacets in to their newfacet neighbors -matchneighbor try to match subridge of newfacet with a neighbor -matchvertices tests whether a facet and hashentry match at a ridge -printhashtable print hash table Allocation and deallocation functions -newfacet creates and allocates space for a facet -newridge creates and allocates space for a ridge -newvertex creates and allocates space for a vertex -deletevisible delete visible facets and vertices -delfacet frees up the memory occupied by a facet -delridge deletes ridge from data structures it belongs to and frees up the -delvertex deletes vertex and its memory -clearcenters clear old data from facet->center Check functions -check_bestdist check that points are not outside their best facet -check_maxout updates max_outside, checks all points against bestfacet -check_output performs the checks at the end of qhull algorithm -check_point check that point is not outside facet -check_points checks that all points are inside all facets -checkconvex check that each ridge in facetlist is convex -checkfacet checks for consistency errors in facet -checkflipped checks facet orientation to the interior point -checkflipped_all checks facet orientation for a facet list -checkpolygon checks the correctness of the structure -checkvertex check vertex for consistency -infiniteloop report infinite loop error due to facet -printlists print out facet list for debugging */ /*---------- -prototypes poly.c in alphabetical order -----------*/ void qh_appendfacet(facetT *facet); void qh_appendvertex(vertexT *vertex); void qh_attachnewfacets (void); boolT qh_checkflipped (facetT *facet, realT *dist, boolT allerror); void qh_delfacet(facetT *facet); void qh_deletevisible(void /*qh visible_list, qh horizon_list*/); setT *qh_facetintersect (facetT *facetA, facetT *facetB, int *skipAp,int *skipBp, int extra); unsigned qh_gethash (int hashsize, setT *set, int size, int firstindex, void *skipelem); facetT *qh_makenewfacet(setT *vertices, boolT toporient, facetT *facet); void qh_makenewplanes ( void /* newfacet_list */); facetT *qh_makenew_nonsimplicial (facetT *visible, vertexT *apex, int *numnew); facetT *qh_makenew_simplicial (facetT *visible, vertexT *apex, int *numnew); void qh_matchneighbor (facetT *newfacet, int newskip, int hashsize, int *hashcount); void qh_matchnewfacets (void); boolT qh_matchvertices (int firstindex, setT *verticesA, int skipA, setT *verticesB, int *skipB, boolT *same); facetT *qh_newfacet(void); ridgeT *qh_newridge(void); int qh_pointid (pointT *point); void qh_removefacet(facetT *facet); void qh_removevertex(vertexT *vertex); void qh_updatevertices (void); /*---------- -prototypes poly2.c in alphabetical order -----------*/ void qh_addhash (void* newelem, setT *hashtable, int hashsize, unsigned hash); void qh_check_bestdist (void); void qh_check_maxout (void); void qh_check_output (void); void qh_check_point (pointT *point, facetT *facet, realT *maxoutside, facetT **errfacet1, facetT **errfacet2); void qh_check_points(void); void qh_checkconvex(facetT *facetlist, int fault); void qh_checkfacet(facetT *facet, boolT newmerge, boolT *waserrorp); void qh_checkflipped_all (facetT *facetlist); void qh_checkpolygon(facetT *facetlist); void qh_checkvertex (vertexT *vertex); void qh_clearcenters (qh_CENTER type); void qh_createsimplex(setT *vertices); void qh_delridge(ridgeT *ridge); void qh_delvertex (vertexT *vertex); setT *qh_facet3vertex (facetT *facet); facetT *qh_findbestfacet (pointT *point, boolT bestoutside, realT *bestdist, boolT *isoutside); facetT *qh_findfacet_all (pointT *point, realT *bestdist, boolT *isoutside, int *numpart); int qh_findgood (facetT *facetlist, int goodhorizon); void qh_findgood_all (facetT *facetlist); void qh_furthestnext (void /* qh facet_list */); void qh_furthestout (facetT *facet); void qh_infiniteloop (facetT *facet); void qh_initialhull(setT *vertices); setT *qh_initialvertices(int dim, setT *maxpoints, pointT *points, int numpoints); vertexT *qh_isvertex (pointT *point, setT *vertices); vertexT *qh_makenewfacets (pointT *point /*horizon_list, visible_list*/); void qh_matchduplicates (facetT *atfacet, int atskip, int hashsize, int *hashcount); vertexT *qh_nearvertex (facetT *facet, pointT *point, realT *bestdistp); int qh_newhashtable(int newsize); vertexT *qh_newvertex(pointT *point); ridgeT *qh_nextridge3d (ridgeT *atridge, facetT *facet, vertexT **vertexp); void qh_outcoplanar (void /* facet_list */); pointT *qh_point (int id); void qh_point_add (setT *set, pointT *point, void *elem); setT *qh_pointfacet (void /*qh facet_list*/); setT *qh_pointvertex (void /*qh facet_list*/); void qh_prependfacet(facetT *facet, facetT **facetlist); void qh_printhashtable(FILE *fp); void qh_printlists (void); void qh_resetlists (boolT stats /*qh newvertex_list newfacet_list visible_list*/); void qh_setvoronoi_all (void); void qh_vertexintersect(setT **vertexsetA,setT *vertexsetB); setT *qh_vertexintersect_new(setT *vertexsetA,setT *vertexsetB); void qh_vertexneighbors (void /*qh facet_list*/); boolT qh_vertexsubset(setT *vertexsetA, setT *vertexsetB); #endif /* qhDEFpoly */