从一组边中获取最外层多边形

Question

假设我有一组连接在一起的二维线段，我需要一个算法来查找集合中最外层的线段。也就是说，该子集最小限度地包围相同区域。 注意：这与查找组成线段的点的凸包不同。

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

- Charles Taylor

---

所以你有一个复杂的多边形，想将其简化为外部边界？例如，如果你放进一个五角星，那么你会得到五个线段并输出十个线段，描述出轮廓？ - Tommy

不行。请看我附上的示例所做的编辑。 - Charles Taylor

明白了。这将是每个完全被边缘包围的点的轮廓吗？边缘一定是原始边缘的子集吗？您能保证没有相交的线段吗？ - Tommy

是的，而且没错。对于特定的应用程序来说，这两个都是正确的。 - Charles Taylor

你的图纸是矢量化还是光栅化形式？ - user1196549

Answer 1

你如何用铅笔做到这一点呢...?

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

- CiaPan

Answer 2

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

1. 计算您的点的凸包。
2. 将外壳集与边缘集相交。 这将使您拥有一系列可能断开的边缘路径。
3. 任何没有两个边缘（即在图形术语中的叶子）的点都通过在原始边缘集中查找最短路径连接到其最接近的叶子。
4. 任何平局都可以通过封闭外壳时产生最小面积的路径来打破。

- dpmcmlxxvi

Answer 3

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

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

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

另一种可能的方法是稍微修改 Gift wrapping algorithm。

- Tomilov Anatoliy

---

问题中添加的图像表明多边形已经三角剖分，但是描述并没有做出这样的保证。 - CiaPan