1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
|
/*<html><pre> -<a href="qh-merge_r.htm"
>-------------------------------</a><a name="TOP">-</a>
merge_r.h
header file for merge_r.c
see qh-merge_r.htm and merge_r.c
Copyright (c) 1993-2020 C.B. Barber.
$Id: //main/2019/qhull/src/libqhull_r/merge_r.h#2 $$Change: 2953 $
$DateTime: 2020/05/21 22:05:32 $$Author: bbarber $
*/
#ifndef qhDEFmerge
#define qhDEFmerge 1
#include "libqhull_r.h"
/*============ -constants- ==============*/
/*-<a href="qh-merge_r.htm#TOC"
>--------------------------------</a><a name="qh_ANGLEnone">-</a>
qh_ANGLEnone
indicates missing angle for mergeT->angle
*/
#define qh_ANGLEnone 2.0
/*-<a href="qh-merge_r.htm#TOC"
>--------------------------------</a><a name="MRG">-</a>
MRG... (mergeType)
indicates the type of a merge (mergeT->type)
MRGcoplanar...MRGtwisted set by qh_test_centrum_merge, qh_test_nonsimplicial_merge
*/
typedef enum { /* must match mergetypes[] */
MRGnone= 0,
/* MRGcoplanar..MRGtwisted go into qh.facet_mergeset for qh_all_merges
qh_compare_facetmerge selects lower mergetypes for merging first */
MRGcoplanar, /* (1) centrum coplanar if centrum ('Cn') or vertex not clearly above or below neighbor */
MRGanglecoplanar, /* (2) angle coplanar if angle ('An') is coplanar */
MRGconcave, /* (3) concave ridge */
MRGconcavecoplanar, /* (4) concave and coplanar ridge, one side concave, other side coplanar */
MRGtwisted, /* (5) twisted ridge, both concave and convex, facet1 is wider */
/* MRGflip go into qh.facet_mergeset for qh_flipped_merges */
MRGflip, /* (6) flipped facet if qh.interior_point is above facet, w/ facet1 == facet2 */
/* MRGdupridge go into qh.facet_mergeset for qh_forcedmerges */
MRGdupridge, /* (7) dupridge if more than two neighbors. Set by qh_mark_dupridges for qh_MERGEridge */
/* MRGsubridge and MRGvertices go into vertex_mergeset */
MRGsubridge, /* (8) merge pinched vertex to remove the subridge of a MRGdupridge */
MRGvertices, /* (9) merge pinched vertex to remove a facet's ridges with the same vertices */
/* MRGdegen, MRGredundant, and MRGmirror go into qh.degen_mergeset */
MRGdegen, /* (10) degenerate facet (!enough neighbors) facet1 == facet2 */
MRGredundant, /* (11) redundant facet (vertex subset) */
/* merge_degenredundant assumes degen < redundant */
MRGmirror, /* (12) mirror facets: same vertices due to null facets in qh_triangulate
f.redundant for both facets*/
/* MRGcoplanarhorizon for qh_mergecycle_all only */
MRGcoplanarhorizon, /* (13) new facet coplanar with the horizon (qh_mergecycle_all) */
ENDmrg
} mergeType;
/*-<a href="qh-merge_r.htm#TOC"
>--------------------------------</a><a name="qh_MERGEapex">-</a>
qh_MERGEapex
flag for qh_mergefacet() to indicate an apex merge
*/
#define qh_MERGEapex True
/*============ -structures- ====================*/
/*-<a href="qh-merge_r.htm#TOC"
>--------------------------------</a><a name="mergeT">-</a>
mergeT
structure used to merge facets
*/
typedef struct mergeT mergeT;
struct mergeT { /* initialize in qh_appendmergeset */
realT angle; /* cosine of angle between normals of facet1 and facet2,
null value and right angle is 0.0, coplanar is 1.0, narrow is -1.0 */
realT distance; /* absolute value of distance between vertices, centrum and facet, or vertex and facet */
facetT *facet1; /* will merge facet1 into facet2 */
facetT *facet2;
vertexT *vertex1; /* will merge vertext1 into vertex2 for MRGsubridge or MRGvertices */
vertexT *vertex2;
ridgeT *ridge1; /* the duplicate ridges resolved by MRGvertices */
ridgeT *ridge2; /* merge is deleted if either ridge is deleted (qh_delridge) */
mergeType mergetype;
};
/*=========== -macros- =========================*/
/*-<a href="qh-merge_r.htm#TOC"
>--------------------------------</a><a name="FOREACHmerge_">-</a>
FOREACHmerge_( merges ) {...}
assign 'merge' to each merge in merges
notes:
uses 'mergeT *merge, **mergep;'
if qh_mergefacet(),
restart or use qh_setdellast() since qh.facet_mergeset may change
see <a href="qset_r.h#FOREACHsetelement_">FOREACHsetelement_</a>
*/
#define FOREACHmerge_(merges) FOREACHsetelement_(mergeT, merges, merge)
/*-<a href="qh-poly_r.htm#TOC"
>--------------------------------</a><a name="FOREACHmergeA_">-</a>
FOREACHmergeA_( vertices ) { ... }
assign 'mergeA' to each merge in merges
notes:
uses 'mergeT *mergeA, *mergeAp;'
see <a href="qset_r.h#FOREACHsetelement_">FOREACHsetelement_</a>
*/
#define FOREACHmergeA_(merges) FOREACHsetelement_(mergeT, merges, mergeA)
/*-<a href="qh-poly_r.htm#TOC"
>--------------------------------</a><a name="FOREACHmerge_i_">-</a>
FOREACHmerge_i_(qh, vertices ) { ... }
assign 'merge' and 'merge_i' for each merge in mergeset
declare:
mergeT *merge;
int merge_n, merge_i;
see:
<a href="qset_r.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a>
*/
#define FOREACHmerge_i_(qh, mergeset) FOREACHsetelement_i_(qh, mergeT, mergeset, merge)
/*============ prototypes in alphabetical order after pre/postmerge =======*/
#ifdef __cplusplus
extern "C" {
#endif
void qh_premerge(qhT *qh, int apexpointid, realT maxcentrum, realT maxangle);
void qh_postmerge(qhT *qh, const char *reason, realT maxcentrum, realT maxangle,
boolT vneighbors);
void qh_all_merges(qhT *qh, boolT othermerge, boolT vneighbors);
void qh_all_vertexmerges(qhT *qh, int apexpointid, facetT *facet, facetT **retryfacet);
void qh_appendmergeset(qhT *qh, facetT *facet, facetT *neighbor, mergeType mergetype, coordT dist, realT angle);
void qh_appendvertexmerge(qhT *qh, vertexT *vertex, vertexT *destination, mergeType mergetype, realT distance, ridgeT *ridge1, ridgeT *ridge2);
setT *qh_basevertices(qhT *qh, facetT *samecycle);
void qh_check_dupridge(qhT *qh, facetT *facet1, realT dist1, facetT *facet2, realT dist2);
void qh_checkconnect(qhT *qh /* qh.new_facets */);
void qh_checkdelfacet(qhT *qh, facetT *facet, setT *mergeset);
void qh_checkdelridge(qhT *qh /* qh.visible_facets, vertex_mergeset */);
boolT qh_checkzero(qhT *qh, boolT testall);
int qh_compare_anglemerge(const void *p1, const void *p2);
int qh_compare_facetmerge(const void *p1, const void *p2);
int qh_comparevisit(const void *p1, const void *p2);
void qh_copynonconvex(qhT *qh, ridgeT *atridge);
void qh_degen_redundant_facet(qhT *qh, facetT *facet);
void qh_drop_mergevertex(qhT *qh, mergeT *merge);
void qh_delridge_merge(qhT *qh, ridgeT *ridge);
vertexT *qh_find_newvertex(qhT *qh, vertexT *oldvertex, setT *vertices, setT *ridges);
vertexT *qh_findbest_pinchedvertex(qhT *qh, mergeT *merge, vertexT *apex, vertexT **pinchedp, realT *distp /* qh.newfacet_list */);
vertexT *qh_findbest_ridgevertex(qhT *qh, ridgeT *ridge, vertexT **pinchedp, coordT *distp);
void qh_findbest_test(qhT *qh, boolT testcentrum, facetT *facet, facetT *neighbor,
facetT **bestfacet, realT *distp, realT *mindistp, realT *maxdistp);
facetT *qh_findbestneighbor(qhT *qh, facetT *facet, realT *distp, realT *mindistp, realT *maxdistp);
void qh_flippedmerges(qhT *qh, facetT *facetlist, boolT *wasmerge);
void qh_forcedmerges(qhT *qh, boolT *wasmerge);
void qh_freemergesets(qhT *qh);
void qh_getmergeset(qhT *qh, facetT *facetlist);
void qh_getmergeset_initial(qhT *qh, facetT *facetlist);
boolT qh_getpinchedmerges(qhT *qh, vertexT *apex, coordT maxdupdist, boolT *iscoplanar /* qh.newfacet_list, vertex_mergeset */);
boolT qh_hasmerge(setT *mergeset, mergeType type, facetT *facetA, facetT *facetB);
void qh_hashridge(qhT *qh, setT *hashtable, int hashsize, ridgeT *ridge, vertexT *oldvertex);
ridgeT *qh_hashridge_find(qhT *qh, setT *hashtable, int hashsize, ridgeT *ridge,
vertexT *vertex, vertexT *oldvertex, int *hashslot);
void qh_initmergesets(qhT *qh);
void qh_makeridges(qhT *qh, facetT *facet);
void qh_mark_dupridges(qhT *qh, facetT *facetlist, boolT allmerges);
void qh_maybe_duplicateridge(qhT *qh, ridgeT *ridge);
void qh_maybe_duplicateridges(qhT *qh, facetT *facet);
void qh_maydropneighbor(qhT *qh, facetT *facet);
int qh_merge_degenredundant(qhT *qh);
void qh_merge_nonconvex(qhT *qh, facetT *facet1, facetT *facet2, mergeType mergetype);
void qh_merge_pinchedvertices(qhT *qh, int apexpointid /* qh.newfacet_list */);
void qh_merge_twisted(qhT *qh, facetT *facet1, facetT *facet2);
void qh_mergecycle(qhT *qh, facetT *samecycle, facetT *newfacet);
void qh_mergecycle_all(qhT *qh, facetT *facetlist, boolT *wasmerge);
void qh_mergecycle_facets(qhT *qh, facetT *samecycle, facetT *newfacet);
void qh_mergecycle_neighbors(qhT *qh, facetT *samecycle, facetT *newfacet);
void qh_mergecycle_ridges(qhT *qh, facetT *samecycle, facetT *newfacet);
void qh_mergecycle_vneighbors(qhT *qh, facetT *samecycle, facetT *newfacet);
void qh_mergefacet(qhT *qh, facetT *facet1, facetT *facet2, mergeType mergetype, realT *mindist, realT *maxdist, boolT mergeapex);
void qh_mergefacet2d(qhT *qh, facetT *facet1, facetT *facet2);
void qh_mergeneighbors(qhT *qh, facetT *facet1, facetT *facet2);
void qh_mergeridges(qhT *qh, facetT *facet1, facetT *facet2);
void qh_mergesimplex(qhT *qh, facetT *facet1, facetT *facet2, boolT mergeapex);
void qh_mergevertex_del(qhT *qh, vertexT *vertex, facetT *facet1, facetT *facet2);
void qh_mergevertex_neighbors(qhT *qh, facetT *facet1, facetT *facet2);
void qh_mergevertices(qhT *qh, setT *vertices1, setT **vertices);
setT *qh_neighbor_intersections(qhT *qh, vertexT *vertex);
setT *qh_neighbor_vertices(qhT *qh, vertexT *vertex, setT *subridge);
void qh_neighbor_vertices_facet(qhT *qh, vertexT *vertexA, facetT *facet, setT **vertices);
void qh_newvertices(qhT *qh, setT *vertices);
mergeT *qh_next_vertexmerge(qhT *qh);
facetT *qh_opposite_horizonfacet(qhT *qh, mergeT *merge, vertexT **vertex);
boolT qh_reducevertices(qhT *qh);
vertexT *qh_redundant_vertex(qhT *qh, vertexT *vertex);
boolT qh_remove_extravertices(qhT *qh, facetT *facet);
void qh_remove_mergetype(qhT *qh, setT *mergeset, mergeType type);
void qh_rename_adjacentvertex(qhT *qh, vertexT *oldvertex, vertexT *newvertex, realT dist);
vertexT *qh_rename_sharedvertex(qhT *qh, vertexT *vertex, facetT *facet);
boolT qh_renameridgevertex(qhT *qh, ridgeT *ridge, vertexT *oldvertex, vertexT *newvertex);
void qh_renamevertex(qhT *qh, vertexT *oldvertex, vertexT *newvertex, setT *ridges,
facetT *oldfacet, facetT *neighborA);
boolT qh_test_appendmerge(qhT *qh, facetT *facet, facetT *neighbor, boolT simplicial);
void qh_test_degen_neighbors(qhT *qh, facetT *facet);
boolT qh_test_centrum_merge(qhT *qh, facetT *facet, facetT *neighbor, realT angle, boolT okangle);
boolT qh_test_nonsimplicial_merge(qhT *qh, facetT *facet, facetT *neighbor, realT angle, boolT okangle);
void qh_test_redundant_neighbors(qhT *qh, facetT *facet);
boolT qh_test_vneighbors(qhT *qh /* qh.newfacet_list */);
void qh_tracemerge(qhT *qh, facetT *facet1, facetT *facet2, mergeType mergetype);
void qh_tracemerging(qhT *qh);
void qh_undo_newfacets(qhT *qh);
void qh_updatetested(qhT *qh, facetT *facet1, facetT *facet2);
setT *qh_vertexridges(qhT *qh, vertexT *vertex, boolT allneighbors);
void qh_vertexridges_facet(qhT *qh, vertexT *vertex, facetT *facet, setT **ridges);
void qh_willdelete(qhT *qh, facetT *facet, facetT *replace);
#ifdef __cplusplus
} /* extern "C" */
#endif
#endif /* qhDEFmerge */
|
