3

メッシュを操作し、エッジをすばやく追加および削除し、頂点に隣接するエッジを CCW または CW の順序ですばやく反復処理する必要があるアルゴリズムを実装しています。

私が取り組んでいるアルゴリズムの説明ではウィングエッジ構造が使用されていますが、このデータ構造でこれらの操作を実行する方法についての簡潔な説明が見つかりません。

4

1 に答える 1

9

私は大学でそれについて学びましたが、それは少し前のことです。

この質問に応えて、私は Web で適切なドキュメントを検索しましたが、良いドキュメントは見つかりませんでしたが、ここで CCW と CW の順序と挿入/削除の簡単な例を見ることができます。この表と図を見て ここに画像の説明を入力 ください: このページから:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/model/winged-e.html

テーブルは 1 つのエッジのエントリのみをa示します。実際のテーブルでは、すべてのエッジに対してこの行があります。次のものが得られることがわかります。

  • 左の前任者、
  • 左後継者、
  • 右の前任者、
  • 右後継者

しかし、ここに重要なポイントがあります。この場合はエッジの方向に相対的であり、右にトラバースされている場合です。X->Y(e->a->c)

したがって、グラフを通過する CW 順序については、これは非常に読みやすいです。a左端には右後継者がcあり、次に行の端を調べますc。

OK、この表は CW 順トラバーサルで読みやすいです。CCW の場合、「このエッジを後ろに歩いたときに、どのエッジから来たのか」を考える必要があります。この場合、左トラバース先行を取得することにより、効果的に次のエッジを CCW オーダーで取得し、同じ方法でbエッジの行エントリを続行します。b

挿入と削除: エッジを単に削除して、グラフがまだ三角形だけで構成されていると考えることができないことは明らかです。削除中は、たとえばとグラフィックで2 つの頂点を結合する必要があります。これを行うには、まずエッジが参照されているすべての場所を確認する必要があります。その参照を修正する必要があります。XYa

では、どこを参照することができaますか？エッジのみb,c,d and e（他のすべてのエッジは遠すぎてわかりませんa）、頂点->エッジテーブルがある場合は（ただし、この例ではエッジテーブルのみを考えてみましょう）。

エッジを修正する方法の例として、 を見てみましょうc。のようaに、c左右の前後 (4 つのエッジ) がありますが、どれがaですか? のテーブルエントリは、その開始ノードまたは終了ノードのいずれかcにノードを持つことができるため、チェックせずにそれを知ることはできません。Yしたがって、それがどれであるかを確認する必要がありますc。開始ノードに Y が含まれていることがわかったとします。次に、aがc's正しい前任者であるかどうかを確認する必要があります (これはどちらであり、c'sエントリを見て と比較することでわかりますa) 。 ORc's正しい後継者かどうか. "後継？？" あなたは尋ねるかもしれませんか？はい、2つの「左トラバース」列は、エッジを後方に移動することに関連していることを覚えておいてください。これで、それが正しい先行者であることがわかり、a正しいc's先行者を挿入することでその参照を修正できますa's。残りの 3 つのエッジを続行すると、エッジ テーブルが完成します。もちろん、追加の修正Node->Verticesは簡単です。X と Y のエントリを調べて、aそこを削除するだけです。

エッジの追加は、基本的に、他の 4 つのエッジのこの修正の逆ですが、少しひねりがあります。分割したいノードを呼び出しZましょう ( と に分割されますX) Y。dノードまたはノードでand をe組み合わせることができるため、正しい方向に分割するように注意する必要がありますe(新しいエッジがグラフィックcの垂直ではなく水平である場合のように)! a最初に、まもなく作成されるX2 つのエッジの間と、新しいエッジのどの 2 つのエッジの間にY追加されるかを確認する必要があります。どちらのエッジを一方のノードに配置し、どちらを他方のノードに配置するかを選択するだけです。 ：あなたが望むものを選択してくださいb、cそして、それらの間の北にある2つのエッジが1つのノード上にあり、他のエッジが他のノード上にあることになりXます。次に、ベクトル減算によって、新しいエッジaが b と c の間にある必要があることがわかります。たとえば、c と北の 2 つのエッジのうちの 1 つとの間ではありません。ベクトル減算は、 newXの目的の位置から の目的の位置を引いたものですY。

于 2011-07-14T15:11:13.210 に答える