668 lines
27 KiB
HTML
668 lines
27 KiB
HTML
|
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
|
||
|
|
<html>
|
||
|
|
|
||
|
|
<head>
|
||
|
|
<title>qvoronoi -- Voronoi diagram</title>
|
||
|
|
</head>
|
||
|
|
|
||
|
|
<body>
|
||
|
|
<!-- Navigation links -->
|
||
|
|
<a name="TOP"><b>Up</b></a><b>:</b>
|
||
|
|
<a href="http://www.qhull.org">Home page</a> for Qhull<br>
|
||
|
|
<b>Up:</b> <a href="index.htm#TOC">Qhull manual</a>: Table of Contents<br>
|
||
|
|
<b>To:</b> <a href="qh-quick.htm#programs">Programs</a>
|
||
|
|
• <a href="qh-quick.htm#options">Options</a>
|
||
|
|
• <a href="qh-opto.htm#output">Output</a>
|
||
|
|
• <a href="qh-optf.htm#format">Formats</a>
|
||
|
|
• <a href="qh-optg.htm#geomview">Geomview</a>
|
||
|
|
• <a href="qh-optp.htm#print">Print</a>
|
||
|
|
• <a href="qh-optq.htm#qhull">Qhull</a>
|
||
|
|
• <a href="qh-optc.htm#prec">Precision</a>
|
||
|
|
• <a href="qh-optt.htm#trace">Trace</a>
|
||
|
|
• <a href="../src/libqhull_r/index.htm">Functions</a><br>
|
||
|
|
<b>To:</b> <a href="#synopsis">sy</a>nopsis
|
||
|
|
• <a href="#input">in</a>put • <a href="#outputs">ou</a>tputs
|
||
|
|
• <a href="#controls">co</a>ntrols • <a href="#graphics">gr</a>aphics
|
||
|
|
• <a href="#notes">no</a>tes • <a href="#conventions">co</a>nventions
|
||
|
|
• <a href="#options">op</a>tions
|
||
|
|
|
||
|
|
<hr>
|
||
|
|
<!-- Main text of document -->
|
||
|
|
<h1><a
|
||
|
|
href="http://www.archinect.com/gallery/displayimage.php?pos=-4658"><img
|
||
|
|
src="normal_voronoi_knauss_oesterle.jpg" alt="[voronoi]" align="middle"
|
||
|
|
height="100"></a>qvoronoi -- Voronoi diagram</h1>
|
||
|
|
|
||
|
|
<p>The Voronoi diagram is the nearest-neighbor map for a set of
|
||
|
|
points. Each region contains those points that are nearer
|
||
|
|
one input site than any other input site. It has many useful properties and applications. See the
|
||
|
|
survey article by Aurenhammer [<a href="index.htm#aure91">'91</a>]
|
||
|
|
and the detailed introduction by O'Rourke [<a
|
||
|
|
href="index.htm#orou94">'94</a>]. The Voronoi diagram is the
|
||
|
|
dual of the <a href=qdelaun.htm>Delaunay triangulation</a>. </p>
|
||
|
|
|
||
|
|
<blockquote>
|
||
|
|
<dl>
|
||
|
|
<dt><b>Example:</b> rbox 10 D3 | qvoronoi <a href="qh-opto.htm#s">s</a>
|
||
|
|
<a href="qh-opto.htm#o">o</a> <a href="qh-optt.htm#TO">TO
|
||
|
|
result</a></dt>
|
||
|
|
<dd>Compute the 3-d Voronoi diagram of 10 random points. Write a
|
||
|
|
summary to the console and the Voronoi vertices and
|
||
|
|
regions to 'result'. The first vertex of the result
|
||
|
|
indicates unbounded regions.</dd>
|
||
|
|
|
||
|
|
<dt> </dt>
|
||
|
|
<dt><b>Example:</b> rbox r y c G0.1 D2 | qvoronoi
|
||
|
|
<a href="qh-opto.htm#s">s</a>
|
||
|
|
<a href="qh-opto.htm#o">o</a> <a href="qh-optt.htm#TO">TO
|
||
|
|
result</a></dt>
|
||
|
|
<dd>Compute the 2-d Voronoi diagram of a triangle and a small
|
||
|
|
square. Write a
|
||
|
|
summary to the console and Voronoi vertices and regions
|
||
|
|
to 'result'. Report a single Voronoi vertex for
|
||
|
|
cocircular input sites. The first vertex of the result
|
||
|
|
indicates unbounded regions. The origin is the Voronoi
|
||
|
|
vertex for the square.</dd>
|
||
|
|
|
||
|
|
<dt> </dt>
|
||
|
|
<dt><b>Example:</b> rbox r y c G0.1 D2 | qvoronoi <a href="qh-optf.htm#Fv2">Fv</a>
|
||
|
|
<a href="qh-optt.htm#TO">TO result</a></dt>
|
||
|
|
<dd>Compute the 2-d Voronoi diagram of a triangle and a small
|
||
|
|
square. Write a
|
||
|
|
summary to the console and the Voronoi ridges to
|
||
|
|
'result'. Each ridge is the perpendicular bisector of a
|
||
|
|
pair of input sites. Vertex "0" indicates
|
||
|
|
unbounded ridges. Vertex "8" is the Voronoi
|
||
|
|
vertex for the square.</dd>
|
||
|
|
|
||
|
|
<dt> </dt>
|
||
|
|
<dt><b>Example:</b> rbox r y c G0.1 D2 | qvoronoi <a href="qh-optf.htm#Fi2">Fi</a></dt>
|
||
|
|
<dd>Print the bounded, separating hyperplanes for the 2-d Voronoi diagram of a
|
||
|
|
triangle and a small
|
||
|
|
square. Note the four hyperplanes (i.e., lines) for Voronoi vertex
|
||
|
|
"8". It is at the origin.
|
||
|
|
</dd>
|
||
|
|
</dl>
|
||
|
|
</blockquote>
|
||
|
|
|
||
|
|
<p>Qhull computes the Voronoi diagram via the <a href="qdelaun.htm">Delaunay
|
||
|
|
triangulation</a>. Each Voronoi
|
||
|
|
vertex is the circumcenter of a facet of the Delaunay
|
||
|
|
triangulation. Each Voronoi region corresponds to a vertex (i.e., input site) of the
|
||
|
|
Delaunay triangulation. </p>
|
||
|
|
|
||
|
|
<p>Qhull outputs the Voronoi vertices for each Voronoi region. With
|
||
|
|
option '<a href="qh-optf.htm#Fv2">Fv</a>',
|
||
|
|
it lists all ridges of the Voronoi diagram with the corresponding
|
||
|
|
pairs of input sites. With
|
||
|
|
options '<a href="qh-optf.htm#Fi2">Fi</a>' and '<a href="qh-optf.htm#Fo2">Fo</a>',
|
||
|
|
it lists the bounded and unbounded separating hyperplanes.
|
||
|
|
You can also output a single Voronoi region
|
||
|
|
for further processing [see <a href="#graphics">graphics</a>].</p>
|
||
|
|
|
||
|
|
<p>Use option '<a href="qh-optq.htm#Qz">Qz</a>' if the input is circular, cospherical, or
|
||
|
|
nearly so. It improves precision by adding a point "at infinity," above the corresponding paraboloid.
|
||
|
|
|
||
|
|
<p>See <a href="http://www.qhull.org/html/qh-faq.htm#TOC">Qhull FAQ</a> - Delaunay and
|
||
|
|
Voronoi diagram questions.</p>
|
||
|
|
|
||
|
|
<p>The 'qvonoroi' program is equivalent to
|
||
|
|
'<a href=qhull.htm#outputs>qhull v</a> <a href=qh-optq.htm#Qbb>Qbb</a>' in 2-d to 3-d, and
|
||
|
|
'<a href=qhull.htm#outputs>qhull v</a> <a href=qh-optq.htm#Qbb>Qbb</a> <a href=qh-optq.htm#Qx>Qx</a>'
|
||
|
|
in 4-d and higher. It disables the following Qhull
|
||
|
|
<a href=qh-quick.htm#options>options</a>: <i>d n v Qbb QbB Qf Qg Qm
|
||
|
|
Qr QR Qv Qx Qz TR E V Fa FA FC FD FS Ft FV Gt Q0,etc</i>.
|
||
|
|
|
||
|
|
<p><b>Copyright © 1995-2015 C.B. Barber</b></p>
|
||
|
|
|
||
|
|
<p>Voronoi image by KOOK Architecture, Silvan Oesterle and Michael Knauss.
|
||
|
|
|
||
|
|
<hr>
|
||
|
|
<h3><a href="#TOP">»</a><a name="synopsis">qvoronoi synopsis</a></h3>
|
||
|
|
|
||
|
|
<pre>
|
||
|
|
qvoronoi- compute the Voronoi diagram.
|
||
|
|
input (stdin): dimension, number of points, point coordinates
|
||
|
|
comments start with a non-numeric character
|
||
|
|
|
||
|
|
options (qh-voron.htm):
|
||
|
|
Qu - compute furthest-site Voronoi diagram
|
||
|
|
Tv - verify result: structure, convexity, and in-circle test
|
||
|
|
. - concise list of all options
|
||
|
|
- - one-line description of all options
|
||
|
|
|
||
|
|
output options (subset):
|
||
|
|
s - summary of results (default)
|
||
|
|
p - Voronoi vertices
|
||
|
|
o - OFF file format (dim, Voronoi vertices, and Voronoi regions)
|
||
|
|
FN - count and Voronoi vertices for each Voronoi region
|
||
|
|
Fv - Voronoi diagram as Voronoi vertices between adjacent input sites
|
||
|
|
Fi - separating hyperplanes for bounded regions, 'Fo' for unbounded
|
||
|
|
G - Geomview output (2-d only)
|
||
|
|
QVn - Voronoi vertices for input point n, -n if not
|
||
|
|
TO file- output results to file, may be enclosed in single quotes
|
||
|
|
|
||
|
|
examples:
|
||
|
|
rbox c P0 D2 | qvoronoi s o rbox c P0 D2 | qvoronoi Fi
|
||
|
|
rbox c P0 D2 | qvoronoi Fo rbox c P0 D2 | qvoronoi Fv
|
||
|
|
rbox c P0 D2 | qvoronoi s Qu Fv rbox c P0 D2 | qvoronoi Qu Fo
|
||
|
|
rbox c G1 d D2 | qvoronoi s p rbox c P0 D2 | qvoronoi s Fv QV0
|
||
|
|
</pre>
|
||
|
|
|
||
|
|
<h3><a href="#TOP">»</a><a name="input">qvoronoi input</a></h3>
|
||
|
|
<blockquote>
|
||
|
|
The input data on <tt>stdin</tt> consists of:
|
||
|
|
<ul>
|
||
|
|
<li>dimension
|
||
|
|
<li>number of points</li>
|
||
|
|
<li>point coordinates</li>
|
||
|
|
</ul>
|
||
|
|
|
||
|
|
<p>Use I/O redirection (e.g., qvoronoi < data.txt), a pipe (e.g., rbox 10 | qvoronoi),
|
||
|
|
or the '<a href=qh-optt.htm#TI>TI</a>' option (e.g., qvoronoi TI data.txt).
|
||
|
|
|
||
|
|
<p>For example, this is four cocircular points inside a square. Their Voronoi
|
||
|
|
diagram has nine vertices and eight regions. Notice the Voronoi vertex
|
||
|
|
at the origin, and the Voronoi vertices (on each axis) for the four
|
||
|
|
sides of the square.
|
||
|
|
<p>
|
||
|
|
<blockquote>
|
||
|
|
<tt>rbox s 4 W0 c G1 D2 > data</tt>
|
||
|
|
<blockquote><pre>
|
||
|
|
2 RBOX s 4 W0 c D2
|
||
|
|
8
|
||
|
|
-0.4941988586954018 -0.07594397977563715
|
||
|
|
-0.06448037284989526 0.4958248496365813
|
||
|
|
0.4911154367094632 0.09383830681375946
|
||
|
|
-0.348353580869097 -0.3586778257652367
|
||
|
|
-1 -1
|
||
|
|
-1 1
|
||
|
|
1 -1
|
||
|
|
1 1
|
||
|
|
</pre></blockquote>
|
||
|
|
|
||
|
|
<p><tt>qvoronoi s p < data</tt>
|
||
|
|
<blockquote><pre>
|
||
|
|
|
||
|
|
Voronoi diagram by the convex hull of 8 points in 3-d:
|
||
|
|
|
||
|
|
Number of Voronoi regions: 8
|
||
|
|
Number of Voronoi vertices: 9
|
||
|
|
Number of non-simplicial Voronoi vertices: 1
|
||
|
|
|
||
|
|
Statistics for: RBOX s 4 W0 c D2 | QVORONOI s p
|
||
|
|
|
||
|
|
Number of points processed: 8
|
||
|
|
Number of hyperplanes created: 18
|
||
|
|
Number of facets in hull: 10
|
||
|
|
Number of distance tests for qhull: 33
|
||
|
|
Number of merged facets: 2
|
||
|
|
Number of distance tests for merging: 102
|
||
|
|
CPU seconds to compute hull (after input): 0.094
|
||
|
|
|
||
|
|
2
|
||
|
|
9
|
||
|
|
4.217546450968612e-17 1.735507986399734
|
||
|
|
-8.402566836762659e-17 -1.364368854147395
|
||
|
|
0.3447488772716865 -0.6395484723719818
|
||
|
|
1.719446929853986 2.136555906154247e-17
|
||
|
|
0.4967882915039657 0.68662371396699
|
||
|
|
-1.729928876283549 1.343733067524222e-17
|
||
|
|
-0.8906163241424728 -0.4594150543829102
|
||
|
|
-0.6656840313875723 0.5003013793414868
|
||
|
|
-7.318364664277155e-19 -1.188217818408333e-16
|
||
|
|
</pre></blockquote>
|
||
|
|
</blockquote>
|
||
|
|
|
||
|
|
</blockquote>
|
||
|
|
<h3><a href="#TOP">»</a> <a name="outputs">qvoronoi
|
||
|
|
outputs</a></h3>
|
||
|
|
<blockquote>
|
||
|
|
|
||
|
|
<p>These options control the output of Voronoi diagrams.</p>
|
||
|
|
<blockquote>
|
||
|
|
|
||
|
|
<dl compact>
|
||
|
|
<dt> </dt>
|
||
|
|
<dd><b>Voronoi vertices</b></dd>
|
||
|
|
<dt><a href="qh-opto.htm#p">p</a></dt>
|
||
|
|
<dd>print the coordinates of the Voronoi vertices. The first line
|
||
|
|
is the dimension. The second line is the number of vertices. Each
|
||
|
|
remaining line is a Voronoi vertex.</dd>
|
||
|
|
<dt><a href="qh-optf.htm#Fn">Fn</a></dt>
|
||
|
|
<dd>list the neighboring Voronoi vertices for each Voronoi
|
||
|
|
vertex. The first line is the number of Voronoi vertices. Each
|
||
|
|
remaining line starts with the number of neighboring vertices.
|
||
|
|
Negative vertices (e.g., <em>-1</em>) indicate vertices
|
||
|
|
outside of the Voronoi diagram.
|
||
|
|
In the circle-in-box example, the
|
||
|
|
Voronoi vertex at the origin has four neighbors.</dd>
|
||
|
|
<dt><a href="qh-optf.htm#FN">FN</a></dt>
|
||
|
|
<dd>list the Voronoi vertices for each Voronoi region. The first line is
|
||
|
|
the number of Voronoi regions. Each remaining line starts with the
|
||
|
|
number of Voronoi vertices. Negative indices (e.g., <em>-1</em>) indicate vertices
|
||
|
|
outside of the Voronoi diagram.
|
||
|
|
In the circle-in-box example, the four bounded regions are defined by four
|
||
|
|
Voronoi vertices.</dd>
|
||
|
|
|
||
|
|
<dt> </dt>
|
||
|
|
<dt> </dt>
|
||
|
|
<dd><b>Voronoi regions</b></dd>
|
||
|
|
<dt><a href="qh-opto.htm#o">o</a></dt>
|
||
|
|
<dd>print the Voronoi regions in OFF format. The first line is the
|
||
|
|
dimension. The second line is the number of vertices, the number
|
||
|
|
of input sites, and "1". The third line represents the vertex-at-infinity.
|
||
|
|
Its coordinates are "-10.101". The next lines are the coordinates
|
||
|
|
of the Voronoi vertices. Each remaining line starts with the number
|
||
|
|
of Voronoi vertices in a Voronoi region. In 2-d, the vertices are
|
||
|
|
listed in adjacency order (unoriented). In 3-d and higher, the
|
||
|
|
vertices are listed in numeric order. In the circle-in-square
|
||
|
|
example, each bounded region includes the Voronoi vertex at
|
||
|
|
the origin. Lines consisting of <em>0</em> indicate
|
||
|
|
coplanar input sites or '<a href="qh-optq.htm#Qz">Qz</a>'. </dd>
|
||
|
|
<dt><a href="qh-optf.htm#Fi2">Fi</a></dt>
|
||
|
|
<dd>print separating hyperplanes for inner, bounded Voronoi
|
||
|
|
regions. The first number is the number of separating
|
||
|
|
hyperplanes. Each remaining line starts with <i>3+dim</i>. The
|
||
|
|
next two numbers are adjacent input sites. The next <i>dim</i>
|
||
|
|
numbers are the coefficients of the separating hyperplane. The
|
||
|
|
last number is its offset. Use '<a href="qh-optt.htm#Tv">Tv</a>' to verify that the
|
||
|
|
hyperplanes are perpendicular bisectors. It will list relevant
|
||
|
|
statistics to stderr. </dd>
|
||
|
|
<dt><a href="qh-optf.htm#Fo2">Fo</a></dt>
|
||
|
|
<dd>print separating hyperplanes for outer, unbounded Voronoi
|
||
|
|
regions. The first number is the number of separating
|
||
|
|
hyperplanes. Each remaining line starts with <i>3+dim</i>. The
|
||
|
|
next two numbers are adjacent input sites on the convex hull. The
|
||
|
|
next <i>dim</i>
|
||
|
|
numbers are the coefficients of the separating hyperplane. The
|
||
|
|
last number is its offset. Use '<a href="qh-optt.htm#Tv">Tv</a>' to verify that the
|
||
|
|
hyperplanes are perpendicular bisectors. It will list relevant
|
||
|
|
statistics to stderr,</dd>
|
||
|
|
<dt> </dt>
|
||
|
|
<dt> </dt>
|
||
|
|
<dd><b>Input sites</b></dd>
|
||
|
|
<dt><a href="qh-optf.htm#Fv2">Fv</a></dt>
|
||
|
|
<dd>list ridges of Voronoi vertices for pairs of input sites. The
|
||
|
|
first line is the number of ridges. Each remaining line starts with
|
||
|
|
two plus the number of Voronoi vertices in the ridge. The next
|
||
|
|
two numbers are two adjacent input sites. The remaining numbers list
|
||
|
|
the Voronoi vertices. As with option 'o', a <em>0</em> indicates
|
||
|
|
the vertex-at-infinity
|
||
|
|
and an unbounded, separating hyperplane.
|
||
|
|
The perpendicular bisector (separating hyperplane)
|
||
|
|
of the input sites is a flat through these vertices.
|
||
|
|
In the circle-in-square example, the ridge for each edge of the square
|
||
|
|
is unbounded.</dd>
|
||
|
|
<dt><a href="qh-optf.htm#Fc">Fc</a></dt>
|
||
|
|
<dd>list coincident input sites for each Voronoi vertex.
|
||
|
|
The first line is the number of vertices. The remaining lines start with
|
||
|
|
the number of coincident sites and deleted vertices. Deleted vertices
|
||
|
|
indicate highly degenerate input (see'<a href="qh-optf.htm#Fs">Fs</a>').
|
||
|
|
A coincident site is assigned to one Voronoi
|
||
|
|
vertex. Do not use '<a href="qh-optq.htm#QJn">QJ</a>' with 'Fc'; the joggle will separate
|
||
|
|
coincident sites.</dd>
|
||
|
|
<dt><a href="qh-optf.htm#FP">FP</a></dt>
|
||
|
|
<dd>print coincident input sites with distance to
|
||
|
|
nearest site (i.e., vertex). The first line is the
|
||
|
|
number of coincident sites. Each remaining line starts with the point ID of
|
||
|
|
an input site, followed by the point ID of a coincident point, its vertex, and distance.
|
||
|
|
Includes deleted vertices which
|
||
|
|
indicate highly degenerate input (see'<a href="qh-optf.htm#Fs">Fs</a>').
|
||
|
|
Do not use '<a href="qh-optq.htm#QJn">QJ</a>' with 'FP'; the joggle will separate
|
||
|
|
coincident sites.</dd>
|
||
|
|
<dt> </dt>
|
||
|
|
<dt> </dt>
|
||
|
|
<dd><b>General</b></dd>
|
||
|
|
<dt><a href="qh-opto.htm#s">s</a></dt>
|
||
|
|
<dd>print summary of the Voronoi diagram. Use '<a
|
||
|
|
href="qh-optf.htm#Fs">Fs</a>' for numeric data.</dd>
|
||
|
|
<dt><a href="qh-opto.htm#i">i</a></dt>
|
||
|
|
<dd>list input sites for each <a href=qdelaun.htm>Delaunay region</a>. Use option '<a href="qh-optp.htm#Pp">Pp</a>'
|
||
|
|
to avoid the warning. The first line is the number of regions. The
|
||
|
|
remaining lines list the input sites for each region. The regions are
|
||
|
|
oriented. In the circle-in-square example, the cocircular region has four
|
||
|
|
edges. In 3-d and higher, report cospherical sites by adding extra points.
|
||
|
|
</dd>
|
||
|
|
<dt><a href="qh-optg.htm#G">G</a></dt>
|
||
|
|
<dd>Geomview output for 2-d Voronoi diagrams.</dd>
|
||
|
|
</dl>
|
||
|
|
</blockquote>
|
||
|
|
</blockquote>
|
||
|
|
<h3><a href="#TOP">»</a> <a name="controls">qvoronoi
|
||
|
|
controls</a></h3>
|
||
|
|
<blockquote>
|
||
|
|
|
||
|
|
<p>These options provide additional control:</p>
|
||
|
|
<blockquote>
|
||
|
|
|
||
|
|
<dl compact>
|
||
|
|
<dt><a href="qh-optq.htm#Qu">Qu</a></dt>
|
||
|
|
<dd>compute the <a href="qvoron_f.htm">furthest-site Voronoi diagram</a>.</dd>
|
||
|
|
<dt><a href="qh-optq.htm#QVn">QVn</a></dt>
|
||
|
|
<dd>select Voronoi vertices for input site <em>n</em> </dd>
|
||
|
|
<dt><a href="qh-optq.htm#Qz">Qz</a></dt>
|
||
|
|
<dd>add a point above the paraboloid to reduce precision
|
||
|
|
errors. Use it for nearly cocircular/cospherical input
|
||
|
|
(e.g., 'rbox c | qvoronoi Qz').</dd>
|
||
|
|
<dt><a href="qh-optt.htm#Tv">Tv</a></dt>
|
||
|
|
<dd>verify result</dd>
|
||
|
|
<dt><a href="qh-optt.htm#TO">TI file</a></dt>
|
||
|
|
<dd>input data from file. The filename may not use spaces or quotes.</dd>
|
||
|
|
<dt><a href="qh-optt.htm#TO">TO file</a></dt>
|
||
|
|
<dd>output results to file. Use single quotes if the filename
|
||
|
|
contains spaces (e.g., <tt>TO 'file with spaces.txt'</tt></dd>
|
||
|
|
<dt><a href="qh-optt.htm#TFn">TFn</a></dt>
|
||
|
|
<dd>report progress after constructing <em>n</em> facets</dd>
|
||
|
|
<dt><a href="qh-optp.htm#PDk">PDk:1</a></dt>
|
||
|
|
<dd>include upper and lower facets in the output. Set <em>k</em>
|
||
|
|
to the last dimension (e.g., 'PD2:1' for 2-d inputs). </dd>
|
||
|
|
<dt><a href="qh-opto.htm#f">f </a></dt>
|
||
|
|
<dd>facet dump. Print the data structure for each facet (i.e.,
|
||
|
|
Voronoi vertex).</dd>
|
||
|
|
</dl>
|
||
|
|
|
||
|
|
</blockquote>
|
||
|
|
</blockquote>
|
||
|
|
<h3><a href="#TOP">»</a> <a name="graphics">qvoronoi
|
||
|
|
graphics</a></h3>
|
||
|
|
<blockquote>
|
||
|
|
|
||
|
|
<p>In 2-d, Geomview output ('<a href="qh-optg.htm#G">G</a>')
|
||
|
|
displays a Voronoi diagram with extra edges to close the
|
||
|
|
unbounded Voronoi regions. To view the unbounded rays, enclose
|
||
|
|
the input points in a square.</p>
|
||
|
|
|
||
|
|
<p>You can also view <i>individual</i> Voronoi regions in 3-d. To
|
||
|
|
view the Voronoi region for site 3 in Geomview, execute</p>
|
||
|
|
|
||
|
|
<blockquote>
|
||
|
|
<p>qvoronoi <data <a href="qh-optq.htm#QVn">QV3</a> <a
|
||
|
|
href="qh-opto.htm#p">p</a> | qconvex s G >output</p>
|
||
|
|
</blockquote>
|
||
|
|
|
||
|
|
<p>The <tt>qvoronoi</tt> command returns the Voronoi vertices
|
||
|
|
for input site 3. The <tt>qconvex</tt> command computes their convex hull.
|
||
|
|
This is the Voronoi region for input site 3. Its
|
||
|
|
hyperplane normals (qconvex 'n') are the same as the separating hyperplanes
|
||
|
|
from options '<a href="qh-optf.htm#Fi">Fi</a>'
|
||
|
|
and '<a href="qh-optf.htm#Fo">Fo</a>' (up to roundoff error).
|
||
|
|
|
||
|
|
<p>See the <a href="qh-eg.htm#delaunay">Delaunay and Voronoi
|
||
|
|
examples</a> for 2-d and 3-d examples. Turn off normalization (on
|
||
|
|
Geomview's 'obscure' menu) when comparing the Voronoi diagram
|
||
|
|
with the corresponding Delaunay triangulation. </p>
|
||
|
|
|
||
|
|
</blockquote>
|
||
|
|
<h3><a href="#TOP">»</a><a name="notes">qvoronoi
|
||
|
|
notes</a></h3>
|
||
|
|
<blockquote>
|
||
|
|
|
||
|
|
<p>You can simplify the Voronoi diagram by enclosing the input
|
||
|
|
sites in a large square or cube. This is particularly recommended
|
||
|
|
for cocircular or cospherical input data.</p>
|
||
|
|
|
||
|
|
<p>See <a href="#graphics">Voronoi graphics</a> for computing
|
||
|
|
the convex hull of a Voronoi region. </p>
|
||
|
|
|
||
|
|
<p>Voronoi diagrams do not include facets that are
|
||
|
|
coplanar with the convex hull of the input sites. A facet is
|
||
|
|
coplanar if the last coefficient of its normal is
|
||
|
|
nearly zero (see <a href="../src/user.h#ZEROdelaunay">qh_ZEROdelaunay</a>).
|
||
|
|
|
||
|
|
<p>Unbounded regions can be confusing. For example, '<tt>rbox c |
|
||
|
|
qvoronoi Qz o</tt>' produces the Voronoi regions for the vertices
|
||
|
|
of a cube centered at the origin. All regions are unbounded. The
|
||
|
|
output is </p>
|
||
|
|
|
||
|
|
<blockquote>
|
||
|
|
<pre>3
|
||
|
|
2 9 1
|
||
|
|
-10.101 -10.101 -10.101
|
||
|
|
0 0 0
|
||
|
|
2 0 1
|
||
|
|
2 0 1
|
||
|
|
2 0 1
|
||
|
|
2 0 1
|
||
|
|
2 0 1
|
||
|
|
2 0 1
|
||
|
|
2 0 1
|
||
|
|
2 0 1
|
||
|
|
0
|
||
|
|
</pre>
|
||
|
|
</blockquote>
|
||
|
|
|
||
|
|
<p>The first line is the dimension. The second line is the number
|
||
|
|
of vertices and the number of regions. There is one region per
|
||
|
|
input point plus a region for the point-at-infinity added by
|
||
|
|
option '<a href="qh-optq.htm#Qz">Qz</a>'. The next two lines
|
||
|
|
lists the Voronoi vertices. The first vertex is the infinity
|
||
|
|
vertex. It is indicate by the coordinates <em>-10.101</em>. The
|
||
|
|
second vertex is the origin. The next nine lines list the
|
||
|
|
regions. Each region lists two vertices -- the infinity vertex
|
||
|
|
and the origin. The last line is "0" because no region
|
||
|
|
is associated with the point-at-infinity. A "0" would
|
||
|
|
also be listed for nearly incident input sites. </p>
|
||
|
|
|
||
|
|
<p>To use option '<a href="qh-optf.htm#Fv">Fv</a>', add an
|
||
|
|
interior point. For example, </p>
|
||
|
|
|
||
|
|
<blockquote>
|
||
|
|
<pre>
|
||
|
|
rbox c P0 | qvoronoi Fv
|
||
|
|
20
|
||
|
|
5 0 7 1 3 5
|
||
|
|
5 0 3 1 4 5
|
||
|
|
5 0 5 1 2 3
|
||
|
|
5 0 1 1 2 4
|
||
|
|
5 0 6 2 3 6
|
||
|
|
5 0 2 2 4 6
|
||
|
|
5 0 4 4 5 6
|
||
|
|
5 0 8 5 3 6
|
||
|
|
5 1 2 0 2 4
|
||
|
|
5 1 3 0 1 4
|
||
|
|
5 1 5 0 1 2
|
||
|
|
5 2 4 0 4 6
|
||
|
|
5 2 6 0 2 6
|
||
|
|
5 3 4 0 4 5
|
||
|
|
5 3 7 0 1 5
|
||
|
|
5 4 8 0 6 5
|
||
|
|
5 5 6 0 2 3
|
||
|
|
5 5 7 0 1 3
|
||
|
|
5 6 8 0 6 3
|
||
|
|
5 7 8 0 3 5
|
||
|
|
</pre>
|
||
|
|
</blockquote>
|
||
|
|
|
||
|
|
<p>The output consists of 20 ridges and each ridge lists a pair
|
||
|
|
of input sites and a triplet of Voronoi vertices. The first eight
|
||
|
|
ridges connect the origin ('P0'). The remainder list the edges of
|
||
|
|
the cube. Each edge generates an unbounded ray through the
|
||
|
|
midpoint. The corresponding separating planes ('Fo') follow each
|
||
|
|
pair of coordinate axes. </p>
|
||
|
|
|
||
|
|
<p>Options '<a href="qh-optq.htm#Qt">Qt</a>' (triangulated output)
|
||
|
|
and '<a href="qh-optq.htm#QJn">QJ</a>' (joggled input) are deprecated. They may produce
|
||
|
|
unexpected results. If you use these options, cocircular and cospherical input sites will
|
||
|
|
produce duplicate or nearly duplicate Voronoi vertices. See also <a
|
||
|
|
href="qh-impre.htm#joggle">Merged facets or joggled input</a>. </p>
|
||
|
|
|
||
|
|
</blockquote>
|
||
|
|
<h3><a href="#TOP">»</a><a name="conventions">qvoronoi conventions</a></h3>
|
||
|
|
<blockquote>
|
||
|
|
|
||
|
|
<p>The following terminology is used for Voronoi diagrams in
|
||
|
|
Qhull. The underlying structure is a Delaunay triangulation from
|
||
|
|
a convex hull in one higher dimension. Facets of the Delaunay
|
||
|
|
triangulation correspond to vertices of the Voronoi diagram.
|
||
|
|
Vertices of the Delaunay triangulation correspond to input sites.
|
||
|
|
They also correspond to regions of the Voronoi diagram. See <a
|
||
|
|
href="qconvex.htm#conventions">convex hull conventions</a>, <a
|
||
|
|
href="qdelaun.htm#conventions">Delaunay conventions</a>, and
|
||
|
|
<a href="index.htm#structure">Qhull's data structures</a>.</p>
|
||
|
|
<blockquote>
|
||
|
|
|
||
|
|
<ul>
|
||
|
|
<li><em>input site</em> - a point in the input (one dimension
|
||
|
|
lower than a point on the convex hull)</li>
|
||
|
|
<li><em>point</em> - a point has <i>d+1</i> coordinates. The
|
||
|
|
last coordinate is the sum of the squares of the input
|
||
|
|
site's coordinates</li>
|
||
|
|
<li><em>coplanar point</em> - a <em>nearly incident</em>
|
||
|
|
input site</li>
|
||
|
|
<li><em>vertex</em> - a point on the paraboloid. It
|
||
|
|
corresponds to a unique input site. </li>
|
||
|
|
<li><em>point-at-infinity</em> - a point added above the
|
||
|
|
paraboloid by option '<a href="qh-optq.htm#Qz">Qz</a>'</li>
|
||
|
|
<li><em>Delaunay facet</em> - a lower facet of the
|
||
|
|
paraboloid. The last coefficient of its normal is
|
||
|
|
clearly negative.</li>
|
||
|
|
<li><em>Voronoi vertex</em> - the circumcenter of a Delaunay
|
||
|
|
facet</li>
|
||
|
|
<li><em>Voronoi region</em> - the Voronoi vertices for an
|
||
|
|
input site. The region of Euclidean space nearest to an
|
||
|
|
input site.</li>
|
||
|
|
<li><em>Voronoi diagram</em> - the graph of the Voronoi
|
||
|
|
regions. It includes the ridges (i.e., edges) between the
|
||
|
|
regions.</li>
|
||
|
|
<li><em>vertex-at-infinity</em> - the Voronoi vertex that
|
||
|
|
indicates unbounded Voronoi regions in '<a
|
||
|
|
href="qh-opto.htm#o">o</a>' output format. Its
|
||
|
|
coordinates are <em>-10.101</em>.</li>
|
||
|
|
<li><em>good facet</em> - a Voronoi vertex with optional
|
||
|
|
restrictions by '<a href="qh-optq.htm#QVn">QVn</a>', etc.</li>
|
||
|
|
</ul>
|
||
|
|
|
||
|
|
</blockquote>
|
||
|
|
</blockquote>
|
||
|
|
<h3><a href="#TOP">»</a><a name="options">qvoronoi options</a></h3>
|
||
|
|
|
||
|
|
<pre>
|
||
|
|
qvoronoi- compute the Voronoi diagram
|
||
|
|
http://www.qhull.org
|
||
|
|
|
||
|
|
input (stdin):
|
||
|
|
first lines: dimension and number of points (or vice-versa).
|
||
|
|
other lines: point coordinates, best if one point per line
|
||
|
|
comments: start with a non-numeric character
|
||
|
|
|
||
|
|
options:
|
||
|
|
Qu - compute furthest-site Voronoi diagram
|
||
|
|
|
||
|
|
Qhull control options:
|
||
|
|
QJn - randomly joggle input in range [-n,n]
|
||
|
|
Qs - search all points for the initial simplex
|
||
|
|
Qz - add point-at-infinity to Voronoi diagram
|
||
|
|
QGn - Voronoi vertices if visible from point n, -n if not
|
||
|
|
QVn - Voronoi vertices for input point n, -n if not
|
||
|
|
|
||
|
|
Trace options:
|
||
|
|
T4 - trace at level n, 4=all, 5=mem/gauss, -1= events
|
||
|
|
Tc - check frequently during execution
|
||
|
|
Ts - statistics
|
||
|
|
Tv - verify result: structure, convexity, and in-circle test
|
||
|
|
Tz - send all output to stdout
|
||
|
|
TFn - report summary when n or more facets created
|
||
|
|
TI file - input data from file, no spaces or single quotes
|
||
|
|
TO file - output results to file, may be enclosed in single quotes
|
||
|
|
TPn - turn on tracing when point n added to hull
|
||
|
|
TMn - turn on tracing at merge n
|
||
|
|
TWn - trace merge facets when width > n
|
||
|
|
TVn - stop qhull after adding point n, -n for before (see TCn)
|
||
|
|
TCn - stop qhull after building cone for point n (see TVn)
|
||
|
|
|
||
|
|
Precision options:
|
||
|
|
Cn - radius of centrum (roundoff added). Merge facets if non-convex
|
||
|
|
An - cosine of maximum angle. Merge facets if cosine > n or non-convex
|
||
|
|
C-0 roundoff, A-0.99/C-0.01 pre-merge, A0.99/C0.01 post-merge
|
||
|
|
Rn - randomly perturb computations by a factor of [1-n,1+n]
|
||
|
|
Wn - min facet width for non-coincident point (before roundoff)
|
||
|
|
|
||
|
|
Output formats (may be combined; if none, produces a summary to stdout):
|
||
|
|
s - summary to stderr
|
||
|
|
p - Voronoi vertices
|
||
|
|
o - OFF format (dim, Voronoi vertices, and Voronoi regions)
|
||
|
|
i - Delaunay regions (use 'Pp' to avoid warning)
|
||
|
|
f - facet dump
|
||
|
|
|
||
|
|
More formats:
|
||
|
|
Fc - count plus coincident points (by Voronoi vertex)
|
||
|
|
Fd - use cdd format for input (homogeneous with offset first)
|
||
|
|
FD - use cdd format for output (offset first)
|
||
|
|
FF - facet dump without ridges
|
||
|
|
Fi - separating hyperplanes for bounded Voronoi regions
|
||
|
|
FI - ID for each Voronoi vertex
|
||
|
|
Fm - merge count for each Voronoi vertex (511 max)
|
||
|
|
Fn - count plus neighboring Voronoi vertices for each Voronoi vertex
|
||
|
|
FN - count and Voronoi vertices for each Voronoi region
|
||
|
|
Fo - separating hyperplanes for unbounded Voronoi regions
|
||
|
|
FO - options and precision constants
|
||
|
|
FP - nearest point and distance for each coincident point
|
||
|
|
FQ - command used for qvoronoi
|
||
|
|
Fs - summary: #int (8), dimension, #points, tot vertices, tot facets,
|
||
|
|
for output: #Voronoi regions, #Voronoi vertices,
|
||
|
|
#coincident points, #non-simplicial regions
|
||
|
|
#real (2), max outer plane and min vertex
|
||
|
|
Fv - Voronoi diagram as Voronoi vertices between adjacent input sites
|
||
|
|
Fx - extreme points of Delaunay triangulation (on convex hull)
|
||
|
|
|
||
|
|
Geomview options (2-d only)
|
||
|
|
Ga - all points as dots
|
||
|
|
Gp - coplanar points and vertices as radii
|
||
|
|
Gv - vertices as spheres
|
||
|
|
Gi - inner planes only
|
||
|
|
Gn - no planes
|
||
|
|
Go - outer planes only
|
||
|
|
Gc - centrums
|
||
|
|
Gh - hyperplane intersections
|
||
|
|
Gr - ridges
|
||
|
|
GDn - drop dimension n in 3-d and 4-d output
|
||
|
|
|
||
|
|
Print options:
|
||
|
|
PAn - keep n largest Voronoi vertices by 'area'
|
||
|
|
Pdk:n - drop facet if normal[k] <= n (default 0.0)
|
||
|
|
PDk:n - drop facet if normal[k] >= n
|
||
|
|
Pg - print good Voronoi vertices (needs 'QGn' or 'QVn')
|
||
|
|
PFn - keep Voronoi vertices whose 'area' is at least n
|
||
|
|
PG - print neighbors of good Voronoi vertices
|
||
|
|
PMn - keep n Voronoi vertices with most merges
|
||
|
|
Po - force output. If error, output neighborhood of facet
|
||
|
|
Pp - do not report precision problems
|
||
|
|
|
||
|
|
. - list of all options
|
||
|
|
- - one line descriptions of all options
|
||
|
|
</pre>
|
||
|
|
|
||
|
|
<!-- Navigation links -->
|
||
|
|
<hr>
|
||
|
|
|
||
|
|
<p><b>Up:</b> <a href="http://www.qhull.org">Home page</a> for Qhull<br>
|
||
|
|
<b>Up:</b> <a href="index.htm#TOC">Qhull manual</a>: Table of Contents<br>
|
||
|
|
<b>To:</b> <a href="qh-quick.htm#programs">Programs</a>
|
||
|
|
• <a href="qh-quick.htm#options">Options</a>
|
||
|
|
• <a href="qh-opto.htm#output">Output</a>
|
||
|
|
• <a href="qh-optf.htm#format">Formats</a>
|
||
|
|
• <a href="qh-optg.htm#geomview">Geomview</a>
|
||
|
|
• <a href="qh-optp.htm#print">Print</a>
|
||
|
|
• <a href="qh-optq.htm#qhull">Qhull</a>
|
||
|
|
• <a href="qh-optc.htm#prec">Precision</a>
|
||
|
|
• <a href="qh-optt.htm#trace">Trace</a>
|
||
|
|
• <a href="../src/libqhull_r/index.htm">Functions</a><br>
|
||
|
|
<b>To:</b> <a href="#synopsis">sy</a>nopsis
|
||
|
|
• <a href="#input">in</a>put • <a href="#outputs">ou</a>tputs
|
||
|
|
• <a href="#controls">co</a>ntrols • <a href="#graphics">gr</a>aphics
|
||
|
|
• <a href="#notes">no</a>tes • <a href="#conventions">co</a>nventions
|
||
|
|
• <a href="#options">op</a>tions
|
||
|
|
<!-- GC common information -->
|
||
|
|
<hr>
|
||
|
|
|
||
|
|
<p><a href="http://www.geom.uiuc.edu/"><img src="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: Sept. 25, 1995 --- <!-- hhmts start --> Last modified: see top <!-- hhmts end --> </p>
|
||
|
|
</body>
|
||
|
|
</html>
|