Tạo biểu đồ Voronoi bằng thuật toán Fortune

 (redpenguin101.github.io)
2 điểm bởi GN⁺ 2025-02-10 | 1 bình luận | Chia sẻ qua WhatsApp
  • Fortune’s Algorithm có thể tạo biểu đồ Voronoi trong thời gian O(n log n), nhưng khó triển khai; trừ khi cần tạo lặp lại các biểu đồ quy mô lớn, cách triển khai O(n²) hoặc dùng thư viện sẽ thực tế hơn
  • Biểu đồ Voronoi chia mặt phẳng thành các vùng gần nhất dựa trên nhiều site; ranh giới được tạo bởi các điểm cách đều hai site
  • Thuật toán duy trì sweep line di chuyển từ trái sang phải và beachline là tiền tuyến của các cung parabol, và chỉ xử lý site event cùng circle event
  • site event chèn một cung mới để chia cung hiện có và tạo incomplete edge; circle event loại bỏ cung ở giữa đồng thời hoàn tất Voronoi Vertex và half edge
  • Trong triển khai thực tế, cần xử lý đồng thời event queue, beachline, bản đồ incomplete edge và DCEL; việc loại bỏ circle event không hợp lệ và dọn dẹp các edge còn lại làm độ phức tạp tăng đáng kể

Độ khó triển khai và phạm vi áp dụng

  • Fortune’s Algorithm là thuật toán tạo biểu đồ Voronoi trong thời gian O(n log n)
  • Nếu mục đích là sử dụng thực tế, nên cân nhắc quy mô yêu cầu trước thay vì triển khai ngay
    • Nếu không phải tạo nhiều biểu đồ lớn mỗi giây, cách triển khai O(n²) có thể là lựa chọn dễ hơn
    • Phương án thực tế hơn là dùng thư viện sẵn có
  • Kết quả hoạt động của thuật toán khá thú vị về mặt trực quan, nhưng quá trình triển khai thì khó và dễ gây nản

Khái niệm cơ bản về biểu đồ Voronoi

  • Biểu đồ Voronoi là một cách chia mặt phẳng thành nhiều vùng, thường được dùng trong sinh bản đồ theo thủ tục
  • Các điểm được chọn làm đầu vào được gọi là site hoặc seed
  • cell tương ứng với mỗi site là tập hợp các điểm trên mặt phẳng gần site đó nhất
  • Ranh giới của cell gồm các điểm cách đều hai site
  • Voronoi Vertex, nơi các cạnh của cell gặp nhau, là điểm cách đều ba site

sweep line, beachline, event

  • Fortune’s Algorithm sử dụng sweep line, một đường thẳng đứng di chuyển từ trái sang phải
  • Khi sweep line gặp một site, một cung parabol có site đó làm tiêu điểm được tạo ra; khi sweep line đi xa hơn, cung sẽ lớn dần
  • Điểm giao nhau của hai cung thuộc hai site khác nhau cách đều hai site, nên trở thành ranh giới của các cell
  • Khi hai ranh giới gặp nhau, một đỉnh của biểu đồ được tạo ra
  • Tiền tuyến của các cung đang hoạt động được gọi là beachline
  • Triển khai thực tế không di chuyển sweep line theo từng pixel, mà chỉ xử lý các điểm cụ thể có thể tính toán được, gọi là event
    • site event: được định nghĩa bởi tọa độ site đã biết trước; khi xử lý, một cung mới được thêm vào beachline
    • circle event: được định nghĩa bởi ba cung trên beachline; khi xử lý, một cung bị loại bỏ và Voronoi Vertex cùng half edge được tạo ra

Tìm ranh giới bằng parabol

  • Trong thuật toán, parabol không được xử lý theo dạng thông thường y = ax^2 + bx + c, mà theo locus definition
  • Một parabol được định nghĩa bởi một focus point và một directrix
    • focus point là site
    • directrix là sweep line
  • Giao điểm của hai parabol dùng cùng một sweep line làm directrix cách đều hai site
  • Vì vậy, tìm giao điểm của hai parabol sẽ tìm được equiedge giữa hai site
  • Bài viết sử dụng mã giả để tính tọa độ x của parabol, cùng ví dụ về việc giao điểm của hai parabol di chuyển dọc theo ranh giới khi vị trí sweep line thay đổi

