画像を参照してください: http://i.stack.imgur.com/NPUmR.jpg
1 つ以上の接続されたサブグラフを含む無向グラフがあります。グラフは、接続された頂点の順序付けられたペアのセットによって定義されます。最大 300 個の頂点が存在する場合があります。グラフは平面です。
画像に示すように、ポリゴンを識別する必要があります。個別のポリゴン内の色付きの各領域。大まかなヒューリスティックは、ポリゴンがグラフ内の閉じたエッジ ループ (サイクル) 間の「囲まれた領域」であるということです。同様の投稿で、Depth First トラバーサルと訪問した頂点のマーキングを使用してサイクルを識別できることが示唆されています。
ただし、この後、画像に示されているように目的の出力を取得する方法がわかりません。
要件 ：
i) ポリゴンが重なったり交差したりしてはなりません。つまり、サイクル ABFHDCA は有効なポリゴンではありません。これは、ポリゴン FHGE とオーバーラップするためです。サイクル ABFEGHDCA は有効なポリゴンです。
ii) 多角形には 3 つ以上のエッジがあり、多角形はグラフのエッジで囲まれている必要があります。XYZ は有効な多角形ですが、グラフの残りの頂点から切り離されています。
iii) K や L のような頂点 (つまり、葉) は、ポリゴンの一部を形成しません。エッジJKなんてどうでもいい。
更新: iv) グラフのエッジは互いに交差しません。2 つのエッジが交わる唯一の場所は頂点です。これは、前のステージ/アルゴリズムによって保証されています。
質問:
サイクルを見つけるためのDFトラベサルで正しい軌道に乗っていますか? DFトラバーサルは、そのような場合に考慮する必要があるすべての（単純な）サイクルを提供してくれますか?特に、XYZがグラフの残りの部分から切断されていますか?
この問題を解決するための既存の代替アルゴリズムはありますか?
その他の注意事項：
a）この問題をより具体的な計算幾何学的用語で定義するのに問題があるため、無向グラフ内で多角形を見つけることに固執しています。グラフ理論を勉強してから何年も経っていることを認めなければなりません。現在ブラッシュアップ中です。
b)これに対する解決策は、凹/凸包アルゴリズムのようには見えません。接続されたエッジのセットについて話しています - 真のポリゴンであり、包含される必要がある点群だけではありません。
c) 上記の例は、私がすぐに思いついたものです。「エッジ」ケースのほとんどをカバーしていると思います（しゃれ）:)
同様のソリューション
- 同様の投稿を見つけましたが、受け入れられたソリューションでは、この例の正しいサイクルが生成されないようです。
前もって感謝します！