← Back to branch summary

~diresu/blender/blender-command-port

« back to all changes in this revision

Viewing changes to extern/qhull/html/qdelau_f.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/qdelau_f.htm
 
1
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
 
2
<html>
 
3
 
 
4
<head>
 
5
<title>qdelaunay Qu -- furthest-site Delaunay triangulation</title>
 
6
</head>
 
7
 
 
8
<body>
 
9
<!-- Navigation links -->
 
10
<a name="TOP"><b>Up</b></a><b>:</b> 
 
11
<a href="http://www.geom.umn.edu/software/qhull">Home 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="#synopsis">sy</a>nopsis 
 
23
&#149; <a href="#input">in</a>put &#149; <a href="#outputs">ou</a>tputs 
 
24
&#149; <a href="#controls">co</a>ntrols &#149; <a href="#graphics">gr</a>aphics 
 
25
&#149; <a href="#notes">no</a>tes &#149; <a href="#conventions">co</a>nventions 
 
26
&#149; <a href="#options">op</a>tions
 
27
 
 
28
<hr>
 
29
<!-- Main text of document -->
 
30
<h1><a
 
31
href="http://www.geom.umn.edu/graphics/pix/Special_Topics/Computational_Geometry/delaunay.html"><img
 
32
src="qh--dt.gif" alt="[delaunay]" align="middle" width="100"
 
33
height="100"></a>qdelaunay Qu -- furthest-site Delaunay triangulation</h1>
 
34
 
 
35
<p>The furthest-site Delaunay triangulation corresponds to the upper facets of the <a href="qdelaun.htm">Delaunay construction</a>.
 
36
Its vertices are the
 
37
extreme points of the input sites.
 
38
It is the dual of the <a
 
39
href="qvoron_f.htm">furthest-site Voronoi diagram</a>.
 
40
 
 
41
<blockquote>
 
42
<dl>
 
43
    <dt><b>Example:</b> rbox 10 D2 | qdelaunay <a
 
44
        href="qh-optq.htm#Qu">Qu</a> <a
 
45
        href="qh-optq.htm#Qt">Qt</a> <a href="qh-opto.htm#s">s</a>
 
46
        <a href="qh-opto.htm#i">i</a> <a href="qh-optt.htm#TO">TO
 
47
        result</a></dt>
 
48
    <dd>Compute the 2-d, furthest-site Delaunay triangulation of 10 random
 
49
        points. Triangulate the output.
 
50
        Write a summary to the console and the regions to
 
51
        'result'.</dd>
 
52
    <dt>&nbsp;</dt>
 
53
    <dt><b>Example:</b> rbox 10 D2 | qdelaunay <a
 
54
        href="qh-optq.htm#Qu">Qu</a> <a
 
55
        href="qh-optq.htm#QJn">QJ</a> <a href="qh-opto.htm#s">s</a>
 
56
        <a href="qh-opto.htm#i">i</a> <a href="qh-optt.htm#TO">TO
 
57
        result</a></dt>
 
58
    <dd>Compute the 2-d, furthest-site Delaunay triangulation of 10 random
 
59
        points. Joggle the input to guarantee triangular output.
 
60
        Write a summary to the console and the regions to
 
61
        'result'.</dd>
 
62
    <dt>&nbsp;</dt>
 
63
    <dt><b>Example:</b> rbox r y c G1 D2 | qdelaunay <a
 
64
        href="qh-optq.htm#Qu">Qu</a> <a href="qh-opto.htm#s">s</a>
 
65
        <a href="qh-optf.htm#Fv">Fv</a> <a href="qh-optt.htm#TO">TO
 
66
        result</a></dt>
 
67
    <dd>Compute the 2-d, furthest-site Delaunay triangulation of a triangle inside
 
68
                a square.
 
69
        Write a summary to the console and unoriented regions to 'result'.
 
70
        Merge regions for cocircular input sites (e.g., the square).
 
71
                The square is the only furthest-site
 
72
        Delaunay region.</dd>
 