Biểu diễn beachline và xử lý site event

  • Mỗi cung của beachline có thể được biểu diễn chỉ bằng tọa độ của site tương ứng
    • sweep line được áp dụng chung cho tất cả các cung
    • Trong triển khai, cung được xử lý như một tọa độ 2D thay vì một đối tượng riêng
  • beachline có thể được biểu diễn bằng một thứ tự đơn giản của các điểm
    • Ví dụ: [arc1, arc2], [arc1, arc2, arc3]
    • Cung của cùng một site có thể xuất hiện nhiều lần trên beachline
    • Ví dụ: [arc1, arc3, arc1, arc2]
  • Khi site event xảy ra, thuật toán tìm cung trên beachline mà một đường kẻ sang trái từ site mới sẽ gặp, rồi cung mới chia tách cung đó
  • Nếu site mới L chia j trong beachline hiện có [.., i, j, k, ..], cấu trúc trở thành [.., i, j, L, j, k, ..]
  • Các site được đưa vào hàng đợi theo thứ tự tọa độ x, và mỗi lần được xử lý, beachline cùng các ứng viên event được cập nhật

circle event và circumcircle

  • Trong ba cung [.., i, j, k, ..] trên beachline, nếu xuất hiện tình huống hai ranh giới gặp nhau thì cung ở giữa j biến mất
  • Khi đó tồn tại một circumcircle đi qua ba site, và tâm của đường tròn cách đều ba site
  • Tâm của circumcircle trở thành Voronoi Vertex
  • circle event được đưa vào event queue dựa trên circle point, là điểm ngoài cùng bên phải của đường tròn
  • Nếu một site mới được phát hiện bên trong đường tròn trước khi sweep line đạt tới circle point, circle event hiện có sẽ trở nên không hợp lệ
    • Vì site mới chia cung ở giữa trước, tổ hợp ba cung không còn được duy trì
    • triple cũ i, j, k biến mất và cần kiểm tra các triple mới như i, j, L, L, j, k

incomplete edge và half edge

  • incomplete edge là một đường có một đầu đã cố định, còn đầu kia được định nghĩa bởi giao điểm của hai cung parabol
  • Khi một cung mới được chèn bởi site event, hai incomplete edge được tạo ra
    • Điểm cố định là tọa độ nơi cung mới gặp beachline hiện có
    • Nếu cung mới j chia cung hiện có i, sẽ tạo ra các edge tương ứng với giao điểm [i, j], [j, i]
  • Khi hai incomplete edge va chạm tại circle event, điểm va chạm đó trở thành Voronoi Vertex
  • incomplete edge hiện có được hoàn tất thành half edge tại điểm này, và một incomplete edge mới được tạo giữa hai cung vừa trở thành kề nhau

Chỉ các đường tròn ngược chiều kim đồng hồ mới trở thành circle event

  • Khi beachline có [i, j, k, j, i], cả ijk và kji đều có thể tạo thành đường tròn, nhưng không phải cả hai đều là circle event hợp lệ
  • Cung ở giữa chỉ biến mất ở phía mà các ranh giới thực sự hội tụ
  • Trong chương trình, orientation của ba điểm được xác định bằng determinant
    • Nếu determinant âm thì là ngược chiều kim đồng hồ và trở thành circle event
    • Nếu determinant dương thì là theo chiều kim đồng hồ và không phải circle event
    • Nếu determinant bằng 0 thì ba điểm thẳng hàng nên không có đường tròn

