凸包与非凸多边形

R2026b
打开实时脚本

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

Random points enclosed by their convex hull boundary

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

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("Convex Polygon")
hold off

Random points enclosed by a convex polygon (their convex hull)

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

plot(x,y,"r.",MarkerSize=10)
hold on
k = boundary(x,y,0.9);
plot(x(k),y(k))
title("Nonconvex Polygon")
hold off

Same points enclosed by a nonconvex polygon with concave vertices

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

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

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

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

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