73
</dl>
 
74
</blockquote>
 
75
 
 
76
<p>As with the Delaunay triangulation, Qhull computes the
 
77
furthest-site Delaunay triangulation by lifting the input sites to a
 
78
paraboloid. The lower facets correspond to the Delaunay
 
79
triangulation while the upper facets correspond to the
 
80
furthest-site triangulation. Neither triangulation includes
 
81
&quot;vertical&quot; facets (i.e., facets whose last hyperplane
 
82
coefficient is nearly zero). Vertical facets correspond to input
 
83
sites that are coplanar to the convex hull of the input. An
 
84
example is points on the boundary of a lattice.</p>
 
85
 
 
86
<p>If you use '<a href="qh-optq.htm#Qt">Qt</a>' (triangulated output) or 
 
87
'<a href="qh-optq.htm#QJn">QJ</a>' (joggled input), all furthest-site 
 
88
Delaunay regions 
 
89
will be simplicial (e.g., triangles in 2-d).  If you do not use
 
90
'QJ', <tt>qdelaunay Qu</tt> merges the furthest-site Delaunay regions 
 
91
for cocircular or cospherical input sites.  This is more accurate
 
92
than joggled input.  See <a
 
93
href="qh-impre.htm#joggle">Joggled input or merged facets</a>. </p>
 
94
 
 
95
<p>The output for 3-d, furthest-site Delaunay triangulations may be confusing if the 
 
96
input contains cospherical data. See the FAQ item
 
97
<a href=qh-faq.htm#extra>Why
 
98
are there extra points in a 4-d or higher convex hull?</a>
 
99
Avoid these problems with triangulated output ('<a href="qh-optq.htm#Qt">Qt</a>') or
 
100
joggled input ('<a href="qh-optq.htm#QJn">QJ</a>').
 
101
</p>
 
102
 
 
103
<p>The 'qdelaunay' program is equivalent to 
 
104
'<a href=qhull.htm#outputs>qhull d</a> <a href=qh-optq.htm#Qbb>Qbb</a>' in 2-d to 3-d, and
 
105
'<a href=qhull.htm#outputs>qhull d</a> <a href=qh-optq.htm#Qbb>Qbb</a> <a href=qh-optq.htm#Qx>Qx</a>' 
 
106
in 4-d and higher.  It disables the following Qhull
 
107
<a href=qh-quick.htm#options>options</a>: <i>d n v H U Qb QB Qc Qf Qg Qi
 
108
Qm Qr QR Qv Qx TR E V FC Fi Fo Fp FV Q0,etc</i>.
 
109
 
 
110
 
 
111
<p><b>Copyright &copy; 1995-2002 The Geometry Center, Minneapolis MN</b></p>
 
112
 
 
113
<hr>
 
114
 
 
115
<h3><a href="#TOP">�</a><a name="synopsis">furthest-site qdelaunay synopsis</a></h3>
 
116
<blockquote>
 
117
 
 
118
See <a href="qdelaun.htm#synopsis">qdelaunay synopsis</a>.  The same
 
119
program is used for both constructions.  Use option '<a href="qh-optq.htm#Qu">Qu</a>'
 
120
for furthest-site Delaunay triangulations.
 
121
 
 
122
</blockquote>
 
123
<h3><a href="#TOP">�</a><a name="input">furthest-site qdelaunay
 
124
input</a></h3>
 
125
 
 
126
<blockquote>
 
127
<p>The input data on <tt>stdin</tt> consists of:</p>
 
128
<ul>
 
129
    <li>dimension 
 
130
    <li>number of points</li>
 
131
    <li>point coordinates</li>
 
132
</ul>
 
133
 
 
134
<p>Use I/O redirection (e.g., qdelaunay Qu &lt; data.txt), a pipe (e.g., rbox 10 | qdelaunay Qu),
 
135
or the '<a href=qh-optt.htm#TI>TI</a>' option (e.g., qdelaunay Qu TI data.txt).  
 
136
 
 
137
<p>For example, this is a square containing four random points.  
 
