Giới thiệu
HDS cho tham số mẫu (template parameters) hoặc cấu trúc dữ liệu halfedge (viết tắt HalfedgeDS) được định nghĩa là cấu trúc dữ liệu tập trung vào cạnh (edge-centered) có khả năng duy trì thông tin liên thuộc (incidence information) của đỉnh (vertices), cạnh (edges) và mặt (faces), như cho bản đồ phẳng (planar maps), đa diện (polyhedra), hoặc các bề mặt hai chiều có thể định hướng (orientable) nhúng trong chiều bất kỳ. Mỗi cạnh được chia thành hai halfedge (nửa cạnh) với hướng ngược nhau. Mỗi halfedge lưu một mặt liên thuộc và một đỉnh liên thuộc. Một halfedge liên thuộc được lưu cho mỗi mặt và mỗi đỉnh. Các biến thể giảm của halfedge data structure có thể loại bỏ một số thông tin này, như con trỏ halfedge trong mặt hoặc lưu trữ mặt hoàn toàn.
Halfedge data structure được định nghĩa là cấu trúc dữ liệu tổ hợp (combinatorial), giải thích hình học được thêm bởi các lớp xây dựng trên halfedge data structure. Các lớp này có thể quen thuộc hơn để cài đặt hơn halfedge data structure trực tiếp, vì halfedge data structure được coi là lớp cài đặt (implementation layer).
Halfedge data structure cũng có thể được hiển thị như một trong các biến thể của cấu trúc dữ liệu quad-edge. Nói chung, 2-variété không định hướng (non-orientable 2-manifolds) có thể được biểu diễn bằng dữ liệu quad-edge, nhưng biến thể ở đây giới hạn chỉ cho 2-variété định hướng (orientable 2-manifolds).
Chương trình ví dụ
Cấu trúc dữ liệu Halfedge mặc định (The Default Halfedge Data Structure)
Chương trình ví dụ sau áp dụng halfedge data structure mặc định và lớp decorator (trang trí). Halfedge data structure mặc định dùng biểu diễn dựa trên danh sách (list-based). Tất cả sự liên thuộc của các mục và kiểu điểm cho đỉnh được giải thích. Lớp traits (đặc tính) đơn giản cung cấp kiểu dùng cho điểm. Chương trình tạo một vòng (loop), bao gồm hai halfedge, một đỉnh (Vertex) và hai mặt (Face1 và Face2), và kiểm tra tính hợp lệ của nó.
#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;
}