The QHULL procedure constructs convex hulls, Delaunay triangulations, and Voronoi diagrams of a set of points of 2-dimensions or higher. It uses and is based on the program QHULL, which is described in Barber, Dobkin and Huhdanpaa, “The Quickhull Algorithm for Convex Hulls,” *ACM Transactions on Mathematical Software*, Vol. 22, No 4, December 1996, Pages 469-483.

**Note: **QHULL accepts complex input but only utilizes the real part of any complex number.

For more information about QHULL see http://www.qhull.org

## Examples

To run this example, copy the text of the following routine, paste it into an IDL editor window, save the window’s contents as ex_qhull.pro, and select **Run ex_qhull** from the **Run** menu.

`PRO ex_qhull`

` ; Create a collection of random points.`

` n = 20`

` seed = 15`

` x = RANDOMU(seed, n)`

` y = RANDOMU(seed, n)`

` ; Construct the Delaunay triangulation`

` ; and the Voronoi diagram.`

` QHULL, x, y, triangle, /DELAUNAY, $`

VDIAGRAM=vdiagram, VVERTICES=vvert, VNORM=vnorm

` ; Plot our input points.`

PLOT, [-0.1, 1.1], [-0.1, 1.1], /NODATA, $

XSTYLE=4, YSTYLE=4

PLOTS, x, y, PSYM=4

` ; Plot the Voronoi diagram.`

FOR i=0,N_ELEMENTS(vdiagram[2,*])-1 DO BEGIN

vdiag = vdiagram[*, i]

j = vdiag[2] + 1

` ; Bounded or unbounded?`

IF (j gt 0) THEN BEGIN ; Bounded.

PLOTS, vvert[*, vdiag[2:3]], PSYM=-5

` CONTINUE`

` ENDIF`

` ; Unbounded, retrieve starting vertex.`

` xystart = vvert[*, vdiag[3]]`

` ; Determine the line equation.`

` ; Vnorm[0]*x + Vnorm[1]*y + Vnorm[2] = 0`

slope = -vnorm[0,-j]/vnorm[1,-j]

intercept = -vnorm[2,-j]/vnorm[1,-j]

` ; Need to determine the line direction.`

` ; Pick a point on one side along the line.`

xunbound = xystart[0] + 5

yunbound = slope*xunbound + intercept

` ; Find the closest original vertex.`

void = MIN( (x-xunbound)^2 + (y-yunbound)^2, idx)

` ; By definition of Voronoi diagram, the line should`

` ; be closest to one of the bisected points. If not,`

` ; our line went in the wrong direction.`

IF (idx ne vdiag[0] && idx ne vdiag[1]) THEN BEGIN

xunbound = xystart[0] - 5

yunbound = slope*xunbound + intercept

` ENDIF`

` PLOTS, [[xystart], [xunbound, yunbound]]`

` ENDFOR`

`END`

For some other examples using the QHULL procedure, see the QGRID3 function.

## Syntax

QHULL, *V*, *Tr*

or,

QHULL, *V0* , *V1*, [, *V2* ... [, *V*6] ] , *Tr*

**Keywords:** [, BOUNDS=*variable* ] [, CONNECTIVITY=*variable* ] [, /DELAUNAY ] [, SPHERE=*variable* ] [, VDIAGRAM=*variable* ] [, VNORMALS=*variable* ] [, VVERTICES=*variable* ]

## Arguments

### V

An input argument providing an *nd*-by-*np* array containing the locations of *np* points, in *nd* dimensions. The number of dimensions, *nd*, must be greater than or equal to 2.

### V0, V1, V2, ..., V(N–1)

Input vectors of dimension *np*-by-1 elements each containing the *i*-th coordinate of *np* points in *nd* dimensions. A maximum of seven input vectors may be specified.

### Tr

A named variable that will contain an *nd1*-by-*nt* array containing the indices of either the convex hull (*nd1* is equal to *nd*), or the Delaunay triangulation (*nd1* is equal to *nd*+1) of the input points.

## Keywords

### BOUNDS

Set this keyword equal to a named variable that will contain the indices of the vertices of the convex hull.

**Note: **The order of the vertices returned in this variable is unspecified.

### CONNECTIVITY

Set this keyword equal to a named variable that will contain the adjacency list for each of the *np* nodes. The list has the following form:

Each element *i*, 0 ≤*i* < *np*, contains the starting index of the connectivity list (*list*) for node *i* within the list array. To obtain the adjacency list for node *i*, extract the list elements from *list*[*i*] to *list*[*i*+1] – 1. The adjacency list is not ordered. To obtain the connectivity list, either the DELAUNAY or SPHERE keywords must also be specified.

For example, to perform a spherical triangulation, use the following procedure call:

QHULL, lon, lat, CONNECTIVITY = list, SHPERE = sphere

which returns the adjacency list in the variable list. The subscripts of the nodes adjacent to *lon*[*i*] and *lat*[*i*] are contained in the array: *list*[*list*[*i*] :*list*[*i*+1] – 1].

### DELAUNAY

Set this keyword to perform a Delaunay triangulation and returns the vertex indices of the resulting polyhedra; otherwise, the convex hull of the data are returned.

### SPHERE

Set this keyword equal to a named variable that will contain the Delaunay triangulation of the points which lie on the surface of a sphere. The *V0* argument contains the longitude, in degrees, and *V1* contains the latitude, in degrees, of each point.

### VDIAGRAM

Set this keyword equal to a named variable that will contain the connectivity array for the Voronoi diagram.

For two-dimensional arrays, VDIAGRAM is a 4-by-*nv* integer array. For each Voronoi ridge, *i*, VDIAGRAM[0:1, *i*] contains the index of the two input points the ridge bisects. VDIAGRAM [2:3,* i*] contains the indices within VVERTICES of the Voronoi vertices. In the case of an unbounded half-space, VDIAGRAM[2, *i*] is set to a negative index, *j*, indicating that the corresponding Voronoi ridge is unbounded, and that the equation for the ridge is contained in VNORMAL[*, –*j*-1], and starts at Voronoi vertex [3,* i*].

For three-dimensional or higher dimensional arrays, VDIAGRAM is returned as a connectivity vector. This vector has the form [*n*, v0, v1, i0, i1, ..., in-3], where n is the number of points needed to describe that particular Voronoi ridge, v0 and v1 contain the indices for the two input points that the ridge bisects, and i0...in -3 contain the indices within VVERTICES of the Voronoi vertices. In the case of an unbounded half-space, VDIAGRAM[*i*] is set to a negative index,* j*, indicating that the corresponding Voronoi ridge is unbounded, and that the equation for the ridge is contained in VNORMAL[*, –*j*-1].

### VNORMALS

Set this keyword equal to a named variable that will contain the normals of each Voronoi ridge that is unbounded. The normals consist of a (*nd*+1)-by-*nu* array, where *nd *is the number of dimensions and *nu* is the number of unbounded vertices. Each row contains the equation for the unbounded ridge in the form:

V_{0}X_{0}+ V_{1}X_{1}+ V_{2}X_{2}+ ... + V_{nd}X_{nd}+ V_{nd+1}= 0

where V_{*} are the elements of the row within VNORMALS, and X_{*} are the multidimensional coordinates. See the preceding description of VDIAGRAM for details.

### VVERTICES

Set this keyword equal to a named variable that will contain the Voronoi vertices.

## Version History

5.5 |
Introduced |