这是二维计算几何中的一个问题。
假设我在没有孔的平面上有一个紧凑的集合 X（即它是简单连接的）。设 w 为向量，并考虑 X 与 X+w 的交集（即 X 被 w 平移）。如果以下情况属实，我说这个交叉点很复杂：
- X 与 X+w 相交
- 如果我们让 Y 是通过填充有界孔从 (X union X+w) 获得的简单连接区域，那么当我们绕过 Y 的边界时，我们可以找到循环顺序为 a,b,c,d 的 4 个点在边界上，使得 a 和 c 在 X 中但不在 X+w 中，而 b 和 d 在 X+w 中但不在 X 中。
为简洁起见，我们将 X 与 X+w 的交集复杂的 w 集合称为 X 的凹壳（注意：这与 alpha 集合无关；它只是一个名称）。
我想知道一种快速实用的算法来计算 X 的凹壳，其中 X 是（比如说）一个多边形盘。除此之外，我可能会对凹形船体的优雅表征感兴趣，也许用不同的术语。最后，我将非常感谢任何讨论这个问题的文献的指点。
以下是一些说明：
- X 的凹壳是空的当且仅当 X 是凸的（因此得名）；这是因为如果 X 是凸的，并且 X 与 X+w 相交，那么 Y 的边界正好落入两个分量中，一个在 X 中，另一个在 X+w 中（从下面的第 3 点开始反过来）。
- 多边形的凹壳应该是一个开放的多边形（即去除了边界），因此可以（例如）作为（开放）三角形的有限联合给出答案。
- 如果 X 是非凸的，我们可以如下找到凹壳的一部分：设 L 是 X 的支撑线，它在两组 P 和 Q 中与 X 相交，它们之间有间隙 I。如果 J 是 X 的边界在 P 和 Q 之间的线段，那么 I 和 J 的并集在 X 的补集中界定了一个开盘 D，如果 p+ 是 P 的最接近 Q 的极值点，则 D-p+是在凹壳中。将这些区域在所有支撑线上的结合称为内凹壳；它看起来比较容易计算，但我认为它应该比一般的凹壳小。