Luồng tổng thể của thuật toán

  • Sắp xếp các site đầu vào theo tọa độ x và đưa vào hàng đợi dưới dạng site event
  • Lấy event tiếp theo ra xử lý cho đến khi hàng đợi rỗng
  • Xử lý site event:
    • Loại bỏ các circle event còn lại trong tương lai mà site mới nằm bên trong đường tròn
    • Tìm cung trên beachline mà site mới sẽ chia
    • Chèn cung mới để chia cung hiện có
    • Thêm hai incomplete edge
    • Kiểm tra xem các triple mới được tạo có thể tạo circle event hay không
  • Xử lý circle event:
    • Thêm tâm circumcircle làm Voronoi Vertex
    • Loại bỏ cung ở giữa khỏi beachline
    • Loại bỏ các circle event trong tương lai trở nên không hợp lệ do cung bị xóa
    • Kiểm tra các triple của những cung mới trở thành kề nhau và thêm circle event
  • Khi hàng đợi rỗng, kéo dài các incomplete edge còn lại đến biên của biểu đồ và tạo Voronoi Vertex tại các điểm gặp biên

Cấu trúc dữ liệu trong triển khai Odin

  • Triển khai ví dụ được viết bằng Odin, một ngôn ngữ thay thế C
  • Toàn bộ mã nằm trong kho RedPenguin101/voronoi
  • Các kiểu cơ bản:
    • V2: điểm 2D dạng [2]int
    • PointPair: cặp gồm hai V2
    • Event: struct {site: bool, a, b, c: V2}
  • Ý nghĩa của Event thay đổi tùy theo loại
    • Với site event, a là tọa độ site, còn b, c không được dùng
    • Với circle event, a, b, c là ba cung trên beachline đã tạo ra event
  • Struct Fortune quản lý các trạng thái sau
    • beachline: mảng V2
    • queue: mảng Event
    • incomplete_edges: map PointPair -> V2
    • vd: DCEL lưu Voronoi Diagram

Các phần bị lược bỏ hoặc đơn giản hóa trong triển khai

  • beachline được biểu diễn bằng vector, nhưng để tăng hiệu quả thì binary tree phù hợp hơn
  • Về mặt khái niệm, event queue cũng là priority queue, nhưng trong triển khai ví dụ, nó được xử lý bằng cách chèn có sắp xếp vào mảng
  • Việc vô hiệu hóa circle event được thực hiện bằng cách duyệt và kiểm tra các event tương lai, và có TODO cho việc cần một cách nhanh hơn
  • clean_beachline_edges là quy trình cắt bỏ các cung không cần thiết ở hai đầu beachline
  • Triển khai có bao gồm xử lý ngoại lệ như các site có cùng tọa độ x, trường hợp circle point trùng với site, và xung đột điểm tham chiếu
  • Bước cuối cùng để dọn dẹp các incomplete edge còn lại, half edge không có twin và vertex sau khi hàng đợi rỗng chỉ được xử lý như các phép toán toán học đơn giản

Lưu biểu đồ Voronoi bằng DCEL

  • Biểu đồ Voronoi thường được lưu bằng Doubly Connected Edge List(DCEL)
  • DCEL là cấu trúc dữ liệu biểu diễn cell-complex theo cách dễ thao tác, gồm vertex và edge
  • Tuy là biểu diễn lấy edge làm trung tâm, nó cũng lưu cả thông tin vertex và face
  • Edge thông thường không có hướng, nhưng trong DCEL, mỗi edge được lưu dưới dạng hai half edge theo hai chiều
  • Trong biểu đồ Voronoi, vertex được lưu trong DCEL không phải là site mà là Voronoi Vertex
  • Đích của edge E được lấy bằng E.twin.origin, và face bên phải được lấy bằng E.twin.left

Bài viết liên quan

