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].
- Example: rbox r y c G0.1 D2 | qdelaunay s Fv TO result
- Compute the 2-d Delaunay triangulation of a triangle and a small square. Write a summary to the console and unoriented regions to 'result'. Merge regions for cocircular input sites (i.e., the square).
- Example: rbox r y c G0.1 D2 | qdelaunay s Fv Qt
- Compute the 2-d Delaunay triangulation of a triangle and a small square. Write a summary and unoriented regions to the console. Produce triangulated output.
- Example: rbox 10 D2 | qdelaunay QJ s i TO result
- Compute the 2-d Delaunay triangulation of 10 random points. Joggle the input to guarantee triangular output. Write a summary to the console and the regions to 'result'.
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 region 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.
If you use 'Qt' (triangulated output), all Delaunay regions will be simplicial (e.g., triangles in 2-d). Some regions may be degenerate and have zero area. Qhull can identify coincident points. If you do not use 'Qt', cocircular and cospherical data will lead to non-simplicial output (e.g., a square).
If you use 'QJ' (joggle), all Delaunay regions will be simplicial (e.g., triangles in 2-d). Duplicate points will create small regions since the points are joggled apart. See Joggled input or merged facets.
The output for 3-d Delaunay triangulations may be confusing if the input contains cospherical data. See the FAQ item Why are there extra points in a 4-d or higher convex hull? Avoid these problems with triangulated output ('Qt') or joggled input ('QJ').
The 'qdelaunay' program is equivalent to 'qhull d Qbb' in 2-d to 3-d, and 'qhull d Qbb Qx' in 4-d and higher. It disables the following Qhull options: d n v H U Qb QB Qc Qf Qg Qi Qm Qr QR Qv Qx TR E V FC Fi Fo Fp Ft FV Q0,etc.
Copyright © 1995-2002 The Geometry Center, Minneapolis MN
qdelaunay- compute the Delaunay triangulation. input (stdin): dimension, number of points, point coordinates comments start with a non-numeric character options (qdelaun.htm): Qt - triangulated output QJ - joggle input instead of merging facets Qu - furthest-site Delaunay triangulation 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) i - vertices incident to each Delaunay region Fx - extreme points (vertices of the convex hull) o - OFF format (shows the points lifted to a paraboloid) G - Geomview output (2-d and 3-d points lifted to a paraboloid) m - Mathematica output (2-d inputs lifted to a paraboloid) QVn - print Delaunay regions that include point n, -n if not TO file- output results to file, may be enclosed in single quotes examples: rbox c P0 D2 | qdelaunay s o rbox c P0 D2 | qdelaunay i rbox c P0 D3 | qdelaunay Fv Qt rbox c P0 D2 | qdelaunay s Qu Fv rbox c G1 d D2 | qdelaunay s i rbox c G1 d D2 | qdelaunay s i Qt rbox M3,4 z 100 D2 | qdelaunay s rbox M3,4 z 100 D2 | qdelaunay s Qt
The input data on stdin consists of:
- number of points
- point coordinates
Use I/O redirection (e.g., qdelaunay < data.txt), a pipe (e.g., rbox 10 | qdelaunay), or the 'TI' option (e.g., qdelaunay TI data.txt).
For example, this is four cocircular points inside a square. Its Delaunay triangulation contains 8 triangles and one four-sided figure.
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 1
qdelaunay s i < dataDelaunay triangulation by the convex hull of 8 points in 3-d Number of input sites: 8 Number of Delaunay regions: 9 Number of non-simplicial Delaunay regions: 1 Statistics for: RBOX s 4 W0 c D2 | QDELAUNAY s i 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.028 9 1 7 5 6 3 4 2 3 6 7 2 6 2 7 1 0 5 4 3 0 4 0 1 5 1 0 3 2
These options control the output of Delaunay triangulations:
- Delaunay regions
- list input sites for each Delaunay region. The first line is the number of regions. The remaining lines list the input sites for each region. The regions are oriented. In 3-d and higher, report cospherical sites by adding extra points. Use triangulated output ('Qt') to avoid non-simpicial regions. For the circle-in-square example, eight Delaunay regions are triangular and the ninth has four input sites.
- list input sites for each Delaunay region. The first line is the number of regions. Each remaining line starts with the number of input sites. The regions are unoriented. For the circle-in-square example, eight Delaunay regions are triangular and the ninth has four input sites.
- list neighboring regions for each Delaunay region. The first line is the number of regions. Each remaining line starts with the number of neighboring regions. Negative indices (e.g., -1) indicate regions outside of the Delaunay triangulation. For the circle-in-square example, the four regions on the square are neighbors to the region-at-infinity.
- list the Delaunay regions for each input site. The first line is the total number of input sites. Each remaining line starts with the number of Delaunay regions. Negative indices (e.g., -1) indicate regions outside of the Delaunay triangulation. For the circle-in-square example, each point on the circle belongs to four Delaunay regions. Use 'Qc FN' to include coincident input sites and deleted vertices.
- print area for each Delaunay region. The first line is the number of regions. The areas follow, one line per region. For the circle-in-square example, the cocircular region has area 0.4.
- Input sites
- list coincident input sites for each Delaunay region. The first line is the number of regions. 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 Delaunay region. Do not use 'QJ' with 'Fc'; the joggle will separate coincident sites.
- 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 region, and distance. Includes deleted vertices which indicate highly degenerate input (see'Fs'). Do not use 'QJ' with 'FP'; the joggle will separate coincident sites.
- list extreme points of the input sites. These points are on the boundary of the convex hull. The first line is the number of extreme points. Each point is listed, one per line. The circle-in-square example has four extreme points.
- compute total area for 's' and 'FS'
- print lower facets of the corresponding convex hull (a paraboloid)
- Mathematica output for the lower facets of the paraboloid (2-d triangulations).
- Geomview output for the paraboloid (2-d or 3-d triangulations).
- print summary for the Delaunay triangulation. Use 'Fs' and 'FS' for numeric data.
These options provide additional control:
- triangulated output. Qhull triangulates non-simplicial facets. It may produce degenerate facets of zero area.
- joggle the input to avoid cospherical and coincident sites.
- compute the furthest-site Delaunay triangulation.
- add a point above the paraboloid to reduce precision errors. Use it for nearly cocircular/cospherical input (e.g., 'rbox c | qdelaunay Qz'). The point is printed for options 'Ft' and 'o'.
- select facets adjacent to input site n (marked 'good').
- 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'
- report progress after constructing n facets
- include upper and lower facets in the output. Set k to the last dimension (e.g., 'PD2:1' for 2-d inputs).
- facet dump. Print the data structure for each facet (i.e., Delaunay region).
For 2-d and 3-d Delaunay triangulations, Geomview ('qdelaunay G') displays the corresponding convex hull (a paraboloid).
To view a 2-d Delaunay triangulation, use 'qdelaunay 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 'qdelaunay 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 lower facets of the corresponding convex hull (a paraboloid).
For 2-d, furthest-site Delaunay triangulations, Mathematica output ('Qu m') displays the upper facets of the corresponding convex hull (a paraboloid).
You can simplify the Delaunay triangulation by enclosing the input sites in a large square or cube. This is particularly recommended for cocircular or cospherical input data.
A non-simplicial Delaunay region indicates nearly cocircular or cospherical input sites. To avoid non-simplicial regions either triangulate the output ('Qt')or joggle the input ('QJ'). Alternatively, use an exact arithmetic code.
Delaunay triangulations 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).
See Imprecision issues :: Delaunay triangulations for a discussion of precision issues. Deleted vertices indicate highly degenerate input. They are listed in the summary output and option 'Fs'.
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:qdelaunay <data s FQ QV0 p | qconvex s Qb3:0B3:0 p
The first call to qdelaunay returns the neighboring points of point 0 in the Delaunay triangulation. The second call to qconvex 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 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.
- 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 coincident input site or a deleted vertex. Deleted vertices indicate highly degenerate input.
- 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'
- lower facet - a facet corresponding to a Delaunay region. The last coefficient of its normal is clearly negative.
- upper facet - a facet corresponding to a furthest-site Delaunay region. The last coefficient of its normal is clearly positive.
- Delaunay region - a lower facet projected to the input sites
- upper Delaunay region - an upper facet projected to the input sites
- non-simplicial facet - more than d input sites are cocircular or cospherical
- good facet - a Delaunay region with optional restrictions by 'QVn', etc.
qdelaunay- compute the Delaunay triangulation 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: Qt - triangulated output QJ - joggle input instead of merging facets Qu - compute furthest-site Delaunay triangulation 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 Delaunay triangulation QGn - print Delaunay region if visible from point n, -n if not QVn - print Delaunay regions that include 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 - print 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 outside point (before roundoff) Output formats (may be combined; if none, produces a summary to stdout): f - facet dump G - Geomview output (see below) i - vertices incident to each Delaunay region m - Mathematica output (2-d only, lifted to a paraboloid) o - OFF format (dim, points, and facets as a paraboloid) p - point coordinates (lifted to a paraboloid) s - summary (stderr) More formats: Fa - area for each Delaunay region FA - compute total area for option 's' Fc - count plus coincident points for each Delaunay region Fd - use cdd format for input (homogeneous with offset first) FD - use cdd format for numeric output (offset first) FF - facet dump without ridges FI - ID of each Delaunay region Fm - merge count for each Delaunay region (511 max) Fn - count plus neighboring region for each Delaunay region FN - count plus neighboring region for each point FO - options and precision constants FP - nearest point and distance for each coincident point FQ - command used for qdelaunay Fs - summary: #int (8), dimension, #points, tot vertices, tot facets, for output: #vertices, #Delaunay regions, #coincident points, #non-simplicial regions #real (2), max outer plane, min vertex FS - sizes: #int (0) #real(2) tot area, 0 Fv - count plus vertices for each Delaunay region Fx - extreme points of Delaunay triangulation (on convex hull) Geomview options (2-d and 3-d) 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 Gt - transparent outer ridges to view 3-d Delaunay Print options: PAn - keep n largest Delaunay regions by area Pdk:n - drop facet if normal[k] <= n (default 0.0) PDk:n - drop facet if normal[k] >= n Pg - print good Delaunay regions (needs 'QGn' or 'QVn') PFn - keep Delaunay regions whose area is at least n PG - print neighbors of good regions (needs 'QGn' or 'QVn') PMn - keep n Delaunay regions 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: email@example.com
Created: Sept. 25, 1995 --- Last modified: see top