37.5 Lưới tam giác Delaunay

37.5.1   Giới thiệu

Lớp Delaunay_triangulation_2<Traits,Tds>  được thiết kế để đại diện cho lưới tam giác Delaunay tạo từ một tập hợp điểm trong mặt phẳng. Một lưới tam giác Delaunay thỏa mãn điều kiện vòng rỗng - empty circle property (còn gọi là điều kiện Delaunay property): bên trong đường tròn ngoại tiếp circumscribing của tam giác không chứa bất kỳ điểm nào của lưới của lưới tam giác đó. Với một tập hợp điểm được thiếp lập mà không có tập con của bốn điểm đồng tròn, lưới tam giác Delaunay là duy nhất, nó tương ứng với đường Vorôni về tập hợp các điểm. Lớp Delaunay_triangulation_2<Traits,Tds> dẫn xuất ra từ lớp Triangulation_2<Traits,Tds>.

Lớp Delaunay_triangulation_2<Traits,Tds>kế thừa các kiểu được định nghĩa bởi lớp cơ bản Triangulation_2<Traits,Tds>. Kiểu bổ sung, cung cấp bởi lớp traits, được định nghĩa để thể hiện sơ đồ Voronoi.

Lớp Delaunay_triangulation_2<Traits,Tds> ghi đè lên các hàm hành viên chịu trách nhiệm chèn, di chuyển hay loại bỏ một điểm từ lưới để duy trì điều kiện Delaunay. Nó cũng có hàm thành viên  (Vertex_handle nearest_vertex(const Point& p)) để trả lời yêu cầu tìm kiếm hàng xóm gần nhất và hàm thành viên để xây dựng các phần tử (đỉnh và cạnh) của sơ đồ Voronoi kép.

Trait hình học - Geometric traits

Trait hình học là một mô hình của khái niệm DelaunayTriangulationTraits_2 đã được nâng cao từ TriangulationTraits_2. Đặc biệt, khái niệm này cung cấp predicate side_of_oriented_circle cái mà cho trước 4 điểm p,q,r,s quyết định vị trí của các điểm với đường tròn đi qua 3 điểm p, q và r. Predicate side_of_oriented_circle đã xác định lưới tam giác Delaunay thật sự. Việc thay đổi predicate cho phép xây dựng các biến thể của lưới tam giácDelaunay cho các hệ đo lường khác nhau như L₁ hoặc L_∞ hoặc bất kỳ metric nào được định nghĩa bởi đối tượng lồi nào. Tuy nhiên, người dùng một hệ đo khác phải cẩn thận rằng lưới tam giác được xây dựng phải là một lưới của đường bao lồi nghĩa là đường bao lòi phải là một cạnh Delaunay. Nó được cấp cho bất cứ hệ đo lồi mịn (như L₂) và có thể được đảm bảo cho hệ đo khác (như L_∞) bởi sự bổ sung đến tập hợp điểm của các điểm bao bên ngoài (sentinel point). Các lớp kernel CGAL và lớp Triangulation_euclidean_traits_2<R>là các mô hình của khái niệm DelaunayTriangulationTraits_2 cho hệ hình học Ơ-clit (euclidean). Lớp trait cho địa hình, Projection_traits_xy_3<R>,

Projection_traits_yz_3<R>, và
Projection_traits_xz_3<R>
đều là kiểu của DelaunayTriangulationTraits_2ngoại trừ việc chúng không thỏa mãn cả hai điều kiện hàm và truy vấn điểm gần nhất.

Thực thi

Chèn một điểm mới vào trong lưới Delaunay được thực hiện bằng cách sử dụng hàm thành viên chèn điểm của lưới tam giác cơ bản và tiếp đến tiến hành một chuỗi các phép đối xứng flip để khôi phục điều kiện Delaunay. Số lượng phép đối xứng phải thực hiện là O(d) nếu đỉnh mới có góc d trong lưới Delaunay cập nhật. Với các điểm phân bố một cách ngẫu nhiên, mỗi phép chèn mất một khoảng thời gian trung bình O(1), một khi điểm đã được định vị trong lưới. Việc gọi hàm loại bỏ trong lưới và trắc lượng lại lỗ hổng tạo ra sẽ làm cho tiêu chuẩn Delaunay được thỏa mãn. Việc loại bỏ đỉnh của góc d mất O(d²). Góc d là O(1) với một một điểm ngẫu nhiên trong lưới. Khi góc của điểm nhỏ hơn hoặc bằng ( ≤ 7) một thủ tục đặc biệt được sử dụng để cho phép gia tăng thời gian loại bỏ toàn cục bởi hệ số của 2 điểm ngẫu nhiên [Dev09].

Dịch chuyển của đỉnh v từ điểm p tới vị trị mới p',đầu tiên kiểm tra lưới được nhúng có còn đồng phẳng hay không sau khi dịch chuyển. Nếu có, việc di chuyển được tiến hành đơn giản bởi một chuỗi các phép đối xứng để xây dựng lại điều kiện Delaunay, cái mà là O(d) ở nơi d là góc đo của đỉnh sau khi dịch chuyển. Ngược lại, sự dịch chuyển được thực hiển bởi việc thêm một đỉnh tại vị trí mới và loại bỏ đỉnh cũ. Sự phức tạp là O(n) trong trường hợp xấu nhất, nhưng chỉ còn O(1 + δ√n) khi phân bố các đỉnh một cách đồng đều trong một đơn vị vuông, nơi δ là khoảng cách (Ơ-clit Euclidean) giữa vị trí mới và cũ.

