查找/移除多余的多边形边缘

Question

我在寻找一种算法，用来获取一组连接点的外部轮廓，也就是图中显示的黑线。这个图是由多个连接点组合而成的，结果出现了一些多余的点和边。图中显示了这个想法：红色的边需要被去掉。

数据的格式是这样的：(v00, v01, v02, ...), (v10, v11, v12, ...), ... 这些数据之间有一些共同的节点（也就是说，节点的数字是一样的）。

这个可以实现吗？

谢谢！

附注：目标代码是Python，任何接近Python的代码都可以。

Answer 1

听起来你想要计算一个平面直线图的无限面，这个图是用一系列线段表示的，比如说：

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

第一步是计算组合嵌入。把每个线段及其反向线段放进一个字典，里面是列表，像这样。（这些Python代码没有经过测试。）

graph = collections.defaultdict(list)
for p1, p2 in segments:
    graph[p1].append(p2)
    graph[p2].append(p1)

接下来，按角度对每个列表进行排序。为了简单起见，我会用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步。

这样就能得到外边的列表。

如果你有多个多边形，可以把你开始时的图的连通部分去掉，然后重新执行这个算法。需要注意的是，这个方法无法识别有孔的多边形。如果有孔，你需要进行额外的测试，找出哪个轮廓在里面，哪个在外面。