Diagramy Voronoiego: Algorytm Fortune'a z przetwornikiem linii, triangulacja Delaunaya i relaksacja Lloyd'a

Definicja i właściwości

Niech P = {p₁, …, pₙ} będzie n różnymi punktami ziarnowymi w ℝ². Wielokąt Voronoi dla ziarna pᵢ to V(pᵢ) = {x ∈ ℝ² | d(x, pᵢ) ≤ d(x, pⱼ) dla wszystkich j ≠ i}, domyślnie używając odległości euklidesowej (innym metrykom przypadają warianty ekstremalne). Granice między sasiednimi wielokątami są bisektory — każda krawędź jest prostopadłą bisektrzyną dwóch ziarn — a trzy wielokąty spotykają się w wierzchołku Voronoi, czyli okregu opisanego na trójkącie utworzonym przez te trzy ziarna. Jako przecięcie półprostych, każdy wielokąt Voronoi jest konvexny, a dla równomiernego procesu punktów Poissona średni wielokąt ma dokładnie 6 boków.

Z siłowej metody do skanowania linii Fortune'a

Najprostszym podejściem jest siłowa metoda najbliższego sąsiada: dla każdego piksela przeszukujemy wszystkie n siedzic i kolorujemy go kolorem najbliższego z nich — O(W·H·n), dobre dla małych n, ale nieefektywne na wysokiej rozdzielczości przy tysiącach siedzi. Algorytm Stevena Fortune'a z 1987 roku oblicza dokładny diagram w czasie O(n log n) przez skanowanie poziomej linii w dół po płaszczyźnie, utrzymując kolejkę zdarzeń (zdarzenia siedziczne i okręgowe) oraz linię plażową z parabolicznych łuków — każdy łuk to zbiór punktów równo odległych od jednego siedzic i linii skanującej. Gdy zdarzenie siedzyczne wywołuje się, łuk powyżej nowego siedziczka podzieli się na dwa i wstawiony zostanie nowy łuk; gdy zdarzenie okręgowe wywołuje się, trzy konvergujące łuki zredukują się do wierzchołka Voronoi.

Algorithm              Time            Space   Notes
Brute force (raster)   O(W·H·n)        O(W·H)  Simple; GPU-parallel
Fortune's algorithm    O(n log n)      O(n)    Exact; reference implementation
Bowyer-Watson (dual)   O(n log n) avg  O(n)    Via Delaunay triangulation

Triangulacja Delaunaya — graf dualny

Triangulacja Delaunaya DT(P) jest prostopadłościanowym dualnym diagramowi Voronoi: łączymy dwa semeny, gdy ich obszary komórkowe dzielą wspólną krawędź. Jej kluczowym celem jest kryterium pustego okręgu opisanego — żaden semente nie leży wewnątrz pustego okręgu opisanego żadnej trójkąta z DT(P) — co sprawia, że maksymalizuje ona najmniejszy kąt wśród wszystkich możliwych triangulacji zbioru punktów, dokładnie dlatego jest standardowym wyborem dla siatek elementów skończonych i siatek numerycznych symulacji, gdzie trójkąty o niewielkiej długości boku (sliver) zdegradowują dokładność. Algorytm Bowyer-Watson zwiększony w czasie dodaje punkty jeden po drugim, usuwając wszystkie trójkąty, których okrąg opisany zawiera nowy punkt i ponownie triangulując powstałą dziurę.

Relaksacja Lloyd'a — tesselaacja Voronoiego centroidalna

Tesselaacja Voronoiego centroidalna (CVT) to specjalny diagram Voronoiego, w którym każdy semen zbiega się ze środkiem ciężkości własnej komórki. Algorytm Lloyd'a iteruje w kierunku CVT poprzez alternację: obliczenie diagramu Voronoiego dla bieżących semen, a następnie przesunięcie każdego semena do środka ciężkości — średniej ważonej pozycji — swojej komórki. Po 10-30 iteracjach semeny rozkładają się równomiernie, tworząc charakterystyczny wzór podobny do foamy, z równymi polemi heksagonalnymi, znaleziony w tkaninach biologicznych, districtingu geograficznym i halftoningu. Przy relaksacji ważenie każdego piksela przez ciemność obrazu prowadzi do stipplinga Voronoiego, techniki wzorcowania punktowego popularizowanej w 2002 roku przez Adrian Secorda.

Zastosowania w naukach, grach i visualizacji

Wspólnie z grafem Delaunaya, dokładne zapytania o najbliższy sąsiad wykonują się w O(log n). Generatory terenów proceduralnych dzielą płaszcźcz na wielokąty „ płyt ” lub biomy za pomocą diagramów Voronoiego i relaksacji Lloyd'a, przypisując wysokość i wilgotność do każdego komórkowego pola, co tworzy w chwili urodzenia geografię prawdopodobną. Komórki biologiczne — tkanina epitelium, foamy z mydła, gruczoły — wszystkie przybliżają diagramy Voronoiego, z siedzeniem w jądrze komórki. W lokalizacji infrastruktury znalezienie n lokali magazynowych, które minimalizują średnią odległość do klientów, jest dokładnie problemem tessellationa Voronoiego centrów, a w fizyce czasowej, symulacje rozpadu używają komórek Voronoiego, aby zdefiniować kawałki rozpadu, przycinając siatkę po granicach komórkowych.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Voronoi Diagram i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.