PL 
EnglishDomyślny
Українська⚪ Relaksacja Lloyda
Przesuwaj każdy punkt do środka ciężkości jego komórki Voronoi i powtarzaj — punkty układają się w centroidalną teselację Voronoi, pięknie równomierną i zbliżoną do heksagonalnej. Energia E maleje monotonicznie.
Podobne symulacje
O tej symulacji
Ta symulacja pokazuje, jak algorytm relaksacji Lloyda przekształca losowo rozrzucone punkty zaczątkowe w centroidalną tesselację Woronoja. W każdej klatce dzieli płótno na diagram Woronoja — każdy piksel jest przypisywany do najbliższego punktu zaczątkowego — a następnie przesuwa każdy punkt w kierunku ważonego gęstością centroidu jego własnej komórki. Powtarzanie tego kroku wielokrotnie doprowadza układ do stanu, w którym centroid każdej komórki pokrywa się z jej punktem zaczątkowym, tworząc jednolite, w przybliżeniu heksagonalne upakowanie, które daje temu algorytmowi wiele zastosowań w generowaniu siatek, kropkowaniu i sztuce opartej na rozkładzie punktów. Bieżący wskaźnik energii E = Σ ρ·|x − c|² śledzi zbieżność i powinien monotonicznie maleć w miarę relaksacji układu.
🔬 Co pokazuje
Malowany pikselowo diagram Woronoja dla do 400 punktów zaczątkowych, przeliczany co krok przez znajdowanie najbliższego punktu zaczątkowego dla każdego piksela. Na podstawie tego diagramu algorytm sumuje piksele każdej komórki (opcjonalnie ważone polem gęstości), by uzyskać jej centroid, a następnie przesuwa każdy punkt zaczątkowy o 85% drogi w kierunku tego centroidu. Statystyki na żywo śledzą liczbę iteracji, całkowitą energię E, średnią powierzchnię komórki oraz odchylenie standardowe powierzchni — spadające odchylenie standardowe jest najwyraźniejszym sygnałem, że tesselacja staje się jednolita.
🎮 Jak korzystać
Przeciągnij suwak liczby punktów zaczątkowych (20–400), by zmienić liczbę relaksowanych komórek, i wybierz tryb gęstości — jednolity, radialny (gęstszy w centrum), gradientowy (gęstszy po lewej) lub maluj własny, gdzie gęstość nanosisz pędzlem bezpośrednio na płótnie. Iteracje na sekundę kontrolują prędkość animacji, przyciski Krok/Auto/Pauza/Reset dają ręczną kontrolę nad pętlą relaksacji, a pola wyboru wyświetlania przełączają wypełnione komórki, nakładkę triangulacji Delaunaya (graf dualny sąsiadujących komórek) i punkty zaczątkowe; kolor komórki może odzwierciedlać indeks, powierzchnię lub pokazywać same kontury.
💡 Czy wiesz, że…
Algorytm Lloyda został pierwotnie opracowany przez Stuarta Lloyda w Bell Labs w 1957 roku do optymalnej kwantyzacji skalarnej w modulacji impulsowo-kodowej, a nie do grafiki — jego zastosowanie do generowania równomiernie rozłożonych zbiorów punktów i tekstur szumu niebieskiego pojawiło się dopiero dekady później. Ta sama idea — na przemian obliczać diagram Woronoja i przesuwać punkty do centroidu — leży u podstaw algorytmu k-średnich, który jest zasadniczo algorytmem Lloyda zastosowanym do przypisywania klastrów zamiast pikseli przestrzennych.
Najczęściej zadawane pytania
Czym jest diagram Woronoja?
Diagram Woronoja dzieli płaszczyznę na obszary, po jednym na każdy punkt zaczątkowy, gdzie każde miejsce w danym obszarze jest bliżej punktu zaczątkowego tego obszaru niż jakiegokolwiek innego. W tej symulacji podział jest obliczany bezpośrednio na pikselach: dla każdego punktu na płótnie algorytm znajduje najbliższy punkt zaczątkowy przez brutalne porównanie odległości i koloruje ten piksel odpowiednio, budując diagram jako siatkę „właściciela piksela", a nie jako jawne krawędzie wielokątów.
Co dokładnie robi relaksacja Lloyda z punktami zaczątkowymi?
Każdy krok oblicza bieżący diagram Woronoja, znajduje centroid (ważony gęstością środek masy) każdej komórki i przesuwa każdy punkt zaczątkowy o 85% drogi z jego bieżącej pozycji w stronę tego centroidu, zamiast przeskakiwać do niego bezpośrednio. Powtarzanie tego jest formą spadku gradientowego na energii kwantyzacji E = Σ ρ·|x − c|², dzięki czemu punkty zaczątkowe stopniowo osadzają się w pozycjach, w których już znajdują się w centroidach swoich własnych komórek.
Czym jest centroidalna tesselacja Woronoja i dlaczego wygląda tak jednolicie?
Centroidalna tesselacja Woronoja (CVT) to punkt stały algorytmu Lloyda: podział, w którym każdy punkt zaczątkowy jest dokładnie centroidem swojej własnej komórki Woronoja. W tym stanie nie ma już żadnej siły netto przesuwającej punkty, a energia przestaje maleć. CVT dążą do komórek o zbliżonej wielkości i w przybliżeniu heksagonalnym kształcie, ponieważ ta konfiguracja lokalnie minimalizuje energię kwantyzacji dla jednolitej gęstości.
Co zmieniają tryby gęstości?
Pole gęstości ρ(x,y) waży, jak bardzo każdy piksel przyczynia się do obliczenia centroidu komórki. Przy jednolitej gęstości każdy piksel liczy się jednakowo, a komórki dążą do równych powierzchni; przy gęstości radialnej lub gradientowej piksele w gęstszych obszarach silniej przyciągają centroidy do siebie, więc komórki po zbieżności są mniejsze i liczniejsze tam, gdzie gęstość jest wysoka. Tryb malowania pozwala narysować dowolne pole gęstości myszą, które jest odczytywane z niewidocznego płótna za każdym razem, gdy siatka jest przebudowywana.
Dlaczego wartość energii stale spada, a potem osiąga plateau?
Energia E = Σ ρ·|x − c|² mierzy całkowitą (ważoną gęstością) sumę kwadratów odległości od każdego piksela do jego punktu zaczątkowego. Ponieważ każdy krok Lloyda przesuwa punkty zaczątkowe w stronę centroidów ich komórek — czyli punktów, które dokładnie minimalizują tę sumę dla ustalonego podziału — każdy krok może jedynie zmniejszyć lub utrzymać E, nigdy jej nie zwiększyć. W miarę zbliżania się tesselacji do centroidalnej tesselacji Woronoja poprawy maleją, a krzywa energii spłaszcza się, co widać na wykresie energii na płótnie.