`tsearchn`

Finds the enclosing simplex of query points in an n-D triangulation.

Category: Mathematics > Computational Geometry

Syntax

t = tsearchn(X, T, XI)

Returns the index of the simplex (row of T) that contains each query point.

[t, P] = tsearchn(X, T, XI)

Also returns the barycentric coordinates of each query point in its simplex.

Description

For every query point tsearchn finds the triangle (or tetrahedron, in higher dimension) that contains it. The barycentric coordinates are weights of the simplex vertices that sum to 1 and reproduce the point; they are all non-negative exactly when the point is inside. They are handy for interpolating vertex data to arbitrary points.

Unlike tsearch, it works in any dimension.

Input arguments

X: n-by-d matrix of triangulation vertices.
T: m-by-(d+1) connectivity matrix.
XI: p-by-d matrix of query points.

Output arguments

t: Column vector of simplex indices. NaN marks a point outside the triangulation.
P: p-by-(d+1) barycentric coordinates; rows are NaN for points outside.

Example

Locate points in two triangles

x = [0 1 0 1]';
y = [0 0 1 1]';
T = [1 2 3; 2 4 3];
[t, bc] = tsearchn([x y], T, [0.2 0.2; 0.8 0.8; 2 2])

Output

t = 3×1

     1
     2
   NaN
bc = 3×3

    0.6000    0.2000    0.2000
    0.2000    0.6000    0.2000
       NaN       NaN       NaN

tsearchn