ハーフエッジデータ構造ウィキペディア

一 ハーフエッジデータ構造 また 二重に接続されたエッジリスト （ dcel ）（英語のダブルチェーンエッジリスト）は、平面グラフのデータ構造です。結び目、半エッジ（ハーフエッジ）、表面で構成されています。各エッジは、それぞれが開始ノード、隣接する領域、同じエッジのその他のセミエッジ、および同じ領域の次の半分に割り当てられている2つの向かいのセミエッジで表されます。逆に、結び目や表面もそれぞれの隣人を「知る」ことができます。

この構造により、特に構造化されていないグリッドで、近隣の問題やエリアやノットの周りの効率的な反復に対する迅速な回答が可能になります。したがって、有限要素の方法で使用されているような非構造化された空間データレコードや、コンピューターグラフィックスとポリゴンネットワーク全般に特に適しています。

ハーフエッジのデータ構造は、それぞれリストに保存されているノード、半エッジ、表面で構成されています。 ^[初め] 彼の「隣人」の少なくとも一部は、これらの要素の個々のそれぞれに対して保存されています。 H.隣接する（「インシデント」）要素。たとえば、その隣接する領域は、各セミエッジ（またはこの領域のポインター）に保存されます。

semi -Edge [ 編集 | ソーステキストを編集します ]

DCELの抜粋。エッジe、次の後継者（e）、前任者の前（e）、そして双子の双子（e）は模範的です

の特性と名前 ハーフエッジ -Datructureは、2つのポイント間の接続が単一の（ “フル）エッジではなく、正確に表されるという事実です 二 SO -CALLED 悪い 現在のエッジ。これらは反対方向に向けられています。 H.半分のエッジのターゲットノードは、残りの半分のエッジの開始ノードであり、その逆も同様です。
この手順の利点は、とりわけ、各セミエッジの前身、後継者、および隣接する領域を明確に割り当てることができることです。このような関係については、次のセクションで詳しく説明します。

灰色の矢印は、それぞれのセミエッジの後継者へのリンクを象徴しています。特別なケースが右下に発生します。セミエッジの後継者も双子です！

各半分は、他の3つのエッジに割り当てられ、それぞれに英語の名前が括弧内にあります。 ^[初め]

• 後継者（「次の半分」）：the 後続 同じエリアへの偶発的なエッジ。
• Zwilling（ “Twin”）：同じエッジのもう1つの反対側の半分。
• 前身（「以前のハーフエッジ」）： 前 同じエリアへの偶発的なエッジ。

「次の」エッジとして、あなたが最初に出会うエッジは、あなたが時計回りであるときに明確に定義されます ターゲットノードに 走り回ります。

また、セミエッジを想像することもできます に対して 付随的なエリアの周りを時計回りに走らせます。ただし、孤立したサブグラフのこの見解は、別の領域にあることに注意する必要があります。 （セクションの表面を参照） 、このサブグラフの外側のセミエッジは の中に 前進する。

さらに、それは各エッジに対して保存されます：

• ノードを開始する（ “origin”、 “source”）
• 偶発的な表面（ “face”）：セミエッジの左側の領域。

ノード [ 編集 | ソーステキストを編集します ]

接続情報の大部分はすでにセミエッジにあるため、個々の結び目の1つだけが1つだけです

• 発信エッジ（ “インシデントエッジ”）

保存。 ^[初め]

ノードは主に1つの部屋のポイントであるため、通常、座標も保存されます。

水面 [ 編集 | ソーステキストを編集します ]

水面 f ライトグレーとその外側のコンポーネントとこの場合の内側のコンポーネント – それぞれが偶発的なコンポーネントの半端で識別されます。

エリアは、セミエッジで作られたサイクルによって定義されます。エリア自体に他のコンポーネントがある場合、これはいくつかのサイクルになる可能性があります。これらの接続コンポーネントを別のオブジェクトとして扱う代わりに、これらのサイクルの半分のエッジが単純に保存されます。 ^[初め]

• 外部コンポーネント（「外側のコンポーネント」）：領域を外側に概説したサイクル
• 内部コンポーネント（「内部コンポーネント」）：エリア内にあるサイクルのリスト。

複雑な問い合わせは、異なる関係の組み合わせを使用して回答できます。

• Semi -Edgeのターゲットノード=双子のノードを開始する
• セミエッジ=セミエッジの双子の偶発的な表面に沿って隣接するエリア
• すべてのハーフエッジが地域に付随する：
  • 前半-EDED =エリアの外部コンポーネント（内部コンポーネント類似）
  • 前半に戻るまで後継者に後継者に従ってください。
• すべての結び目の付随的な表面：以下の例のコードを参照してください。

サンプルコード [ 編集 | ソーステキストを編集します ]

すべての領域における反復のコードの例偶発的。アルゴリズムは、現在のセミエッジの領域を決定する必要があり、その後何かを行うことができるという違いを持つ、すべてのインシデントのセミエッジの反復についてこれに対応しています。

初め  =  InciseEdge （ ノード ）;  current_halbkant  =  初め ;  する  {   IT_RENDWASを実行します （  インシデントフェイス （ current_halbkant ））;   current_halbkant  =  次 （ ツイン （ current_halbkant ））;  }  その間 （  current_halbkant  ！=  初め ））  

さらに質問と用語の比較については、polygonnetz＃用語比較も参照してください。

双子と後継の関係で構成される半編集のみで構成されるデータ構造でさえ、すでに機能の範囲の大部分を提供しています！したがって、グラフの移動はすでに可能です。エリアとノットはすでに暗黙的に含まれています。同じエッジに戻って同じエッジに達するまで、後継者を半分から歩くときに生じるサイクル。交互に双子と後継者によって発生するやや複雑なサイクルは、結び目を識別します。

このようなミニマリストのソリューションは、まれな場合にはすでに十分です。たとえば、エッジによって購入されたエリアが、道路ネットワークや川の場合のように実用的な役割を果たさない場合。 ^[2]

1. ↑ ^{a b c d} マーク・デ・バーグ、オトフリード・チョン、マーク・ヴァン・クレヴェルド、マーク・オーバーマーズ： 計算ジオメトリ：アルゴリズムとアプリケーション 。 Springer-Verlag、Berlin / Heidelberg / New York 2000、ISBN 3-540-65620-0、S。31–32
2. ↑ マーク・デ・バーグ、オトフリード・チョン、マーク・ヴァン・クレヴェルド、マーク・オーバーマーズ： 計算ジオメトリ：アルゴリズムとアプリケーション 。 Springer-Verlag、Berlin / Heidelberg / New York 2000、ISBN 3-540-65620-0、S。33