Note: This page has been translated by MathWorks. Please click here

To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

N-D Voronoi diagram

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

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

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

`voronoin`

uses Qhull.

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

specifies a
cell array of Qhull options. The default options are:

`{'Qbb'}`

for 2- and 3-dimensional input`{'Qbb','Qx'}`

for 4 and higher-dimensional input

If `options`

is `[]`

, the
default options are used. If `code`

is `{''}`

,
no options are used, not even the default. For more information on
Qhull and its options, see `http://www.qhull.org`

.

You can plot individual bounded cells of an n-dimensional 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.

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,:)`

.

The following example illustrates the `options`

input
to `voronoin`

. The commands

X = [-1 -1; 1 -1; 1 1; -1 1]; [V,C] = voronoin(X)

return an error message.

? qhull input error: can not scale last coordinate. Input is cocircular or cospherical. Use option 'Qz' to add a point at infinity.

The error message indicates that you should add the option `'Qz'`

.
The following command passes the option `'Qz'`

, along
with the default `'Qbb'`

, to `voronoin`

.

[V,C] = voronoin(X,{'Qbb','Qz'}) V = Inf Inf 0 0 C = [1x2 double] [1x2 double] [1x2 double] [1x2 double]

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

Was this topic helpful?