include/libqhull_r/merge_r.h

0001 /*<html><pre>  -<a                             href="qh-merge_r.htm"
0002   >-------------------------------</a><a name="TOP">-</a>
0003
0004    merge_r.h
0005    header file for merge_r.c
0006
0007    see qh-merge_r.htm and merge_r.c
0008
0009    Copyright (c) 1993-2020 C.B. Barber.
0010    $Id: //main/2019/qhull/src/libqhull_r/merge_r.h#2 $$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_r.h"
0018
0019
0020 /*============ -constants- ==============*/
0021
0022 /*-<a                             href="qh-merge_r.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_r.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_r.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_r.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_r.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_r.h#FOREACHsetelement_">FOREACHsetelement_</a>
0109 */
0110 #define FOREACHmerge_(merges) FOREACHsetelement_(mergeT, merges, merge)
0111
0112 /*-<a                             href="qh-poly_r.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_r.h#FOREACHsetelement_">FOREACHsetelement_</a>
0121 */
0122 #define FOREACHmergeA_(merges) FOREACHsetelement_(mergeT, merges, mergeA)
0123
0124 /*-<a                             href="qh-poly_r.htm#TOC"
0125   >--------------------------------</a><a name="FOREACHmerge_i_">-</a>
0126
0127   FOREACHmerge_i_(qh, 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_r.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a>
0136 */
0137 #define FOREACHmerge_i_(qh, mergeset) FOREACHsetelement_i_(qh, mergeT, mergeset, merge)
0138
0139 /*============ prototypes in alphabetical order after pre/postmerge =======*/
0140
0141 #ifdef __cplusplus
0142 extern "C" {
0143 #endif
0144
0145 void    qh_premerge(qhT *qh, int apexpointid, realT maxcentrum, realT maxangle);
0146 void    qh_postmerge(qhT *qh, const char *reason, realT maxcentrum, realT maxangle,
0147              boolT vneighbors);
0148 void    qh_all_merges(qhT *qh, boolT othermerge, boolT vneighbors);
0149 void    qh_all_vertexmerges(qhT *qh, int apexpointid, facetT *facet, facetT **retryfacet);
0150 void    qh_appendmergeset(qhT *qh, facetT *facet, facetT *neighbor, mergeType mergetype, coordT dist, realT angle);
0151 void    qh_appendvertexmerge(qhT *qh, vertexT *vertex, vertexT *destination, mergeType mergetype, realT distance, ridgeT *ridge1, ridgeT *ridge2);
0152 setT   *qh_basevertices(qhT *qh, facetT *samecycle);
0153 void    qh_check_dupridge(qhT *qh, facetT *facet1, realT dist1, facetT *facet2, realT dist2);
0154 void    qh_checkconnect(qhT *qh /* qh.new_facets */);
0155 void    qh_checkdelfacet(qhT *qh, facetT *facet, setT *mergeset);
0156 void    qh_checkdelridge(qhT *qh /* qh.visible_facets, vertex_mergeset */);
0157 boolT   qh_checkzero(qhT *qh, boolT testall);
0158 int     qh_compare_anglemerge(const void *p1, const void *p2);
0159 int     qh_compare_facetmerge(const void *p1, const void *p2);
0160 int     qh_comparevisit(const void *p1, const void *p2);
0161 void    qh_copynonconvex(qhT *qh, ridgeT *atridge);
0162 void    qh_degen_redundant_facet(qhT *qh, facetT *facet);
0163 void    qh_drop_mergevertex(qhT *qh, mergeT *merge);
0164 void    qh_delridge_merge(qhT *qh, ridgeT *ridge);
0165 vertexT *qh_find_newvertex(qhT *qh, vertexT *oldvertex, setT *vertices, setT *ridges);
0166 vertexT *qh_findbest_pinchedvertex(qhT *qh, mergeT *merge, vertexT *apex, vertexT **pinchedp, realT *distp /* qh.newfacet_list */);
0167 vertexT *qh_findbest_ridgevertex(qhT *qh, ridgeT *ridge, vertexT **pinchedp, coordT *distp);
0168 void    qh_findbest_test(qhT *qh, boolT testcentrum, facetT *facet, facetT *neighbor,
0169            facetT **bestfacet, realT *distp, realT *mindistp, realT *maxdistp);
0170 facetT *qh_findbestneighbor(qhT *qh, facetT *facet, realT *distp, realT *mindistp, realT *maxdistp);
0171 void    qh_flippedmerges(qhT *qh, facetT *facetlist, boolT *wasmerge);
0172 void    qh_forcedmerges(qhT *qh, boolT *wasmerge);
0173 void    qh_freemergesets(qhT *qh);
0174 void    qh_getmergeset(qhT *qh, facetT *facetlist);
0175 void    qh_getmergeset_initial(qhT *qh, facetT *facetlist);
0176 boolT   qh_getpinchedmerges(qhT *qh, vertexT *apex, coordT maxdupdist, boolT *iscoplanar /* qh.newfacet_list, vertex_mergeset */);
0177 boolT   qh_hasmerge(setT *mergeset, mergeType type, facetT *facetA, facetT *facetB);
0178 void    qh_hashridge(qhT *qh, setT *hashtable, int hashsize, ridgeT *ridge, vertexT *oldvertex);
0179 ridgeT *qh_hashridge_find(qhT *qh, setT *hashtable, int hashsize, ridgeT *ridge,
0180               vertexT *vertex, vertexT *oldvertex, int *hashslot);
0181 void    qh_initmergesets(qhT *qh);
0182 void    qh_makeridges(qhT *qh, facetT *facet);
0183 void    qh_mark_dupridges(qhT *qh, facetT *facetlist, boolT allmerges);
0184 void    qh_maybe_duplicateridge(qhT *qh, ridgeT *ridge);
0185 void    qh_maybe_duplicateridges(qhT *qh, facetT *facet);
0186 void    qh_maydropneighbor(qhT *qh, facetT *facet);
0187 int     qh_merge_degenredundant(qhT *qh);
0188 void    qh_merge_nonconvex(qhT *qh, facetT *facet1, facetT *facet2, mergeType mergetype);
0189 void    qh_merge_pinchedvertices(qhT *qh, int apexpointid /* qh.newfacet_list */);
0190 void    qh_merge_twisted(qhT *qh, facetT *facet1, facetT *facet2);
0191 void    qh_mergecycle(qhT *qh, facetT *samecycle, facetT *newfacet);
0192 void    qh_mergecycle_all(qhT *qh, facetT *facetlist, boolT *wasmerge);
0193 void    qh_mergecycle_facets(qhT *qh, facetT *samecycle, facetT *newfacet);
0194 void    qh_mergecycle_neighbors(qhT *qh, facetT *samecycle, facetT *newfacet);
0195 void    qh_mergecycle_ridges(qhT *qh, facetT *samecycle, facetT *newfacet);
0196 void    qh_mergecycle_vneighbors(qhT *qh, facetT *samecycle, facetT *newfacet);
0197 void    qh_mergefacet(qhT *qh, facetT *facet1, facetT *facet2, mergeType mergetype, realT *mindist, realT *maxdist, boolT mergeapex);
0198 void    qh_mergefacet2d(qhT *qh, facetT *facet1, facetT *facet2);
0199 void    qh_mergeneighbors(qhT *qh, facetT *facet1, facetT *facet2);
0200 void    qh_mergeridges(qhT *qh, facetT *facet1, facetT *facet2);
0201 void    qh_mergesimplex(qhT *qh, facetT *facet1, facetT *facet2, boolT mergeapex);
0202 void    qh_mergevertex_del(qhT *qh, vertexT *vertex, facetT *facet1, facetT *facet2);
0203 void    qh_mergevertex_neighbors(qhT *qh, facetT *facet1, facetT *facet2);
0204 void    qh_mergevertices(qhT *qh, setT *vertices1, setT **vertices);
0205 setT   *qh_neighbor_intersections(qhT *qh, vertexT *vertex);
0206 setT   *qh_neighbor_vertices(qhT *qh, vertexT *vertex, setT *subridge);
0207 void    qh_neighbor_vertices_facet(qhT *qh, vertexT *vertexA, facetT *facet, setT **vertices);
0208 void    qh_newvertices(qhT *qh, setT *vertices);
0209 mergeT *qh_next_vertexmerge(qhT *qh);
0210 facetT *qh_opposite_horizonfacet(qhT *qh, mergeT *merge, vertexT **vertex);
0211 boolT   qh_reducevertices(qhT *qh);
0212 vertexT *qh_redundant_vertex(qhT *qh, vertexT *vertex);
0213 boolT   qh_remove_extravertices(qhT *qh, facetT *facet);
0214 void    qh_remove_mergetype(qhT *qh, setT *mergeset, mergeType type);
0215 void    qh_rename_adjacentvertex(qhT *qh, vertexT *oldvertex, vertexT *newvertex, realT dist);
0216 vertexT *qh_rename_sharedvertex(qhT *qh, vertexT *vertex, facetT *facet);
0217 boolT   qh_renameridgevertex(qhT *qh, ridgeT *ridge, vertexT *oldvertex, vertexT *newvertex);
0218 void    qh_renamevertex(qhT *qh, vertexT *oldvertex, vertexT *newvertex, setT *ridges,
0219                         facetT *oldfacet, facetT *neighborA);
0220 boolT   qh_test_appendmerge(qhT *qh, facetT *facet, facetT *neighbor, boolT simplicial);
0221 void    qh_test_degen_neighbors(qhT *qh, facetT *facet);
0222 boolT   qh_test_centrum_merge(qhT *qh, facetT *facet, facetT *neighbor, realT angle, boolT okangle);
0223 boolT   qh_test_nonsimplicial_merge(qhT *qh, facetT *facet, facetT *neighbor, realT angle, boolT okangle);
0224 void    qh_test_redundant_neighbors(qhT *qh, facetT *facet);
0225 boolT   qh_test_vneighbors(qhT *qh /* qh.newfacet_list */);
0226 void    qh_tracemerge(qhT *qh, facetT *facet1, facetT *facet2, mergeType mergetype);
0227 void    qh_tracemerging(qhT *qh);
0228 void    qh_undo_newfacets(qhT *qh);
0229 void    qh_updatetested(qhT *qh, facetT *facet1, facetT *facet2);
0230 setT   *qh_vertexridges(qhT *qh, vertexT *vertex, boolT allneighbors);
0231 void    qh_vertexridges_facet(qhT *qh, vertexT *vertex, facetT *facet, setT **ridges);
0232 void    qh_willdelete(qhT *qh, facetT *facet, facetT *replace);
0233
0234 #ifdef __cplusplus
0235 } /* extern "C" */
0236 #endif
0237
0238 #endif /* qhDEFmerge */