30.1.2 三角剖分中的点识别¶

通常需要确定 N 维空间中的某个特定点是否位于该 N 维空间中一组点的 Delaunay 镶嵌内，如果是的话，则找出包含该点的 N-单纯形，以及镶嵌中哪个点最接近该目标点。函数 tsearch 在三角剖分中执行此功能，而函数 tsearchn 和 dsearchn 在 N 维镶嵌中执行此功能。

要判断用向量 p 表示的特定点是否落在 N-单纯形的某个单纯形内，我们可以将该点的笛卡尔坐标表示为关于该 N-单纯形的参数形式。这种参数形式称为该点的重心坐标（Barycentric Coordinates）。如果定义 N-单纯形的点由 N + 1 个向量 t(i,:) 给出，则定义点 p 的重心坐标由下式给出：

p = beta * t

其中 beta 包含 N + 1 个值，这些值作为一个向量共同表示点 p 的重心坐标。为确保 beta 的值有唯一解，需要施加一个额外的条件：

sum (beta) == 1

因此我们可以将上述等式写成：

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

求解 beta，我们可以写成：

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

这样就得到了将点 p 的笛卡尔坐标转换为重心坐标 beta 的公式。重心坐标的一个重要性质是，对于 N-单纯形内的所有点，满足：

0 <= beta(i) <= 1

因此，tsearch 和 tsearchn 中的测试本质上只需要用 N-单纯形的每个单纯形的重心坐标来表示每个点，并检验 beta 的值。这正是 tsearchn 中采用的实现方式。tsearch 是针对二维情况优化过的，不会显式构造重心坐标。

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

搜索包含目标点的 Delaunay 凸包。

对于 t = delaunay (x, y)，在 t 中查找包含点 (xi, yi) 的索引。对于凸包外部的点，idx 为 NaN。

编程说明：该算法的复杂度为 O(M*N)，用于在 N 个三角形中定位 M 个点。如果待定位的点位于一条连续的路径上，性能通常会快得多；算法会先检查一个点是否位于其前一个点所在的区域内，从而加速连续路径上的点查找。

另请参阅： delaunay, delaunayn.

idx = tsearchn (x, t, xi) ¶

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

查找包含给定点的单纯形。

tsearchn 通常与 delaunayn 一起使用：t = delaunayn (x) 返回一组单纯形 t，然后 tsearchn 返回 t 中包含每个 xi 点的行索引。对于凸包外部的点，idx 为 NaN。

如果指定了输出参数，tsearchn 还会返回所包围单纯形的重心坐标 p。

另请参阅： tsearch, dsearchn, delaunayn.

tsearch 的一个使用示例可以通过一个简单的三角剖分来展示：

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

该剖分由 tri 定义的两个三角形组成。然后我们可以确定一个点落在哪个三角形中：

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

我们也可以确认一个点不在任何一个三角形内：

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

函数 dsearchn 用于查找镶嵌中距离目标点最近的点。目标点不一定需要在镶嵌内部，并且即使该点在镶嵌内，返回的最近点也不一定是该点所在的 N-单纯形的顶点之一。

idx = dsearchn (x, tri, xi) ¶

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

idx = dsearchn (x, xi) ¶

[idx, d] = dsearchn (…) ¶

返回 x 中距离 xi 各元素最近的点的索引 idx。

如果提供了 outval，则对于 xi 中不包含在单纯形 tri 内的点，其索引值将被设置为 outval。通常 tri 由 delaunayn (x) 返回。

可选的输出 d 包含一个列向量，表示查询点 xi 与最近的单纯形点 x 之间的距离。

兼容性说明：dsearchn 算法仅在指定了 outval 时，才会使用输入的 tri 来判断是否有任何点位于三角剖分区域之外。为了兼容性，即使未指定 outval，tri 也可以作为输入参数传入，但它不会被使用或检查其是否为有效的三角剖分，传入它不会影响输出 idx 或计算效率。

另请参阅： tsearchn, delaunayn.

dsearchn 的一个使用示例如下，使用上述的 x、y 和 tri 值：

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

如果希望将镶嵌外部的点标记出来，可以如下使用 dsearchn：

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

其中在镶嵌外部的点的索引被标记为 NaN。