Giới thiệu
HDS cho các tham số mẫu hoặc cấu trúc dữ liệu halfedge (viết tắt là HalfedgeDS) được định nghĩa là cấu trúc dữ liệu tập trung vào cạnh có khả năng duy trì thông tin về tỷ lệ của các đỉnh, cạnh và mặt, chẳng hạn như đối với bản đồ phẳng, khối đa diện hoặc hai chiều có thể định hướng khác bề mặt được nhúng trong kích thước ngẫu nhiên. Mỗi cạnh được chia thành hai nửa cạnh có hướng ngược nhau. Mỗi halfedge lưu trữ một mặt sự cố và một đỉnh sự cố. Một halfedge sự cố được lưu trữ cho mỗi mặt và mỗi đỉnh. Các biến thể rút gọn của cấu trúc dữ liệu halfedge có thể loại bỏ một số thông tin này, chẳng hạn như các con trỏ halfedge trong các khuôn mặt hoặc việc lưu trữ các khuôn mặt.
Cấu trúc dữ liệu halfedge được định nghĩa là cấu trúc dữ liệu tổ hợp, việc giải thích hình học được thêm vào bởi các lớp được xây dựng trên đầu cấu trúc dữ liệu halfedge. Các lớp này có thể được biết đến nhiều hơn để triển khai trực tiếp cấu trúc dữ liệu halfedge, vì cấu trúc dữ liệu halfedge được coi như một lớp triển khai.
Cấu trúc dữ liệu halfedge cũng có thể được hiển thị như một trong những biến thể của cấu trúc dữ liệu bốn cạnh. Nói chung, 2 đa tạp không định hướng có thể được biểu thị bằng dữ liệu 4 cạnh, nhưng biến thể ở đây chỉ giới hạn ở các đa tạp 2 định hướng.
Chương trình mẫu
Cấu trúc dữ liệu Halfedge mặc định
Chương trình ví dụ sau áp dụng cấu trúc dữ liệu halfedge mặc định và lớp decorator. Cấu trúc dữ liệu halfedge mặc định thực hiện biểu diễn dựa trên danh sách. Các mục 'tất cả các tỷ lệ và một loại điểm cho các đỉnh được giải thích. Lớp đặc điểm tầm thường cung cấp kiểu được triển khai cho điểm. Chương trình xây dựng một vòng lặp, bao gồm hai nửa cạnh, một đỉnh (Vertex) và hai mặt (Face1 và Face2) và xác minh tính hợp lệ của nó.
#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;
}