Halfedge Data Structure (ครึ่งขอบโครงสร้างข้อมูล)

Introduction

Halfedge Data Structure (HDS) = Edge-centered Data Structure รักษา Incidence Information ของ Vertices, Edges, Faces สำหรับ Planar Maps, Polyhedra, Orientable 2D Surfaces Embedded ใน Dimension ใดก็ได้

แต่ละ Edge แบ่งเป็น 2 Halfedges ที่มี Orientation ตรงข้าม
แต่ละ Halfedge เก็บ: 1 Incident Face + 1 Incident Vertex
แต่ละ Face/Vertex เก็บ: 1 Incident Halfedge

Reduced Variants: ลดข้อมูลบางส่วน (Halfedge Pointers ใน Faces, หรือเก็บ Faces เลยไม่ได้)

HDS = Combinatorial Data Structure Geometric Interpretation เพิ่มโดย Classes บน HDS (ง่ายกว่าใช้ HDS ตรงๆ)

HDS เป็น Variant ของ Quad-edge Data Structure Quad-edge = Non-orientable 2-Manifolds, HDS = Orientable 2-Manifolds เท่านั้น

Example: Default Halfedge Data Structure (CGAL)

#include 
#include 
struct Traits { typedef int Point_2; };
typedef CGAL::HalfedgeDS_default HDS;
typedef CGAL::HalfedgeDS_decorator Decorator;

int main() {
    HDS hds;
    Decorator decorator(hds);
    decorator.create_loop();  // สร้าง Loop: 2 Halfedges, 1 Vertex, 2 Faces
    CGAL_assertion(decorator.is_valid());
    return 0;
}

สรุป

HDS เป็น Foundation สำหรับ Geometry Processing (Mesh Operations, Subdivision, Remeshing) ใช้ใน CGAL, OpenMesh, libigl เป็นต้น