138
Its furthest-site Delaunay 
 
139
triangulation contains one square.
 
140
<p>
 
141
<blockquote>
 
142
<tt>rbox c 4 D2 &gt; data</tt> 
 
143
<blockquote><pre>
 
144
2 RBOX c 4 D2
 
145
8
 
146
-0.4999921736307369 -0.3684622117955817
 
147
0.2556053225468894 -0.0413498678629751
 
148
0.0327672376602583 -0.2810408135699488
 
149
-0.452955383763607 0.17886471718444
 
150
  -0.5   -0.5
 
151
  -0.5    0.5
 
152
   0.5   -0.5
 
153
   0.5    0.5
 
154
</pre></blockquote>
 
155
 
 
156
<p><tt>qdelaunay Qu i &lt; data</tt>
 
157
<blockquote><pre>
 
158
 
 
159
Furthest-site Delaunay triangulation by the convex hull of 8 points in 3-d:
 
160
 
 
161
  Number of input sites: 8
 
162
  Number of Delaunay regions: 1
 
163
  Number of non-simplicial Delaunay regions: 1
 
164
 
 
165
Statistics for: RBOX c 4 D2 | QDELAUNAY s Qu i
 
166
 
 
167
  Number of points processed: 8
 
168
  Number of hyperplanes created: 20
 
169
  Number of facets in hull: 11
 
170
  Number of distance tests for qhull: 34
 
171
  Number of merged facets: 1
 
172
  Number of distance tests for merging: 107
 
173
  CPU seconds to compute hull (after input): 0.02
 
174
 
 
175
1
 
176
7 6 4 5
 
177
</pre></blockquote>
 
178
</blockquote>
 
179
 
 
180
</blockquote>
 
181
<h3><a href="#TOP">�</a><a name="outputs">furthest-site qdelaunay
 
182
outputs</a></h3>
 
183
<blockquote>
 
184
 
 
185
<p>These options control the output of furthest-site Delaunay triangulations:</p>
 
186
<blockquote>
 
187
 
 
188
<dl compact>
 
189
    <dd><b>furthest-site Delaunay regions</b></dd>
 
190
    <dt><a href="qh-opto.htm#i">i</a></dt>
 
191
    <dd>list input sites for each furthest-site Delaunay region. The first line is the number of regions.  The
 
192
        remaining lines list the input sites for each region.  The regions are
 
193
                oriented.  In 3-d and
 
194
        higher, report cospherical sites by adding extra points.  For the points-in-square example,
 
195
        the square is the only furthest-site Delaunay region.</dd>
 
196
    <dt><a href="qh-optf.htm#Fv">Fv</a></dt>
 
197
    <dd>list input sites for each furthest-site Delaunay region.  The first line is the number of regions.  
 
198
        Each remaining line starts with the number of input sites.  The regions
 
199
        are unoriented.  For the points-in-square example,
 
200
        the square is the only furthest-site Delaunay region.</dd>
 
201
    <dt><a href="qh-optf.htm#Ft">Ft</a></dt>
 
202
    <dd>print a triangulation of the furthest-site Delaunay regions in OFF format.  The first line
 
203
        is the dimension.  The second line is the number of input sites and added points, 
 
204
        followed by the number of simplices and the number of ridges.
 
205
    The input coordinates are next, followed by the centrum coordinates.  There is
 
206
        one centrum for each non-simplicial furthest-site Delaunay region.  Each remaining line starts
 
207
        with dimension+1.  The 
 
208
        simplices are oriented.
 
209
        For the points-in-square example, the square has a centrum at the
 
210
        origin.  It splits the square into four triangular regions.</dd>
 
211
    <dt><a href="qh-optf.htm#Fn">Fn</a></dt>
 
212
    <dd>list neighboring regions for each furthest-site Delaunay region.  The first line is the
 
213
        number of regions.  Each remaining line starts with the number of 
 
214
        neighboring regions.  Negative indices (e.g., <em>-1</em>) indicate regions
 
