Matlab高维空间搜索方法详解

点位置搜索

点位置搜索是一种通过封闭查询点来确定单纯形(三角形、四面体等)的三角剖分搜索算法。在最近邻点搜索的情况下，根据问题的维度，在 MATLAB 中执行点位置搜索有多种方法：

对于 4 维和更高维，使用 delaunayn 函数构建三角剖分，并使用补充的 tsearchn 函数执行点位置搜索。虽然这些 N 维函数支持二维和三维，但它们并没有三角剖分提供的搜索方法通用和高效。

此示例说明如何使用 delaunayTriangulation 类来执行二维点位置搜索。

首先从一个二维点集开始。

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 标签。

dt = delaunayTriangulation(X);

triplot(dt);

hold on

ic = incenter(dt);

numtri = size(dt,1);

trilabels = arrayfun(@(x) {sprintf('T%d', x)}, (1:numtri)');

Htl = text(ic(:,1), ic(:,2), trilabels, 'FontWeight', ...

'bold', 'HorizontalAlignment', 'center', 'Color', ...

'blue');

hold off

现在创建一些查询点，并将其添加到绘图中。然后使用 pointLocation 方法查找对应的包围三角形的索引。

q = [5.9344 6.2363;

2.2143 2.1910;

7.0948 3.6615;

7.6040 2.2770;

6.0724 2.5828;

6.5464 6.9407;

6.4588 6.1690;

4.3534 3.9026;

5.9329 7.7013;

3.0271 2.2067];

hold on;

plot(q(:,1),q(:,2),'*r');

vxlabels = arrayfun(@(n) {sprintf('q%d', n)}, (1:10)');

Hpl = text(q(:,1)+0.2, q(:,2)+0.2, vxlabels, 'FontWeight', ...

'bold', 'HorizontalAlignment','center', ...

'BackgroundColor', 'none');

hold off

ti = pointLocation(dt,q);

执行三维点位置搜索是对使用 delaunayTriangulation 执行二维点位置搜索的直接扩展。

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

创建四维随机样本点，然后使用 delaunayn 进行三角剖分：

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

tri = delaunayn(X);使用 tsearchn 函数创建一些查询点，求出对应封闭单纯形的索引：

q = rand(5,4);

ti = tsearchn(X,tri,q)pointLocation 方法和 tsearchn 函数允许以可选参数的形式返回对应的重心坐标。在四维示例中，可按如下方式计算重心坐标：

[ti,bc] = tsearchn(X,tri,q)重心坐标对执行线性插值很有用。这些坐标提供了可用于在封闭单纯形的每个顶点缩放数值的权值。有关详细信息，请参阅 内插散点数据。

免责声明：本文系网络转载或改编，未找到原创作者，版权归原作者所有。如涉及版权，请联系删