← Back to branch summary

~diresu/blender/blender-command-port

« back to all changes in this revision

Viewing changes to extern/qhull/html/qh-eg.htm

  • Committer: theeth
  • Date: 2008-10-14 16:52:04 UTC
  • Revision ID: vcs-imports@canonical.com-20081014165204-r32w2gm6s0osvdhn
copy back trunk

Show diffs side-by-side

added added

removed removed

Lines of Context:
extern/qhull/html/qh-eg.htm
 
1
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
 
2
<html>
 
3
 
 
4
<head>
 
5
<title>Examples of Qhull</title>
 
6
</head>
 
7
 
 
8
<body>
 
9
<!-- Navigation links -->
 
10
<p><a name="TOP"><b>Up:</b></a> <a href="http://www.geom.umn.edu/software/qhull">Home
 
11
page</a> for Qhull <br>
 
12
<b>Up:</b> <a href="index.htm#TOC">Qhull manual</a>: Table of Contents<br>
 
13
<b>To:</b> <a href="qh-quick.htm#programs">Programs</a>
 
14
&#149; <a href="qh-quick.htm#options">Options</a> 
 
15
&#149; <a href="qh-opto.htm#output">Output</a> 
 
16
&#149; <a href="qh-optf.htm#format">Formats</a> 
 
17
&#149; <a href="qh-optg.htm#geomview">Geomview</a> 
 
18
&#149; <a href="qh-optp.htm#print">Print</a>
 
19
&#149; <a href="qh-optq.htm#qhull">Qhull</a> 
 
20
&#149; <a href="qh-optc.htm#prec">Precision</a> 
 
21
&#149; <a href="qh-optt.htm#trace">Trace</a><br>
 
22
<b>To: </b><a href="#TOC">Qhull examples: Table of Contents</a> (please wait
 
23
while loading)<br>
 
24
 
 
25
<hr>
 
26
<!-- Main text of document -->
 
27
<h1><a
 
28
href="http://www.geom.umn.edu/graphics/pix/Special_Topics/Computational_Geometry/half.html"><img
 
29
src="qh--half.gif" alt="[halfspace]" align="middle" width="100"
 
30
height="100"></a> Examples of Qhull</h1>
 
31
 
 
32
<p>This section of the Qhull manual will introduce you to Qhull
 
33
and its options. Each example is a file for viewing with <a
 
34
href="index.htm#geomview">Geomview</a>.  You will need to
 
35
use a Unix computer with a copy of Geomview.
 
36
<p>
 
37
If you are not running Unix, you can view <a
 
38
href="http://www.geom.umn.edu/graphics/pix/Special_Topics/Computational_Geometry/welcome.html">pictures</a> 
 
39
for some of the examples.  To understand Qhull without Geomview, try the
 
40
examples in <a href="qh-quick.htm#programs">Programs</a> and
 
41
<a href="qh-quick.htm#programs">Programs/input</a>.  You can also try small
 
42
examples that you compute by hand.  Use <a href="rbox.htm">rbox</a>
 
43
to generate examples.
 
44
<p>
 
45
To generate the Geomview examples, execute the shell script <tt>eg/q_eg</tt>.
 
46
It uses <tt>rbox</tt>.  The shell script <tt>eg/q_egtest</tt> generates
 
47
test examples, and <tt>eg/q_test</tt> exercises the code. If you
 
48
find yourself viewing the inside of a 3-d example, use Geomview's
 
49
normalization option on the 'obscure' menu.</p>
 
50
 
 
51
<p><b>Copyright &copy; 1995-2002 The Geometry Center, Minneapolis MN</b></p>
 
52
 
 
53
<hr>
 
54
 
 
55
<h2><a href="#TOP">�</a><a name="TOC">Qhull examples: Table of
 
56
Contents </a></h2>
 
57
 
 
58
<ul>
 
59
    <li><a href="#2d">2-d and 3-d examples</a></li>
 
60
    <li><a href="#how">How Qhull adds a point</a></li>
 
61
    <li><a href="#joggle">Joggled input and triangulated output</a></li>
 
62
    <li><a href="#delaunay">Delaunay and Voronoi diagrams</a></li>
 
63
    <li><a href="#merge">Facet merging for imprecision</a></li>
 
64
    <li><a href="#4d">4-d objects</a></li>
 
65
    <li><a href="#half">Halfspace intersections</a></li>
 
66
</ul>
 
67
 
 
68
<hr>
 
69
<ul>
 
70
    <li><a href="#TOC">�</a><a name="2d">2-d and 3-d examples</a><ul>
 
71
            <li><a href="#01">eg.01.cube</a></li>
 
72
            <li><a href="#02">eg.02.diamond.cube</a></li>
 
73
            <li><a href="#03">eg.03.sphere</a></li>
 
74
            <li><a href="#04">eg.04.circle</a></li>
 
75
            <li><a href="#05">eg.05.spiral</a></li>
 
76
            <li><a href="#06">eg.06.merge.square</a></li>
 
77
            <li><a href="#07">eg.07.box</a></li>
 
78
            <li><a href="#08a">eg.08a.cube.sphere</a></li>
 
79
            <li><a href="#08b">eg.08b.diamond.sphere</a></li>
 
80
            <li><a href="#09">eg.09.lens</a></li>
 
81
        </ul>
 
82
    </li>
 
