我再次对多边形算法有一些疑问。
我将尝试解释我的问题：
我正在使用名为 Geometric Tools(GT) 的第三方库的一个子集来对我的多边形执行布尔运算。为此，我必须将我的内部多边形格式转换为 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(internal) 对象。
当有两条边共享同一个顶点作为起始顶点时，该算法的缺陷就很明显了。例子：
<1,2>
<1,3>
<1,5>
当遍历我的边时，我如何知道这些边中的哪一个属于我当前正在遍历的多边形？当发生这种重复情况时，我可以尝试向后遍历边缘。那么问题将是如果在反转时发现另一个重复项，则遍历可能会无限地来回进行。
我的问题是，我该如何解决这个问题？完全可以解决吗？我可以使用 BSP 树以某种方式解决这个问题吗？角落案例的数量有点令人生畏。
非常感谢任何帮助，因为 5 个月的工作取决于这项工作。
编辑：
澄清一下：我想从几何工具使用的多边形的索引表示转换为我们的内部多边形格式，这只是列表中的一系列连接顶点。