二重連結エッジリスト（DCEL ）は、ハーフエッジデータ構造とも呼ばれ、平面グラフの平面への埋め込み、および3D多面体の埋め込みを表現するデータ構造です。このデータ構造は、対象となるオブジェクト（頂点、エッジ、面）に関連付けられた位相情報を効率的に操作できます。これは、平面の多角形分割（一般に平面直線グラフ（PSLG）と呼ばれる）を扱うために、計算幾何学の多くのアルゴリズムで使用されます。例えば、ボロノイ図は、境界ボックス内のDCELによって表現されるのが一般的です。
このデータ構造は、もともとミュラーとプレパラタ[1]によって3次元凸多面体の表現のために提案されたものです。ここで説明するデータ構造の簡略版は連結グラフのみを考慮していますが、DCEL構造は、連結されていないコンポーネント間にダミーエッジを導入することで、連結されていないグラフも扱えるように拡張できます。[2]
データ構造
DCELは、単なる辺の双方向リンクリストではありません。一般的に、DCELには、細分化された各辺、頂点、面のレコードが含まれます。各レコードには追加情報が含まれる場合があり、例えば、面には領域名が含まれることがあります。各辺は通常2つの面を囲むため、各辺を2つの「ハーフエッジ」と見なすと便利です（右の図では、2つの頂点の間にある、反対方向の2つの辺で表されています）。各ハーフエッジは1つの面に「関連付けられて」おり、その面へのポインタを持ちます。面に関連付けられたすべてのハーフエッジは、時計回りまたは反時計回りです。例えば、右の図では、中央の面（つまり「内部」ハーフエッジ）に関連付けられたすべてのハーフエッジは反時計回りです。ハーフエッジには、同じ面の次のハーフエッジと前のハーフエッジへのポインタがあります。もう一方の面に到達するには、ハーフエッジの双子の面に移動し、そこからもう一方の面をトラバースします。各ハーフエッジには、その原点頂点へのポインターもあります (目的の頂点は、その双子のハーフエッジまたは次のハーフエッジの原点を照会することによって取得できます)。
各頂点は、その頂点の座標を保持し、その頂点を原点とする任意の辺へのポインタも保持します。各面は、その外側の境界のハーフエッジへのポインタを保持します（面が境界を持たない場合、ポインタはnullになります）。また、ハーフエッジのリストも保持します。ハーフエッジは、面に含まれる可能性のある穴ごとに1つずつ存在します。頂点または面が特に重要な情報を保持しない場合は、それらを格納する必要はありません。これにより、メモリ容量が節約され、データ構造の複雑さが軽減されます。
参照
参考文献
- ^ Muller, DE; Preparata, FP (1978). 「二つの凸多面体の交差を求める」.理論計算機科学. 7 (2): 217– 236. doi : 10.1016/0304-3975(78)90051-8 . hdl : 2142/74093 .
- ^ デ・バーグ、マーク;チョン、オトフリート。マーク・ヴァン・クレフェルト。オーバーマーズ、マーク (2008)。計算幾何学、アルゴリズム、およびアプリケーション(第 3 版)。スプリンガー。29 ～ 33ページ 。ISBN 978-3-540-77973-5。
