소개
템플릿 매개변수용 HDS, 즉 하프엣지 데이터 구조(halfedge data structure, 약칭 HalfedgeDS)는 정점(vertex), 변(edge), 면(face) 사이의 인접(incidence) 정보를 유지할 수 있는 엣지 중심 데이터 구조로 정의됩니다. 평면 지도(planar map), 다면체(polyhedron), 또는 임의 차원 공간에 매장된 방향 가능한 2차원 곡면 등을 표현하는 데 활용됩니다.
각 변은 서로 반대 방향을 가진 두 개의 하프엣지(halfedge)로 분리됩니다. 각 하프엣지는 하나의 인접 면과 하나의 인접 정점을 저장하며, 반대로 각 면과 각 정점에는 하나의 인접 하프엣지가 저장됩니다. 하프엣지 데이터 구조의 축소 변형(variant)을 사용하면 면에 저장되는 하프엣지 포인터나 아예 면 자체를 저장하지 않는 등 일부 정보를 생략할 수 있습니다.
하프엣지 데이터 구조는 조합적(combinatorial) 데이터 구조로 정의되며, 기하학적 해석은 이 구조 위에 구축된 클래스들을 통해 추가됩니다. 하프엣지 데이터 구조는 구현 계층(implementation layer)으로 취급되기 때문에, 실제 응용 프로그램에서는 이러한 상위 클래스를 직접 사용하는 것이 더 편리하고 일반적입니다.
또한 하프엣지 데이터 구조는 쿼드엣지(quad-edge) 데이터 구조의 변형 중 하나로 볼 수도 있습니다. 일반적으로 쿼드엣지 데이터는 비방향성(non-orientable) 2차원 다양체까지 표현할 수 있지만, 여기서 다루는 변형은 방향 가능한(orientable) 2차원 다양체로 한정됩니다.
예제 프로그램
기본 하프엣지 데이터 구조
다음 예제 프로그램은 기본(default) 하프엣지 데이터 구조와 데코레이터(decorator) 클래스를 활용합니다. 기본 하프엣지 데이터 구조는 리스트(list) 기반 표현을 구현하며, 항목(item)들의 모든 인접 관계와 정점을 위한 점(point) 타입이 정의되어 있습니다. 단순한 traits 클래스가 점에 사용될 타입을 제공합니다. 이 프로그램은 두 개의 하프엣지, 하나의 정점(Vertex), 그리고 두 개의 면(Face1, Face2)으로 구성된 루프(loop)를 생성한 뒤, 그 유효성을 검증합니다.
#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/HalfedgeDS_decorator.h>
struct Traits { typedef int Point_2; };
typedef CGAL::HalfedgeDS_default<Traits> HDS;
typedef CGAL::HalfedgeDS_decorator<HDS> Decorator;
int main() {
HDS hds;
Decorator decorator(hds);
decorator.create_loop();
CGAL_assertion(decorator.is_valid());
return 0;
}