Main Content

voronoin

N-D Voronoi diagram

collapse all in page

Syntax

[v,c] = voronoin(P)
[v,c] = voronoin(P,opts)

Description

[v,c] = voronoin(P) returns the Voronoi vertices v and the Voronoi cells c of the Voronoi diagram for the N-D points in a matrix P.

example

[v,c] = voronoin(P,opts) also specifies the Qhull options used to compute the Voronoi diagram.

Examples

collapse all

Open Live Script

Create a matrix of 2-D points and compute the Voronoi vertices and diagram cells.

P = [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]
P = 7×2

    0.5000         0
         0    0.5000
   -0.5000   -0.5000
   -0.2000   -0.1000
   -0.1000    0.1000
    0.1000   -0.1000
    0.1000    0.1000


[v,c] = voronoin(P)
v = 10×2

       Inf       Inf
    0.7000   -1.6500
   -0.0500   -0.0500
   -0.0500   -0.5250
   -1.4500    0.6500
   -1.7500    0.7500
         0    0.2875
    0.3833    0.3833
         0         0
    0.2875         0


c=7×1 cell array
    {[  10 2 1 8]}
    {[ 8 1 6 5 7]}
    {[   6 1 2 4]}
    {[   6 4 3 5]}
    {[   9 3 5 7]}
    {[10 2 4 3 9]}
    {[  10 8 7 9]}

Input Arguments

collapse all

Points, specified as a matrix whose columns contain the coordinates for the corresponding dimension. For example, to define a set of 2-D points, place the x-coordinates in the first column of P and the corresponding y-coordinates in the second column.

Qhull options, specified as a cell array of character vectors indicating which Qhull algorithms to use. For a list of options, see Qhull control options.

By default, opts is set to {'Qbb'} for 2- and 3-dimensional input. For 4-dimensional input and higher, opts is set to {'Qbb','Qx'}.

Output Arguments

collapse all

Voronoi vertices, returned as a matrix with the same number of columns as the input. Each row contains the coordinates of an N-D point in the Voronoi diagram, with the first row containing Inf values. A row of Inf values represents an unbounded cell.

Indices, returned as a cell array. Each element of c contains the row indices of the Voronoi vertices v that make up a Voronoi cell.

More About

collapse all

Voronoi Diagram

Given a point in a set of coplanar points, you can draw a boundary around it that includes all points closer to it than to any other point in the set. This boundary defines a single Voronoi polygon. The collection of all Voronoi polygons for every point in the set is called a Voronoi diagram.

Tips

  • You can plot individual bounded cells of an N-D Voronoi diagram. To do this, use the convhulln function to compute the vertices of the facets that make up the Voronoi cell. Then, use patch or other plotting functions to generate the figure.

Algorithms

voronoin is based on Qhull [1]. For more information, see http://www.qhull.org/. For copyright information, see http://www.qhull.org/COPYING.txt.

References

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

Extended Capabilities

Version History

Introduced before R2006a

See Also

| | | | |