Up: Home page for Qhull
Up: Qhull manual: Table of Contents
To: ProgramsOptionsOutputFormatsGeomviewPrintQhullPrecisionTrace
To: synopsis • input • outputs • controls • graphics • notes • conventions • options

[delaunay]qvoronoi -- Voronoi diagram

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 ['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 Joggled input or merged facets.

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-2002 The Geometry Center, Minneapolis MN


qvoronoi synopsis

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

qvoronoi input

The input data on stdin consists of:

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 > data
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

qvoronoi 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

qvoronoi outputs

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.

qvoronoi controls

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.
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).

qvoronoi graphics

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

qvoronoi <data 'QV3' 'p' | qconvex s G >output

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.

qvoronoi notes

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
0

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 '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 5

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.

qvoronoi conventions

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.

qvoronoi options

qvoronoi- compute the Voronoi diagram
    http://www.geom.umn.edu/software/qhull

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: ProgramsOptionsOutputFormatsGeomviewPrintQhullPrecisionTrace
To: synopsis • input • outputs • controls • graphics • notes • conventions • options


The Geometry Center Home Page

Comments to: qhull@geom.umn.edu
Created: Sept. 25, 1995 --- Last modified: see top