# Documentation

### This is machine translation

Translated by
Mouse over text to see original. Click the button below to return to the English verison of the page.

# voronoin

N-D Voronoi diagram

## Syntax

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

## Description

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

## Visualization

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.

## Examples

### Example 1

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

### Example 2

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]```

collapse all

### Algorithms

`voronoin` is based on Qhull [1]. For information about Qhull, 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.