voronoin (MATLAB Functions)

n-D Voronoi diagram

Syntax

```
[V,C] = voronoin(X)
```

Description

[V,C] = voronoin(X) returns Voronoi vertices V and the Voronoi cells C of the Voronoi diagram of X. V is a numv-by-n array of the numv Voronoi vertices in n-D space, each row corresponds to a Voronoi vertex. C is a vector cell array where each element contains the indices into V of the vertices of the corresponding Voronoi cell. X is an m-by-n array, representing m n-D points, where n > 1 and m >= n+1.

The first row of V is a point at infinity. If any index in a cell of the cell array is 1, then the corresponding Voronoi cell contains the first point in V, a point at infinity. This means the Voronoi cell is unbounded.

Visualization

You can plot individual bounded cells of an n-D Voronoi diagram. To do this, use convhulln to compute the vertices of the facets that make up the Voronoi cell. Then use patch and other plot functions to generate the figure. For an example, see Tessellation and Interpolation of Scattered Data in Higher Dimensions in the MATLAB documentation.

Examples

Let

x = [ 0.5    0
      0      0.5
     -0.5   -0.5
     -0.2   -0.1
     -0.1    0.1
      0.1   -0.1
      0.1    0.1 ]

then

[V,C] = voronoin(x)

V =
       Inf       Inf
       0.3833    0.3833
       0.7000   -1.6500
       0.2875    0.0000
      -0.0000    0.2875
      -0.0000   -0.0000
      -0.0500   -0.5250
      -0.0500   -0.0500
      -1.7500    0.7500
      -1.4500    0.6500
C = 

    [1x4 double]
    [1x5 double]
    [1x4 double]
    [1x4 double]
    [1x4 double]
    [1x5 double]
    [1x4 double]

Use a for loop to see the contents of the cell array C.

for i=1:length(C), disp(C{i}), end

     4    2    1    3
    10    5    2    1    9
     9    1    3    7
    10    8    7    9
    10    5    6    8
     8    6    4    3    7
     6    4    2    5

In particular, the fifth Voronoi cell consists of 4 points: V(10,:), V(5,:), V(6,:), V(8,:).

Algorithm

voronoin is based on Qhull [2]. It uses the Qhull joggle option ('QJ'). For information about qhull, see http://www.geom.umn.edu/software/qhull/. For copyright information, see http://www.geom.umn.edu/software/download/COPYING.html.

See Also

convhull, convhulln, delaunay, delaunayn, voronoi

Reference

[1] Barber, C. B., D.P. Dobkin, and H.T. Huhdanpaa, "The Quickhull Algorithm for Convex Hulls," ACM Transactions on Mathematical Software, Vol. 22, No. 4, Dec. 1996, p. 469-483. Available in HTML format at http://www.acm.org/ pubs/citations/journals/toms/1996-22-4/p469-barber/ and in PostScript format at ftp://geom.umn.edu/pub/software/qhull-96.ps.

[2] National Science and Technology Research Center for Computation and Visualization of Geometric Structures (The Geometry Center), University of Minnesota. 1993.

voronoi wait