215
        outside of the furthest-site Delaunay triangulation.
 
216
        For the points-in-square example, the four neighboring regions 
 
217
        are outside of the triangulation.  They belong to the regular
 
218
        Delaunay triangulation.</dd>
 
219
    <dt><a href="qh-optf.htm#FN">FN</a></dt>
 
220
    <dd>list the furthest-site Delaunay regions for each input site.  The first line is the
 
221
        total number of input sites.  Each remaining line starts with the number of 
 
222
        furthest-site Delaunay regions.  Negative indices (e.g., <em>-1</em>) indicate regions
 
223
        outside of the furthest-site Delaunay triangulation.
 
224
        For the points-in-square example, the four random points belong to no region
 
225
        while the square's vertices belong to region <em>0</em> and three
 
226
        regions outside of the furthest-site Delaunay triangulation.</dd>
 
227
    <dt><a href="qh-optf.htm#Fa">Fa</a></dt>
 
228
    <dd>print area for each furthest-site Delaunay region. The first line is the number of regions.
 
229
        The areas follow, one line per region.  For the points-in-square example, the
 
230
        square has unit area. </dd>
 
231
 
 
232
    <dt>&nbsp;</dt>
 
233
    <dt>&nbsp;</dt>
 
234
    <dd><b>Input sites</b></dd>
 
235
    <dt><a href="qh-optf.htm#Fx">Fx</a></dt>
 
236
    <dd>list extreme points of the input sites.  These points are vertices of the furthest-point
 
237
        Delaunay triangulation.  They are on the
 
238
        boundary of the convex hull.   The first line is the number of
 
239
        extreme points.  Each point is listed, one per line.  The points-in-square example
 
240
        has four extreme points.</dd>
 
241
    <dt>&nbsp;</dt>
 
242
    <dt>&nbsp;</dt>
 
243
    <dd><b>General</b></dd>
 
244
    <dt><a href="qh-optf.htm#FA">FA</a></dt>
 
245
    <dd>compute total area for '<a href="qh-opto.htm#s">s</a>'
 
246
        and '<a href="qh-optf.htm#FS">FS</a>'.  This is the
 
247
                same as the area of the convex hull.</dd>
 
248
    <dt><a href="qh-opto.htm#o">o</a></dt>
 
249
    <dd>print upper facets of the corresponding convex hull (a
 
250
        paraboloid)</dd>
 
251
    <dt><a href="qh-opto.htm#m">m</a></dt>
 
252
    <dd>Mathematica output for the upper facets of the paraboloid (2-d triangulations).</dd>
 
253
    <dt><a href="qh-optg.htm#G">G</a></dt>
 
254
    <dd>Geomview output for the paraboloid (2-d or 3-d triangulations).</dd>
 
255
    <dt><a href="qh-opto.htm#s">s</a></dt>
 
256
    <dd>print summary for the furthest-site Delaunay triangulation. Use '<a
 
257
        href="qh-optf.htm#Fs">Fs</a>' and '<a
 
258
        href="qh-optf.htm#FS">FS</a>' for numeric data.</dd>
 
259
</dl>
 
260
</blockquote>
 
261
 
 
262
</blockquote>
 
263
<h3><a href="#TOP">�</a><a name="controls">furthest-site qdelaunay
 
264
controls</a></h3>
 
265
<blockquote>
 
266
 
 
267
<p>These options provide additional control:</p>
 
268
<blockquote>
 
269
 
 
270
<dl compact>
 
271
   <dt><a href="qh-optq.htm#Qu">Qu</a></dt>
 
272
    <dd>must be used for furthest-site Delaunay triangulation.</dd>
 
273
    <dt><a href="qh-optq.htm#Qt">Qt</a></dt>
 
274
    <dd>triangulated output.  Qhull triangulates non-simplicial facets.  It may produce
 
275
     degenerate facets of zero area.</dd>
 
276
   <dt><a href="qh-optq.htm#QJn">QJ</a></dt>
 
