37.4 Lưới tam giác cơ bản Basic Triangulations

37.4   L­ưới tam giác cơ bản

37.4.1   Giới thiệu

Figure 37.5:  Flip.

Lớp Triangulation_2<Traits,Tds>giống như một lớp cơ sở phục vụ cho các lớp lưới tam giác 2D và thực thi giao diện người dùng tới một lưới tam giác.

Các đỉnh và mặt của lưới tam giác được truy cập thông qua điều khiển (handles), biến lặp (iterators) và bộ truyền (circulators). Handle là một kiểu của khái niệm Handle đề xuất đến hai toán tử khác nhau * và ->. Bộ truyền là một kiểu dành hết cho việc duyệt qua các chỗi vòng tròn.

(A circulator is a type devoted to visit circular sequences). Điều khiển được dùng đến bất cứ khi nào phần tử được truy cập không phải là thành phần của một chuỗi. Biến lặp và bộ truyền được sử dụng để duyệt qua tất cả hoặc từng phần của lưới tam giác.

Biến lặp và bộ truyền đều có hai chiều không thay đổi. Chúng có thể được chuyển đổi thành điều khiển với cùng một kiểu giá trị, để khi gọi một hàm thành viên, bất cứ đối số kiểu điều khiển đều có thể được thay thế bởi biến lặp hay bộ truyền với cùng kiểu giá trị. Lớp lưới tam giác cho phép duyệt tới các đỉnh và các mặt bên của mặt phẳng theo cùng hoặc ngược chiều kim đồng hồ.

Có các bộ truyền để truy suất đến các cạnh, hay các mặt có liên quan đến đỉnh cho trước, hoặc đỉnh liền kề với nó. Một kiểu bộ truyền khác lại cho phép truy suất đến mọi mặt phẳng có chứa một đoạn thẳng cho trước. Bộ truyền bước qua các đối tượng vô hạn cũng giống như các đối tượng hữu hạn.

Lớp lưới tam giác đề xuất một vài biến lặp để duyệt qua tất cả các mặt, các cạnh hay đỉnh và một số biến khác để duyệt đến mặt, đường, hoặc đỉnh được chọn.

Lớp lưới tam giác cung cấp một phương thức để định vị một điểm cho trước có liên quan đến lưới tam giác. Trong trường hợp đặc biệt, phương thức đó sẽ cho biết bất kể là điểm trùng đó với một mắt lưới, nằm trên một cạnh, trong mặt phẳng hay bên ngoài đường bao. Trong trường hợp lưới suy biến, điểm cũng có thể nằm bên ngoài đường bao afin của lưới.

 Lưới tam giác còn cung cấp các phương thức định vị một điểm với một mặt phẳng hữu hạn của lưới hay với vòng tròn ngoại tiếp. Các mặt phẳng của lưới và các vòng tròn ngoại tiếp của chúng có chiều ngược chiều kim đồng hồ.

Lưới có thể được chỉnh sửa bởi vài hàm khác nhau như thêm 1 điểm, loại bỏ 1 đỉnh, chuyển đổi một đỉnh, đối xứng một cạnh... Việc đối xứng một cạnh hoàn toàn có thể thực hiện khi hợp của hai mặp phẳng liên quan hình thành một tứ giác lồi (xem hình 37.5).

Hình 37.5:  Đối xứng.

Thực thi

Công việc định vị được thực hiện bởi một đoạn thẳng di động. Nó bắt đầu từ một đỉnh của mặt phẳng cho trước như là một tham số tuỳ chọn hoặc tại một điểm tự chọn của lưới nếu không được cho trước. Mất một khoảng thời gian O(n) trong trường hợp xấu nhất, còn trung bình là O(√n) nếu các đỉnh phân bố một cách ngẫu nhiên. Lớp Triangulation_hierarchy_2<Traits,Tds>, được nói đến trong mục 37.10, thực thie một cấu trúc dữ liệu được thiết kế để đưa ra một thuật toán định vị điểm hiệu quả hơn.

Chèn một điểm được thực hiện bằng cách định vị một mặt phẳng chứa điểm đó, sau đó chia mặt phẳng thành 3 mặt phẳng mới. Nếu điểm rơi bên ngoài đường bao, lưới tam giác sẽ được khôi phục lại bởi phép đối xứng. Nếu nằm ngoài vị, việc chèn điểm sẽ mất một khoảng thời gian O(1).Đây chỉ là đường biên amortized cho các điểm nằm bên ngoài đường bao lồi.

Việc loại một đỉnh được thực hiện bằng cách loại bỏ tất cả các tam giác kề bên, và xây dựng lại lưới tam giác từ lỗ thủng (hole). Công việc này mất một khoảng thời gian tỉ lệ đến d², trong đó d là số đo độ của đỉnh loại bỏ, là O(1) cho một đỉnh ngẫu nhiên.

