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
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
|
<!-- Do not edit with Front Page, it adds too many spaces -->
<html>
<head>
<meta http-equiv="Content-Type"
content="text/html; charset=iso-8859-1">
<title>merge.c -- facet merge operations</title>
</head>
<body>
<!-- Navigation links -->
<p><a name="TOP"><b>Up:</b></a> <a
href="http://www.qhull.org">Home page</a> for Qhull<br>
<b>Up:</b> <a href="../../html/index.htm#TOC">Qhull manual</a>: Table of Contents <br>
<b>Up:</b> <a href="../../html/qh-quick.htm#programs">Programs</a>
• <a href="../../html/qh-quick.htm#options">Options</a>
• <a href="../../html/qh-opto.htm#output">Output</a>
• <a href="../../html/qh-optf.htm#format">Formats</a>
• <a href="../../html/qh-optg.htm#geomview">Geomview</a>
• <a href="../../html/qh-optp.htm#print">Print</a>
• <a href="../../html/qh-optq.htm#qhull">Qhull</a>
• <a href="../../html/qh-optc.htm#prec">Precision</a>
• <a href="../../html/qh-optt.htm#trace">Trace</a>
• <a href="index.htm">Functions</a><br>
<b>Up:</b> <a href="../../html/qh-code.htm#TOC">Qhull code: Table of Contents</a><br>
<b>To:</b> <a href="index.htm">Qhull functions</a>, macros, and data structures<br>
<b>To:</b> <a href="qh-geom.htm">Geom</a> • <a href="qh-globa.htm">Global</a>
• <a href="qh-io.htm">Io</a> • <a href="qh-mem.htm">Mem</a>
• <a href="qh-merge.htm#TOC">Merge</a> • <a href="qh-poly.htm">Poly</a>
• <a href="qh-qhull.htm">Qhull</a> • <a href="qh-set.htm">Set</a>
• <a href="qh-stat.htm">Stat</a> • <a href="qh-user.htm">User</a>
</p>
<hr>
<h2>merge.c -- facet merge operations</h2>
<blockquote>
<p>Qhull handles precision problems by merged facets or joggled input.
Except for redundant vertices, it corrects a problem by
merging two facets. When done, all facets are clearly
convex. See <a href="../../html/qh-impre.htm">Imprecision in Qhull</a>
for further information. </p>
<p>Users may joggle the input ('<a href="../../html/qh-optq.htm#QJn">QJn</a>')
instead of merging facets. </p>
<p>Qhull detects and corrects the following problems: </p>
<ul>
<li><b>More than two facets meeting at a ridge. </b>When
Qhull creates facets, it creates an even number
of facets for each ridge. A convex hull always
has two facets for each ridge. More than two
facets may be created if non-adjacent facets
share a vertex. This is called a <em>duplicate
ridge</em>. In 2-d, a duplicate ridge would
create a loop of facets. </li>
</ul>
<ul>
<li><b>A facet contained in another facet. </b>Facet
merging may leave all vertices of one facet as a
subset of the vertices of another facet. This is
called a <em>redundant facet</em>. </li>
</ul>
<ul>
<li><b>A facet with fewer than three neighbors. </b>Facet
merging may leave a facet with one or two
neighbors. This is called a <em>degenerate facet</em>.
</li>
</ul>
<ul>
<li><b>A facet with flipped orientation. </b>A
facet's hyperplane may define a halfspace that
does not include the interior point.This is
called a <em>flipped facet</em>. </li>
</ul>
<ul>
<li><strong>A coplanar horizon facet.</strong> A
newly processed point may be coplanar with an
horizon facet. Qhull creates a new facet without
a hyperplane. It links new facets for the same
horizon facet together. This is called a <em>samecycle</em>.
The new facet or samecycle is merged into the
horizon facet. </li>
</ul>
<ul>
<li><b>Concave facets. </b>A facet's centrum may be
above a neighboring facet. If so, the facets meet
at a concave angle. </li>
</ul>
<ul>
<li><b>Coplanar facets. </b>A facet's centrum may be
coplanar with a neighboring facet (i.e., it is
neither clearly below nor clearly above the
facet's hyperplane). Qhull removes coplanar
facets in independent sets sorted by angle.</li>
</ul>
<ul>
<li><b>Redundant vertex. </b>A vertex may have fewer
than three neighboring facets. If so, it is
redundant and may be renamed to an adjacent
vertex without changing the topological
structure.This is called a <em>redundant vertex</em>.
</li>
</ul>
</blockquote>
<p><b>Copyright © 1995-2015 C.B. Barber</b></p>
<hr>
<p><a href="#TOP">»</a> <a href="qh-geom.htm#TOC">Geom</a>
<a name="TOC">•</a> <a href="qh-globa.htm#TOC">Global</a>
• <a href="qh-io.htm#TOC">Io</a> • <a href="qh-mem.htm#TOC">Mem</a>
• <b>Merge</b> • <a href="qh-poly.htm#TOC">Poly</a>
• <a href="qh-qhull.htm#TOC">Qhull</a> • <a href="qh-set.htm#TOC">Set</a>
• <a href="qh-stat.htm#TOC">Stat</a> • <a href="qh-user.htm#TOC">User</a>
</p>
<h3>Index to <a href="merge.c">merge.c</a> and
<a href="merge.h">merge.h</a></h3>
<ul>
<li><a href="#mtype">merge.h data types, macros, and
global sets</a> </li>
<li><a href="#mconst">merge.h constants</a> </li>
</ul>
<ul>
<li><a href="#mtop">top-level merge functions</a> </li>
<li><a href="#mset">functions for identifying merges</a></li>
<li><a href="#mbest">functions for determining the
best merge</a> </li>
<li><a href="#mmerge">functions for merging facets</a>
</li>
<li><a href="#mcycle">functions for merging a cycle
of facets</a> </li>
<li><a href="#mrename">functions for renaming a
vertex</a> </li>
<li><a href="#mvertex">functions for identifying
vertices for renaming</a> </li>
<li><a href="#mcheck">functions for check and trace</a> </li>
</ul>
<h3><a href="qh-merge.htm#TOC">»</a><a name="mtype">merge.h data
types, macros, and global sets</a></h3>
<ul>
<li><a href="merge.h#mergeT">mergeT</a> structure to
identify a merge of two facets</li>
<li><a href="merge.h#FOREACHmerge_">FOREACHmerge_</a>
assign 'merge' to each merge in merges </li>
<li><a href="libqhull.h#qh-set">qh global sets</a>
qh.facet_mergeset contains non-convex merges
while qh.degen_mergeset contains degenerate and
redundant facets</li>
</ul>
<h3><a href="qh-merge.htm#TOC">»</a><a name="mconst">merge.h
constants</a></h3>
<ul>
<li><a href="libqhull.h#qh-prec">qh precision constants</a>
precision constants for Qhull </li>
<li><a href="merge.h#MRG">MRG...</a> indicates the
type of a merge (mergeT->type)</li>
<li><a href="merge.h#qh_ANGLEredundant">qh_ANGLEredundant</a>
indicates redundant merge in mergeT->angle </li>
<li><a href="merge.h#qh_ANGLEdegen">qh_ANGLEdegen</a>
indicates degenerate facet in mergeT->angle </li>
<li><a href="merge.h#qh_ANGLEconcave">qh_ANGLEconcave</a>
offset to indicate concave facets in
mergeT->angle </li>
<li><a href="merge.h#qh_MERGEapex">qh_MERGEapex</a>
flag for qh_mergefacet() to indicate an apex
merge </li>
</ul>
<h3><a href="qh-merge.htm#TOC">»</a><a name="mtop">top-level merge
functions</a></h3>
<ul>
<li><a href="merge.c#all_merges">qh_all_merges</a>
merge all non-convex facets </li>
<li><a href="merge.c#checkzero">qh_checkzero</a>
check that facets are clearly convex </li>
<li><a href="merge.c#flippedmerges">qh_flippedmerges</a>
merge flipped facets into best neighbor </li>
<li><a href="merge.c#forcedmerges">qh_forcedmerges</a>
merge all duplicate ridges </li>
<li><a href="merge.c#merge_degenredundant">qh_merge_degenredundant</a>
merge degenerate and redundant facets </li>
<li><a href="merge.c#merge_nonconvex">qh_merge_nonconvex</a>
merge a non-convex ridge </li>
<li><a href="merge.c#premerge">qh_premerge</a>
pre-merge non-convex facets </li>
<li><a href="merge.c#postmerge">qh_postmerge</a>
post-merge nonconvex facets as defined by
maxcentrum/maxangle </li>
</ul>
<h3><a href="qh-merge.htm#TOC">»</a><a name="mset">functions for
identifying merges</a></h3>
<ul>
<li><a href="merge.c#appendmergeset">qh_appendmergeset</a>
appends an entry to qh.facet_mergeset</li>
<li><a href="merge.c#compareangle">qh_compareangle</a>
used by qsort() to order merges </li>
<li><a href="merge.c#comparemerge">qh_comparemerge</a>
used by qsort() to order merges </li>
<li><a href="merge.c#degen_redundant_facet">qh_degen_redundant_facet</a>
check for a degenerate and redundant facet</li>
<li><a href="merge.c#degen_redundant_neighbors">qh_degen_redundant_neighbors</a>
append degenerate and redundant neighbors to
qh.degen_mergeset </li>
<li><a href="merge.c#getmergeset_initial">qh_getmergeset_initial</a>
build initial qh.facet_mergeset </li>
<li><a href="merge.c#getmergeset">qh_getmergeset</a>
update qh.facet_mergeset </li>
<li><a href="merge.c#mark_dupridges">qh_mark_dupridges</a>
add duplicated ridges to qh.facet_mergeset</li>
<li><a href="merge.c#maydropneighbor">qh_maydropneighbor</a>
drop neighbor relationship if no ridge between
facet and neighbor </li>
<li><a href="merge.c#test_appendmerge">qh_test_appendmerge</a>
test a pair of facets for convexity and append to
qh.facet_mergeset if non-convex </li>
<li><a href="merge.c#test_vneighbors">qh_test_vneighbors</a>
test vertex neighbors for convexity </li>
</ul>
<h3><a href="qh-merge.htm#TOC">»</a><a name="mbest">functions for
determining the best merge</a></h3>
<ul>
<li><a href="merge.c#findbest_test">qh_findbest_test</a>
test neighbor for best merge </li>
<li><a href="merge.c#findbestneighbor">qh_findbestneighbor</a>
finds best neighbor of a facet for merging (i.e.,
closest hyperplane) </li>
</ul>
<h3><a href="qh-merge.htm#TOC">»</a><a name="mmerge">functions for
merging facets</a></h3>
<ul>
<li><a href="merge.c#copynonconvex">qh_copynonconvex</a>
copy non-convex flag to another ridge for the
same neighbor </li>
<li><a href="merge.c#makeridges">qh_makeridges</a>
creates explicit ridges between simplicial facets
</li>
<li><a href="merge.c#mergefacet">qh_mergefacet</a>
merges one facet into another facet</li>
<li><a href="merge.c#mergeneighbors">qh_mergeneighbors</a>
merges the neighbors of two facets </li>
<li><a href="merge.c#mergeridges">qh_mergeridges</a>
merges the ridge sets of two facets </li>
<li><a href="merge.c#mergesimplex">qh_mergesimplex</a>
merge a simplicial facet into another simplicial
facet </li>
<li><a href="merge.c#mergevertex_del">qh_mergevertex_del</a>
delete a vertex due to merging one facet into
another facet </li>
<li><a href="merge.c#mergevertex_neighbors">qh_mergevertex_neighbors</a>
merge the vertex neighbors of two facets </li>
<li><a href="merge.c#mergevertices">qh_mergevertices</a>
merge the vertex sets of two facets </li>
<li><a href="merge.c#newvertices">qh_newvertices</a>
register all vertices as new vertices </li>
<li><a href="merge.c#updatetested">qh_updatetested</a>
clear tested flags and centrums involved in a
merge </li>
<li><a href="merge.c#willdelete">qh_willdelete</a>
moves facet to qh.visible_list; sets replacement
or NULL </li>
</ul>
<h3><a href="qh-merge.htm#TOC">»</a><a name="mcycle">functions for
merging a cycle of facets</a></h3>
<p>If a point is coplanar with an horizon facet, the
corresponding new facets are linked together (a <em>samecycle</em>)
for merging.</p>
<ul>
<li><a href="merge.c#basevertices">qh_basevertices</a>
return temporary set of base vertices for a
samecycle </li>
<li><a href="merge.c#mergecycle">qh_mergecycle</a>
merge a samecycle into a horizon facet </li>
<li><a href="merge.c#mergecycle_all">qh_mergecycle_all</a>
merge all samecycles into horizon facets</li>
<li><a href="merge.c#mergecycle_facets">qh_mergecycle_facets</a>
finish merge of samecycle </li>
<li><a href="merge.c#mergecycle_neighbors">qh_mergecycle_neighbors</a>
merge neighbor sets for samecycle </li>
<li><a href="merge.c#mergecycle_ridges">qh_mergecycle_ridges</a>
merge ridge sets for samecycle </li>
<li><a href="merge.c#mergecycle_vneighbors">qh_mergecycle_vneighbors</a>
merge vertex neighbor sets for samecycle </li>
</ul>
<h3><a href="qh-merge.htm#TOC">»</a><a name="mrename">functions
for renaming a vertex</a></h3>
<ul>
<li><a href="merge.c#comparevisit">qh_comparevisit</a>
used by qsort() to order vertices by visitid</li>
<li><a href="merge.c#reducevertices">qh_reducevertices</a>
reduce vertex sets </li>
<li><a href="merge.c#redundant_vertex">qh_redundant_vertex</a>
returns true if detect and rename redundant
vertex </li>
<li><a href="merge.c#rename_sharedvertex">qh_rename_sharedvertex</a>
detect and rename a shared vertex </li>
<li><a href="merge.c#renameridgevertex">qh_renameridgevertex</a>
rename oldvertex to newvertex in a ridge </li>
<li><a href="merge.c#renamevertex">qh_renamevertex</a>
rename oldvertex to newvertex in ridges </li>
<li><a href="merge.c#remove_extravertices">qh_remove_extravertices</a>
remove extra vertices in non-simplicial facets </li>
</ul>
<h3><a href="qh-merge.htm#TOC">»</a><a name="mvertex">functions
for identifying vertices for renaming</a></h3>
<ul>
<li><a href="merge.c#find_newvertex">qh_find_newvertex</a>
locate new vertex for renaming old vertex </li>
<li><a href="merge.c#hashridge">qh_hashridge</a> add
ridge to hashtable </li>
<li><a href="merge.c#hashridge_find">qh_hashridge_find</a>
returns matching ridge in hashtable</li>
<li><a href="merge.c#neighbor_intersections">qh_neighbor_intersections</a>
return intersection of vertex sets for
neighboring facets </li>
<li><a href="merge.c#vertexridges">qh_vertexridges</a>
return temporary set of ridges adjacent to a
vertex </li>
<li><a href="merge.c#vertexridges_facet">qh_vertexridges_facet</a>
add adjacent ridges for a vertex in facet </li>
</ul>
<h3><a href="qh-merge.htm#TOC">»</a><a name="mcheck">functions for check and
trace</a></h3>
<ul>
<li><a href="merge.c#checkconnect">qh_checkconnect</a>
check that new facets are connected </li>
<li><a href="merge.c#tracemerge">qh_tracemerge</a>
print trace message after merge </li>
<li><a href="merge.c#tracemerging">qh_tracemerging</a>
print trace message during post-merging </li>
</ul>
<p><!-- Navigation links --> </p>
<hr>
<p><b>Up:</b>
<a href="http://www.qhull.org">Home page for
Qhull</a> <br>
<b>Up:</b> <a href="../../html/index.htm#TOC">Qhull manual: Table of Contents</a> <br>
<b>Up:</b> <a href="../../html/qh-quick.htm#programs">Programs</a>
• <a href="../../html/qh-quick.htm#options">Options</a>
• <a href="../../html/qh-opto.htm#output">Output</a>
• <a href="../../html/qh-optf.htm#format">Formats</a>
• <a href="../../html/qh-optg.htm#geomview">Geomview</a>
• <a href="../../html/qh-optp.htm#print">Print</a>
• <a href="../../html/qh-optq.htm#qhull">Qhull</a>
• <a href="../../html/qh-optc.htm#prec">Precision</a>
• <a href="../../html/qh-optt.htm#trace">Trace</a>
• <a href="index.htm">Functions</a><br>
<b>Up:</b> <a href="../../html/qh-code.htm#TOC">Qhull code: Table of Contents</a> <br>
<b>To:</b> <a href="index.htm">Qhull functions</a>, macros, and data structures<br>
<b>To:</b> <a href="qh-geom.htm">Geom</a> •
<a href="qh-globa.htm">Global</a> • <a href="qh-io.htm">Io</a>
• <a href="qh-mem.htm">Mem</a> • <a href="qh-merge.htm">Merge</a>
• <a href="qh-poly.htm">Poly</a> • <a href="qh-qhull.htm#TOC">Qhull</a>
• <a href="qh-set.htm">Set</a> • <a href="qh-stat.htm">Stat</a>
• <a href="qh-user.htm">User</a><br>
</p>
<p><!-- GC common information --> </p>
<hr>
<p><a href="http://www.geom.uiuc.edu/"><img
src="../../html/qh--geom.gif" align="middle" width="40" height="40"></a><i>The
Geometry Center Home Page </i></p>
<p>Comments to: <a href=mailto:qhull@qhull.org>qhull@qhull.org</a>
</a><br>
Created: May 2, 1997 --- <!-- hhmts start --> Last modified: see top <!-- hhmts end --> </p>
</body>
</html>
|
