Documentation

# 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

collapse all

Compute Voronoi vertices and diagram cells.

Define a 2-D array of points and compute the vertices and diagram cells.

`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]`
```X = 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(X)`
```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 = 7x1 cell array {1x4 double} {1x5 double} {1x4 double} {1x4 double} {1x4 double} {1x5 double} {1x4 double} ```

Use a for loop to display the contents of the cell array `C`.

```for i = 1:length(C) disp(C{i}); end```
``` 9 2 1 8 8 1 6 5 7 6 1 2 4 6 4 3 5 10 3 5 7 10 3 4 2 9 10 7 8 9 ```

Compute the Voronoi vertices and diagram cells of a 2-D set of points by specifying the convex hull parameters. The first row of `C` contains a point at infinity.

```X = [-1 -1; 1 -1; 1 1; -1 1]; [V,C] = voronoin(X,{'Qbb','Qz'})```
```V = 2×2 Inf Inf 0 0 ```
```C = 4x1 cell array {1x2 double} {1x2 double} {1x2 double} {1x2 double} ```

## Algorithms

`voronoin` is based on Qhull . For information about Qhull, see `http://www.qhull.org/`.

## References

 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.

Download ebook