## 空间搜索

### 简介

MATLAB® 提供了使用 Delaunay 三角剖分或常规三角剖分执行空间搜索所必需的函数。MATLAB 支持的搜索查询包括：

• 最近邻点搜索（有时称为最近点搜索或邻近搜索）。

• 点位置搜索（有时称为三角形内的点搜索或单纯形内的点搜索，其中单纯形是三角形、四面体或更高维度的等效形状）。

### 最近邻点搜索

```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];```

```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```

`dt = delaunayTriangulation(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```

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

```q = rand(5,4); xi = dsearchn(X,tri, q) ```
`nearestNeighbor` 方法和 `dsearchn` 函数允许以可选参数的形式返回查询点与其最近邻点之间的欧几里德距离。在四维示例中，可以计算距离 (`dnn`)，如下所示：
`[xi,dnn] = dsearchn(X,tri, q)`

### 点位置搜索

```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];```

``` 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```

```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);`

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

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