ハーフエッジデータ構造（HalfedgeDS）とは？基本概念とCGAL実装例をわかりやすく解説

はじめに

テンプレートパラメータとして用いられるハーフエッジデータ構造（Halfedge Data Structure、略称 HalfedgeDS）は、頂点・辺・面の接続情報（インシデンス情報）を管理できる、辺を中心としたデータ構造として定義されています。平面地図（planar map）や多面体など、任意の次元空間に埋め込まれた向き付け可能な2次元曲面の表現に適した構造です。

このデータ構造では、各辺が逆向きの向きを持つ2つのハーフエッジ（半辺）に分割されます。各ハーフエッジは、隣接する1つの面と1つの頂点への参照を保持し、逆に各面および各頂点にも、それぞれ1つの接続ハーフエッジが格納されます。さらに、簡略化されたバリアントでは、面側のハーフエッジポインタや、面そのものの格納といった一部の情報を省略することも可能です。

組合せデータ構造としての位置づけ

ハーフエッジデータ構造はあくまで組合せ論的なデータ構造として定義されており、幾何的な解釈はその上に構築されるクラス群によって付加されます。ハーフエッジデータ構造自体は実装レイヤーとして扱われるため、実際のアプリケーションでは、これらの上位クラスを介して利用するのが一般的です。

また、ハーフエッジデータ構造はクアッドエッジデータ構造（quad-edge data structure）の変種の一つと見なすこともできます。一般にクアッドエッジデータは非可向な2次元多様体も表現できるのに対し、ここで紹介する変種は向き付け可能な2次元多様体のみを扱うよう制限されている点に注意してください。

サンプルプログラム

デフォルトのハーフエッジデータ構造

以下のサンプルプログラムは、デフォルトのハーフエッジデータ構造とデコレータクラスを使用した例です。デフォルトのハーフエッジデータ構造はリストベースの表現を実装しており、各要素のすべての接続情報に加え、頂点用の点型が定義されています。トレイトクラスには単純なものを使用し、点に対して実装される型を指定しています。

このプログラムは、2つのハーフエッジ、1つの頂点、2つの面からなるループを構築し、その妥当性を検証します。

#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/HalfedgeDS_decorator.h>

struct Traits { typedef int Point_2; };

typedef CGAL::HalfedgeDS_default<Traits> HDS1;
typedef CGAL::HalfedgeDS_decorator<HDS> Decorator1;

int main() {
    HDS1 hds1;
    Decorator1 decorator(hds1);
    decorator.create_loop();
    CGAL_assertion(decorator.is_valid());
    return 0;
}