Sysquake Pro – Table of Contents

Sysquake for LaTeX – Table of Contents

# Triangulation Functions

### delaunay

2-d Delaunay triangulation.

#### Syntax

t = delaunay(x, y) (t, e) = delaunay(x, y)

#### Description

`delaunay(x,y)` calculates the Delaunay triangulation of
2-d points given by arrays `x` and `y`. Both arrays
must have the same number of values, `m`. The result is an array
of three columns. Each row corresponds to a triangle;
values are indices in `x` and `y`.

The second output argument, if requested, is a logical vector of
size `m`-by-1; elements are true if the corresponding point in
`x` and `y` belongs to the convex hull of the set of
points.

The Delaunay triangulation is a net of triangles which link all the starting points in such a way that no point is included in the circumscribed circle of any other triangle. Triangles are "as equilateral" as possible.

#### Example

Delaunay triangulation of 20 random points:

x = rand(20, 1); y = rand(20, 1); (t, e) = delaunay(x, y);

With Sysquake graphical functions, points belonging to the convex hull are displayed as crosses and interior points as circles:

clf; scale equal; plot(x(e), y(e), 'x'); plot(x(~e), y(~e), 'o');

Array of vertex indices is modified to have closed triangles:

t = [t, t(:, 1)];

Triangles are displayed:

plot(x(t), y(t));

#### See also

### delaunayn

N-d Delaunay triangulation.

#### Syntax

t = delaunayn(x) (t, e) = delaunayn(x)

#### Description

`delaunayn(x)` calculates the Delaunay triangulation of
points given by the rows of array `x` in a space of dimension
`size(x,2)`. The result is an array with one more column.
Each row corresponds to a simplex;
values are row indices in `x` and give the vertices of each polyhedron.

The second output argument, if requested, is a logical vector with as
many elements as rows in `x`; elements are true if the corresponding
point in `x` belongs to the convex hull of the set of
points.

#### See also

### griddata

Data interpolation in 2-d plane.

#### Syntax

vi = griddata(x, y, v, xi, yi) vi = griddata(x, y, v, xi, yi, method)

#### Description

`griddata(x,y,v,xi,yi)` interpolates values at coordinates given by
the corresponding elements of arrays `xi` and `yi` in
a 2-dimension plane. Original data are defined by corresponding elements of
arrays `x`, `y`, and `v` (which must have the same
size), such that the value at coordinate `[x(i);y(i)]` is `v(i)`. The result is
an array with the same size as `xi` and `yi` where `vi(j)` is
the value interpolated at `[xi(j);yi(j)]`.

All coordinates are real (imaginary components are ignored). Values `v` and `vi`
can be real or complex. The result for coordinates outside the convex hull defined by `x`
and `y` is NaN.

`griddata` is based on Delaunay triangulation. The interpolation
method used in each triangle is linear by default, or can be specified with an
additional input argument, a string:

Argument | Meaning |
---|---|

'0' or 'nearest' | nearest value |

'1' or 'linear' | linear |

#### Example

Nearest value interpolation in 2D plane of a few values `v(x,y)`. The plane
is sampled with a regular grid with `meshgrid`.

x = [0.2; 1.8; 0.7; 0.9; 1.6]; y = [0.2; 0.7; 1.8; 1.1; 1.7]; v = [0.1; 0.3; 0.9; 0.5; 0.4]; (xi, yi) = meshgrid(0:0.01:2); vi = griddata(x, y, v, xi, yi, '0');

In Sysquake, the result can be displayed as a contour plot. For locations where
the values cannot be interpolated, i.e. outside the convex hull defined by `x`
and `y`, values are set to 0.

vi(isnan(vi)) = 0; contour(vi, [], 20);

#### See also

`delaunay`,
`tsearch`,
`griddatan`,
`interpn`

### griddatan

Data interpolation in N-d space.

#### Syntax

vi = griddatan(x, v, xi) vi = griddatan(x, v, xi, method)

#### Description

`griddatan(x,v,xi)` interpolates values at coordinates given by
the `p` rows of `p`-by-`n` array `xi` in
an `n`-dimension space. Original data are defined by `m`-by-`n`
array `x` and `m`-by-1 column vector `v`, such that
the value at coordinate `x(i,:)'` is `v(i)`. The result is
a `p`-by-1 column vector `vi` where `vi(j)` is
the value interpolated at `xi(j,:)'`.

Coordinates `x` and `xi` are real (imaginary components are
ignored). Values `v` and `vi` can be real or complex. The result
for coordinates outside the convex hull defined by `x` is NaN.

`griddatan` is based on Delaunay triangulation. The interpolation
method used in each simplex is linear by default, or can be specified with an
additional input argument, a string:

Argument | Meaning |
---|---|

'0' or 'nearest' | nearest value |

'1' or 'linear' | linear |

#### Example

Linear interpolation in 2D plane of a few values `v(x,y)`. The plane
is sampled with a regular grid with `meshgrid`. Since `griddatan`
interpolates a 1-dim array of points, the result is reshaped to match `x`
and `y` (compare with the example of `griddata`).

