libqhull: poly.h Source File

Go to the documentation of this file.
00001 /*<html><pre>  -<a                             href="qh-poly.htm"
00002   >-------------------------------</a><a name="TOP">-</a>
00003 
00004    poly.h
00005    header file for poly.c and poly2.c
00006 
00007    see qh-poly.htm, libqhull.h and poly.c
00008 
00009    Copyright (c) 1993-2011 The Geometry Center.
00010    $Id: //main/2011/qhull/src/libqhull/poly.h#2 $$Change: 1342 $
00011    $DateTime: 2011/03/07 21:55:47 $$Author: bbarber $
00012 */
00013 
00014 #ifndef qhDEFpoly
00015 #define qhDEFpoly 1
00016 
00017 #include "libqhull.h"
00018 
00019 /*===============   constants ========================== */
00020 
00021 /*-<a                             href="qh-geom.htm#TOC"
00022   >--------------------------------</a><a name="ALGORITHMfault">-</a>
00023 
00024   ALGORITHMfault
00025     use as argument to checkconvex() to report errors during buildhull
00026 */
00027 #define qh_ALGORITHMfault 0
00028 
00029 /*-<a                             href="qh-poly.htm#TOC"
00030   >--------------------------------</a><a name="DATAfault">-</a>
00031 
00032   DATAfault
00033     use as argument to checkconvex() to report errors during initialhull
00034 */
00035 #define qh_DATAfault 1
00036 
00037 /*-<a                             href="qh-poly.htm#TOC"
00038   >--------------------------------</a><a name="DUPLICATEridge">-</a>
00039 
00040   DUPLICATEridge
00041     special value for facet->neighbor to indicate a duplicate ridge
00042 
00043   notes:
00044     set by matchneighbor, used by matchmatch and mark_dupridge
00045 */
00046 #define qh_DUPLICATEridge (facetT *)1L
00047 
00048 /*-<a                             href="qh-poly.htm#TOC"
00049   >--------------------------------</a><a name="MERGEridge">-</a>
00050 
00051   MERGEridge       flag in facet
00052     special value for facet->neighbor to indicate a merged ridge
00053 
00054   notes:
00055     set by matchneighbor, used by matchmatch and mark_dupridge
00056 */
00057 #define qh_MERGEridge (facetT *)2L
00058 
00059 
00060 /*============ -structures- ====================*/
00061 
00062 /*=========== -macros- =========================*/
00063 
00064 /*-<a                             href="qh-poly.htm#TOC"
00065   >--------------------------------</a><a name="FORALLfacet_">-</a>
00066 
00067   FORALLfacet_( facetlist ) { ... }
00068     assign 'facet' to each facet in facetlist
00069 
00070   notes:
00071     uses 'facetT *facet;'
00072     assumes last facet is a sentinel
00073 
00074   see:
00075     FORALLfacets
00076 */
00077 #define FORALLfacet_( facetlist ) if (facetlist ) for ( facet=( facetlist ); facet && facet->next; facet= facet->next )
00078 
00079 /*-<a                             href="qh-poly.htm#TOC"
00080   >--------------------------------</a><a name="FORALLnew_facets">-</a>
00081 
00082   FORALLnew_facets { ... }
00083     assign 'newfacet' to each facet in qh.newfacet_list
00084 
00085   notes:
00086     uses 'facetT *newfacet;'
00087     at exit, newfacet==NULL
00088 */
00089 #define FORALLnew_facets for ( newfacet=qh newfacet_list;newfacet && newfacet->next;newfacet=newfacet->next )
00090 
00091 /*-<a                             href="qh-poly.htm#TOC"
00092   >--------------------------------</a><a name="FORALLvertex_">-</a>
00093 
00094   FORALLvertex_( vertexlist ) { ... }
00095     assign 'vertex' to each vertex in vertexlist
00096 
00097   notes:
00098     uses 'vertexT *vertex;'
00099     at exit, vertex==NULL
00100 */
00101 #define FORALLvertex_( vertexlist ) for (vertex=( vertexlist );vertex && vertex->next;vertex= vertex->next )
00102 
00103 /*-<a                             href="qh-poly.htm#TOC"
00104   >--------------------------------</a><a name="FORALLvisible_facets">-</a>
00105 
00106   FORALLvisible_facets { ... }
00107     assign 'visible' to each visible facet in qh.visible_list
00108 
00109   notes:
00110     uses 'vacetT *visible;'
00111     at exit, visible==NULL
00112 */
00113 #define FORALLvisible_facets for (visible=qh visible_list; visible && visible->visible; visible= visible->next)
00114 
00115 /*-<a                             href="qh-poly.htm#TOC"
00116   >--------------------------------</a><a name="FORALLsame_">-</a>
00117 
00118   FORALLsame_( newfacet ) { ... }
00119     assign 'same' to each facet in newfacet->f.samecycle
00120 
00121   notes:
00122     uses 'facetT *same;'
00123     stops when it returns to newfacet
00124 */
00125 #define FORALLsame_(newfacet) for (same= newfacet->f.samecycle; same != newfacet; same= same->f.samecycle)
00126 
00127 /*-<a                             href="qh-poly.htm#TOC"
00128   >--------------------------------</a><a name="FORALLsame_cycle_">-</a>
00129 
00130   FORALLsame_cycle_( newfacet ) { ... }
00131     assign 'same' to each facet in newfacet->f.samecycle
00132 
00133   notes:
00134     uses 'facetT *same;'
00135     at exit, same == NULL
00136 */
00137 #define FORALLsame_cycle_(newfacet) \
00138      for (same= newfacet->f.samecycle; \
00139          same; same= (same == newfacet ?  NULL : same->f.samecycle))
00140 
00141 /*-<a                             href="qh-poly.htm#TOC"
00142   >--------------------------------</a><a name="FOREACHneighborA_">-</a>
00143 
00144   FOREACHneighborA_( facet ) { ... }
00145     assign 'neighborA' to each neighbor in facet->neighbors
00146 
00147   FOREACHneighborA_( vertex ) { ... }
00148     assign 'neighborA' to each neighbor in vertex->neighbors
00149 
00150   declare:
00151     facetT *neighborA, **neighborAp;
00152 
00153   see:
00154     <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a>
00155 */
00156 #define FOREACHneighborA_(facet)  FOREACHsetelement_(facetT, facet->neighbors, neighborA)
00157 
00158 /*-<a                             href="qh-poly.htm#TOC"
00159   >--------------------------------</a><a name="FOREACHvisible_">-</a>
00160 
00161   FOREACHvisible_( facets ) { ... }
00162     assign 'visible' to each facet in facets
00163 
00164   notes:
00165     uses 'facetT *facet, *facetp;'
00166     see <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a>
00167 */
00168 #define FOREACHvisible_(facets) FOREACHsetelement_(facetT, facets, visible)
00169 
00170 /*-<a                             href="qh-poly.htm#TOC"
00171   >--------------------------------</a><a name="FOREACHnewfacet_">-</a>
00172 
00173   FOREACHnewfacet_( facets ) { ... }
00174     assign 'newfacet' to each facet in facets
00175 
00176   notes:
00177     uses 'facetT *newfacet, *newfacetp;'
00178     see <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a>
00179 */
00180 #define FOREACHnewfacet_(facets) FOREACHsetelement_(facetT, facets, newfacet)
00181 
00182 /*-<a                             href="qh-poly.htm#TOC"
00183   >--------------------------------</a><a name="FOREACHvertexA_">-</a>
00184 
00185   FOREACHvertexA_( vertices ) { ... }
00186     assign 'vertexA' to each vertex in vertices
00187 
00188   notes:
00189     uses 'vertexT *vertexA, *vertexAp;'
00190     see <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a>
00191 */
00192 #define FOREACHvertexA_(vertices) FOREACHsetelement_(vertexT, vertices, vertexA)
00193 
00194 /*-<a                             href="qh-poly.htm#TOC"
00195   >--------------------------------</a><a name="FOREACHvertexreverse12_">-</a>
00196 
00197   FOREACHvertexreverse12_( vertices ) { ... }
00198     assign 'vertex' to each vertex in vertices
00199     reverse order of first two vertices
00200 
00201   notes:
00202     uses 'vertexT *vertex, *vertexp;'
00203     see <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a>
00204 */
00205 #define FOREACHvertexreverse12_(vertices) FOREACHsetelementreverse12_(vertexT, vertices, vertex)
00206 
00207 
00208 /*=============== prototypes poly.c in alphabetical order ================*/
00209 
00210 void    qh_appendfacet(facetT *facet);
00211 void    qh_appendvertex(vertexT *vertex);
00212 void    qh_attachnewfacets(void);
00213 boolT   qh_checkflipped(facetT *facet, realT *dist, boolT allerror);
00214 void    qh_delfacet(facetT *facet);
00215 void    qh_deletevisible(void /*qh visible_list, qh horizon_list*/);
00216 setT   *qh_facetintersect(facetT *facetA, facetT *facetB, int *skipAp,int *skipBp, int extra);
00217 int     qh_gethash(int hashsize, setT *set, int size, int firstindex, void *skipelem);
00218 facetT *qh_makenewfacet(setT *vertices, boolT toporient, facetT *facet);
00219 void    qh_makenewplanes(void /* newfacet_list */);
00220 facetT *qh_makenew_nonsimplicial(facetT *visible, vertexT *apex, int *numnew);
00221 facetT *qh_makenew_simplicial(facetT *visible, vertexT *apex, int *numnew);
00222 void    qh_matchneighbor(facetT *newfacet, int newskip, int hashsize,
00223                           int *hashcount);
00224 void    qh_matchnewfacets(void);
00225 boolT   qh_matchvertices(int firstindex, setT *verticesA, int skipA,
00226                           setT *verticesB, int *skipB, boolT *same);
00227 facetT *qh_newfacet(void);
00228 ridgeT *qh_newridge(void);
00229 int     qh_pointid(pointT *point);
00230 void    qh_removefacet(facetT *facet);
00231 void    qh_removevertex(vertexT *vertex);
00232 void    qh_updatevertices(void);
00233 
00234 
00235 /*========== -prototypes poly2.c in alphabetical order ===========*/
00236 
00237 void    qh_addhash(void* newelem, setT *hashtable, int hashsize, int hash);
00238 void    qh_check_bestdist(void);
00239 void    qh_check_maxout(void);
00240 void    qh_check_output(void);
00241 void    qh_check_point(pointT *point, facetT *facet, realT *maxoutside, realT *maxdist, facetT **errfacet1, facetT **errfacet2);
00242 void    qh_check_points(void);
00243 void    qh_checkconvex(facetT *facetlist, int fault);
00244 void    qh_checkfacet(facetT *facet, boolT newmerge, boolT *waserrorp);
00245 void    qh_checkflipped_all(facetT *facetlist);
00246 void    qh_checkpolygon(facetT *facetlist);
00247 void    qh_checkvertex(vertexT *vertex);
00248 void    qh_clearcenters(qh_CENTER type);
00249 void    qh_createsimplex(setT *vertices);
00250 void    qh_delridge(ridgeT *ridge);
00251 void    qh_delvertex(vertexT *vertex);
00252 setT   *qh_facet3vertex(facetT *facet);
00253 facetT *qh_findbestfacet(pointT *point, boolT bestoutside,
00254            realT *bestdist, boolT *isoutside);
00255 facetT *qh_findbestlower(facetT *upperfacet, pointT *point, realT *bestdistp, int *numpart);
00256 facetT *qh_findfacet_all(pointT *point, realT *bestdist, boolT *isoutside,
00257                           int *numpart);
00258 int     qh_findgood(facetT *facetlist, int goodhorizon);
00259 void    qh_findgood_all(facetT *facetlist);
00260 void    qh_furthestnext(void /* qh facet_list */);
00261 void    qh_furthestout(facetT *facet);
00262 void    qh_infiniteloop(facetT *facet);
00263 void    qh_initbuild(void);
00264 void    qh_initialhull(setT *vertices);
00265 setT   *qh_initialvertices(int dim, setT *maxpoints, pointT *points, int numpoints);
00266 vertexT *qh_isvertex(pointT *point, setT *vertices);
00267 vertexT *qh_makenewfacets(pointT *point /*horizon_list, visible_list*/);
00268 void    qh_matchduplicates(facetT *atfacet, int atskip, int hashsize, int *hashcount);
00269 void    qh_nearcoplanar(void /* qh.facet_list */);
00270 vertexT *qh_nearvertex(facetT *facet, pointT *point, realT *bestdistp);
00271 int     qh_newhashtable(int newsize);
00272 vertexT *qh_newvertex(pointT *point);
00273 ridgeT *qh_nextridge3d(ridgeT *atridge, facetT *facet, vertexT **vertexp);
00274 void    qh_outcoplanar(void /* facet_list */);
00275 pointT *qh_point(int id);
00276 void    qh_point_add(setT *set, pointT *point, void *elem);
00277 setT   *qh_pointfacet(void /*qh facet_list*/);
00278 setT   *qh_pointvertex(void /*qh facet_list*/);
00279 void    qh_prependfacet(facetT *facet, facetT **facetlist);
00280 void    qh_printhashtable(FILE *fp);
00281 void    qh_printlists(void);
00282 void    qh_resetlists(boolT stats, boolT resetVisible /*qh newvertex_list newfacet_list visible_list*/);
00283 void    qh_setvoronoi_all(void);
00284 void    qh_triangulate(void /*qh facet_list*/);
00285 void    qh_triangulate_facet(facetT *facetA, vertexT **first_vertex);
00286 void    qh_triangulate_link(facetT *oldfacetA, facetT *facetA, facetT *oldfacetB, facetT *facetB);
00287 void    qh_triangulate_mirror(facetT *facetA, facetT *facetB);
00288 void    qh_triangulate_null(facetT *facetA);
00289 void    qh_vertexintersect(setT **vertexsetA,setT *vertexsetB);
00290 setT   *qh_vertexintersect_new(setT *vertexsetA,setT *vertexsetB);
00291 void    qh_vertexneighbors(void /*qh facet_list*/);
00292 boolT   qh_vertexsubset(setT *vertexsetA, setT *vertexsetB);
00293 
00294 
00295 #endif /* qhDEFpoly */