最近邻点搜索

R2026b

根据问题的维度，MATLAB 中有多种方法可计算最近邻点：

对于二维和三维搜索，使用 triangulation 类提供并由 delaunayTriangulation 类继承的 nearestNeighbor 方法。
对于 4 维和更高维，使用 delaunayn 函数构建三角剖分，并使用补充的 dsearchn 函数执行搜索。虽然这些 N 维函数支持二维和三维，但它们并没有三角剖分提供的搜索方法通用和高效。

此示例说明如何使用 delaunayTriangulation 执行二维最近邻搜索。

首先创建一个包含 15 个点的随机点集。

X = [3.5 8.2; 6.8 8.3; 1.3 6.5; 3.5 6.3; 5.8 6.2; 8.3 6.5;...
    1 4; 2.7 4.3; 5 4.5; 7 3.5; 8.7 4.2; 1.5 2.1; 4.1 1.1; ...
    7 1.5; 8.5 2.75];

绘制这些点并添加注解，以显示 ID 标签。

plot(X(:,1),X(:,2),'ob')
hold on
vxlabels = arrayfun(@(n) {sprintf("X%d",n)},(1:15)');
Hpl = text(X(:,1) + 0.2,X(:,2) + 0.2,vxlabels, ...
      FontWeight="bold",HorizontalAlignment="center", ...
      BackgroundColor="none");
hold off

Fifteen points labeled X1 through X15 plotted in a 2-D region

创建这些点的德劳内三角剖分。

dt = delaunayTriangulation(X);

创建一些查询点，并使用 nearestNeighbor 方法针对每个查询点在 X 中查找其对应的最近邻的索引。

numq = 10;
rng(0,"twister");
q = 2 + rand(numq,2)*6;
xi = nearestNeighbor(dt,q);

在绘图中添加查询点，并添加将查询点连接到其最近邻的线段。

xnn = X(xi,:);

hold on
plot(q(:,1),q(:,2),"or");
plot([xnn(:,1) q(:,1)]',[xnn(:,2) q(:,2)]',"-r");

vxlabels = arrayfun(@(n) {sprintf("q%d",n)},(1:numq)');
Hpl = text(q(:,1) + 0.2,q(:,2) + 0.2,vxlabels, ...
      FontWeight="bold",HorizontalAlignment="center", ...
      BackgroundColor="none");

hold off

Points X1–X15 with red query points q1–q10 connected by red lines to their nearest neighbors

执行三维最近邻搜索是对基于 delaunayTriangulation 的二维示例的直接扩展。

对于四维以及更高维而言，使用以下示例中所述的 delaunayn 和 dsearchn 函数：

创建四维随机样本点，并使用 delaunayn 对这些点执行三角剖分：

X = 20*rand(50,4)-10;
tri = delaunayn(X);

创建一些查询点，使用 dsearchn 函数针对每个查询点在 X 间查找与其对应的最近邻点的索引：

q = rand(5,4);
xi = dsearchn(X,tri, q);

nearestNeighbor 方法和 dsearchn 函数允许以可选参量的形式返回查询点与其最近邻点之间的欧几里德距离。在四维示例中，可以计算距离 (dnn)，如下所示：

[xi,dnn] = dsearchn(X,tri,q);