computational-geometry - 一组边的最外层多边形

Question

假设我有一组全部连接的二维线段。我需要一种算法来找到集合中最外层的段。即，限定同一区域的最小子集。

注意：这与找到构成线段的点的凸包不同。

编辑：顶部是初始段集。下面是删除了内部段的相同轮廓。（忽略灰色的小十字，它们只是用来标记交叉点。）

Answer 1

你会用铅笔怎么做……？

1. 找到最左边的顶点（最小 x）。如果有多个，请选择其中最低的一个（最小 y）。当前顶点下方没有顶点，因此以“向下”方向作为参考。
2. 找到从当前顶点出发的所有边并计算它们的方向（方位角）。找到与参考方向成最小正角（逆时针）的那个。那将是大纲部分。
3. 选择它的另一端作为新的“当前”顶点，并将从该顶点到最近顶点的方向设置为新的参考方向。
4. 从第 2 步开始，直到到达起始顶点。
5. 删除所有未访问的段。
6. 删除所有孤立的顶点（如果在步骤 5 中出现）。

Answer 2

以下是一种从凸包开始然后向内工作的方法。直觉是，您从船体上的边缘开始，然后通过沿着边缘集中的最短路径找到“沿”间隙的最近点来填充间隙。

1. 计算点的凸包。
2. 将船体集与边集相交。这将为您留下一系列可能断开的边缘路径。
3. 任何没有两条边的点（即图中的叶）通过在原始边集中找到最短路径来连接到其最近的叶。
4. 任何关系都可以被船体封闭时形成最小区域的路径打破。

Answer 3

给定一个三角非凸多边形，您可以指定顶点遍历的方向（逆时针顺时针方向）。使所有三角形都以类似的方向 WRT 遍历其顶点。将所有三角形分解为有向边。每个三角形的每条边都是两个顶点的元组(a, b)。对于每个相邻的三角形，您有两个相反的边(a, b)和(b, a)。您可以简单地将这样的一对边排除在进一步考虑之外。最后，您将获得一组专门的外边缘。

如果您的多边形由非简单部分组成（但您仍然可以指定顶点遍历的方向），则不会失去一般性。

源段构造多边形的三角剖分是明显的步骤：将顶点拉伸到 $d + 1$ 抛物面和三角剖分，然后排除三角形，包含至少一条不匹配任何源段的边。

另一种可能的方法是稍微修改礼品包装算法。