![[delaunay]](qh--dt.gif)
qvoronoi -- Voronoi diagramqvoronoi -- Voronoi diagramThe 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 ['91] and the detailed introduction by O'Rourke ['94]. The Voronoi diagram is the dual of the Delaunay triangulation.
- Example: rbox 10 D3 | qvoronoi s o TO result
- 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.
- Example: rbox r y c G0.1 D2 | qvoronoi s o TO result
- 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.
- Example: rbox r y c G0.1 D2 | qvoronoi Fv TO result
- 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.
- Example: rbox r y c G0.1 D2 | qvoronoi Fi
- 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.
Qhull computes the Voronoi diagram via the Delaunay triangulation. 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.
Qhull outputs the Voronoi vertices for each Voronoi region. With option 'Fv', it lists all ridges of the Voronoi diagram with the corresponding pairs of input sites. With options 'Fi' and 'Fo', it lists the bounded and unbounded separating hyperplanes. You can also output a single Voronoi region for further processing [see graphics].
See Qhull FAQ - Delaunay and Voronoi diagram questions.
Options 'Qt' (triangulated output) and 'QJ' (joggled input) may produce unexpected results. Cocircular and cospherical input sites will produce duplicate or nearly duplicate Voronoi vertices. See also Merged facets or joggled input.
The 'qvonoroi' program is equivalent to 'qhull v Qbb' in 2-d to 3-d, and 'qhull v Qbb Qx' in 4-d and higher. It disables the following Qhull options: 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.
Copyright © 1995-2003 The Geometry Center, Minneapolis MN
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
Qt - triangulated output
QJ - joggle input instead of merging facets
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 G1 d D2 | qvoronoi Qt s p
rbox c P0 D2 | qvoronoi s Fv QV0
The input data on stdin consists of:
- dimension
- number of points
- point coordinates
Use I/O redirection (e.g., qvoronoi < data.txt), a pipe (e.g., rbox 10 | qvoronoi), or the 'TI' option (e.g., qvoronoi TI data.txt).
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.
rbox s 4 W0 c G1 D2 > data2 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 1qvoronoi s p < data
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
These options control the output of Voronoi diagrams.
- Voronoi vertices
- p
- 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.
- Fn
- 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., -1) indicate vertices outside of the Voronoi diagram. In the circle-in-box example, the Voronoi vertex at the origin has four neighbors.
- FN
- 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., -1) indicate vertices outside of the Voronoi diagram. In the circle-in-box example, the four bounded regions are defined by four Voronoi vertices.
- Voronoi regions
- o
- 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 0 indicate coplanar input sites or 'Qz'.
- Fi
- print separating hyperplanes for inner, bounded Voronoi regions. The first number is the number of separating hyperplanes. Each remaining line starts with 3+dim. The next two numbers are adjacent input sites. The next dim numbers are the coefficients of the separating hyperplane. The last number is its offset. Use 'Tv' to verify that the hyperplanes are perpendicular bisectors. It will list relevant statistics to stderr.
- Fo
- print separating hyperplanes for outer, unbounded Voronoi regions. The first number is the number of separating hyperplanes. Each remaining line starts with 3+dim. The next two numbers are adjacent input sites on the convex hull. The next dim numbers are the coefficients of the separating hyperplane. The last number is its offset. Use 'Tv' to verify that the hyperplanes are perpendicular bisectors. It will list relevant statistics to stderr,
- Input sites
- Fv
- 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 0 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.
- Fc
- 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'Fs'). A coincident site is assigned to one Voronoi vertex. Do not use 'QJ' with 'Fc'; the joggle will separate coincident sites.
- FP
- 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'Fs'). Do not use 'QJ' with 'FP'; the joggle will separate coincident sites.
- General
- s
- print summary of the Voronoi diagram. Use 'Fs' for numeric data.
- i
- list input sites for each Delaunay region. Use option 'Pp' 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.
- G
- Geomview output for 2-d Voronoi diagrams.
These options provide additional control:
- Qt
- triangulated output. If a Voronoi vertex is defined by cospherical data, Qhull duplicates the vertex. For example, if the data contains a square, the output will contain two copies of the Voronoi vertex.
- QJ
- joggle the input to avoid Voronoi vertices defined by more than dim+1 points. It is less accurate than triangulated output ('Qt').
- Qu
- compute the furthest-site Voronoi diagram.
- QVn
- select Voronoi vertices for input site n
- Qz
- add a point above the paraboloid to reduce precision errors. Use it for nearly cocircular/cospherical input (e.g., 'rbox c | qvoronoi Qz').
- Tv
- verify result
- TI file
- input data from file. The filename may not use spaces or quotes.
- TO file
- output results to file. Use single quotes if the filename contains spaces (e.g., TO 'file with spaces.txt'
- TFn
- report progress after constructing n facets
- PDk:1
- include upper and lower facets in the output. Set k to the last dimension (e.g., 'PD2:1' for 2-d inputs).
- f
- facet dump. Print the data structure for each facet (i.e., Voronoi vertex).
In 2-d, Geomview output ('G') 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.
You can also view individual Voronoi regions in 3-d. To view the Voronoi region for site 3 in Geomview, execute
The qvoronoi command returns the Voronoi vertices for input site 3. The qconvex 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 'Fi' and 'Fo' (up to roundoff error).
See the Delaunay and Voronoi examples 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.
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.
See Voronoi graphics for computing the convex hull of a Voronoi region.
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 qh_ZEROdelaunay).
Unbounded regions can be confusing. For example, 'rbox c | qvoronoi Qz o' produces the Voronoi regions for the vertices of a cube centered at the origin. All regions are unbounded. The output is
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 0The 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 'Qz'. The next two lines lists the Voronoi vertices. The first vertex is the infinity vertex. It is indicate by the coordinates -10.101. 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.
To use option 'Fv', add an interior point. For example,
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 5The 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.
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 convex hull conventions, Delaunay conventions, and Qhull's data structures.
- input site - a point in the input (one dimension lower than a point on the convex hull)
- point - a point has d+1 coordinates. The last coordinate is the sum of the squares of the input site's coordinates
- coplanar point - a nearly incident input site
- vertex - a point on the paraboloid. It corresponds to a unique input site.
- point-at-infinity - a point added above the paraboloid by option 'Qz'
- Delaunay facet - a lower facet of the paraboloid. The last coefficient of its normal is clearly negative.
- Voronoi vertex - the circumcenter of a Delaunay facet
- Voronoi region - the Voronoi vertices for an input site. The region of Euclidean space nearest to an input site.
- Voronoi diagram - the graph of the Voronoi regions. It includes the ridges (i.e., edges) between the regions.
- vertex-at-infinity - the Voronoi vertex that indicates unbounded Voronoi regions in 'o' output format. Its coordinates are -10.101.
- good facet - a Voronoi vertex with optional restrictions by 'QVn', etc.
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
Qt - triangulated output
QJ - joggle input instead of merging facets
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
Up: Home page for Qhull
Up: Qhull manual: Table of Contents
To: Programs
• Options
• Output
• Formats
• Geomview
• Print
• Qhull
• Precision
• Trace
To: synopsis
• input • outputs
• controls • graphics
• notes • conventions
• options
The Geometry Center
Home Page
Comments to: qhull@qhull.org
Created: Sept. 25, 1995 --- Last modified: see top