🔷 Diagram Woronoja

Mając zbiór punktów zaczątkowych, diagram Woronoja dzieli płaszczyznę na obszary, z których każdy zawiera wszystkie miejsca bliższe swojemu punktowi niż jakiemukolwiek innemu. Każda komórka jest „terytorium” jednego punktu, a granice komórek są równoodległe od sąsiednich punktów.

Algorytm Lloyda wielokrotnie przelicza diagram Woronoja i przesuwa każdy punkt do centroidu jego komórki. Powtarzanie tego procesu tworzy centroidalną teselację Woronoja o bardziej jednolitych, równomiernie rozmieszczonych komórkach, przydatną do próbkowania i generowania siatek.

Odległość euklidesowa daje obszary najbliższego punktu wyznaczone liniami prostymi, o gładkich granicach. Odległość miejska (Manhattan) mierzy wzdłuż osi siatki, tworząc kanciaste komórki o krawędziach w kształcie rombu, a odległość Czebyszewa liczy większą różnicę na osiach, dając obszary o kwadratowym wpływie. Każda metryka inaczej kształtuje komórki.

Triangulacja Delaunaya łączy punkty, których komórki Woronoja mają wspólną krawędź, i jest geometrycznym dualem diagramu Woronoja. Jej nałożenie pokazuje, jak punkty są powiązane, i jest sama w sobie szeroko wykorzystywana do generowania dobrze ukształtowanych siatek trójkątów.

Każda granica leży dokładnie w połowie drogi, według wybranej metryki, między dwoma sąsiednimi punktami. Przy odległości euklidesowej są to symetralne odcinków łączących sąsiednie punkty, spotykające się w wierzchołkach równoodległych od trzech lub więcej punktów.

Pojawiają się w spękaniach wysychającego błota, pianach mydlanych, granicach ziaren kryształów, układzie komórek liści, wzorach umaszczenia zwierząt takich jak żyrafy oraz podziałach terytorialnych, ponieważ wiele procesów wzrostu i upakowania naturalnie minimalizuje odległość do najbliższych centrów.

Wspierają zapytania o najbliższego sąsiada, wykrywanie kolizji, generowanie siatek, tekstury proceduralne i mapy w grach, interpolację przestrzenną danych oraz planowanie obszarów usługowych, takich jak zasięgi masztów, szkół czy szpitali.

Więcej punktów tworzy więcej, mniejszych komórek i dokładniejszy podział płaszczyzny. Średnie pole komórki maleje w przybliżeniu proporcjonalnie do odwrotności liczby punktów, a granice stają się gęstsze i bardziej złożone.

Przesunięcie każdego punktu do centroidu jego komórki rozsuwa skupione punkty i wypełnia rzadkie obszary. Powtarzane iteracje zbiegają do komórek o podobnym rozmiarze i zwartych, zbliżonych do sześciokątów kształtach, zmniejszając nieregularność losowego rozmieszczenia.

Są to struktury dualne: każdy wierzchołek Woronoja odpowiada środkowi okręgu opisanego na trójkącie Delaunaya, a krawędzie Woronoja są prostopadłe do krawędzi Delaunaya. Obliczenie jednej struktury praktycznie daje drugą, a obie mają kluczowe znaczenie w geometrii obliczeniowej.