计算凸包

MATLAB^® 提供多种计算凸包的方式：

• 使用 MATLAB 函数 convhull 和 convhulln

• 使用 delaunayTriangulation 类提供的 convexHull 方法

• 使用 alphaShape 函数以及 alpha 半径 Inf。

convhull 函数支持在二维和三维空间中计算凸包。convhulln 函数支持在 N 维空间 (N ≥ 2) 中计算凸包。对于二维或三维计算，建议使用 convhull 函数，因为其稳定性和性能更好。

delaunayTriangulation 类支持从德劳内三角剖分进行凸包的二维或三维计算。这种计算方式的效率不如专用的 convhull 和 convhulln 函数。但是，如果有一个点集的 delaunayTriangulation，并且需要凸包，则 convexHull 方法可从现有的三角剖分更高效地计算凸包。

alphaShape 函数还通过将 alpha 半径输入参数设置为 Inf，来支持凸包的二维或三维计算。但是，与 delaunayTriangulation 相似，使用 alphaShape 计算凸包不如直接使用 convhull 或 convhulln 高效。在处理以前创建的阿尔法形状对象时例外。

使用 convhull 和 convhulln 计算凸包

convhull 和 convhulln 函数取一个点集，输出位于凸包边界上的点的索引。凸包基于点索引的表示法支持绘图，且便于数据访问。下面这些示例说明凸包的计算和表示。

第一个示例使用 seamount 数据集的一个二维点集作为 convhull 函数的输入。

加载数据。

load seamount

计算点集的凸包。

K = convhull(x,y);

K 表示绕凸包沿逆时针方向排列的点的索引。

绘制数据及其凸包。

plot(x,y,'.','markersize',12)
xlabel('Longitude')
ylabel('Latitude')
hold on

plot(x(K),y(K),'r')

给凸包上的点添加点标签，以观察 K 的结构。

[K,A] = convhull(x,y);

convhull 可以计算二维和三维点集的凸包。可以重复使用海底山数据集说明三维凸包的计算。

包含海底山 z 坐标数据仰角。

close(gcf)
K = convhull(x,y,z);

在三维空间中，凸包的边界 K 由三角剖分表示。这是以矩阵格式表示的一组三角面，并有关于点数组的索引。矩阵 K 的每一行表示一个三角形。

由于凸包的边界表示为三角剖分，因此可以使用三角剖分绘图函数 trisurf。

trisurf(K,x,y,z,'Facecolor','cyan')

三维凸包约束的体积可由 convhull 选择性返回，语法如下。

[K,V] = convhull(x,y,z);

convhull 函数还提供通过移除对面积或体积无贡献的顶点来简化凸包表示的选项。例如，如果凸包的边界面共线或共面，则可以合并这些面，以给出更精确的表示。下面的示例说明此选项的用法。

[x,y,z] = meshgrid(-2:1:2,-2:1:2,-2:1:2);
x = x(:);
y = y(:); 
z = z(:);

K1 = convhull(x,y,z);
subplot(1,2,1)
defaultFaceColor  = [0.6875 0.8750 0.8984];
trisurf(K1,x,y,z,'Facecolor',defaultFaceColor)
axis equal
title(sprintf('Convex hull with simplify\nset to false'))

K2 = convhull(x,y,z,'simplify',true);
subplot(1,2,2)
trisurf(K2,x,y,z,'Facecolor',defaultFaceColor)
axis equal
title(sprintf('Convex hull with simplify\nset to true'))

MATLAB 提供 convhulln 函数来支持更高维凸包和超体积的计算。虽然 convhulln 支持 N 维，但是由于内存需求迅猛增长，对高于十维情况下出现的问题难以应对。

convhull 函数在二维和三维情况下优于 convhulln，因为它更稳定，表现出更佳的性能。

使用 delaunayTriangulation 类计算凸包

本示例显示在二维空间中点集的德劳内三角剖分与该点集的凸包之间的关系。

delaunayTriangulation 类支持二维和三维空间中德劳内三角剖分的计算。这个类还提供 convexHull 方法从三角剖分获得凸包。

在二维空间内创建一组点的德劳内三角剖分。

X = [-1.5 3.2; 1.8 3.3; -3.7 1.5; -1.5 1.3; 0.8 1.2; ...
      3.3 1.5; -4.0 -1.0; -2.3 -0.7; 0 -0.5; 2.0 -1.5; ...
      3.7 -0.8; -3.5 -2.9; -0.9 -3.9; 2.0 -3.5; 3.5 -2.25];

dt = delaunayTriangulation(X);

绘制三角剖分并高亮显示仅由展现该凸包的单一三角形共有的边。

triplot(dt)

fe = freeBoundary(dt)';
hold on
plot(X(fe,1), X(fe,2), '-r', 'LineWidth',2)
hold off

在三维空间中，仅由一个四面体共有的三角剖分的面表示凸包的边界。

专用 convhull 函数通常比基于 convexHull 方法的计算更高效。但是，在以下情况下适合基于三角剖分的途径：

• 已有点集的一个 delaunayTriangulation，并且还需要凸包。

• 需要逐渐从点集中添加或移除一些点，并且需要在编辑这些点后频繁地重新计算凸包。

使用 alphaShape 的凸包计算

此示例说明了如何使用 alphaShape 函数计算二维点集的凸包。

alphaShape 通过二维或三维点集计算正则化的 alpha 形状。您可以指定阿尔法半径，它确定阿尔法形状包围点集的松紧程度。在 alpha 半径设为 Inf 时，生成的 alpha 形状是点集的凸包。

创建一个二维点集。

X = [-1.5 3.2; 1.8 3.3; -3.7 1.5; -1.5 1.3; 0.8 1.2; ...
      3.3 1.5; -4.0 -1.0; -2.3 -0.7; 0 -0.5; 2.0 -1.5; ...
      3.7 -0.8; -3.5 -2.9; -0.9 -3.9; 2.0 -3.5; 3.5 -2.25];

使用 alpha 半径等于 Inf 的 alpha 形状计算并绘制该点集的凸包。

shp = alphaShape(X,Inf);
plot(shp)

另请参阅

convhull | convhulln | convexHull | delaunayTriangulation | alphaShape

相关主题

• 使用德劳内三角剖分