1 bình luận

 
GN⁺ 2025-02-10
Ý kiến trên Hacker News

  • Trước đây tôi từng làm một bản triển khai bằng ClojureScript có hoạt ảnh minh họa cách thuật toán Fortune vận hành: https://voronoi.ajwerner.net/#/app-diagrams
    Đây thực sự là một thuật toán rất đẹp
    Nhưng sau dự án đó thì tôi hơi ghét thuật toán Fortune, vì độ ổn định số dấu phẩy động của nó không tốt
    Nếu các điểm nằm thẳng hàng hoặc gần như thẳng hàng theo chuẩn dấu phẩy động thì nó có thể bị hỏng
    Nếu tôi nhớ không nhầm thì ở điểm này delaunator tốt hơn: https://github.com/mapbox/delaunator

    • Hoạt ảnh này là bản đẹp nhất tôi từng thấy
      Tôi thấy có liên kết đến bản triển khai “old” trên trang tham khảo, nên muốn hỏi liệu bản hoạt ảnh hiện tại có khả năng được công bố dưới dạng mã nguồn mở hay không

  • Vài năm trước tôi đã làm một bản trực quan hóa 3D kiểu này: https://x.com/KangarooPhysics/status/1253336959755251716

  • Có một bản triển khai JavaScript của Raymond Hill, người nổi tiếng với uBlock Origin: https://github.com/gorhill/Javascript-Voronoi
    Tôi đã chỉnh sửa nó một chút để làm cho nó chuyển động: https://animations.adgent.com/voronoi.html

    • Hoạt ảnh này gợi nhớ đến phong cách của A Scanner Darkly (2006)
      Tôi tự hỏi liệu có thể đưa video làm đầu vào rồi áp dụng một thuật toán hiển thị theo kiểu Voronoi hay không
      Đến mức đó thì về mặt chặt chẽ có thể nó không còn là sơ đồ Voronoi nữa, nhưng trông có lẽ sẽ khá ngầu

  • D3.js có một bản triển khai mới: https://github.com/d3/d3-delaunay
    Ở phần cuối trang đó có giải thích về thuật toán quét được sử dụng và danh sách các bản triển khai bằng những ngôn ngữ khác ngoài JavaScript
    d3-voronoi cũ đang bị loại bỏ dần, nhưng vẫn có thể xem tại đây: https://github.com/d3/d3-voronoi

  • Nếu bạn không quan tâm đến các cạnh mà chỉ cần tô mỗi vùng của từng điểm bằng một màu khác nhau, thì có thể dùng một biến thể của flood fill bắt đầu từ các điểm hạt giống
    Chỉ cần đưa pixel vào stack khi khoảng cách của màu đó ngắn hơn màu đã được tô trên pixel đó

    • Có thể dựng một cảnh 3D với các nón vuông góc có màu khác nhau, mỗi nón có đỉnh đặt tại một đỉnh trên mặt phẳng 2D và trục dựng vuông góc với mặt phẳng
      Nếu render bằng phép chiếu trực giao 2D từ phía trên các đỉnh, thì z-buffer sẽ giữ lại pixel của đỉnh gần nhất
      Có lẽ cũng có thể làm bằng shader, nhưng demo nón 3D kiểu cổ điển thì rất dễ hiểu và dễ triển khai

  • Thật thú vị khi D3 đã chuyển từ thuật toán Fortune sang https://mapbox.github.io/delaunator/
    Lý do là nó “nhanh hơn 5~10 lần so với d3-voronoi khi tạo phép tam giác hóa Delaunay hoặc sơ đồ Voronoi, vững hơn về mặt số học, tích hợp sẵn render Canvas, đồng thời cung cấp khả năng duyệt đồ thị Delaunay và nhiều cải tiến khác”

    • Nếu D3 cho rằng delaunator là lựa chọn tốt nhất cho hiệu ứng kiểu này, thì giờ tôi chẳng còn lý do nào để không thêm nó vào thư viện canvas của mình ngoài thói quen trì hoãn rất tự nhiên
      Đoạn mã hiện tại dùng để tính các ô lát thực sự ngây thơ đến mức đau khổ
      Thảo luận mới: https://github.com/KaliedaRik/Scrawl-canvas/discussions/120

  • Bài này làm tôi phải đi tìm xem dạo này Steve đang ở đâu
    Chúng tôi quen biết nhau từ vài chục năm trước

  • Một bài liên quan đáng xem: https://news.ycombinator.com/item?id=37998923 - Dùng thuật toán Fortune để tạo sơ đồ Voronoi và phép tam giác hóa Delaunay trong O(n log n) (2020)
    Bài trước đó và phần thảo luận cũng có phần tóm tắt ngắn về các thuật toán khác
    Cá nhân tôi vẫn thích nhất Jump Flooding Algorithm: https://en.wikipedia.org/wiki/Jump_flooding_algorithm