x = [0.2; 1.8; 0.7; 0.9; 1.6]; y = [0.2; 0.7; 1.8; 1.1; 1.7]; v = [0.1; 0.3; 0.9; 0.5; 0.4]; (xi, yi) = meshgrid(0:0.01:2); vi = griddatan([x,y], v, [xi(:),yi(:)], '1'); vi = reshape(vi, size(xi));

In Sysquake, the result can be displayed as a contour plot. For locations where
the values cannot be interpolated, i.e. outside the convex hull defined by `x`
and `y`, values are set to 0.

vi(isnan(vi)) = 0; contour(vi, [], 20);

#### See also

`delaunayn`,
`tsearchn`,
`griddata`,
`interpn`

### tsearch

Search of points in triangles.

#### Syntax

ix = tsearch(x, y, t, xi, yi)

#### Description

`tsearch(x,y,t,xi,yi)` searches in which triangle is located each point given by
the corresponding elements of arrays `xi` and `yi`. Corresponding elements
of arrays `x` and `y` represent the
vertices of the triangles, and rows of array `t` represent their indices in
`x` and `y`; array `t` is usually the result of `delaunay`.
Dimensions of `x` and `y`, and of `xi` and `yi`, must be
equal.
The result is an array with the same size as `xi` and `yi` where each element
is the row index in `t` of the first triangle which contains the point, or
NaN if the point is outside all triangles (i.e. outside the convex hull of points defined by
`x` and `y` if `t` is a proper triangulation such as the one computed with
`delaunay`).

#### Example

Search for triangles containing points [0,0] and [0,1] corresponding to Delaunay triangulation of 20 random points:

x = randn(20, 1); y = randn(20, 1); t = delaunay(x, y); xi = [0, 0]; yi = [0, 1]; ix = tsearch(x, y, t, xi, yi);

#### See also

`tsearchn`,
`delaunay`,
`voronoi`,
`griddata`

### tsearchn

Search of points in triangulation simplices.

#### Syntax

ix = tsearchn(x, t, xi)

#### Description

`tsearchn(x,t,xi)` searches in which simplex each point given by
the rows of array `xi` is located. Rows of array `x` represent the
vertices of the simplices, and rows of array `t` represent their indices in
`x`; array `t` is usually the result of `delaunayn`.
Dimensions must match: in a space of `n` dimensions, `x` and
`xi` have `n` columns, and `t` has `n+1` columns.
The result is a column vector with one element for each row of `xi`, which
is the row index in `t` of the first simplex which contains the point, or
NaN if the point is outside all simplices (i.e. outside the convex hull of points `x`
if `t` is a proper triangulation of `x` such as the one computed with
`delaunayn`).

#### Example

Search for simplices containing points [0,0] and [0,1] corresponding to Delaunay triangulation of 20 random points:

x = randn(20, 2); t = delaunayn(x); xi = [0, 0; 0, 1]; ix = tsearchn(x, t, xi);

#### See also

`tsearch`,
`delaunayn`,
`voronoin`,
`griddatan`

### voronoi

2-d Voronoi tessalation.

#### Syntax

(v, p) = voronoi(x, y)

#### Description

`voronoi(x,y)` calculates the Voronoi tessalation of
the set of 2-d points given by arrays `x` and `y`.
Both arrays must have the same number of values, `m`.
The first output argument `v` is an array of two columns which
contains the coordinates of the vertices of the Voronoi cells, one row per
vertex. The first row contains infinity and is used as a marker for
unbounded Voronoi cells. The second output argument `p` is a
list of vectors of row indices in `v`; each element describes the
Voronoi cell corresponding to a point in `x`. In each cell,
vertices are sorted counterclockwise.

Voronoi tessalation is a tessalation (a partition of the plane) such that each region is the set of points closer to one of the initial point than to any other one. Two regions are in contact if and only if their initial points are linked in the corresponding Delaunay triangulation.

#### Example

Voronoi tessalation of 20 random points:

x = rand(20, 1); y = rand(20, 1); (v, p) = voronoi(x, y);

These points are displayed as crosses with Sysquake graphical functions. The scale is fixed, because Voronoi polygons can have vertices which are far away from the points.

clf; scale('equal', [0,1,0,1]); plot(x, y, 'x');

Voronoi polygons are displayed in a loop, skipping unbounded polygons.
The first vertex is repeated to have closed polygons. Since `plot`
expects row vectors, vertex coordinates are transposed.

for p1 = p if ~any(p1 == 1) p1 = [p1, p1(1)]; plot(v(p1,1)', v(p1,2)'); end end

#### See also

### voronoin

N-d Voronoi tessalation.

#### Syntax

(v, p) = voronoin(x)

#### Description

`voronoin(x)` calculates the Voronoi tessalation of
the set of points given by the rows of arrays `x` in a space
of dimension `n=size(x,2)`.
The first output argument `v` is an array of `n` columns
which contains the coordinates of the vertices of the Voronoi cells, one row per
vertex. The first row contains infinity and is used as a marker for
unbounded Voronoi cells. The second output argument `p` is a
list of vectors of row indices in `v`; each element describes the
Voronoi cell corresponding to a point in `x`. In each cell,
vertices are sorted by index.