37.2 Thể hiện của lưới tam giác trong CGAL

37.2   Biểu diễn của lưới tam giác CGAL

Tập hợp các mặt phẳng

Lưới tam giác 2D của CGAL được xem như là một phần của mặt phẳng, bao quanh lưới mặt phẳng và được bao bọc  bởi đường bao lồi từ các đỉnh của lưới. Mặt không bao đơn của phần này là phần bù của đường bao lồi. Trong nhiều ứng dụng khác nhau, như phân cấp của Kirkpatrick hoặc xây dựng Delaynay sau này, nó rất tiện lợi để gắn với lưới tam giác duy nhất. Vì vậy, một đỉnh tưởng tượng, gọi là đỉnh vô hạn được thêm vào lưới giống như thêm một cạnh (infinite edge) hay một mặt vô hạn có liên quan. Mỗi cạnh hay cạnh vô hạn lại có liên quan tới đỉnh vô hạn và với mỗi đỉnh của đường bao lồi.

Hình 37.1:  Đỉnh vô hạn (Infinite vertex) và mặt vô hạn infinite faces

Bởi vậy, mỗi cạnh của lưới có liên quan tới đúng hai mặt phẳng và tập hợp các tam giác của lưới tương đương một cách tôpô với hình cầu hai chiều. Nó mở rộng tới các lưới ít chiều hơn xuất hiện trong trường hợp suy biến hoặc khi lưới có ít hơn 3 đỉnh. Bao gồm mặt vô hạn, một lưới 1 chiều là một vòng bao và có các đỉnh tương đương với hình cầu 1 chiều (1-sphere). Lưới không chiều là lưới mà miền của chúng suy biến thành 1 điểm, được biểu diễn bằng hai đỉnh tương đương với hình cầu 0 chiều (0-sphere).

Hãy nhớ rằng đỉnh vô hạn không có bất cứ một tạo độ nào và không một vị từ hình học (geometric predicate) có thể áp dụng trên cả nó lẫn mặt phẳng vô hạn.

Một thể hiện dựa trên mặt và đỉnh

Vì là một tập hợp các mặt tam giác với kích thước nhất định, nên lưới tam giác không được thực thi như là một lớp trên đỉnh của bản đồ phẳng. CGAL sử dụng biểu diễn nội hàm của lưới dựa trên các mặt và các đỉnh hơn là dựa trên các cạnh. Giống như một biểu diễn tiết kiệm không gian lưu trữ và kết quả trong thuật toán nhanh hơn  [BDTY00]. 

Phần tử cơ bản của một biểu diễn là đỉnh và mặt. Mỗi mặt tam giác lại cho phép truy suất đến 3 đỉnh liên quan và tới 3 mặt liền kề khác. Mỗi một đỉnh lại cho phép truy suất đến một trong nhiều mặt phẳng liên quan và thông qua mặt phẳng đó, lại có thể truy suất đến nhiều mặt phẳng khác.

Ba đỉnh của mặt phẳng được đánh số thứ tự từ 0 đến 2 theo ngược chiều kim đồng. Tương tự, các mặt phẳng liền kề với mặt phẳng đó cũng được đánh số thứ tự 0, 1, 2. Mặt phẳng kề được đánh số thứ tự i đối diện với đỉnh có cùng số thứ tự. Xem hình vẽ 37.2, hàm ccw(i) và cw(i) chỉ ra trên mỗi minh họa ứng với  i+1 và i-1 theo môđun 3.

Các cạnh không được nhắc tới ở đây, chúng chỉ thể hiện sự liền kề giữa hai mặt phẳng mà thôi. Mỗi cạnh có hai biểu diễn ngầm: cạnh của của mặt phẳng f đối diện với đỉnh thứ i, và có thể được biểu diễn giống như là cạnh của mặt phẳng liền kề neighbor(i) của f.

Hình 37.2: Đỉnh và miền bên cạnh (neighbors).

 Link nguồn: http://www.cgal.org/