Diagramy Voronoi: Przestrzeń najbliższego sąsiada, jeszcze bardziej zrównoważona

Każdy punkt w płaszczyźnie jest zwany najbliższym centrum

Rozrzucamy kilka punktów, nazywanych centrami, po płaszczyźnie. Dla każdego innego punktu na tej płaszczyźnie pytamy, który z nich jest najbliżej. Zbiór punktów najbliżej danego centrum — jego wielokąt Voronoi — to wielokąt wypukły, a cała kolekcja takich wielokątów dla wszystkich centrów tworzy diagram Voronoi. Granica między dwoma sąsiednimi wielokątami zawsze jest prostopadłym biegunem między tymi dwoma centrami, ponieważ ta linia biegunowa to dokładnie zbiór punktów równoodległych od obu centrów.

Zaprezentowany przez Georgy Voronoi, który formalizował ten konstrukcji w 1908 roku, diagram już wcześniej pojawiał się w szkicach Renisa o podziale przestrzeni wokół sąsiadujących gwiazd. Zachęca on do regularnych wzorów naturalnych: wielokątowe rysy kurzu zaschniętego, domeny rywalizujących kolonii bakteriowych na płyce do eksperymentów, oraz terenowe obszary zwierząt rozprzestrzeniających się od najbliższych konkurencji, ponieważ „ najbliżej mnie, najdalej od sąsiada” to dokładnie zasady matematyka zakodowała.

Obliczanie rastrowe: sztuczka, która działa

Klasyczny sposób na tworzenie dokładnego diagramu Voronoi polega na algorytmie Fortune'a z przesuwającą się linią, który działa w czasie O(n log n) i wydaje wielokąty bezpośrednio. Dla interaktywnej powierzchni rastrowej, prostszy, brutalnie proste podejście jest zwykle wystarczające: dla każdego piksela oblicz dystans do wszystkich n siedzib i koloruj go na podstawie najbardziej bliskiej z nich.

dla każdego piksela (x, y): najlepsze = infinity; właściciel = -1 dla i w zakresie 0..n-1: d = (x - siedziby[i].x)^2 + (y - siedziby[i].y)^2 // kwadratowy dystans, nie ma potrzeby obliczania pierwiastka jeśli d < najlepsze: najlepsze = d; właściciel = i piksel(x, y) = kolor[właściciel] To jest O(szerokość · wysokość · n) na ramkę, co brzmiałoby jako nadmiernie wydajne, ale jest łatwo szybkie na średnim rozdzielczym i liczbie siedzib w dzisiejszych systemach harwarej, a jednocześnie unikając wszystkich przypadków brzegowych dokładnych obliczeń wielokątów — degenerycyjnych siedzi wyrażonego na jednej linii, precyzji liczbowej przy granicach komórek — za darmo. Jest również prosto paralelny w stosunku do pikseli, co jest powodem, dla którego ten sam podejście naturalnie pasuje do shadera fragmentu GPU (wariant "piskotu skokowego" oblicza przybliżony diagram Voronoi na GPU w logarytmicznych przebiegach zamiast jednego przebiegu na siedzibę).

for each pixel (x, y):
  best = infinity; owner = -1
  for i in 0..n-1:
    d = (x - sites[i].x)^2 + (y - sites[i].y)^2   // squared distance, no sqrt needed
    if d < best: best = d; owner = i
  pixel(x, y) = colour[owner]

Algorytm Lloyd'a: relaksacja w stronę srodka masy

Diagram Voronoi zbudowany na losowych punktach zwykle wygląda nierównomiernie — niektóre komórki są gęste, a inne rozproszone. Algorytm Stuart Lloyd'a z 1957 roku (pierwotnie opracowany do kwantyzacji sygnałów analogowych, później ponownie odkryty dla generowania siatek i grafiki komputerowej) naprawia to za pomocą pięknego i prostego powtarzania: oblicza się diagram Voronoi, a następnie przesuwa każdy punkt do środka masy swojej własnej komórki, a następnie powtarza tę operację.

powtórz k razy: komórki = voronoi(punkty) dla i w zakresie 0..n-1: punkty[i] = środek masy obszaru (centroid) komórkę[i] Każda iteracja przyciąga diagram bliżej do tzw. diagramu Voronoi centroidalnego, czyli punktu stałego, w którym każdy punkt znajduje się dokładnie na swoim własnym centrum masy komórki. Wizualnie, komórki stają się równomiernie rozmiarowe, bardziej skompaktowane i krawędzie prostej do ułożenia w formę siedmiokątnego parkietu, który minimalizuje średni kwadratowy odstęp między dowolnym punktem w komórce a jej punktem. To samo problem optymalizacji, który występuje w kwantyzacji sygnałów, gdzie algorytm Lloyd'a znany jest jako kwantyzacja Lloyd-Max, oraz w klasterowaniu k-means, które jest zastosowaniem algorytmu Lloyd'a do danych o dowolnej wymiarowości zamiast płaszczyzny 2D.

repeat k times:
  cells = voronoi(sites)
  for i in 0..n-1:
    sites[i] = centroid(cells[i])   // area-weighted center of mass

Dual Delaunaya

Połącz pary punktów sites, dla których obszary Voronoi mają wspólną granicę, i otrzymany wynik to triangulacja Delaunaya — geometriski dual do diagramu Voronoi. Ma ona charakterystyczną własność, że żaden z punktów nie leży wewnątrz okręgu opisanego na trójkątany przez dowolne trzy inne punkty, co sprawia, że jest to triangulacja, która unika jak najmniej czubkowych trójkątów dla danej zbiorowości punktów. Dlatego, ponieważ obie struktury są dualne, większość bibliotek z geometrii obliczeniowej liczy je razem w jednym przebiegu; jeśli potrzebujesz jednej z nich, otrzymujesz drugą za koszt czytania połączeń inaczej.

Gdzie to występuje

Tesselacje Voronoi centroidalne stanowią standardowe miejsce rozpoczęcia dla generowania siatek elementów skończonych, ponieważ dobrze zasypanych, równomiernie rozmiarowych komórek prowadzi do symulacji numerycznie stabilnych. Algorytmy stipplujące wykorzystują relaksację Lloyd'a z wagiem, aby umieszczać punkty, które powtarzają tonę obrazu poprzez gęstość punktów zamiast za pomocą oświetlenia. Problemy planowania ścieżek i umieszczania czujników na mapie często redukują się do podziału Voronoi z wagą, ponieważ bezpośrednio odpowiadają na pytanie „który zasób jest najbliżej każdego lokalizacji”. A proceduralne generowanie w grach wykorzystuje diagramy Voronoi regularnie, dla map terenów, tekstur skalowanej przez komórki i terenów o zasypanych komórkach, dokładnie dlatego, że kilka iteracji relaksacji przekształca pureskansowy rozrzut w coś, co czyta się jako świadomie, organicznie zaprojektowane.

Często zadawane pytania

Wypróbuj na żywo

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