9

私は幾何学的な無向平面グラフを持っています。これは、各ノードに位置があり、2 つのエッジが交差しないグラフであり、エッジが交差していないすべてのサイクルを見つけたいと考えています。

この問題に対する既知の適切な解決策はありますか?

私がやろうとしているのは、一種のA*ような解決策です:

  • パスとして最小ヒープにすべてのエッジを挿入します
  • すべてのオプションで最短経路を延長する
  • 開始点以外にループバックするパスをカリングします (必要ない場合があります)。
  • 指定されたエッジで ang を使用する 3 番目のパスをカリングします

誰もこれに問題があると思いますか? それは機能しますか？

4

3 に答える 3

11

私の最初の本能は、迷路ソルバーに続く壁に似た方法を使用することです。基本的に、エッジをたどり、常に頂点から最も右のエッジを取り出します。この方法で遭遇するすべてのサイクルは、面の境界になります。どのエッジをどの方向にトラバースしたかを追跡する必要があります。エッジを両方向にトラバースすると、エッジが分離する面が識別されます。すべてのエッジが両方向にトラバースされると、境界によってすべての面が識別されます。

于 2009-05-08T03:26:52.723 に答える
5

「交差エッジ」と呼ばれるものは、一般にコードとして知られています。したがって、あなたの問題はすべての和音のないサイクルを見つけることです。

この紙が役に立ちそうです。

于 2009-05-08T03:26:14.440 に答える
2

これを行う簡単な方法は、外に出て各顔を列挙することです。原理は単純です：

  • 各エッジの「α-visited」フラグと「β-visited」フラグ、およびそのようなフラグごとの未訪問エッジの二重リンクリストのペアを維持します。「α」と「β」の分割は、問題のエッジに対応する線上の平面の分割に対応する必要があります。どちら側がαでどちら側がβかは任意です。
  • 各頂点Vについて：
    • 隣接するエッジのペアごとに、E =（V_1、V）、E'=（V_2、V）（つまり、角度で並べ替え、隣接するペア、および最初と最後を取得）：
    • Eのどちら側S（S =αまたはβ）V_2が存在するかを判別します。
    • 以下に説明するように、EのサイドSを使用して、Vから始めてタイルを歩きます。

タイルの歩行は、次の方法で実行されます。

  • V=V_initとします
  • ループ：
    • V_next=VではないEの頂点
    • E'=Eの現在の側にあるV_nextからEに隣接するエッジ
    • S'=Vを含むE'の側
    • V_next = Vの場合、ループが見つかりました。途中で通過したすべてのエッジを記録し、それらのエッジペアを訪問済みとしてマークします。
    • E'= E（エッジが1つしかない）の場合、行き止まりになっています。この散歩を中止する
    • それ以外の場合は、V = V_next、E = E'、S = S'とし、続行します。

これが理にかなっていることを願っています。説明するためにおそらくいくつかの図が必要です...

于 2009-05-08T03:45:46.407 に答える