ハーフエッジデータ構造

はじめに

テンプレートパラメータまたはハーフエッジデータ構造（HalfedgeDSと略記）のHDSは、平面マップ、多面体、またはその他の方向付け可能な2次元など、頂点、エッジ、および面の入射情報を維持できるエッジ中心のデータ構造として定義されます。ランダムな次元に埋め込まれたサーフェス。各エッジは、反対方向の2つのハーフエッジに分割されます。各ハーフエッジには、1つの入射面と1つの入射頂点が格納されます。各面と各頂点に1つの入射ハーフエッジが格納されます。ハーフエッジデータ構造のバリエーションを減らすと、面のハーフエッジポインタや面の保存など、この情報の一部を削除できます。

ハーフエッジデータ構造はコンビナトリアルデータ構造として定義され、幾何学的解釈はハーフエッジデータ構造の上に構築されたクラスによって追加されます。ハーフエッジデータ構造は実装レイヤーとして扱われるため、これらのクラスは、ハーフエッジデータ構造よりも直接実装することが知られている可能性があります。

ハーフエッジデータ構造は、クアッドエッジデータ構造の変形の1つとして表示することもできます。一般に、向き付け不可能な2多様体は、クアッドエッジデータで表すことができますが、ここでの変形は、向き付け可能な2多様体のみに制限されています。

サンプルプログラム

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

次のサンプルプログラムは、デフォルトのハーフエッジデータ構造とデコレータクラスを適用します。デフォルトのハーフエッジデータ構造は、リストベースの表現を実装します。アイテムのすべての発生率と頂点のポイントタイプについて説明します。些細な特性クラスは、ポイントに実装されたタイプを提供します。プログラムは、2つのハーフエッジ、1つの頂点（Vertex）と2つの面（Face1とFace2）で構成されるループを構築し、その有効性を検証します。

#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/HalfedgeDS_decorator.h>
struct Traits { typedefint 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;
}