include/libqhull/merge.h

0001 /*<html><pre>  -<a                             href="qh-merge.htm"
0002   >-------------------------------</a><a name="TOP">-</a>
0003
0004    merge.h
0005    header file for merge.c
0006
0007    see qh-merge.htm and merge.c
0008
0009    Copyright (c) 1993-2020 C.B. Barber.
0010    $Id: //main/2019/qhull/src/libqhull/merge.h#3 $$Change: 2953 $
0011    $DateTime: 2020/05/21 22:05:32 $$Author: bbarber $
0012 */
0013
0014 #ifndef qhDEFmerge
0015 #define qhDEFmerge 1
0016
0017 #include "libqhull.h"
0018
0019
0020 /*============ -constants- ==============*/
0021
0022 /*-<a                             href="qh-merge.htm#TOC"
0023   >--------------------------------</a><a name="qh_ANGLEnone">-</a>
0024
0025   qh_ANGLEnone
0026     indicates missing angle for mergeT->angle
0027 */
0028 #define qh_ANGLEnone 2.0
0029
0030 /*-<a                             href="qh-merge.htm#TOC"
0031   >--------------------------------</a><a name="MRG">-</a>
0032
0033   MRG... (mergeType)
0034     indicates the type of a merge (mergeT->type)
0035     MRGcoplanar...MRGtwisted set by qh_test_centrum_merge, qh_test_nonsimplicial_merge
0036 */
0037 typedef enum {  /* must match mergetypes[] */
0038   MRGnone= 0,
0039                   /* MRGcoplanar..MRGtwisted go into qh.facet_mergeset for qh_all_merges
0040                      qh_compare_facetmerge selects lower mergetypes for merging first */
0041   MRGcoplanar,          /* (1) centrum coplanar if centrum ('Cn') or vertex not clearly above or below neighbor */
0042   MRGanglecoplanar,     /* (2) angle coplanar if angle ('An') is coplanar */
0043   MRGconcave,           /* (3) concave ridge */
0044   MRGconcavecoplanar,   /* (4) concave and coplanar ridge, one side concave, other side coplanar */
0045   MRGtwisted,           /* (5) twisted ridge, both concave and convex, facet1 is wider */
0046                   /* MRGflip go into qh.facet_mergeset for qh_flipped_merges */
0047   MRGflip,              /* (6) flipped facet if qh.interior_point is above facet, w/ facet1 == facet2 */
0048                   /* MRGdupridge go into qh.facet_mergeset for qh_forcedmerges */
0049   MRGdupridge,          /* (7) dupridge if more than two neighbors.  Set by qh_mark_dupridges for qh_MERGEridge */
0050                   /* MRGsubridge and MRGvertices go into vertex_mergeset */
0051   MRGsubridge,          /* (8) merge pinched vertex to remove the subridge of a MRGdupridge */
0052   MRGvertices,          /* (9) merge pinched vertex to remove a facet's ridges with the same vertices */
0053                   /* MRGdegen, MRGredundant, and MRGmirror go into qh.degen_mergeset */
0054   MRGdegen,             /* (10) degenerate facet (!enough neighbors) facet1 == facet2 */
0055   MRGredundant,         /* (11) redundant facet (vertex subset) */
0056                         /* merge_degenredundant assumes degen < redundant */
0057   MRGmirror,            /* (12) mirror facets: same vertices due to null facets in qh_triangulate
0058                            f.redundant for both facets*/
0059                   /* MRGcoplanarhorizon for qh_mergecycle_all only */
0060   MRGcoplanarhorizon,   /* (13) new facet coplanar with the horizon (qh_mergecycle_all) */
0061   ENDmrg
0062 } mergeType;
0063
0064 /*-<a                             href="qh-merge.htm#TOC"
0065   >--------------------------------</a><a name="qh_MERGEapex">-</a>
0066
0067   qh_MERGEapex
0068     flag for qh_mergefacet() to indicate an apex merge
0069 */
0070 #define qh_MERGEapex     True
0071
0072 /*============ -structures- ====================*/
0073
0074 /*-<a                             href="qh-merge.htm#TOC"
0075   >--------------------------------</a><a name="mergeT">-</a>
0076
0077   mergeT
0078     structure used to merge facets
0079 */
0080
0081 typedef struct mergeT mergeT;
0082 struct mergeT {         /* initialize in qh_appendmergeset */
0083   realT   angle;        /* cosine of angle between normals of facet1 and facet2,
0084                            null value and right angle is 0.0, coplanar is 1.0, narrow is -1.0 */
0085   realT   distance;     /* absolute value of distance between vertices, centrum and facet, or vertex and facet */
0086   facetT *facet1;       /* will merge facet1 into facet2 */
0087   facetT *facet2;
0088   vertexT *vertex1;     /* will merge vertext1 into vertex2 for MRGsubridge or MRGvertices */
0089   vertexT *vertex2;
0090   ridgeT  *ridge1;      /* the duplicate ridges resolved by MRGvertices */
0091   ridgeT  *ridge2;      /* merge is deleted if either ridge is deleted (qh_delridge) */
0092   mergeType mergetype;
0093 };
0094
0095
0096 /*=========== -macros- =========================*/
0097
0098 /*-<a                             href="qh-merge.htm#TOC"
0099   >--------------------------------</a><a name="FOREACHmerge_">-</a>
0100
0101   FOREACHmerge_( merges ) {...}
0102     assign 'merge' to each merge in merges
0103
0104   notes:
0105     uses 'mergeT *merge, **mergep;'
0106     if qh_mergefacet(),
0107       restart or use qh_setdellast() since qh.facet_mergeset may change
0108     see <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a>
0109 */
0110 #define FOREACHmerge_(merges) FOREACHsetelement_(mergeT, merges, merge)
0111
0112 /*-<a                             href="qh-poly.htm#TOC"
0113   >--------------------------------</a><a name="FOREACHmergeA_">-</a>
0114
0115   FOREACHmergeA_( vertices ) { ... }
0116     assign 'mergeA' to each merge in merges
0117
0118   notes:
0119     uses 'mergeT *mergeA, *mergeAp;'
0120     see <a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a>
0121 */
0122 #define FOREACHmergeA_(merges) FOREACHsetelement_(mergeT, merges, mergeA)
0123
0124 /*-<a                             href="qh-poly.htm#TOC"
0125   >--------------------------------</a><a name="FOREACHmerge_i_">-</a>
0126
0127   FOREACHmerge_i_( vertices ) { ... }
0128     assign 'merge' and 'merge_i' for each merge in mergeset
0129
0130   declare:
0131     mergeT *merge;
0132     int     merge_n, merge_i;
0133
0134   see:
0135     <a href="qset.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a>
0136 */
0137 #define FOREACHmerge_i_(mergeset) FOREACHsetelement_i_(mergeT, mergeset, merge)
0138
0139 /*============ prototypes in alphabetical order after pre/postmerge =======*/
0140
0141 void    qh_premerge(int apexpointid, realT maxcentrum, realT maxangle);
0142 void    qh_postmerge(const char *reason, realT maxcentrum, realT maxangle,
0143              boolT vneighbors);
0144 void    qh_all_merges(boolT othermerge, boolT vneighbors);
0145 void    qh_all_vertexmerges(int apexpointid, facetT *facet, facetT **retryfacet);
0146 void    qh_appendmergeset(facetT *facet, facetT *neighbor, mergeType mergetype, coordT dist, realT angle);
0147 void    qh_appendvertexmerge(vertexT *vertex, vertexT *destination, mergeType mergetype, realT distance, ridgeT *ridge1, ridgeT *ridge2);
0148 setT   *qh_basevertices(facetT *samecycle);
0149 void    qh_check_dupridge(facetT *facet1, realT dist1, facetT *facet2, realT dist2);
0150 void    qh_checkconnect(void /* qh.new_facets */);
0151 void    qh_checkdelfacet(facetT *facet, setT *mergeset);
0152 void    qh_checkdelridge(void /* qh.visible_facets, vertex_mergeset */);
0153 boolT   qh_checkzero(boolT testall);
0154 int     qh_compare_anglemerge(const void *p1, const void *p2);
0155 int     qh_compare_facetmerge(const void *p1, const void *p2);
0156 int     qh_comparevisit(const void *p1, const void *p2);
0157 void    qh_copynonconvex(ridgeT *atridge);
0158 void    qh_degen_redundant_facet(facetT *facet);
0159 void    qh_drop_mergevertex(mergeT *merge);
0160 void    qh_delridge_merge(ridgeT *ridge);
0161 vertexT *qh_find_newvertex(vertexT *oldvertex, setT *vertices, setT *ridges);
0162 vertexT *qh_findbest_pinchedvertex(mergeT *merge, vertexT *apex, vertexT **pinchedp, realT *distp /* qh.newfacet_list */);
0163 vertexT *qh_findbest_ridgevertex(ridgeT *ridge, vertexT **pinchedp, coordT *distp);
0164 void    qh_findbest_test(boolT testcentrum, facetT *facet, facetT *neighbor,
0165            facetT **bestfacet, realT *distp, realT *mindistp, realT *maxdistp);
0166 facetT *qh_findbestneighbor(facetT *facet, realT *distp, realT *mindistp, realT *maxdistp);
0167 void    qh_flippedmerges(facetT *facetlist, boolT *wasmerge);
0168 void    qh_forcedmerges(boolT *wasmerge);
0169 void    qh_freemergesets(void);
0170 void    qh_getmergeset(facetT *facetlist);
0171 void    qh_getmergeset_initial(facetT *facetlist);
0172 boolT   qh_getpinchedmerges(vertexT *apex, coordT maxdupdist, boolT *iscoplanar /* qh.newfacet_list, vertex_mergeset */);
0173 boolT   qh_hasmerge(setT *mergeset, mergeType type, facetT *facetA, facetT *facetB);
0174 void    qh_hashridge(setT *hashtable, int hashsize, ridgeT *ridge, vertexT *oldvertex);
0175 ridgeT *qh_hashridge_find(setT *hashtable, int hashsize, ridgeT *ridge,
0176               vertexT *vertex, vertexT *oldvertex, int *hashslot);
0177 void    qh_initmergesets(void);
0178 void    qh_makeridges(facetT *facet);
0179 void    qh_mark_dupridges(facetT *facetlist, boolT allmerges);
0180 void    qh_maybe_duplicateridge(ridgeT *ridge);
0181 void    qh_maybe_duplicateridges(facetT *facet);
0182 void    qh_maydropneighbor(facetT *facet);
0183 int     qh_merge_degenredundant(void);
0184 void    qh_merge_nonconvex(facetT *facet1, facetT *facet2, mergeType mergetype);
0185 void    qh_merge_pinchedvertices(int apexpointid /* qh.newfacet_list */);
0186 void    qh_merge_twisted(facetT *facet1, facetT *facet2);
0187 void    qh_mergecycle(facetT *samecycle, facetT *newfacet);
0188 void    qh_mergecycle_all(facetT *facetlist, boolT *wasmerge);
0189 void    qh_mergecycle_facets(facetT *samecycle, facetT *newfacet);
0190 void    qh_mergecycle_neighbors(facetT *samecycle, facetT *newfacet);
0191 void    qh_mergecycle_ridges(facetT *samecycle, facetT *newfacet);
0192 void    qh_mergecycle_vneighbors(facetT *samecycle, facetT *newfacet);
0193 void    qh_mergefacet(facetT *facet1, facetT *facet2, mergeType mergetype, realT *mindist, realT *maxdist, boolT mergeapex);
0194 void    qh_mergefacet2d(facetT *facet1, facetT *facet2);
0195 void    qh_mergeneighbors(facetT *facet1, facetT *facet2);
0196 void    qh_mergeridges(facetT *facet1, facetT *facet2);
0197 void    qh_mergesimplex(facetT *facet1, facetT *facet2, boolT mergeapex);
0198 void    qh_mergevertex_del(vertexT *vertex, facetT *facet1, facetT *facet2);
0199 void    qh_mergevertex_neighbors(facetT *facet1, facetT *facet2);
0200 void    qh_mergevertices(setT *vertices1, setT **vertices);
0201 setT   *qh_neighbor_intersections(vertexT *vertex);
0202 setT   *qh_neighbor_vertices(vertexT *vertex, setT *subridge);
0203 void    qh_neighbor_vertices_facet(vertexT *vertexA, facetT *facet, setT **vertices);
0204 void    qh_newvertices(setT *vertices);
0205 mergeT *qh_next_vertexmerge(void);
0206 facetT *qh_opposite_horizonfacet(mergeT *merge, vertexT **vertex);
0207 boolT   qh_reducevertices(void);
0208 vertexT *qh_redundant_vertex(vertexT *vertex);
0209 boolT   qh_remove_extravertices(facetT *facet);
0210 void    qh_remove_mergetype(setT *mergeset, mergeType type);
0211 void    qh_rename_adjacentvertex(vertexT *oldvertex, vertexT *newvertex, realT dist);
0212 vertexT *qh_rename_sharedvertex(vertexT *vertex, facetT *facet);
0213 boolT   qh_renameridgevertex(ridgeT *ridge, vertexT *oldvertex, vertexT *newvertex);
0214 void    qh_renamevertex(vertexT *oldvertex, vertexT *newvertex, setT *ridges,
0215                         facetT *oldfacet, facetT *neighborA);
0216 boolT   qh_test_appendmerge(facetT *facet, facetT *neighbor, boolT simplicial);
0217 void    qh_test_degen_neighbors(facetT *facet);
0218 boolT   qh_test_centrum_merge(facetT *facet, facetT *neighbor, realT angle, boolT okangle);
0219 boolT   qh_test_nonsimplicial_merge(facetT *facet, facetT *neighbor, realT angle, boolT okangle);
0220 void    qh_test_redundant_neighbors(facetT *facet);
0221 boolT   qh_test_vneighbors(void /* qh.newfacet_list */);
0222 void    qh_tracemerge(facetT *facet1, facetT *facet2, mergeType mergetype);
0223 void    qh_tracemerging(void);
0224 void    qh_undo_newfacets(void);
0225 void    qh_updatetested(facetT *facet1, facetT *facet2);
0226 setT   *qh_vertexridges(vertexT *vertex, boolT allneighbors);
0227 void    qh_vertexridges_facet(vertexT *vertex, facetT *facet, setT **ridges);
0228 void    qh_willdelete(facetT *facet, facetT *replace);
0229
0230 #endif /* qhDEFmerge */