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?