libqhull: merge.h Source File

Go to the documentation of this file.
00001 /*<html><pre>  -<a                             href="qh-merge.htm"
00002   >-------------------------------</a><a name="TOP">-</a>
00003 
00004    merge.h
00005    header file for merge.c
00006 
00007    see qh-merge.htm and merge.c
00008 
00009    Copyright (c) 1993-2011 C.B. Barber.
00010    $Id: //main/2011/qhull/src/libqhull/merge.h#2 $$Change: 1342 $
00011    $DateTime: 2011/03/07 21:55:47 $$Author: bbarber $
00012 */
00013 
00014 #ifndef qhDEFmerge
00015 #define qhDEFmerge 1
00016 
00017 #include "libqhull.h"
00018 
00019 
00020 /*============ -constants- ==============*/
00021 
00022 /*-<a                             href="qh-merge.htm#TOC"
00023   >--------------------------------</a><a name="qh_ANGLEredundant">-</a>
00024 
00025   qh_ANGLEredundant
00026     indicates redundant merge in mergeT->angle
00027 */
00028 #define qh_ANGLEredundant 6.0
00029 
00030 /*-<a                             href="qh-merge.htm#TOC"
00031   >--------------------------------</a><a name="qh_ANGLEdegen">-</a>
00032 
00033   qh_ANGLEdegen
00034     indicates degenerate facet in mergeT->angle
00035 */
00036 #define qh_ANGLEdegen     5.0
00037 
00038 /*-<a                             href="qh-merge.htm#TOC"
00039   >--------------------------------</a><a name="qh_ANGLEconcave">-</a>
00040 
00041   qh_ANGLEconcave
00042     offset to indicate concave facets in mergeT->angle
00043 
00044   notes:
00045     concave facets are assigned the range of [2,4] in mergeT->angle
00046     roundoff error may make the angle less than 2
00047 */
00048 #define qh_ANGLEconcave  1.5
00049 
00050 /*-<a                             href="qh-merge.htm#TOC"
00051   >--------------------------------</a><a name="MRG">-</a>
00052 
00053   MRG... (mergeType)
00054     indicates the type of a merge (mergeT->type)
00055 */
00056 typedef enum {  /* in sort order for facet_mergeset */
00057   MRGnone= 0,
00058   MRGcoplanar,          /* centrum coplanar */
00059   MRGanglecoplanar,     /* angle coplanar */
00060                         /* could detect half concave ridges */
00061   MRGconcave,           /* concave ridge */
00062   MRGflip,              /* flipped facet. facet1 == facet2 */
00063   MRGridge,             /* duplicate ridge (qh_MERGEridge) */
00064                         /* degen and redundant go onto degen_mergeset */
00065   MRGdegen,             /* degenerate facet (!enough neighbors) facet1 == facet2 */
00066   MRGredundant,         /* redundant facet (vertex subset) */
00067                         /* merge_degenredundant assumes degen < redundant */
00068   MRGmirror,            /* mirror facet from qh_triangulate */
00069   ENDmrg
00070 } mergeType;
00071 
00072 /*-<a                             href="qh-merge.htm#TOC"
00073   >--------------------------------</a><a name="qh_MERGEapex">-</a>
00074 
00075   qh_MERGEapex
00076     flag for qh_mergefacet() to indicate an apex merge
00077 */
00078 #define qh_MERGEapex     True
00079 
00080 /*============ -structures- ====================*/
00081 
00082 /*-<a                             href="qh-merge.htm#TOC"
00083   >--------------------------------</a><a name="mergeT">-</a>
00084 
00085   mergeT
00086     structure used to merge facets
00087 */
00088 
00089 typedef struct mergeT mergeT;
00090 struct mergeT {         /* initialize in qh_appendmergeset */
00091   realT   angle;        /* angle between normals of facet1 and facet2 */
00092   facetT *facet1;       /* will merge facet1 into facet2 */
00093   facetT *facet2;
00094   mergeType type;
00095 };
00096 
00097 
00098 /*=========== -macros- =========================*/
00099 
00100 /*-<a                             href="qh-merge.htm#TOC"
00101   >--------------------------------</a><a name="FOREACHmerge_">-</a>
00102 
00103   FOREACHmerge_( merges ) {...}
00104     assign 'merge' to each merge in merges
00105 
00106   notes:
00107     uses 'mergeT *merge, **mergep;'
00108     if qh_mergefacet(),
00109       restart since qh.facet_mergeset may change
00110     see <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a>
00111 */
00112 #define FOREACHmerge_( merges ) FOREACHsetelement_(mergeT, merges, merge)
00113 
00114 /*============ prototypes in alphabetical order after pre/postmerge =======*/
00115 
00116 void    qh_premerge(vertexT *apex, realT maxcentrum, realT maxangle);
00117 void    qh_postmerge(const char *reason, realT maxcentrum, realT maxangle,
00118              boolT vneighbors);
00119 void    qh_all_merges(boolT othermerge, boolT vneighbors);
00120 void    qh_appendmergeset(facetT *facet, facetT *neighbor, mergeType mergetype, realT *angle);
00121 setT   *qh_basevertices( facetT *samecycle);
00122 void    qh_checkconnect(void /* qh new_facets */);
00123 boolT   qh_checkzero(boolT testall);
00124 int     qh_compareangle(const void *p1, const void *p2);
00125 int     qh_comparemerge(const void *p1, const void *p2);
00126 int     qh_comparevisit(const void *p1, const void *p2);
00127 void    qh_copynonconvex(ridgeT *atridge);
00128 void    qh_degen_redundant_facet(facetT *facet);
00129 void    qh_degen_redundant_neighbors(facetT *facet, facetT *delfacet);
00130 vertexT *qh_find_newvertex(vertexT *oldvertex, setT *vertices, setT *ridges);
00131 void    qh_findbest_test(boolT testcentrum, facetT *facet, facetT *neighbor,
00132            facetT **bestfacet, realT *distp, realT *mindistp, realT *maxdistp);
00133 facetT *qh_findbestneighbor(facetT *facet, realT *distp, realT *mindistp, realT *maxdistp);
00134 void    qh_flippedmerges(facetT *facetlist, boolT *wasmerge);
00135 void    qh_forcedmerges( boolT *wasmerge);
00136 void    qh_getmergeset(facetT *facetlist);
00137 void    qh_getmergeset_initial(facetT *facetlist);
00138 void    qh_hashridge(setT *hashtable, int hashsize, ridgeT *ridge, vertexT *oldvertex);
00139 ridgeT *qh_hashridge_find(setT *hashtable, int hashsize, ridgeT *ridge,
00140               vertexT *vertex, vertexT *oldvertex, int *hashslot);
00141 void    qh_makeridges(facetT *facet);
00142 void    qh_mark_dupridges(facetT *facetlist);
00143 void    qh_maydropneighbor(facetT *facet);
00144 int     qh_merge_degenredundant(void);
00145 void    qh_merge_nonconvex( facetT *facet1, facetT *facet2, mergeType mergetype);
00146 void    qh_mergecycle(facetT *samecycle, facetT *newfacet);
00147 void    qh_mergecycle_all(facetT *facetlist, boolT *wasmerge);
00148 void    qh_mergecycle_facets( facetT *samecycle, facetT *newfacet);
00149 void    qh_mergecycle_neighbors(facetT *samecycle, facetT *newfacet);
00150 void    qh_mergecycle_ridges(facetT *samecycle, facetT *newfacet);
00151 void    qh_mergecycle_vneighbors( facetT *samecycle, facetT *newfacet);
00152 void    qh_mergefacet(facetT *facet1, facetT *facet2, realT *mindist, realT *maxdist, boolT mergeapex);
00153 void    qh_mergefacet2d(facetT *facet1, facetT *facet2);
00154 void    qh_mergeneighbors(facetT *facet1, facetT *facet2);
00155 void    qh_mergeridges(facetT *facet1, facetT *facet2);
00156 void    qh_mergesimplex(facetT *facet1, facetT *facet2, boolT mergeapex);
00157 void    qh_mergevertex_del(vertexT *vertex, facetT *facet1, facetT *facet2);
00158 void    qh_mergevertex_neighbors(facetT *facet1, facetT *facet2);
00159 void    qh_mergevertices(setT *vertices1, setT **vertices);
00160 setT   *qh_neighbor_intersections(vertexT *vertex);
00161 void    qh_newvertices(setT *vertices);
00162 boolT   qh_reducevertices(void);
00163 vertexT *qh_redundant_vertex(vertexT *vertex);
00164 boolT   qh_remove_extravertices(facetT *facet);
00165 vertexT *qh_rename_sharedvertex(vertexT *vertex, facetT *facet);
00166 void    qh_renameridgevertex(ridgeT *ridge, vertexT *oldvertex, vertexT *newvertex);
00167 void    qh_renamevertex(vertexT *oldvertex, vertexT *newvertex, setT *ridges,
00168                         facetT *oldfacet, facetT *neighborA);
00169 boolT   qh_test_appendmerge(facetT *facet, facetT *neighbor);
00170 boolT   qh_test_vneighbors(void /* qh newfacet_list */);
00171 void    qh_tracemerge(facetT *facet1, facetT *facet2);
00172 void    qh_tracemerging(void);
00173 void    qh_updatetested( facetT *facet1, facetT *facet2);
00174 setT   *qh_vertexridges(vertexT *vertex);
00175 void    qh_vertexridges_facet(vertexT *vertex, facetT *facet, setT **ridges);
00176 void    qh_willdelete(facetT *facet, facetT *replace);
00177 
00178 #endif /* qhDEFmerge */