voronoin

Compute Voronoi diagram in N-D space

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.

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

Examples

2-D Voronoi Diagram

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

P — Points

matrix

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.

opts — Qhull options

cell array of character vectors

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

v — Voronoi vertices

matrix

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.

c — Indices

cell array

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

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. For example, see 3-D Voronoi Diagram.

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

C/C++ Code Generation

Generate C and C++ code using MATLAB® Coder™.

Usage notes and limitations:

For C/C++ code generation:

• The function voronoin is not supported in parallel for-loops (parfor-loops).

GPU Code Generation

Generate CUDA® code for NVIDIA® GPUs using GPU Coder™.

Refer to the usage notes and limitations in the C/C++ Code Generation section. The same usage notes and limitations apply to GPU code generation.

Thread-Based Environment

Run code in the background using MATLAB® backgroundPool or accelerate code with Parallel Computing Toolbox™ ThreadPool.

The voronoin function fully supports thread-based environments. For more information, see Run MATLAB Functions in Thread-Based Environment.

Version History

Introduced before R2006a