Sau khi tiến hành định vị một điểm,  hàng xóm gần nhất của điểm được tìm thấy sau khoảng thời gian O(n) trong trường hợp xấu nhất, nhưng chỉ là O(1) nếu các đỉnh phân bố ngẫu nhiên.

37.5.2   Ví dụ: Địa hình Delaunay Terrain

Dưới đây là đoạn mã tạo một lưới tam giác Delaunay dựa trên hệ hình học Ơ-clit cho hình chiếu của mô hình địa hình. Các điểu có cao độ, là những điểm 3D, nhưng predicate được sử dụng để xây dựng lưới Delaunay được tính toán dựa trên tọa độ x và y của các điểm mà thôi.

Các lớp Projection_traits_xy_3<K> là một phần của Kernel hình học đồng phẳng 2D và 3D, và thay thế lớp Triangulation_euclidean_traits_xy_3<K>.

File: examples/Triangulation_2/terrain.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Projection_traits_xy_3.h>
#include <CGAL/Delaunay_triangulation_2.h>

#include <fstream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Projection_traits_xy_3<K>  Gt;
typedef CGAL::Delaunay_triangulation_2<Gt> Delaunay;

typedef K::Point_3   Point;

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

  Delaunay dt(begin, end);
  std::cout << dt.number_of_vertices() << std::endl;
  return 0;
}

37.5.3   Ví dụ: Sơ đồ Voronoi

Đoạn mã dưới đây có tác dụng tính toán các cạnh của sơ đồ Voronoi dựa trên tập điểm và in số lượng của các cạnh hữu hạn và số lượng tia của sơ đồ.

File: examples/Triangulation_2/voronoi.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>

#include <fstream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;

typedef CGAL::Delaunay_triangulation_2<K>  Triangulation;
typedef Triangulation::Edge_iterator  Edge_iterator;
typedef Triangulation::Point          Point;

int main( )
{
  std::ifstream in("data/voronoi.cin");
  std::istream_iterator<Point> begin(in);
  std::istream_iterator<Point> end;
  Triangulation T;
  T.insert(begin, end);

  int ns = 0;
  int nr = 0;
  Edge_iterator eit =T.edges_begin();
  for ( ; eit !=T.edges_end(); ++eit) {
    CGAL::Object o = T.dual(eit);
    if (CGAL::object_cast<K::Segment_2>(&o)) {++ns;}
    else if (CGAL::object_cast<K::Ray_2>(&o)) {++nr;}
  }
  std::cout << "The Voronoi diagram has " << ns << " finite edges "
            << " and " << nr << " rays" << std::endl;
  return 0;
}

37.5.4   Ví dụ: In đường Voronoi giới hạn bởi hình chữ nhật

Đoạn mã dưới đây có tác dụng tính toán lưới tam giác Delaunay dựa trên tập hợp điểm và in đường Voronoi được giới hạn bởi hình chữ nhật cho trước.


Figure 37.6:  Sơ đồ Voronoi (màu đỏ) của các điểm màu đen được giới hạn bởi hình chữ nhật xanh.

File: examples/Triangulation_2/print_cropped_voronoi.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <iterator>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef K::Iso_rectangle_2 Iso_rectangle_2;
typedef K::Segment_2 Segment_2;
typedef K::Ray_2 Ray_2;
typedef K::Line_2 Line_2;
typedef CGAL::Delaunay_triangulation_2<K>  Delaunay_triangulation_2;

//A class to recover Voronoi diagram from stream.
//Rays, lines and segments are cropped to a rectangle
//so that only segments are stored
struct Cropped_voronoi_from_delaunay{
  std::list<Segment_2> m_cropped_vd;
  Iso_rectangle_2 m_bbox;
  
  Cropped_voronoi_from_delaunay(const Iso_rectangle_2& bbox):m_bbox(bbox){}
  
  template <class RSL>
  void crop_and_extract_segment(const RSL& rsl){
    CGAL::Object obj = CGAL::intersection(rsl,m_bbox);
    const Segment_2* s=CGAL::object_cast<Segment_2>(&obj);
    if (s) m_cropped_vd.push_back(*s);
  }
  
  void operator<<(const Ray_2& ray)    { crop_and_extract_segment(ray); }
  void operator<<(const Line_2& line)  { crop_and_extract_segment(line); }
  void operator<<(const Segment_2& seg){ crop_and_extract_segment(seg); }
};

int main(){
  //consider some points
  std::vector<Point_2> points;
  points.push_back(Point_2(0,0));
  points.push_back(Point_2(1,1));
  points.push_back(Point_2(0,1));
  
  Delaunay_triangulation_2 dt2;
  //insert points into the triangulation
  dt2.insert(points.begin(),points.end());
  //construct a rectangle
  Iso_rectangle_2 bbox(-1,-1,2,2);
  Cropped_voronoi_from_delaunay vor(bbox);
  //extract the cropped Voronoi diagram
  dt2.draw_dual(vor);
  //print the cropped Voronoi diagram as segments
  std::copy(vor.m_cropped_vd.begin(),vor.m_cropped_vd.end(),
    std::ostream_iterator<Segment_2>(std::cout,"\n"));
}