Up: Home page for Qhull
Up: Qhull manual
Up: Qhull options

To: SynopsisMainOutputFormatsGeomviewPrintQhullPrecisionTrace


[delaunay] Qhull Delaunay triangulation and Voronoi diagram options

Copyright © 1995, 1997 The Geometry Center, Minneapolis MN


»Delaunay triangulation ('d')

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. The Delaunay triangulation is the projected ridges of the lower convex hull. See the examples, Delaunay and Voronoi diagrams.

As shown by these examples, the Delaunay triangulation is a convex hull in Qhull. 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.

»Delaunay conventions

The following terminology is used for Delaunay triangulations in Qhull. The underlying structure is a convex hull in one higher dimension. See convex hull conventions.

»Delaunay outputs

These options control the output of Delaunay triangulations:

»Delaunay controls

These options provide additional control:

»Delaunay graphics

For 2-d and 3-d Delaunay triangulations, Geomview ('qhull d G') displays the corresponding convex hull (a paraboloid).

To get 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 get 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 ('m') displays the corresponding convex hull (a paraboloid).

»Delaunay notes

A non-simplicial facet indicates nearly cocircular or cospherical input sites. Unfortunately, many uses of Delaunay triangulations assume simplicial (e.g., triangular) facets. You can use option 'Ft' to print a triangulation. It adds points for non-simplicial facets. You can use an exact arithmetic code, or use Qhull with options 'Q0 Po' to force output despite precision errors. The later is likely to work, but it can not guarantee a correct output.

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]

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.

»Voronoi vertices and regions ('v')

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. In 2-d, it generates the Voronoi diagram. In higher-dimensions, it does not output the ridges that connect neighboring Voronoi regions. With work, the user can derive this information from Qhull's data structures.

»Voronoi 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 and to regions of the Voronoi diagram. See convex hull conventions and Delaunay conventions.

» Voronoi outputs

These options control the output of Voronoi vertices and regions. 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").

» Voronoi controls

These options provide additional control:

» Voronoi 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 Voronoi regions in 3-d. To view the Voronoi region for site 3 in Geomview, execute

qhull <data FQ s GV3 v Fc Pg | qhull s G >output

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.

»Voronoi notes

To produce the unbounded rays in 2-d, enclose the input points in a square.

In 3-d and higher, the adjacency information for the Voronoi diagram can be determined from Qhull's data structures.

Qhull does not compute the unbounded regions of a Voronoi diagram. 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.

»Furthest-site Delaunay triangulation ('d Qu')

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

»furthest-site Delaunay conventions

The following terminology is used for furthest-site Delaunay triangulations in Qhull. The underlying structure is a convex hull in one higher dimension. See convex hull conventions and Delaunay conventions.

»furthest-site Delaunay outputs

These options control the output of furthest-site Delaunay triangulations:

»furthest-site Delaunay controls

These options provide additional control:

»furthest-site Delaunay graphics

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

»furthest-site Delaunay notes

See Delaunay notes.

»Furthest-site Voronoi vertices and regions ('v Qu')

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. In 2-d, it generates the furthest-site Voronoi diagram. In higher-dimensions, it does not output the ridges that connect neighboring furthest-site Voronoi regions. With work, the user can derive this information from Qhull's data structures.

» furthest-site Voronoi conventions

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 and to regions of the furthest-site Voronoi diagram. See convex hull conventions and furthest-site Delaunay conventions.

»furthest-site Voronoi outputs

These options control the output of furthest-site Voronoi vertices and regions. 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.

»furthest-site Voronoi controls

These options provide additional control:

»furthest-site Voronoi graphics

In 2-d, Geomview output ('G') displays a furthest-site Voronoi diagram with extra edges to close the unbounded furthest-site Voronoi regions. Most regions will be unbounded!

You can also view bounded, furthest-site Voronoi regions in 3-d. To view the furthest-site Voronoi region for site 3 in Geomview, execute

qhull <data FQ s GV3 v Qu Fc Pg | qhull s G >output

The first qhull command returns the furthest-site Voronoi vertices for all facets incident to point 3 in the furthest-site Delaunay triangulation. The second qhull command computes their convex hull. This is the furthest-site Voronoi region for input site 3. It will not work if the region is 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.

»furthest-site Voronoi notes

See Voronoi notes.


Up: Home page for Qhull
Up: Qhull manual
Up: Qhull options

To: SynopsisMainOutputFormatsGeomviewPrintQhullPrecisionTrace


The Geometry Center Home Page

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