Tạo sơ đồ Voronoi bằng thuật toán Fortune

Tạo sơ đồ Voronoi

• Sơ đồ Voronoi là gì?

  • Sơ đồ Voronoi là một cách chia mặt phẳng thành nhiều vùng, thường được dùng để tạo bản đồ theo quy trình thủ tục.
  • Chọn nhiều điểm trên mặt phẳng, gọi là 'site', và vùng tương ứng với mỗi site là vùng chứa mọi điểm gần site đó nhất.
  • Ranh giới của mỗi vùng được tạo thành từ các điểm cách đều hai site. Điểm cách đều ba site được gọi là 'đỉnh Voronoi'.

• Thuật toán Fortune

  • Thuật toán Fortune là phương pháp tạo sơ đồ bằng cách dùng một đường quét di chuyển từ trái sang phải trên mặt phẳng.
  • Khi đường quét gặp một site, một 'bubble' (cung parabol) được tạo ra xung quanh nó, và bubble sẽ lớn dần khi đường quét đi xa hơn.
  • Khi các cung của hai site va vào nhau, điểm va chạm đó trở thành ranh giới của các ô.
  • Ranh giới của tất cả các bubble đang hoạt động được gọi là 'beachline'.

• Giải thích thuật ngữ

  • Site: Một điểm 2 chiều, quyết định hình dạng của sơ đồ Voronoi.
  • Đường quét: Một đường thẳng đứng cắt qua vùng, xử lý từng sự kiện trong hàng đợi sự kiện.
  • Beachline: Một đường gồm nhiều cung, trong đó các cung sẽ được thêm hoặc xóa khi sự kiện được xử lý.
  • Giao điểm: Điểm nơi hai cung của beachline gặp nhau, cách đều các site liên quan.
  • Hàng đợi sự kiện: Nơi lưu các sự kiện site và circle, được sắp xếp theo thứ tự tăng dần của tọa độ x.
  • Sự kiện site: Một trong hai loại sự kiện trong hàng đợi, được xác định bởi tọa độ của site tương ứng.
  • Sự kiện circle: Loại sự kiện còn lại trong hàng đợi, được xác định bởi ba cung nằm trên chu vi của một đường tròn.
  • Đỉnh Voronoi: Điểm cách đều ba site, là góc của một ô.
  • Ranh giới đẳng cự: Đường thẳng gồm các điểm cách đều hai site.
  • Ranh giới chưa hoàn chỉnh: Một đường có một đầu là điểm cố định, còn đầu kia được xác định bởi giao điểm của hai tiêu điểm parabol.

• Tiếp tuyến của parabol

  • Khái niệm và tính chất của parabol rất quan trọng trong thuật toán này.
  • Parabol được xác định bởi một điểm tiêu và một đường thẳng (directrix).
  • Nếu đặt tiêu điểm là hai site và dùng đường quét làm directrix, ta có thể tìm đường ranh giới cách đều hai site bằng cách tìm giao điểm của hai parabol.

• Quay lại với beachline

  • Beachline là 'ranh giới' của tất cả các cung tại một vị trí xác định của đường quét.
  • Mỗi cung có thể được biểu diễn bằng điểm tiêu của site.
  • Beachline có thể được biểu diễn như một chuỗi điểm đơn giản.

• Cung mới được tạo khi đường quét gặp một site mới

  • Beachline là một chuỗi điểm, trong đó mỗi điểm biểu diễn một site và một cung.
  • Khi đường quét gặp một site mới, một cung mới được tạo và chèn vào chuỗi.

• Ranh giới giao nhau và đường tròn ngoại tiếp

  • Khi ba site nằm trên chu vi một đường tròn, tâm của đường tròn đó cách đều cả ba điểm.
  • Tâm đường tròn ngoại tiếp sẽ trở thành một đỉnh Voronoi.

• Ranh giới chưa hoàn chỉnh

  • Ranh giới chưa hoàn chỉnh có một đầu là điểm cố định, đầu còn lại là giao điểm của hai cung.
  • Khi hai ranh giới chưa hoàn chỉnh va vào nhau, một đỉnh Voronoi được tạo ra và các ranh giới chưa hoàn chỉnh được chuyển thành nửa cạnh.

• Chỉ các đường tròn theo chiều ngược kim đồng hồ mới tạo ra sự kiện circle

  • Chỉ khi ba cung được đọc theo chiều ngược kim đồng hồ thì một sự kiện circle mới được tạo.

• Tóm tắt

  • Khi có một tập site, hãy đưa tất cả các điểm site vào hàng đợi dưới dạng sự kiện 'site' và sắp xếp theo giá trị x.
  • Trong khi hàng đợi chưa rỗng, lấy sự kiện tiếp theo ra khỏi hàng đợi và xử lý.
  • Nếu là sự kiện site, thêm một cung mới vào beachline và tạo ranh giới chưa hoàn chỉnh.
  • Nếu là sự kiện circle, thêm một đỉnh Voronoi và xóa cung khỏi beachline.