最近点算法

线性四面体的重心形成点云。算法的关键部分之一是快速选择请求插值的给定新位置最近的 n 个点。该过程在二维中如图 209 所示。

**图 209:** 最近点算法示意
$\begin{figure}\centering YX\|\epsfig{file=near2d.eps,width=12cm} VS\|\end{figure}$

两个全局轴的交点 p 是执行插值的点。黑圆圈表示点云。假设我们想知道最近的 3 个点。云中的点以两个排序数组提供，一个按全局 x 方向排序，一个按全局 y 方向排序。首先，使用 ident.f 程序确定点 p 在这两个数组中的位置。然后，以 p 为中心扩展一个矩形，分别向东、北、西、南方向扩展，直到达到云中的下一个点。这用简单的虚线表示，点分别记为 A、B、C 和 D（A 和 D 重合）。然后计算 p 到这些点的距离，进行排序，并存储在一个数组中。该数组的大小是请求的最近邻居的数量，所以在我们的情况下只保留最小的三个距离。

接下来，矩形在每个方向上继续扩展，直到到达下一个云点，分别记为 E、F、G 和 H。同样，计算 p 到这些点的距离，存储在距离数组中，排序并保留最小的三个值（只需要三个最近的点）。现在，重复此过程，直到 p 到矩形角点之一的最小距离（图中最长矩形用 1、2、3 和 4 表示）超过距离数组中的最大值。然后我们知道已经找到了最近的三个相邻点。

三维中的过程完全等价，我们只是多了两个方向"向后"和"向前"。