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

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

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