またしても、ポリゴンアルゴリズムに関していくつか質問があります。
私は私の問題を説明しようとします：
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.
ここで、ほとんどの場合に機能するアルゴリズムを作成しましたが、2つのエッジが同じ開始頂点を共有すると、クラッシュしてバーンします。私の現在のアルゴリズムがどのように機能するかを説明することから始めましょう。
キーが頂点インデックスを表す整数であるstd::mapを作成します。この値は、エッジ配列のどこに、開始インデックスとしてkey-indexを持つエッジがあるかを表します。
モックアップの例：
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（内部）オブジェクトになる可能性があります。
このアルゴリズムの欠陥は、開始頂点と同じ頂点を共有する2つのエッジがある場合に明らかです。例：
<1,2>
<1,3>
<1,5>
エッジをトラバースするとき、これらのエッジのどれが現在トラバースしているポリゴンに属しているかをどのように知ることができますか？このような重複した状況が発生した場合は、エッジを後方にトラバースしてみることができます。問題は、反転中に別の重複が見つかった場合に、トラバースが無限に前後に移動する可能性です。
私の質問は、どうすればこれを解決できますか？それはまったく解決可能ですか？BSPツリーを使用してこれを何らかの方法で解決できますか？コーナーケースの数は少し気が遠くなるほどです。
5か月の作業はこの作業に依存するため、どんな助けでも大歓迎です。
編集：
明確にするために：Geometry Toolsが機能するポリゴンのインデックス付き表現から、リスト内の一連の接続された頂点である内部ポリゴン形式に変換したいと思います。