区域边界的类型

凸包与非凸多边形

N 维空间中点集的凸包是封闭该点集中所有点的最小凸形区域。如果将二维点集想象为钉在木板上的钉子，则通过拉一根橡皮筋并围绕所有钉子将会构成该点集的凸包。

rng('default')
x = rand(20,1);
y = rand(20,1);
plot(x,y,'r.','MarkerSize',10)
hold on
k = convhull(x,y);
plot(x(k),y(k))
title('The Convex Hull of a Set of Points')
hold off

凸多边形是不含凹顶点的多边形，例如：

x = rand(20,1);
y = rand(20,1);
k = convhull(x,y);
plot(x(k),y(k))
title('Convex Polygon')

您也可以创建非凸点集的边界。如果从上面对凸包进行收紧，您可以使用凹顶点将所有点封闭在非凸多边形中：

k = boundary(x,y,0.9);
plot(x(k),y(k))
title('Nonconvex Polygon')

凸包具有很多应用。从平面中离散点集的凸包可以计算由该点集确定边界的区域的上界。凸包简化了更复杂的多边形或多面体的表现形式。例如，要确定两个非凸几何体是否相交，可以应用一系列快速否定步骤避免进行完全相交分析造成的损失：

• 检查围绕每个几何体的轴对齐边界框是否相交。

• 如果边界框相交，则可以计算每个几何体的凸包，并检查凸包的交集。

如果凸包不相交，则会避免进行更广泛的相交检验所需要的代价。

尽管凸包和非凸多边形是表示相对简单边界的方便方法，但它们实际是一种称为阿尔法形状的更常见几何结构的特定实例。

阿尔法形状

点集的阿尔法形状是凸包和德劳内三角剖分子图的推广。换言之，凸包只是其中一种阿尔法形状类型，完整系列的阿尔法形状可以从给定点集的德劳内三角剖分进行派生。

rng(4)
x = rand(20,1);
y = rand(20,1);
plot(x,y,'r.','MarkerSize',20)
hold on
shp = alphaShape(x,y,100);
plot(shp)
title('Convex Alpha Shape')
hold off

与凸包不同，阿尔法形状具有用于控制细节程度或者边界在点集周围的拟合紧密度的参数。该参数称为阿尔法或阿尔法半径。在 0 到 Inf 范围内更改 alpha 半径可生成一组该点集特有的不同 alpha 形状。

plot(x,y,'r.','MarkerSize',20)
hold on
shp = alphaShape(x,y,.5);
plot(shp)
title('Nonconvex Alpha Shape')
hold off

更改阿尔法半径有时会产生具有多个区域的阿尔法形状，其中可能包含也可能不包含孔洞。不过，MATLAB® 中的 alphaShape 函数始终返回正则化的 alpha 形状，以防出现孤立或空悬的点、边或面。

plot(x,y,'r.','MarkerSize',20)
hold on
shp = alphaShape(x,y);
plot(shp)
title('Alpha Shape with Multiple Regions')
hold off

另请参阅

convhull | alphaShape

相关主题

• 使用 delaunayTriangulation 类
• 三角剖分矩阵格式