![[delaunay]](qh--dt.gif)
Qhull options: Delaunay and VoronoiUp: Home
page for Qhull
Up: Qhull manual: Table of
Contents
Up: Qhull options
To: Synopsis • Main • Output • Formats • Geomview • Print • Qhull • Precision • Trace
Qhull options: Delaunay and VoronoiThis section lists the options for Delaunay triangulations, Voronoi diagrams, furthest-site Delaunay triangulations, and furthest-site Voronoi diagrams.
Qhull computes these structures as convex hulls. This may be confusing. To help you understand Qhull, each structure is introduced with a representative example. You can use the same options with your application. Experiment with the other options as you need them.
Copyright © 1995-1998 The Geometry Center, Minneapolis MN
The Delaunay triangulation is the triangulation with empty circumspheres. It has many useful properties and applications. See the survey article by Aurenhammer ['91] and the detailed introduction by O'Rourke ['94].
Qhull computes the Delaunay triangulation by computing a convex hull. It lifts the input sites to a paraboloid by adding the sum of the squares of the coordinates. It computes the convex hull of the lifted sites, and projects the lower convex hull to the input. Each triangle of the Delaunay triangulation corresponds to a facet of the lower half of the convex hull. Facets of the upper half of the convex hull correspond to the furthest-site Delaunay triangulation. See the examples, Delaunay and Voronoi diagrams.
See Qhull FAQ - Delaunay and Voronoi diagram questions.
Most users should use 'qhull d QJ' or 'qhull d Qbb'. If you use 'QJ', duplicate points will create small triangles. If you do not use 'QJ', the output reports duplicate input sites and merges facets for cocircular or cospherical input sites. See Joggled input or merged facets.
The following terminology is used for Delaunay triangulations in Qhull for dimension d. The underlying structure is the lower facets of a convex hull in dimension d+1. For further information, see data structures and convex hull conventions.
These options control the output of Delaunay triangulations:
These options provide additional control:
For 2-d and 3-d Delaunay triangulations, Geomview ('qhull d G') displays the corresponding convex hull (a paraboloid).
To view a 2-d Delaunay triangulation, use 'qhull d GrD2' to drop the last dimension. This is the same as viewing the hull without perspective (see Geomview's 'cameras' menu).
To view a 3-d Delaunay triangulation, use 'qhull d GrD3' to drop the last dimension. You may see extra edges. These are interior edges that Geomview moves towards the viewer (see 'lines closer' in Geomview's camera options). Use option 'Gt' to make the outer ridges transparent in 3-d. See Delaunay and Voronoi examples.
For 2-d Delaunay triangulations, Mathematica output ('m') displays the corresponding convex hull (a paraboloid).
A non-simplicial facet indicates nearly cocircular or cospherical input sites. To avoid non-simplicial facets joggle the input with 'QJ' or use option 'Ft' to print a triangulation. It adds points for non-simplicial facets. Alternatively, use an exact arithmetic code.
To compute the Delaunay triangulation of points on a sphere, compute their convex hull. If the sphere is the unit sphere at the origin, the facet normals are the Voronoi vertices of the input. The points may be restricted to a hemisphere. [S. Fortune]
The 3-d Delaunay triangulation of regular points on a half spiral (e.g., 'rbox 100 l | qhull d') has quadratic size, while the Delaunay triangulation of random 3-d points is approximately linear for reasonably sized point sets.
With the Qhull library, you can use qh_findbestfacet in poly2.c to locate the facet that contains a point. You should first lift the point to the paraboloid (i.e., the last coordinate is the sum of the squares of the point's coordinates -- qh_setdelaunay). Do not use options 'Qbb', 'QbB', 'Qbk:n', or 'QBk:n' since these scale the last coordinate.
If a point is interior to the convex hull of the input set, it is interior to the adjacent vertices of the Delaunay triangulation. This is demonstrated by the following pipe for point 0:
qhull <data d s FQ QV0 Pg p | qhull s Qb3:0B3:0 p
The first call to Qhull returns the neighboring points of point 0 in the Delaunay triangulation. The second call to Qhull returns the vertices of the convex hull of these points (after dropping the lifted coordinate). If point 0 is interior to the original point set, it is interior to the reduced point set.
The Voronoi diagram is the nearest-neighbor map for a set of points. 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.
Qhull computes the Voronoi diagram via the Delaunay triangulation ('d'). Each Voronoi vertex is the circumcenter of a facet of the Delaunay triangulation. Each Voronoi region corresponds to a vertex of the Delaunay triangulation (i.e., an input site).
Qhull outputs the Voronoi vertices for each Voronoi region (i.e., each input point). With option 'Fv'), it lists all ridges of the Voronoi diagram with the corresponding pair of input sites. You can also output a single Voronoi region for further processing [see graphics].
See Qhull FAQ - Delaunay and Voronoi diagram questions.
Most users should use 'qhull v QJ' or 'qhull v Qbb'. If you use 'QJ', duplicate points will create small triangles and cocircular or cospherical input sites create multiple Voronoi vertices. If you do not use 'QJ', the output reports duplicate input sites and reports one Voronoi vertex for cocircular or cospherical input sites. See Joggled input or merged facets'.
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 and Delaunay conventions.
These options control the output of Voronoi diagrams. Other output options return the corresponding Delaunay triangulation.
For the 'o' option, the first number is the dimension. The next two numbers are the number of vertices and the number of input sites. The line ends with a "1". The Voronoi vertices are listed one per line. The first (0'th) vertex indicates the infinity vertex. Its coordinates are -10.101. The infinity vertex also occurs for degenerate Delaunay triangles.
The Voronoi regions follow the vertices with one line per input site. Each region is defined by the number of Voronoi vertices followed by the index of each vertex. Coplanar input sites have "0" vertices. In 2-d, the vertices are listed in adjacency order (unoriented). In 3-d and higher, the vertices are listed in numeric order. A zero index indicates the infinity vertex. Such regions are unbounded. If you use option 'Qz', the last line will be the Voronoi region for the point-at-infinity (a single "0").
For the 'Fv' option, the first line is the number of ridges. The remaining lines list the number of indices, a pair of input sites, and the corresponding ridge of the Voronoi diagram. Vertex 0 indicates an unbounded ray.
These options provide additional control:
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 first qhull command returns the Voronoi vertices for all facets incident to point 3 in the Delaunay triangulation. The second qhull command computes their convex hull. This is the Voronoi region for input site 3.
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.
See Voronoi graphics for computing the convex hull of a Voronoi region.
Unbounded regions can be confusing. For example, 'rbox c | qhull v 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 | qhull v 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.
The furthest-site Delaunay triangulation is dual of the furthest-site Voronoi diagram. It corresponds to the upper Delaunay facets of the Delaunay construction ('d').
As in the Delaunay triangulation, Qhull computes the furthest-site triangulation by lifting the input sites to a paraboloid. The lower facets correspond to the Delaunay triangulation while the upper facets correspond to the furthest-site triangulation. Neither triangulation includes "vertical" facets (i.e., facets whose last hyperplane coefficient is nearly zero). Vertical facets correspond to input sites that are coplanar to the convex hull of the input. An example is points on the boundary of a lattice.
Most users should use 'qhull d Qu QJ' or 'qhull d Qu Qbb'. If you use 'QJ', duplicate points will create small triangles. If you do not use 'QJ', the output reports duplicate input sites and merges facets for cocircular or cospherical input sites. See Joggled input or merged facets'.
The following terminology is used for furthest-site Delaunay triangulations in Qhull. The underlying structure is the upper facets of a convex hull in one higher dimension. See convex hull conventions and Delaunay conventions.
These options control the output of furthest-site Delaunay triangulations:
These options provide additional control:
For 2-d and 3-d furthest-site Delaunay triangulations, Geomview ('qhull d Qu G') displays the corresponding convex hull (a paraboloid).
To get a 2-d furthest-site Delaunay triangulation, use 'qhull d Qu GrD2' to drop the last dimension. This is the same as viewing the hull without perspective (see Geomview's 'cameras' menu).
To get a 3-d furthest-site Delaunay triangulation, use 'qhull d Qu GrD3' to drop the last dimension. You may see extra edges. These are interior edges that Geomview moves towards the viewer (see 'lines closer' in Geomview's camera options). Use option 'Gt' to make the outer ridges transparent in 3-d.
For 2-d furthest-site Delaunay triangulations, Mathematica ('m') displays the corresponding convex hull (a paraboloid).
See Delaunay notes.
The furthest-site Voronoi diagram is the furthest-neighbor map for a set of points. See the survey article by Aurenhammer ['91] and a brief introduction by O'Rourke ['94].
The furthest-site Voronoi diagram is the dual of the furthest-site Delaunay triangulation. Each furthest-site Voronoi vertex is the circumcenter of an upper facet of the Delaunay triangulation. Each furthest-site Voronoi region corresponds to a vertex of the Delaunay triangulation (i.e., an input site). The correspondence skips interior input sites.
Qhull outputs the furthest-site Voronoi vertices for each furthest-site Voronoi region, and the ridge of the furthest-site Voronoi diagram for each corresponding pair of input sites on the convex hull.
Most users should use 'qhull v Qu QJ' or 'qhull v Qu Qbb'. If you use 'QJ', duplicate points will create small triangles. If you do not use 'QJ', the output reports duplicate input sites and merges facets for cocircular or cospherical input sites. See Joggled input or merged facets'.
The following terminology is used for furthest-site Voronoi diagrams in Qhull. The underlying structure is a furthest-site Delaunay triangulation from a convex hull in one higher dimension. Upper facets of the Delaunay triangulation correspond to vertices of the furthest-site Voronoi diagram. Vertices of the furthest-site Delaunay triangulation correspond to input sites. They also define regions of the furthest-site Voronoi diagram. All vertices are extreme points of the input sites. See convex hull conventions and furthest-site Delaunay conventions.
These options control the output of furthest-site Voronoi diagram. Other output options return the corresponding furthest-site Delaunay triangulation.
For the 'o' option, the first number is the dimension. The next two numbers are the number of vertices and the number of input sites. The line ends with a "1". The furthest-site Voronoi vertices are listed one per line. The first (0'th) vertex indicates the infinity vertex. Its coordinates are -10.101. The infinity vertex also occurs for degenerate Delaunay triangles.
The furthest-site Voronoi regions follow the vertices with one line per input site. Each region is defined by the number of furthest-site Voronoi vertices followed by the index of each vertex. Coplanar and interior input sites have "0" vertices. In 2-d, the vertices are listed in adjacency order (unoriented). In 3-d and higher, the vertices are listed in numeric order. A zero index indicates the infinity vertex. Such regions are unbounded.
For the 'Fv' option, the first line is the number of ridges. The remaining lines list the number of indices, a pair of input sites, and the corresponding ridge of the furthest-site Voronoi diagram. Vertex 0 indicates an unbounded ray.
These options provide additional control:
In 2-d, Geomview output ('G') displays a furthest-site Voronoi diagram with extra edges to close the unbounded furthest-site Voronoi regions. All regions will be unbounded.
See the Delaunay and Voronoi examples for a 2-d example. Turn off normalization (on Geomview's 'obscure' menu) when comparing the furthest-site Voronoi diagram with the corresponding Voronoi diagram.
See Voronoi notes.
Up: Home
page for Qhull
Up: Qhull manual: Table of
Contents
Up: Qhull options
To: Synopsis • Main • Output • Formats • Geomview • Print • Qhull • Precision • Trace
The Geometry Center
Home Page
Comments to: qhull@geom.umn.edu
Created: Sept. 25, 1995 --- Last modified: see top