Sơ đồ Voronoi

Sơ đồ Voronoi của một tập hợp các điểm được chọn ngẫu nhiên trên mặt phẳng (tất cả các điểm này đều nằm trong hình vẽ).

Trong toán học, một sơ đồ Voronoi, đặt tên theo nhà toán học người Nga Georgy Voronoi, là một cách phân tách một không gian mêtric theo khoảng cách tới một tập hợp rời rạc các vật thể cho trước trong không gian. Tập hợp các vật thể có thể là tập hợp rời rạc các điểm. Trong ngành thủy văn, sơ đồ này còn được gọi là đa giác Thiessen theo tên nhà khí tượng học người Mỹ Alfred H. Thiessen.

Trong trường hợp đơn giản nhất, khi các vật thể là các điểm, ta có một tập hợp S gồm các điểm trên mặt phẳng, được gọi là các điểm Voronoi. Mỗi điểm s ứng với một ô Voronoi, hay còn gọi là ô Dirichlet, ký hiệu là V(s), bao gồm tất cả các điểm gần s hơn tất cả các điểm Voronoi khác. Các cạnh của sơ đồ Voronoi là tập các điểm có khoảng cách tới hai điểm Voronoi gần nhất là như nhau. Các đỉnh của sơ đồ Voronoi là các điểm có khoảng cách tới ít nhất ba điểm Voronoi gần nhất là như nhau.

Các tính chất

[sửa | sửa mã nguồn]
  • Đồ thị đối ngẫu của sơ đồ Voronoi trên mặt phẳng là lưới tam giác Delaunay cho cùng một tập hợp điểm.
  • Hai điểm gần nhất trong tập hợp điểm tương ứng với hai ô Voronoi liền kề nhau.
  • Hai điểm liền kề nhau trên bao lồi khi và chỉ khi các ô Voronoi của chúng có một cạnh chung có độ dài vô hạn.

Các thuật toán

[sửa | sửa mã nguồn]

Thuật toán Fortune có thể xây dựng sơ đồ Voronoi cho n điểm trên mặt phẳng trong thời gian O(n log(n))[1].

Sơ đồ Voronoi của n điểm trong không gian Euclide d chiều đòi hỏi bộ nhớ để lưu trữ. Trong trường hợp sai số nhỏ là chấp nhận được, có thể sử dụng sơ đồ Voronoi xấp xỉ, trong đó mỗi điểm nằm trong ô Voronoi của điểm Voronoi gần nhất hoặc xấp xỉ gần nhất[2].

Trong thủy văn

[sửa | sửa mã nguồn]
Một lưu vực có 9 trạm mưa

Trong ngành thủy văn, sơ đồ Voronoi được ứng dụng như là một phương pháp được dùng để tính lượng mưa bình quân lưu vực và được gọi là đa giác Thiessen.

Cơ sở của phương pháp là: nếu một lưu vực có nhiều trạm mưa thì mưa tại một điểm bất kì trên lưu vực sẽ coi bằng lượng mưa đo đạc được tại trạm mưa gần đó nhất.

Trên bản đồ lưu vực có các trạm mưa có thể kẻ các đường trung trực giữa tất cả các cặp trạm mưa lân cận nhau. Tập hợp các đường trung trực này cùng với biên của lưu vực tạo thành các đa giác Thiessen.

Trong trường hợp tổng quát, trạm mưa không nhất thiết phải nằm trong lưu vực, miễn là đa giác chứa trạm mưa đó có phần diện tích nằm trong lưu vực.

Như vậy với một lưu vực có nhiều trạm đo mưa sẽ có lượng mưa trung bình trên toàn lưu vực là trung bình có trọng số của các lượng mưa tại các trạm thành phần với trọng số tỉ lệ với diện tích của hình đa giác chứa trạm mưa đó.

trong đó:

  • f1, f2... các diện tích đa giác thành phần
  • X1, X2... lượng mưa các trạm thành phần
  • F: diện tích toàn bộ lưu vực
  • : lượng mưa trung bình của lưu vực
  1. ^ Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf (2000). Computational Geometry (ấn bản thứ 2). Springer-Verlag. ISBN 3-540-65620-0.Quản lý CS1: sử dụng tham số tác giả (liên kết) Chương 7: Voronoi Diagrams: pp. 147–163. Có mô tả thuật toán Fortune.
  2. ^ S. Arya, T. Malamatos, D. M. Mount. “Space-Efficient Approximate Voronoi Diagrams” (PDF). Proc. 34th ACM Symp. on Theory of Computing (STOC 2002). tr. 721–730.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)

Liên kết ngoài

[sửa | sửa mã nguồn]

(tiếng Anh)

Chúng tôi bán
Bài viết liên quan
Giới thiệu nhân vật Kaeya Alberich - Genshin Impact
Giới thiệu nhân vật Kaeya Alberich - Genshin Impact
Đêm mà Kaeya Alberich nhận được Vision trời đổ cơn mưa to
GPS Là gì? Có phải bạn luôn bị theo dõi khi bật định vị trên điện thoại?
GPS Là gì? Có phải bạn luôn bị theo dõi khi bật định vị trên điện thoại?
Phát triển bởi quân đội Mỹ nhưng tín hiệu GPS được cung cấp miễn phí cho tất cả mọi người.
Có thật soi gương diện mạo đẹp hơn 30% so với thực tế?
Có thật soi gương diện mạo đẹp hơn 30% so với thực tế?
Lúc chúng ta soi gương không phải là diện mạo thật và chúng ta trong gương sẽ đẹp hơn chúng ta trong thực tế khoảng 30%
Nhân vật Entoma Vasilissa Zeta - Overlord
Nhân vật Entoma Vasilissa Zeta - Overlord
Entoma Vasilissa Zeta (エ ン ト マ ・ ヴ ァ シ リ ッ サ ・ ゼ ー タ, εντομα ・ βασιλισσα ・ ζ) là một chiến hầu người nhện và là thành viên của "Pleiades Six Stars," đội chiến hầu của Great Tomb of Nazarick. Cô ấy được tạo ra bởi Genjiro.