voronoin

N-D Voronoi diagram

collapse all in page

Syntax

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

Description

example

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

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


c=7×1 cell array
    {1x4 double}
    {1x5 double}
    {1x4 double}
    {1x4 double}
    {1x4 double}
    {1x5 double}
    {1x4 double}

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 http://www.qhull.org/html/qh-optq.htm.

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 information, see http://www.qhull.org/.

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.

See Also

| | | | |

Introduced before R2006a

MATLAB Documentation

Support