c++ - 将索引多边形转换为未索引的多边形。出现了几个问题

Question

我又对多边形算法有一些疑问。

我将尝试解释我的问题:

我正在使用名为几何工具 (GT) 的第三方库的子集对我的多边形执行 bool 运算。为此，我必须将我的内部多边形格式转换为 GT 使用的格式。

我们的内部多边形格式由一个顶点数组组成，而 GT 多边形由一个索引顶点数组组成，其中每条边由一对索引表示。

用于说明的正方形示例:

内部格式:

vertices[0] = Vertex2D(1,0) -> start
vertices[1] = Vertex2D(1,1)
vertices[2] = Vertex2D(0,1)
vertices[3] = Vertex2D(0,0)
vertices[4] = Vertex2D(1,0) -> end

外部格式:

vertices[0] = Vertex2D(1,0) 
vertices[1] = Vertex2D(1,1)
vertices[2] = Vertex2D(0,1)
vertices[3] = Vertex2D(0,0)

edges[0] = std::pair<int,int>(0,1)
edges[1] = std::pair<int,int>(1,2)
edges[2] = std::pair<int,int>(2,3)
edges[3] = std::pair<int,int>(3,0)

//There is also a BSP tree of the polygon which I don't care to depict here.

现在，我编写了一个在大多数情况下都有效的算法，但当两条边共享相同的起始顶点时就会崩溃和烧毁。让我先解释一下我当前的算法是如何工作的。

创建一个 std::map，其中键是表示顶点索引的整数。 该值表示边数组中哪里有以键索引为起始索引的边。

模型示例:

std::vector< std::pair< int, int > > edge_array;

edge_array.push_back( std::pair< int, int >( 0, 1 ) );
edge_array.push_back( std::pair< int, int >( 2, 3 ) );
edge_array.push_back( std::pair< int, int >( 1, 2 ) );
edge_array.push_back( std::pair< int, int >( 3, 0 ) );

std::map< int, int > edge_starts;
for ( int i = 0 ; i < edge_array.size(); ++i ) {
  edge_starts[ edge_array[i].first ] = i;
}

要从正确的边缘跳到正确的边缘，我现在可以在 while 循环内执行以下操作:

while ( current_placed_index = first_index_in_polygon ) {
  int index_to_next_edge_to_be_traversed = edge_starts[ current_edge.second ];
}

在这个循环中做了一些优化，顶点索引被添加到一个数组中。

每次关闭多边形时，我都会找到第一个未遍历的边并开始制作另一个多边形。我一直这样做，直到 GTPolygon 中不再有未遍历的边为止。

因此每个 GTPolygon 可以产生多个 Polygon(内部)对象。

当有两条边共享同一个顶点作为起始顶点时，此算法的缺陷就很明显。示例:

<1,2>
<1,3>
<1,5>

当遍历我的边时，我如何知道这些边中的哪一条属于我当前正在遍历的多边形？当发生这种重复情况时，我可以尝试向后遍历边缘。那么问题就是如果在逆向时发现另一个重复项，则遍历可能会无限地来回遍历。

我的问题是，我该如何解决这个问题？它完全可以解决吗？ 我可以使用 BSP 树以某种方式解决这个问题吗？角落案例的数量有点令人生畏。

非常感谢任何帮助，因为 5 个月的工作取决于这项工作。

编辑:

澄清一下:我想将 Geometry Tools 使用的多边形的索引表示转换为我们的内部多边形格式，它只是列表中一系列连接的顶点。

Answer 1

您正在有效地尝试找到所有 cycles在undirected graph其中每个循环代表唯一多边形的边缘。 This paper建议 depth-first search (DFS)解决方案。