83
    <li><a href="#TOC">�</a><a name="how">How Qhull adds a point</a><ul>
 
84
            <li><a href="#10a">eg.10a.sphere.visible</a></li>
 
85
            <li><a href="#10b">eg.10b.sphere.beyond</a></li>
 
86
            <li><a href="#10c">eg.10c.sphere.horizon</a></li>
 
87
            <li><a href="#10d">eg.10d.sphere.cone</a></li>
 
88
            <li><a href="#10e">eg.10e.sphere.new</a></li>
 
89
            <li><a href="#14">eg.14.sphere.corner</a></li>
 
90
        </ul>
 
91
    </li>
 
92
    <li><a href="#TOC">�</a> <a name="joggle">Joggled input and triangulated output</a>
 
93
        <ul>
 
94
            <li><a href="#15a">eg.15a.surface</a></li>
 
95
            <li><a href="#15b">eg.15b.triangle</a></li>
 
96
            <li><a href="#15c">eg.15c.joggle</a></li>
 
97
        </ul>
 
98
    <li><a href="#TOC">�</a><a name="delaunay"> Delaunay and
 
99
        Voronoi diagrams</a><ul>
 
100
            <li><a href="#17a">eg.17a.delaunay.2</a></li>
 
101
            <li><a href="#17b">eg.17b.delaunay.2i</a></li>
 
102
            <li><a href="#17c">eg.17c.delaunay.2-3</a></li>
 
103
            <li><a href="#17d">eg.17d.voronoi.2</a></li>
 
104
            <li><a href="#17e">eg.17e.voronoi.2i</a></li>
 
105
            <li><a href="#17f">eg.17f.delaunay.3</a></li>
 
106
            <li><a href="#18a">eg.18a.furthest.2-3</a></li>
 
107
            <li><a href="#18b">eg.18b.furthest-up.2-3</a></li>
 
108
            <li><a href="#18c">eg.18c.furthest.2</a></li>
 
109
            <li><a href="#19">eg.19.voronoi.region.3</a></li>
 
110
        </ul>
 
111
    </li>
 
112
    <li><a href="#TOC">�</a><a name="merge">Facet merging for
 
113
        imprecision </a><ul>
 
114
            <li><a href="#20">eg.20.cone</a></li>
 
115
            <li><a href="#21a">eg.21a.roundoff.errors</a></li>
 
116
            <li><a href="#21b">eg.21b.roundoff.fixed</a></li>
 
117
            <li><a href="#22a">eg.22a.merge.sphere.01</a></li>
 
118
            <li><a href="#22b">eg.22b.merge.sphere.-01</a></li>
 
119
            <li><a href="#22c">eg.22c.merge.sphere.05</a></li>
 
120
            <li><a href="#22d">eg.22d.merge.sphere.-05</a></li>
 
121
            <li><a href="#23">eg.23.merge.cube</a></li>
 
122
        </ul>
 
123
    </li>
 
124
    <li><a href="#TOC">�</a><a name="4d">4-d objects</a><ul>
 
125
            <li><a href="#24">eg.24.merge.cube.4d-in-3d</a></li>
 
126
            <li><a href="#30">eg.30.4d.merge.cube</a></li>
 
127
            <li><a href="#31">eg.31.4d.delaunay</a></li>
 
128
            <li><a href="#32">eg.32.4d.octant</a></li>
 
129
        </ul>
 
130
    </li>
 
131
    <li><a href="#TOC">�</a><a name="half">Halfspace
 
132
        intersections</a><ul>
 
133
            <li><a href="#33a">eg.33a.cone</a></li>
 
134
            <li><a href="#33b">eg.33b.cone.dual</a></li>
 
135
            <li><a href="#33c">eg.33c.cone.halfspace</a></li>
 
136
        </ul>
 
137
    </li>
 
138
</ul>
 
139
 
 
140
<hr>
 
141
 
 
142
<h2><a href="#TOC">�</a>2-d and 3-d examples</h2>
 
143
 
 
144
<h3><a href="#2d">�</a><a name="01">rbox c D3 | qconvex G
 
145
&gt;eg.01.cube </a></h3>
 
146
 
 
147
<p>The first example is a cube in 3-d. The color of each facet
 
148
indicates its normal. For example, normal [0,0,1] along the Z
 
149
axis is (r=0.5, g=0.5, b=1.0). With the 'Dn' option in <tt>rbox</tt>,
 
150
you can generate hypercubes in any dimension. Above 7-d the
 
151
number of intermediate facets grows rapidly. Use '<a
 
152
href="qh-optt.htm#TFn">TFn</a>' to track qconvex's progress. Note
 
153
that each facet is a square that qconvex merged from coplanar
 
154
triangles.</p>
 
155
 
 
156
<h3><a href="#2d">�</a><a name="02">rbox c d G3.0 | qconvex G
 
157
&gt;eg.02.diamond.cube </a></h3>
 
158
 
 
159
<p>The second example is a cube plus a diamond ('d') scaled by <tt>rbox</tt>'s
 
160
'G' option. In higher dimensions, diamonds are much simpler than
 
161
hypercubes. </p>
 
162
 
 
163
<h3><a href="#2d">�</a><a name="03">rbox s 100 D3 | qconvex G
 
164
&gt;eg.03.sphere </a></h3>
 
165
 
 
166
<p>The <tt>rbox s</tt> option generates random points and
 
167
projects them to the d-sphere. All points should be on the convex
 
