30.1.2 Identifying Points in Triangulation ¶

It is often necessary to identify whether a particular point in the N-dimensional space is within the Delaunay tessellation of a set of points in this N-dimensional space, and if so which N-simplex contains the point and which point in the tessellation is closest to the desired point. The function tsearch performs this function in a triangulation, and the functions tsearchn and dsearchn in an N-dimensional tessellation.

To identify whether a particular point represented by a vector p falls within one of the simplices of an N-simplex, we can write the Cartesian coordinates of the point in a parametric form with respect to the N-simplex. This parametric form is called the Barycentric Coordinates of the point. If the points defining the N-simplex are given by N + 1 vectors t(i,:), then the Barycentric coordinates defining the point p are given by

p = beta * t

where beta contains N + 1 values that together as a vector represent the Barycentric coordinates of the point p. To ensure a unique solution for the values of beta an additional criteria of

sum (beta) == 1

is imposed, and we can therefore write the above as

p - t(end, :) = beta(1:end-1) * (t(1:end-1, :)
                - ones (N, 1) * t(end, :)

Solving for beta we can then write

beta(1:end-1) = (p - t(end, :)) /
                (t(1:end-1, :) - ones (N, 1) * t(end, :))
beta(end) = sum (beta(1:end-1))

which gives the formula for the conversion of the Cartesian coordinates of the point p to the Barycentric coordinates beta. An important property of the Barycentric coordinates is that for all points in the N-simplex

0 <= beta(i) <= 1

Therefore, the test in tsearch and tsearchn essentially only needs to express each point in terms of the Barycentric coordinates of each of the simplices of the N-simplex and test the values of beta. This is exactly the implementation used in tsearchn. tsearch is optimized for 2-dimensions and the Barycentric coordinates are not explicitly formed.

: idx = tsearch (x, y, t, xi, yi) ¶

Search for the enclosing Delaunay convex hull.

For t = delaunay (x, y), finds the index in t containing the points (xi, yi). For points outside the convex hull, idx is NaN.

Programming Note: The algorithm is O(M*N) for locating M points in N triangles. Performance is typically much faster if the points to be located are in a single continuous path; a point is first checked against the region its predecessor was found in, speeding up lookups for points along a continuous path.

See also: delaunay, delaunayn.

: idx = tsearchn (x, t, xi) ¶

: [idx, p] = tsearchn (x, t, xi) ¶

Find the simplexes enclosing the given points.

tsearchn is typically used with delaunayn: t = delaunayn (x) returns a set of simplexes t, then tsearchn returns the row index of t containing each point of xi. For points outside the convex hull, idx is NaN.

If requested, tsearchn also returns the barycentric coordinates p of the enclosing simplexes.

See also: tsearch, dsearchn, delaunayn.

An example of the use of tsearch can be seen with the simple triangulation

x = [-1; -1; 1; 1];
y = [-1; 1; -1; 1];
tri = [1, 2, 3; 2, 3, 4];

consisting of two triangles defined by tri. We can then identify which triangle a point falls in like

tsearch (x, y, tri, -0.5, -0.5)
⇒ 1
tsearch (x, y, tri, 0.5, 0.5)
⇒ 2

and we can confirm that a point doesn’t lie within one of the triangles like

tsearch (x, y, tri, 2, 2)
⇒ NaN

The dsearchn function finds the closest point in a tessellation to the desired point. The desired point does not necessarily have to be in the tessellation, and even if it the returned point of the tessellation does not have to be one of the vertices of the N-simplex within which the desired point is found.

: idx = dsearchn (x, tri, xi) ¶

: idx = dsearchn (x, tri, xi, outval) ¶

: idx = dsearchn (x, xi) ¶

: [idx, d] = dsearchn (…) ¶

Return the index idx of the closest point in x to the elements xi.

If outval is supplied, then the values of xi that are not contained within one of the simplices tri are set to outval. Generally, tri is returned from delaunayn (x).

The optional output d contains a column vector of distances between the query points xi and the nearest simplex points x.

Compatibility note: The dsearchn algorithm only uses the input tri when outdim is specified to determine if any points lie outside of the triangulation region. For compatibility, tri is accepted as an input even when outdim is not specified, but it is not used or checked to be a valid triangulation, and providing it will not affect either the output idx or the calculation efficiency.

See also: tsearchn, delaunayn.

An example of the use of dsearchn, using the above values of x, y and tri is

dsearchn ([x, y], tri, [-2, -2])
⇒ 1

If you wish the points that are outside the tessellation to be flagged, then dsearchn can be used as

dsearchn ([x, y], tri, [-2, -2], NaN)
⇒ NaN
dsearchn ([x, y], tri, [-0.5, -0.5], NaN)
⇒ 1

where the point outside the tessellation are then flagged with NaN.