algorithm - 从随机列出的边中检测多边形

Question

我有一个包含许多多边形边缘的矢量图。每条边由起点和终点表示。没有明确指出边之间的连接。我需要从这些数据中提取多边形。这样做的明显方法是获取每条边的一个顶点，在所有其他边中搜索匹配的顶点，然后对边的下一个顶点重复此操作，直到我有一个闭环。但这是非常低效的。

有什么好的算法可以提取多边形，只给定边缘的起点和终点，没有特定的顺序？

Answer 1

尝试这样的事情（python-pseudocode）：

vertices = {} #map (x, y) coords to a list of all edges containing that vertex

for edge in edges:
    #add start & end vertices
    if edge.start not in vertices:
        vertices[edge.start] = []
    if edge.end not in vertices:
        vertices[edge.end] = []
    vertices[edge.start].append(edge)
    vertices[edge.end].append(edge)

现在你有了所有的顶点和从每个顶点出来的所有边。您现在可以为您的算法做最初的想法，但不必在所有边中搜索匹配的顶点，查找是即时的。

Answer 2

一种简单的方法是：

Sort the list of edges by end point. Call that array edges
Create a new array, polygon, size is num_edges 
edgeIndex = 0
copy edge from edges[0] to polygon[0]
count = 1
while (count < number_of_edges)
{
    starting_point = edges[edgeIndex].endpoint
    // do a binary search to find the segment that starts
    // at this edge's end point
    newIndex = binary_search(edges, starting_point)
    copy edge[newIndex] to polygon[count]
    ++count
    edgeIndex = newIndex
}

完成此操作后，polygon数组应按顺序包含边。

以上假设边缘点是合理输出的。也就是说，给定一个顶点为 '[(0, 0), (10, 10), (10, 0)]' 的三角形，边为：

{(0, 0), (10, 10)}
{(10, 10), (10, 0)}
{(10, 0), (0, 0)}

虽然不一定按这个顺序。如果给定第二条边{(10, 0), (10, 10)}（即开始和结束是相反的），那么问题就有点困难了。

您可以使用哈希映射和直接查找来做同样的事情，这将比二进制搜索更快。

另请注意，这假设您不会有两个以上的边连接到任何单个点。