277
    <dd>joggle the input to avoid cospherical and coincident
 
278
        sites.</dd>
 
279
    <dt><a href="qh-optq.htm#QVn">QVn</a></dt>
 
280
    <dd>select facets adjacent to input site <em>n</em> (marked
 
281
        'good').</dd>
 
282
    <dt><a href="qh-optt.htm#Tv">Tv</a></dt>
 
283
    <dd>verify result.</dd>
 
284
    <dt><a href="qh-optt.htm#TO">TI file</a></dt>
 
285
    <dd>input data from file.  The filename may not use spaces or quotes.</dd>
 
286
    <dt><a href="qh-optt.htm#TO">TO file</a></dt>
 
287
    <dd>output results to file.  Use single quotes if the filename
 
288
        contains spaces (e.g., <tt>TO 'file with spaces.txt'</tt></dd>
 
289
    <dt><a href="qh-optt.htm#TFn">TFn</a></dt>
 
290
    <dd>report progress after constructing <em>n</em> facets</dd>
 
291
    <dt><a href="qh-optp.htm#PDk">PDk:1</a></dt>
 
292
    <dd>include upper and lower facets in the output.  Set <em>k</em>
 
293
        to the last dimension (e.g., 'PD2:1' for 2-d inputs). </dd>
 
294
    <dt><a href="qh-opto.htm#f">f</a></dt>
 
295
    <dd>facet dump.  Print the data structure for each facet (i.e., furthest-site Delaunay region).</dd>
 
296
</dl>
 
297
</blockquote>
 
298
 
 
299
</blockquote>
 
300
<h3><a href="#TOP">�</a><a name="graphics">furthest-site qdelaunay
 
301
graphics</a></h3>
 
302
<blockquote>
 
303
 
 
304
See <a href="qdelaun.htm#graphics">Delaunay graphics</a>.  
 
305
They are the same except
 
306
for Mathematica output.
 
307
 
 
308
</blockquote>
 
309
<h3><a href="#TOP">�</a><a name="notes">furthest-site
 
310
qdelaunay notes</a></h3>
 
311
<blockquote>
 
312
 
 
313
<p>The furthest-site Delaunay triangulation does not
 
314
record coincident input sites.  Use <tt>qdelaunay</tt> instead.
 
315
 
 
316
<p><tt>qdelaunay Qu</tt> does not work for purely cocircular
 
317
or cospherical points (e.g., rbox c | qdelaunay Qu).  Instead,
 
318
use <tt>qdelaunay Qz</tt>.  In this case, it is the same as 
 
319
the furthest-site Delaunay triangulation.
 
320
 
 
321
<p>A non-simplicial, furthest-site Delaunay region indicates nearly cocircular or
 
322
cospherical input sites. To avoid non-simplicial regions triangulate
 
323
the output ('<a href="qh-optq.htm#Qt">Qt</a>') or joggle
 
324
the input ('<a href="qh-optq.htm#QJn">QJ</a>').  You may also triangulate
 
325
non-simplicial regions with option '<a
 
326
href="qh-optf.htm#Ft">Ft</a>'. It adds
 
327
the centrum to non-simplicial regions. Alternatively, use an <a
 
328
href="qh-impre.htm#exact">exact arithmetic code</a>.</p>
 
329
 
 
330
<p>Furthest-site Delaunay triangulations do not include facets that are
 
331
coplanar with the convex hull of the input sites.  A facet is
 
332
coplanar if the last coefficient of its normal is
 
333
nearly zero (see <a href="../src/user.h#ZEROdelaunay">qh_ZEROdelaunay</a>).
 
334
 
 
335
</blockquote>
 
336
<h3><a href="#TOP">�</a><a name="conventions">furthest-site qdelaunay conventions</a></h3>
 
337
<blockquote>
 
338
 
 
339
<p>The following terminology is used for furthest-site Delaunay
 
340
triangulations in Qhull. The underlying structure is the upper
 
341
facets of a convex hull in one higher dimension. See <a
 
342
href="qconvex.htm#conventions">convex hull conventions</a>, <a
 
343
href="qdelaun.htm#conventions">Delaunay conventions</a>,
 
344
and <a href="index.htm#structure">Qhull's data structures</a></p>
 
345
<blockquote>
 
346
<ul>
 
347
    <li><em>input site</em> - a point in the input (one dimension
 
348
        lower than a point on the convex hull)</li>
 
349
    <li><em>point</em> - <i>d+1</i> coordinates. The last
 
350
        coordinate is the sum of the squares of the input site's
 
351
        coordinates</li>
 
352
    <li><em>vertex</em> - a point on the paraboloid. It
 
353
        corresponds to a unique input site. </li>
 
354
    <li><em>furthest-site Delaunay facet</em> - an upper facet of the
 
355
        paraboloid. The last coefficient of its normal is
 
356
                clearly positive.</li>
 
357
    <li><em>furthest-site Delaunay region</em> - a furthest-site Delaunay 
 
358
            facet projected to the input sites</li>
 
359
    <li><em>non-simplicial facet</em> - more than <em>d</em>
 
360
        points are cocircular or cospherical</li>
 
361
    <li><em>good facet</em> - a furthest-site Delaunay facet with optional
 
362
        restrictions by '<a href="qh-optq.htm#QVn">QVn</a>', etc.</li>
 
363
</ul>
 
364
</blockquote>
 
365
</blockquote>
 
366
<h3><a href="#TOP">�</a><a name="options">furthest-site qdelaunay options</a></h3>
 
367
<blockquote>
 
368
 
 
369
See <a href="qdelaun.htm#options">qdelaunay options</a>.    The same
 
370
program is used for both constructions.  Use option '<a href="qh-optq.htm#Qu">Qu</a>'
 
371
for furthest-site Delaunay triangulations.
 
372
 
 
373
</blockquote>
 
374
<!-- Navigation links -->
 
375
<hr>
 
376
 
 
377
<p><b>Up:</b> <a href="http://www.geom.umn.edu/software/qhull">Home page</a> for Qhull<br>
 
378
<b>Up:</b> <a href="index.htm#TOC">Qhull manual</a>: Table of Contents<br>
 
379
<b>To:</b> <a href="qh-quick.htm#programs">Programs</a>
 
380
&#149; <a href="qh-quick.htm#options">Options</a> 
 
381
&#149; <a href="qh-opto.htm#output">Output</a> 
 
382
&#149; <a href="qh-optf.htm#format">Formats</a> 
 
383
&#149; <a href="qh-optg.htm#geomview">Geomview</a> 
 
384
&#149; <a href="qh-optp.htm#print">Print</a>
 
385
&#149; <a href="qh-optq.htm#qhull">Qhull</a> 
 
386
&#149; <a href="qh-optc.htm#prec">Precision</a> 
 
387
&#149; <a href="qh-optt.htm#trace">Trace</a><br>
 
388
<b>To:</b> <a href="#synopsis">sy</a>nopsis 
 
389
&#149; <a href="#input">in</a>put &#149; <a href="#outputs">ou</a>tputs 
 
390
&#149; <a href="#controls">co</a>ntrols &#149; <a href="#graphics">gr</a>aphics 
 
391
&#149; <a href="#notes">no</a>tes &#149; <a href="#conventions">co</a>nventions 
 
392
&#149; <a href="#options">op</a>tions
 
393
<!-- GC common information -->
 
394
<hr>
 
395
 
 
396
<p><a href="http://www.geom.umn.edu/"><img src="qh--geom.gif"
 
397
align="middle" width="40" height="40"></a><i>The Geometry Center
 
398
Home Page </i></p>
 
399
 
 
400
<p>Comments to: <a href=mailto:qhull@geom.umn.edu>qhull@geom.umn.edu</a>
 
401
</a><br>
 
402
Created: Sept. 25, 1995 --- <!-- hhmts start --> Last modified: see top <!-- hhmts end --> </p>
 
403
</body>
 
404
</html>