無向グラフでユニークなループを見つける

Question

現在、Unityのノードベースのビルダーで作業しています。このシステムはワークフローが非常にシンプルです。ユーザーは単にキューブであるノードを作成し、相互に接続して壁を作成することができます。メッシュ処理はすでに完了しており、すばやくスムーズに動作します。

ここで私がしようとしているのは、いくつの閉じた部屋が作成されているか、どの部屋にどのような頂点が含まれているかを検出することです。可能な入力は、次の画像で見ることができる：最初の画像で

、ループは

あろう（1,5,3,4）、（1、 2,6,8,7,5）、（6,9,12,11,10,8）、（8,10,14,13）および（10,11,17,16,15,14）。

第一

それらは、

（1,2,5,6,8,7）、（2,3,4,14,13,6,5）だろう（6,13,12,11,10）および（8,6,10,9）。

各ノードは、最大4つの他のノード（基幹側に1つ）に接続でき、すべてのリンクは両側に格納されます。私はノードが特定の順序で来る必要はありません。

一般的なループ検出アルゴリズムを使用し、サブループを再帰的に検索するには、内部接続がないループが見つかるまで再帰的に検索することを検討しましたが、これは非常にリソースを消費します。内部接続のないループを検出するために使用できるいくつかのプロパティがグラフ上で何回も繰り返されていなければなりませんが、見つけられませんでした。

ご意見はありますか？作業するには、次のアルゴリズムについて、あなたは以下のものが必要

Answer 1

：

• （あなたはおそらく既に持っている）エッジのユニークな方向エッジがされているかどうかを指定すべてのエッジのための
• 2つのフラグ未使用エッジ

と前後方向

頂点のリストで使用されるその後のアイデアは以下の通りです。使用されていないエッジのあるノードを取り出し、使用していないエッジのいずれかを隣接ノードに移動します（方向を覚えておいてください）。そのようにすると、使用されている方向に従って、すぐにエッジにマークを付けます。この隣人は、あなたが来た方向を知っています。未使用の最初のエッジが見つかるまで反時計回りの順序で見てください（再びエッジ方向を注意してください）。時計回りの順序で検索することもできます。これは、すべての出力面の順序を定義します。例えば。左端から来た場合は、それぞれ下端、右端、上端を確認してください。このエッジを横切って（使用済みとしてマーク）、開始頂点に到着するまで繰り返します。すべての訪問頂点があなたの部屋を形成します。

このようにすると、使用されていないエッジで頂点リストを更新する必要があります。

最終的に、境界のための顔も作成します。あなたはこれを検出できます。その向き計算することによって：

(x1, y1) x (x2, y2) = (x1 * y2) - (x2 * y1) 

境界面：

v1 x v2 + v2 x v3 + v3 x v4 + ... + vn x v1 

v頂点の位置であり

、及びxを（顔向きを表す）外積のz成分を表します他のすべての顔とは異なる向きになります。実際の符号は、エッジトラバーサル時に反時計回りか時計回りのどちらを使用したかによって異なります。

Answer 2

これは最初の質問にのみ回答していますが、2番目の質問では役に立ちます。閉じられた部屋の数は実際に閉じた公式を有する。 1 - V + Eここで、Vは頂点の数であり、Eはエッジの数である。 2番目の例では、頂点が14、エッジが17、部屋が4です。 数学は少し複雑ですが、キーワードはEuler characteristicです。