Di chuyển một đỉnh được thực hiện như sau: Đầu tiên, kiểm tra xem lưới tam giác mới có còn đồng phẳng hay không, nếu còn, đỉnh đã được đặt chính xách tại một vị trí mới; ngược lại, điểm được chèn tại một vị trí mới và đỉnh tại vị trí cũ sẽ được loại bỏ.

Displacement of a vertex is done by: first, verifying if the triangulation embedding remains planar after the displacement; if yes the vertex is directly placed at the new location; otherwise, a point is inserted at the new location and the vertex at the obsolete location is removed.

Mặt, cạnh và đỉnh lặp trên các đặc tính hữu hận được dẫn xuất từ bản sao của chúng kiểm tra tất cả tính năng (cả hữu hạn và vô hạn) được tự dẫn xuất từ biến lặp tương ứng của cấu trúc dữ liệu lưới tam giác.

The face, edge, and vertex iterators on finite features are derived from their counterparts visiting all (finite and infinite) features which are themselves derived from the corresponding iterators of the triangulation data structure.

Traits hình học - Geometric Traits

Traits hình học là một lưới tam giác được đòi hỏi để cung cấp đối tượng hình học (điểm, đoạn thẳng và tam giác) cùng xây dựng lên lưới tam giác với predicate hình học trên các đối tượng đó. Các predicate là:
The geometric traits of a triangulation is required to provide the geometric objects (points, segments and triangles) building up the triangulation together with the geometric predicates on those objects. The required predicates are:

- So sánh của tọa độ x hoặc y của hai điểm.

- Sự kiểm tra hướng, cái mà tính toán kiểu thứ tự của 3 điểm cho trước.

Khái niệm TriangulationTraits_2 miêu tả yêu cầu cho lớp traits hình học của lưới tam giác. Lớp kernel CGAL là các mô hình của thuật ngữ này. Thư viện CGAL còn cung cấp các mô hình chuyên dụng của TriangulationTraits_2 sử dụng đối tượng kernel hình học và predicate. Các lớp này tự templated với kernel CGAL và trích xuất các kiểu và predicate yêu cầu từ kernel. Lớp traits Triangulation_euclidean_traits_2<R> được thiết kế để làm việc với các điểm hai chiều thông thường. LớpProjection_traits_xy_3<R> là một lớp traits hình học để xây dựng lưới tam giác của một địa hình. Các điểm dữ liệu đều có 3 tọa độ x, y, z. Lưới tam giác được xây dựng phù hợp với hình chiếu của các điểm trên mặt phẳng xy và được kéo lên điểm dữ liệu 3 chiều gốc. Việc này vô cùng hữu ích khi làm việc với địa hình GIS. Thay vì chiếu các điểm 3 chiều và duy trì một ánh xạ giữa các điểm với hình chiếu của nó (mất rất nhiều không gian và dễ bị lỗi), lớp traits cung cấp predicate hình học được mà bỏ đi tọa độ z của điểm. Xem mục  37.5 làm ví dụ. CGAL còn cung cấp lớp traits hình học Projection_traits_yz_3<R> và Projection_traits_xz_3<R> để làm việc với hình chiếu trên mặt phẳng yz và xz tương ứng.

37.4.2 Ví dụ về một lưới tam giác cơ bản

Chương trình sau đây tạo ra một lưới tam giác của các điểm 2D, sử dụng kernel mặc định Exact_predicate_inexact_constructions_kernel như là một traits hình học và cấu trúc lưới tam giác mặc định. Dữ liệu tọa độ điểm được đọc từ tệp tin và chèn vào lưới tam giác. Cuối cùng, điểm trên đường bao được viết ra bằng lệnh cout.

File: examples/Triangulation_2/triangulation_prog1.cpp

#include <fstream>

#include <cgal xact_predicates_inexact_constructions_kernel.h="">
#include <cgal riangulation_2.h="">

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;

typedef CGAL::Triangulation_2<k>         Triangulation;
typedef Triangulation::Vertex_circulator Vertex_circulator;
typedef Triangulation::Point             Point;

int main() {
  std::ifstream in("data/triangulation_prog1.cin");
  std::istream_iterator<point> begin(in);
  std::istream_iterator<point> end;

  Triangulation t;
  t.insert(begin, end);

  Vertex_circulator vc = t.incident_vertices(t.infinite_vertex()),
    done(vc);
  if (vc != 0) {
    do { std::cout << vc->point() << std::endl;
    }while(++vc != done);
  }
  return 0;
}

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