从多边形中查找/删除多余边

Question

在外线中寻找一个外线的外线算法。图形是一组链接顶点的组合，导致多余的顶点和边。图中显示了这样的想法：红色的边需要去除。在

数据看起来像：（v00，v01，v02，…，（v10，v11，v12，…）。。。数据共享公共节点（顶点的数值数据相同）。在

{1美元^

这能做到吗？在

谢谢你

目标代码是Python。任何接近Python的东西都是完美的。在

Answer 1

{你想把它表示成一个无限的面，比如说你想计算一个无限的线段

[((x1, y1), (x2, y2)), ((x3, y3), (x4, y4)), ...].

第一步是计算组合嵌入。把每一个片段和它的反面插入到列表的dict中，如下所示。（所有这些Python都未经测试）

^{pr2}$

现在，按角度对每个列表排序。为了简单起见，我将使用atan2。在

for (x1, y1), p2s in graph.items():
    p2s.sort(key=lambda (x2, y2): math.atan2(y2 - y1, x2 - x1))

在无限面上找到一个顶点。最底端，按最左边的方式断开领带最左端就可以了（代码按最底端断开领带，这并不重要）。在

v0 = min(graph.keys())

v0邻接列表上的第一条边在无限面上逆时针方向。从它的逆时针方向开始。在

e0 = (graph[v0][0], v0)

现在，按以下方式迭代边。在

e = e0
while True:
    yield e
    v = e[1]
    neighbors = graph[v]
    e = (v, neighbors[neighbors.index(e[0]) - 1])
    if e == e0:
        break

给定一条在无限面上顺时针定向的有向边，通过反转它来获得下一条边，然后以顺时针顺序定位具有相同尾部的下一条边。重复，直到回到起始边缘。在

Answer 2

1. 列出顶点及其坐标，并列出边。在
2. 对于每个顶点，按逆时针角度对其入射边进行排序。在
3. 从最左边的顶点开始（如果有几个顶点，则最左边最下面）。在
4. 选择角度为-π/2的第一条边。在
5. 穿过边缘。在
6. 按排序顺序拾取传入边之后的第一条边。在
7. 如果这不是开始使用的顶点，请转到5。在

这将生成外部边的列表。在

如果有多个多边形，则可以删除已开始的图形的连接组件，然后在整个过程中重复该算法。请注意，它不识别带孔的多边形。如果你有洞，你将需要运行单独的测试，以找出哪个轮廓在里面。在