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, voronoi

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

delaunay, tsearchn, voronoin

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, delaunay

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.

See also

voronoi, delaunayn