168
hull. Notice that random points look more clustered than you
 
169
might expect. You can get a smoother distribution by merging
 
170
facets and printing the vertices, e.g.,<i> rbox 1000 s | qconvex
 
171
A-0.95 p | qconvex G &gt;eg.99</i>.</p>
 
172
 
 
173
<h3><a href="#2d">�</a><a name="04">rbox s 100 D2 | qconvex G
 
174
&gt;eg.04.circle </a></h3>
 
175
 
 
176
<p>In 2-d, there are many ways to generate a convex hull. One of
 
177
the earliest algorithms, and one of the fastest, is the 2-d
 
178
Quickhull algorithm [c.f., Preparata &amp; Shamos <a
 
179
href="index.htm#pre-sha85">'85</a>]. It was the model for
 
180
Qhull.</p>
 
181
 
 
182
<h3><a href="#2d">�</a><a name="05">rbox 10 l | qconvex G
 
183
&gt;eg.05.spiral </a></h3>
 
184
 
 
185
<p>One rotation of a spiral.</p>
 
186
 
 
187
<h3><a href="#2d">�</a><a name="06">rbox 1000 D2 | qconvex C-0.03
 
188
Qc Gapcv &gt;eg.06.merge.square</a></h3>
 
189
 
 
190
<p>This demonstrates how Qhull handles precision errors. Option '<a
 
191
href="qh-optc.htm#Cn">C-0.03</a>' requires a clearly convex angle
 
192
between adjacent facets. Otherwise, Qhull merges the facets. </p>
 
193
 
 
194
<p>This is the convex hull of random points in a square. The
 
195
facets have thickness because they must be outside all points and
 
196
must include their vertices. The colored lines represent the
 
197
original points and the spheres represent the vertices. Floating
 
198
in the middle of each facet is the centrum. Each centrum is at
 
199
least 0.03 below the planes of its neighbors. This guarantees
 
200
that the facets are convex.</p>
 
201
 
 
202
<h3><a href="#2d">�</a><a name="07">rbox 1000 D3 | qconvex G
 
203
&gt;eg.07.box </a></h3>
 
204
 
 
205
<p>Here's the same distribution but in 3-d with Qhull handling
 
206
machine roundoff errors. Note the large number of facets. </p>
 
207
 
 
208
<h3><a href="#2d">�</a><a name="08a">rbox c G0.4 s 500 | qconvex G
 
209
&gt;eg.08a.cube.sphere </a></h3>
 
210
 
 
211
<p>The sphere is just barely poking out of the cube. Try the same
 
212
distribution with randomization turned on ('<a
 
213
href="qh-optq.htm#Qr">Qr</a>'). This turns Qhull into a
 
214
randomized incremental algorithm. To compare Qhull and
 
215
randomization, look at the number of hyperplanes created and the
 
216
number of points partitioned. Don't compare CPU times since Qhull's
 
217
implementation of randomization is inefficient. The number of
 
218
hyperplanes and partitionings indicate the dominant costs for
 
219
Qhull. With randomization, you'll notice that the number of
 
220
facets created is larger than before. This is especially true as
 
221
you increase the number of points. It is because the randomized
 
222
algorithm builds most of the sphere before it adds the cube's
 
223
vertices.</p>
 
224
 
 
225
<h3><a href="#2d">�</a><a name="08b">rbox d G0.6 s 500 | qconvex G
 
226
&gt;eg.08b.diamond.sphere </a></h3>
 
227
 
 
228
<p>This is a combination of the diamond distribution and the
 
229
sphere.</p>
 
230
 
 
231
<h3><a href="#2d">�</a><a name="09">rbox 100 L3 G0.5 s | qconvex 
 
232
G &gt;eg.09.lens </a></h3>
 
233
 
 
234
<p>Each half of the lens distribution lies on a sphere of radius
 
235
three. A directed search for the furthest facet below a point
 
236
(e.g., qh_findbest in <tt>geom.c</tt>) may fail if started from
 
237
an arbitrary facet. For example, if the first facet is on the
 
238
opposite side of the lens, a directed search will report that the
 
239
point is inside the convex hull even though it is outside. This
 
240
problem occurs whenever the curvature of the convex hull is less
 
241
than a sphere centered at the test point. </p>
 
242
 
 
243
<p>To prevent this problem, Qhull does not use directed search
 
244
all the time. When Qhull processes a point on the edge of the
 
245
lens, it partitions the remaining points with an exhaustive
 
246
search instead of a directed search (see qh_findbestnew in <tt>geom2.c</tt>).
 
247
</p>
 
248
 
 
249
<h2><a href="#TOC">�</a>How Qhull adds a point</h2>
 
250
 
 
251
<h3><a href="#how">�</a><a name="10a">rbox 100 s P0.5,0.5,0.5 |
 
252
qconvex Ga QG0 &gt;eg.10a.sphere.visible</a></h3>
 
253
 
 
254
<p>The next 4 examples show how Qhull adds a point. The point
 
255
[0.5,0.5,0.5] is at one corner of the bounding box. Qhull adds a
 
256
point using the beneath-beyond algorithm. First Qhull finds all
 
257
of the facets that are visible from the point. Qhull will replace
 
258
these facets with new facets.</p>
 
259
 
 
260
<h3><a href="#how">�</a><a name="10b">rbox 100 s
 
261
P0.5,0.5,0.5|qconvex Ga QG-0 &gt;eg.10b.sphere.beyond </a></h3>
 
262
 
 
263
<p>These are the facets that are not visible from the point.
 
264
Qhull will keep these facets.</p>
 
265
 
 
266
<h3><a href="#how">�</a><a name="10c">rbox 100 s P0.5,0.5,0.5 |
 
267
qconvex PG Ga QG0 &gt;eg.10c.sphere.horizon </a></h3>
 
268
 
 
269
<p>These facets are the horizon facets; they border the visible
 
270
facets. The inside edges are the horizon ridges. Each horizon
 
271
ridge will form the base for a new facet.</p>
 
272
 
 
273
<h3><a href="#how">�</a><a name="10d">rbox 100 s P0.5,0.5,0.5 |
 
274
qconvex Ga QV0 PgG &gt;eg.10d.sphere.cone </a></h3>
 
275
 
 
276
<p>This is the cone of points from the new point to the horizon
 
277
facets.  Try combining this image with <tt>eg.10c.sphere.horizon</tt>
 
278
and <tt>eg.10a.sphere.visible</tt>.
 
279
</p>
 
280
 
 
281
<h3><a href="#how">�</a><a name="10e">rbox 100 s P0.5,0.5,0.5 |
 
282
qconvex Ga &gt;eg.10e.sphere.new</a></h3>
 
283
 
 
284
<p>This is the convex hull after [0.5,0.5,0.5] has been added.
 
285
Note that in actual practice, the above sequence would never
 
286
happen. Unlike the randomized algorithms, Qhull always processes
 
287
a point that is furthest in an outside set. A point like
 
288
[0.5,0.5,0.5] would be one of the first points processed.</p>
 
289
 
 
290
<h3><a href="#how">�</a><a name="14">rbox 100 s P0.5,0.5,0.5 |
 
291
qhull Ga QV0g Q0 &gt;eg.14.sphere.corner</a></h3>
 
292
 
 
293
<p>The '<a href="qh-optq.htm#QVn">QVn</a>', '<a
 
294
href="qh-optq.htm#QGn">QGn </a>' and '<a href="qh-optp.htm#Pdk">Pdk</a>'
 
295
options define good facets for Qhull. In this case '<a
 
296
href="qh-optq.htm#QVn">QV0</a>' defines the 0'th point
 
297
[0.5,0.5,0.5] as the good vertex, and '<a href="qh-optq.htm#Qg">Qg</a>'
 
298
tells Qhull to only build facets that might be part of a good
 
299
facet. This technique reduces output size in low dimensions. It
 
300
does not work with facet merging.</p>
 
301
 
 
302
<h2><a href="#TOC">�</a>Joggled input and triangulated output</h2>
 
303
 
 
304
<h3><a href="#joggle">�</a><a name="15a">rbox 500 W0 | qconvex QR0 Qc Gvp &gt;eg.15a.surface</a></h3>
 
305
 
 
306
<p>This is the convex hull of 500 points on the surface of
 
307
a cube.  Note the large, non-simplicial facet for each face. 
 
308
Qhull merges non-convex facets.
 
309
 
 
310
<p>If the facets were not merged, Qhull
 
311
would report precision problems.  For example, turn off facet merging
 
312
with option '<a href="qh-optq.htm#Q0">Q0</a>'.  Qhull may report concave
 
313
facets, flipped facets, or other precision errors:
 
314
<blockquote>
 
315
rbox 500 W0 | qhull QR0 Q0
 
316
</blockquote>
 
317
 
 
318
<p>
 
319
<h3><a href="#joggle">�</a><a name="15b">rbox 500 W0 | qconvex QR0 Qt Qc Gvp &gt;eg.15b.triangle</a></h3>
 
320
 
 
321
<p>Like the previous examples, this is the convex hull of 500 points on the 
 
322
surface of a cube.  Option '<a href="qh-optq.htm#Qt">Qt</a>' triangulates the
 
323
non-simplicial facets.  Triangulated output is  
 
324
particularly helpful for Delaunay triangulations.
 
325
 
 
326
<p>
 
327
<h3><a href="#joggle">�</a><a name="15c">rbox 500 W0 | qconvex QR0 QJ5e-2 Qc Gvp &gt;eg.15c.joggle</a></h3>
 
328
 
 
329
<p>This is the convex hull of 500 joggled points on the surface of
 
330
a cube.  The option '<a href="qh-optq.htm#QJn">QJ5e-2</a>'
 
331
sets a very large joggle to make the effect visible.  Notice
 
332
that all of the facets are triangles.  If you rotate the cube,
 
333
you'll see red-yellow lines for coplanar points.
 
334
<p>
 
335
With option '<a href="qh-optq.htm#QJn">QJ</a>', Qhull joggles the
 
336
input to avoid precision problems.  It adds a small random number
 
337
to each input coordinate.  If a precision
 
338
error occurs, it increases the joggle and tries again.  It repeats
 
339
this process until no precision problems occur.
 
340
<p>
 
341
Joggled input is a simple solution to precision problems in
 
342
computational geometry.  Qhull can also merge facets to handle
 
343
precision problems.  See <a href="qh-impre.htm#joggle">Joggled input
 
344
or merged facets</a>.  
 
345
 
 
346
<h2><a href="#TOC">�</a>Delaunay and Voronoi diagrams</h2>
 
347
 
 
348
<h3><a href="#delaunay">�</a><a name="17a">qdelaunay Qt
 
349
&lt;eg.data.17 GnraD2 &gt;eg.17a.delaunay.2</a></h3>
 
350
 
 
351
<p>
 
352
The input file, <tt>eg.data.17</tt>, consists of a square, 15 random
 
353
points within the outside half of the square, and 6 co-circular
 
354
points centered on the square.
 
355
 
 
356
<p>The Delaunay triangulation is the triangulation with empty
 
357
circumcircles.  The input for this example is unusual because it
 
358
includes six co-circular points.  Every triangular subset of these 
 
359
points has the same circumcircle.  Option '<a href="qh-optq.htm#Qt">Qt</a>'
 
360
triangulates the co-circular facet.</p>
 
361
 
 
362
<h3><a href="#delaunay">�</a><a name="17b">qdelaunay &lt;eg.data.17
 
363
GnraD2 &gt;eg.17b.delaunay.2i</a></h3>
 
364
 
 
365
<p>This is the same example without triangulated output ('<a href="qh-optq.htm#Qt">Qt</a>').  qdelaunay
 
366
merges the non-unique Delaunay triangles into a hexagon.</p>
 
367
 
 
368
<h3><a href="#delaunay">�</a><a name="17c">qdelaunay &lt;eg.data.17
 
369
Ga &gt;eg.17c.delaunay.2-3 </a></h3>
 
370
 
 
371
<p>This is how Qhull generated both diagrams. Use Geomview's
 
372
'obscure' menu to turn off normalization, and Geomview's
 
373
'cameras' menu to turn off perspective. Then load this <a
 
374
href="http://www.geom.umn.edu/graphics/pix/Special_Topics/Computational_Geometry/delaunay.html">object</a>
 
375
with one of the previous diagrams.</p>
 
376
 
 
377
<p>The points are lifted to a paraboloid by summing the squares
 
378
of each coordinate. These are the light blue points. Then the
 
379
convex hull is taken. That's what you see here. If you look up
 
380
the Z-axis, you'll see that points and edges coincide.</p>
 
381
 
 
382
<h3><a href="#delaunay">�</a><a name="17d">qvoronoi QJ
 
383
&lt;eg.data.17 Gna &gt;eg.17d.voronoi.2</a></h3>
 
384
 
 
385
<p>The Voronoi diagram is the dual of the Delaunay triangulation.
 
386
Here you see the original sites and the Voronoi vertices.   
 
387
Notice the each
 
388
vertex is equidistant from three sites. The edges indicate the
 
389
Voronoi region for a site. Qhull does not draw the unbounded
 
390
edges. Instead, it draws extra edges to close the unbounded
 
391
Voronoi regions. You may find it helpful to enclose the input
 
392
points in a square.  You can compute the unbounded
 
393
rays from option '<a href="qh-optf.htm#Fo2">Fo</a>'.
 
394
</p>
 
395
 
 
396
<p>Instead
 
397
of triangulated output ('<a href="qh-optq.htm#Qt">Qt</a>'), this 
 
398
example uses joggled input ('<a href="qh-optq.htm#QJn">QJ</a>').  
 
399
Normally, you should use neither 'QJ' nor 'Qt' for Voronoi diagrams.
 
400
 
 
401
<h3><a href="#delaunay">�</a><a name="17e">qvoronoi &lt;eg.data.17
 
402
Gna &gt;eg.17e.voronoi.2i </a></h3>
 
403
 
 
404
<p>This looks the same as the previous diagrams, but take a look
 
405
at the data.  Run 'qvoronoi p &lt;eg/eg.data.17'.  This prints
 
406
the Voronoi vertices.  
 
407
 
 
408
<p>With 'QJ', there are four nearly identical Voronoi vertices
 
409
within 10^-11 of the origin.  Option 'QJ' joggled the input.  After the joggle,
 
410
the cocircular 
 
411
input sites are no longer cocircular.  The corresponding Voronoi vertices are 
 
412
similar but not identical.
 
413
 
 
414
<p>This example does not use options 'Qt' or 'QJ'.  The cocircular
 
415
input sites define one Voronoi vertex near the origin. </p>
 
416
 
 
417
<p>Option 'Qt' would triangulate the corresponding Delaunay region into
 
418
four triangles.  Each triangle is assigned the same Voronoi vertex.</p>
 
419
 
 
420
<h3><a href="#delaunay">�</a><a name="17f"> rbox c G0.1 d |
 
421
qdelaunay Gt Qz &lt;eg.17f.delaunay.3 </a></h3>
 
422
 
 
423
<p>This is the 3-d Delaunay triangulation of a small cube inside
 
424
a prism. Since the outside ridges are transparent, it shows the
 
425
interior of the outermost facets. If you slice open the
 
426
triangulation with Geomview's ginsu, you will see that the innermost
 
427
facet is a cube. Note the use of '<a href="qh-optq.htm#Qz">Qz</a>'
 
428
to add a point &quot;at infinity&quot;. This avoids a degenerate
 
429
input due to cospherical points.</p>
 
430
 
 
431
<h3><a href="#delaunay">�</a><a name="18a">rbox 10 D2 d | qdelaunay
 
432
Qu G &gt;eg.18a.furthest.2-3 </a></h3>
 
433
 
 
434
<p>The furthest-site Voronoi diagram contains Voronoi regions for
 
435
points that are <i>furthest </i>from an input site. It is the
 
436
dual of the furthest-site Delaunay triangulation. You can
 
437
determine the furthest-site Delaunay triangulation from the
 
438
convex hull of the lifted points (<a href="#17c">eg.17c.delaunay.2-3</a>).
 
439
The upper convex hull (blue) generates the furthest-site Delaunay
 
440
triangulation. </p>
 
441
 
 
442
<h3><a href="#delaunay">�</a><a name="18b">rbox 10 D2 d | qdelaunay
 
443
Qu Pd2 G &gt;eg.18b.furthest-up.2-3</a></h3>
 
444
 
 
445
<p>This is the upper convex hull of the preceding example. The
 
446
furthest-site Delaunay triangulation is the projection of the
 
447
upper convex hull back to the input points. The furthest-site
 
448
Voronoi vertices are the circumcenters of the furthest-site
 
449
Delaunay triangles. </p>
 
450
 
 
451
<h3><a href="#delaunay">�</a><a name="18c">rbox 10 D2 d | qvoronoi
 
452
Qu Gv &gt;eg.18c.furthest.2</a></h3>
 
453
 
 
454
<p>This shows an incomplete furthest-site Voronoi diagram. It
 
455
only shows regions with more than two vertices. The regions are
 
456
artificially truncated. The actual regions are unbounded. You can
 
457
print the regions' vertices with 'qvoronoi Qu <a
 
458
href="qh-opto.htm#o">o</a>'. </p>
 
459
 
 
460
<p>Use Geomview's 'obscure' menu to turn off normalization, and
 
461
Geomview's 'cameras' menu to turn off perspective. Then load this
 
462
with the upper convex hull.</p>
 
463
 
 
464
<h3><a href="#delaunay">�</a><a name="19">rbox 10 D3 | qvoronoi QV5
 
465
p | qconvex G &gt;eg.19.voronoi.region.3 </a></h3>
 
466
 
 
467
<p>This shows the Voronoi region for input site 5 of a 3-d
 
468
Voronoi diagram.</p>
 
469
 
 
470
<h2><a href="#TOC">�</a>Facet merging for imprecision</h2>
 
471
 
 
472
<h3><a href="#merge">�</a><a name="20">rbox r s 20 Z1 G0.2 |
 
473
qconvex G &gt;eg.20.cone </a></h3>
 
474
 
 
475
<p>There are two things unusual about this <a
 
476
href="http://www.geom.umn.edu/graphics/pix/Special_Topics/Computational_Geometry/cone.html">cone</a>.
 
477
One is the large flat disk at one end and the other is the
 
478
rectangles about the middle. That's how the points were
 
479
generated, and if those points were exact, this is the correct
 
480
hull. But <tt>rbox</tt> used floating point arithmetic to
 
481
generate the data. So the precise convex hull should have been
 
482
triangles instead of rectangles. By requiring convexity, Qhull
 
483
has recovered the original design.</p>
 
484
 
 
485
<h3><a href="#merge">�</a><a name="21a">rbox 200 s | qhull Q0
 
486
R0.01 Gav Po &gt;eg.21a.roundoff.errors </a></h3>
 
487
 
 
488
<p>This is the convex hull of 200 cospherical points with
 
489
precision errors ignored ('<a href="qh-optq.htm#Q0">Q0</a>'). To
 
490
demonstrate the effect of roundoff error, we've added a random
 
491
perturbation ('<a href="qh-optc.htm#Rn">R0.01</a>') to every
 
492
distance and hyperplane calculation. Qhull, like all other convex
 
493
hull algorithms with floating point arithmetic, makes
 
494
inconsistent decisions and generates wildly wrong results. In
 
495
this case, one or more facets are flipped over. These facets have
 
496
the wrong color. You can also turn on 'normals' in Geomview's
 
497
appearances menu and turn off 'facing normals'. There should be
 
498
some white lines pointing in the wrong direction. These
 
499
correspond to flipped facets. </p>
 
500
 
 
501
<p>Different machines may not produce this picture. If your
 
502
machine generated a long error message, decrease the number of
 
503
points or the random perturbation ('<a href="qh-optc.htm#Rn">R0.01</a>').
 
504
If it did not report flipped facets, increase the number of
 
505
points or perturbation.</p>
 
506
 
 
507
<h3><a href="#merge">�</a><a name="21b">rbox 200 s | qconvex Qc
 
508
R0.01 Gpav &gt;eg.21b.roundoff.fixed </a></h3>
 
509
 
 
510
<p>Qhull handles the random perturbations and returns an
 
511
imprecise <a
 
512
href="http://www.geom.umn.edu/graphics/pix/Special_Topics/Computational_Geometry/fixed.html">sphere</a>.
 
513
In this case, the output is a weak approximation to the points.
 
514
This is because a random perturbation of '<a
 
515
href="qh-optc.htm#Rn">R0.01 </a>' is equivalent to losing all but
 
516
1.8 digits of precision. The outer planes float above the points
 
517
because Qhull needs to allow for the maximum roundoff error. </p>
 
518
<p> 
 
519
If you start with a smaller random perturbation, you 
 
520
can use joggle ('<a href="qh-optq.htm#QJn">QJn</a>') to avoid
 
521
precision problems.  You need to set <i>n</i> significantly
 
522
larger than the random perturbation.  For example, try 
 
523
'rbox 200 s | qconvex Qc R1e-4 QJ1e-1'.
 
524
 
 
525
<h3><a href="#merge">�</a><a name="22a">rbox 1000 s| qconvex C0.01
 
526
Qc Gcrp &gt;eg.22a.merge.sphere.01</a></h3>
 
527
 
 
528
<h3><a href="#merge">�</a><a name="22b">rbox 1000 s| qconvex
 
529
C-0.01 Qc Gcrp &gt;eg.22b.merge.sphere.-01</a></h3>
 
530
 
 
531
<h3><a href="#merge">�</a><a name="22c">rbox 1000 s| qconvex C0.05
 
532
Qc Gcrpv &gt;eg.22c.merge.sphere.05</a></h3>
 
533
 
 
534
<h3><a href="#merge">�</a><a name="22d">rbox 1000 s| qconvex
 
535
C-0.05 Qc Gcrpv &gt;eg.22d.merge.sphere.-05</a></h3>
 
536
 
 
537
<p>The next four examples compare post-merging and pre-merging ('<a
 
538
href="qh-optc.htm#Cn2">Cn</a>' vs. '<a href="qh-optc.htm#Cn">C-n</a>').
 
539
Qhull uses '-' as a flag to indicate pre-merging.</p>
 
540
 
 
541
<p>Post-merging happens after the convex hull is built. During
 
542
post-merging, Qhull repeatedly merges an independent set of
 
543
non-convex facets. For a given set of parameters, the result is
 
544
about as good as one can hope for.</p>
 
545
 
 
546
<p>Pre-merging does the same thing as post-merging, except that
 
547
it happens after adding each point to the convex hull. With
 
548
pre-merging, Qhull guarantees a convex hull, but the facets are
 
549
wider than those from post-merging. If a pre-merge option is not
 
550
specified, Qhull handles machine round-off errors.</p>
 
551
 
 
552
<p>You may see coplanar points appearing slightly outside
 
553
the facets of the last example.  This is becomes Geomview moves
 
554
line segments forward toward the viewer.  You can avoid the
 
555
effect by setting 'lines closer' to '0' in Geomview's camera menu.
 
556
 
 
557
<h3><a href="#merge">�</a><a name="23">rbox 1000 | qconvex s
 
558
Gcprvah C0.1 Qc &gt;eg.23.merge.cube</a></h3>
 
559
 
 
560
<p>Here's the 3-d imprecise cube with all of the Geomview
 
561
options. There's spheres for the vertices, radii for the coplanar
 
562
points, dots for the interior points, hyperplane intersections,
 
563
centrums, and inner and outer planes.  The radii are shorter than
 
564
the spheres because this uses post-merging ('<a href="qh-optc.htm#Cn2">C0.1</a>')
 
565
instead of pre-merging.
 
566
 
 
567
<h2><a href="#TOC">�</a>4-d objects</h2>
 
568
 
 
569
<p>With Qhull and Geomview you can develop an intuitive sense of
 
570
4-d surfaces. When you get into trouble, think of viewing the
 
571
surface of a 3-d sphere in a 2-d plane.</p>
 
572
 
 
573
<h3><a href="#4d">�</a><a name="24">rbox 5000 D4 | qconvex s GD0v
 
574
Pd0:0.5 C-0.02 C0.1 &gt;eg.24.merge.cube.4d-in-3d</a></h3>
 
575
 
 
576
<p>Here's one facet of the imprecise cube in 4-d. It's projected
 
577
into 3-d (the '<a href="qh-optg.htm#GDn">GDn</a>' option drops
 
578
dimension n). Each ridge consists of two triangles between this
 
579
facet and the neighboring facet. In this case, Geomview displays
 
580
the topological ridges, i.e., as triangles between three
 
581
vertices. That is why the cube looks lopsided.</p>
 
582
 
 
583
<h3><a href="#4d">�</a><a name="30">rbox 5000 D4 | qconvex s
 
584
C-0.02 C0.1 Gh &gt;eg.30.4d.merge.cube </a></h3>
 
585
 
 
586
<p><a
 
587
href="http://www.geom.umn.edu/graphics/pix/Special_Topics/Computational_Geometry/4dcube.html">Here</a>
 
588
is the equivalent in 4-d of the imprecise <a href="#06">square</a>
 
589
and imprecise <a href="#23">cube</a>. It's the imprecise convex
 
590
hull of 5000 random points in a hypercube. It's a full 4-d object
 
591
so Geomview's <tt>ginsu </tt>does not work. If you view it in
 
592
Geomview, you'll be inside the hypercube. To view 4-d objects
 
593
directly, either load the <tt>4dview</tt> module or the <tt>ndview
 
594
</tt>module. For <tt>4dview</tt>, you must have started Geomview
 
595
in the same directory as the object. For <tt>ndview</tt>,
 
596
initialize a set of windows with the prefab menu, and load the
 
597
object through Geomview. The <tt>4dview</tt> module includes an
 
598
option for slicing along any hyperplane. If you do this in the x,
 
599
y, or z plane, you'll see the inside of a hypercube.</p>
 
600
 
 
601
<p>The '<a href="qh-optg.htm#Gh">Gh</a>' option prints the
 
602
geometric intersections between adjacent facets. Note the strong
 
603
convexity constraint for post-merging ('<a href="qh-optc.htm#Cn2">C0.1</a>').
 
604
It deletes the small facets.</p>
 
605
 
 
606
<h3><a href="#4d">�</a><a name="31">rbox 20 D3 | qdelaunay G
 
607
&gt;eg.31.4d.delaunay </a></h3>
 
608
 
 
609
<p>The Delaunay triangulation of 3-d sites corresponds to a 4-d
 
610
convex hull. You can't see 4-d directly but each facet is a 3-d
 
611
object that you can project to 3-d. This is exactly the same as
 
612
projecting a 2-d facet of a soccer ball onto a plane.</p>
 
613
 
 
614
<p>Here we see all of the facets together. You can use Geomview's
 
615
<tt>ndview</tt> to look at the object from several directions.
 
616
Try turning on edges in the appearance menu. You'll notice that
 
617
some edges seem to disappear. That's because the object is
 
618
actually two sets of overlapping facets.</p>
 
619
 
 
620
<p>You can slice the object apart using Geomview's <tt>4dview</tt>.
 
621
With <tt>4dview</tt>, try slicing along the w axis to get a
 
622
single set of facets and then slice along the x axis to look
 
623
inside. Another interesting picture is to slice away the equator
 
624
in the w dimension.</p>
 
625
 
 
626
<h3><a href="#4d">�</a><a name="32">rbox 30 s D4 | qconvex s G
 
627
Pd0d1d2D3</a></h3>
 
628
 
 
629
<p>This is the positive octant of the convex hull of 30 4-d
 
630
points. When looking at 4-d, it's easier to look at just a few
 
631
facets at once. If you picked a facet that was directly above
 
632
you, then that facet looks exactly the same in 3-d as it looks in
 
633
4-d. If you pick several facets, then you need to imagine that
 
634
the space of a facet is rotated relative to its neighbors. Try
 
635
Geomview's <tt>ndview</tt> on this example.</p>
 
636
 
 
637
<h2><a href="#TOC">�</a>Halfspace intersections</h2>
 
638
 
 
639
<h3><a href="#half">�</a><a name="33a">rbox 10 r s Z1 G0.3 |
 
640
qconvex G &gt;eg.33a.cone </a></h3>
 
641
 
 
642
<h3><a href="#half">�</a><a name="33b">rbox 10 r s Z1 G0.3 |
 
643
qconvex FV n | qhalf G &gt;eg.33b.cone.dual</a></h3>
 
644
 
 
645
<h3><a href="#half">�</a><a name="33c">rbox 10 r s Z1 G0.3 |
 
646
qconvex FV n | qhalf Fp | qconvex G &gt;eg.33c.cone.halfspace</a></h3>
 
647
 
 
648
<p>These examples illustrate halfspace intersection. The first
 
649
picture is the convex hull of two 20-gons plus an apex. The
 
650
second picture is the dual of the first. Try loading <a
 
651
href="http://www.geom.umn.edu/graphics/pix/Special_Topics/Computational_Geometry/half.html">both</a>
 
652
at once. Each vertex of the second picture corresponds to a facet
 
653
or halfspace of the first. The vertices with four edges
 
654
correspond to a facet with four neighbors. Similarly the facets
 
655
correspond to vertices. A facet's normal coefficients divided by
 
656
its negative offset is the vertice's coordinates. The coordinates
 
657
are the intersection of the original halfspaces. </p>
 
658
 
 
659
<p>The third picture shows how Qhull can go back and forth
 
660
between equivalent representations. It starts with a cone,
 
661
generates the halfspaces that define each facet of the cone, and
 
662
then intersects these halfspaces. Except for roundoff error, the
 
663
third picture is a duplicate of the first. </p>
 
664
<!-- Navigation links -->
 
665
<hr>
 
666
 
 
667
<p><b>Up:</b> <a href="http://www.geom.umn.edu/software/qhull">Home
 
668
page for Qhull</a> <br>
 
669
<b>Up:</b> <a href="index.htm#TOC">Qhull manual: Table of Contents</a><br>
 
670
<b>To:</b> <a href="qh-quick.htm#programs">Programs</a>
 
671
&#149; <a href="qh-quick.htm#options">Options</a> 
 
672
&#149; <a href="qh-opto.htm#output">Output</a> 
 
673
&#149; <a href="qh-optf.htm#format">Formats</a> 
 
674
&#149; <a href="qh-optg.htm#geomview">Geomview</a> 
 
675
&#149; <a href="qh-optp.htm#print">Print</a>
 
676
&#149; <a href="qh-optq.htm#qhull">Qhull</a> 
 
677
&#149; <a href="qh-optc.htm#prec">Precision</a> 
 
678
&#149; <a href="qh-optt.htm#trace">Trace</a><br>
 
679
<b>To: </b><a href="#TOC">Qhull examples: Table of Contents</a> (please wait
 
680
while loading)<br>
 
681
<!-- GC common information -->
 
682
<hr>
 
683
 
 
684
<p><a href="http://www.geom.umn.edu/"><img src="qh--geom.gif"
 
685
align="middle" width="40" height="40"></a><i>The Geometry Center
 
686
Home Page </i></p>
 
687
 
 
688
<p>Comments to: <a href=mailto:qhull@geom.umn.edu>qhull@geom.umn.edu</a>
 
689
</a><br>
 
690
Created: Sept. 25, 1995 --- <!-- hhmts start --> Last modified: see top <!-- hhmts end --> </p>
 
691
</body>
 
692
</html>