Rozluźnianie Lloyda | mysimulator.uk

Rozpocznij od diagramu ościółkowego

Rozsyp zestaw punktów na płaszczyźnie i zapytaj, dla każdego położenia, który punkt jest najbliżej – odpowiedź dzieli płaszczyznę na obszary zwane komórkami ościółkowymi, po jednym na punkt, a cała partia to diagram ościółkowy. Losowe punkty generują diagram ościółkowy z bardzo nierównymi komórkami: niektóre małe i zatłoczone, inne ogromne i puste, ponieważ nic w losowym rozmieszczeniu nie zniechęca do gromadzenia się. Stuart Lloyd, pracujący w Bell Labs w 1957 roku nad problemem kwantyzacji sygnałów, znalazł niezwykle prostą procedurę, która przekształca ten nierówny bałagan w coś zbliżającego się do jednorodności.

Krok relaksacji: przesunięcie do centroidu

Algorytm Lloyda alternuje dwie operacje. Po pierwsze, buduje diagram Voronoja dla aktualnych punktów. Po drugie, zastępuje każdy punkt centroidem (środkiem masy) własnej komórki, zamiast jego pierwotnego położenia. Powtarza się. W każdym cyklu każdy punkt jest przesuwany w kierunku środka obszaru, który obecnie kontroluje – punkt znajdujący się w komórce wypływającej do jednej ze stron, zostaje pociągnięty w stronę tego wypływu, co zmniejsza nierównowagę dla następnego razu.

repeat for N iterations:
  V = VoronoiDiagram(points)              // one cell per point
  for each point p, with cell C in V:
    p ← centroid(C)                        // area-weighted centre of mass

energy being minimised:
  E = Σ over cells ∫∫_C |x − centroid(C)|² dA

demo na żywo · powiązana symulacja● LIVE

Dlaczego energia spada w każdym kroku

Proces można zrozumieć jako zbieżność gradientową na określonej wielkości: sumę, dla każdej komórki, kwadratów odległości od każdego punktu wewnątrz komórki do centroidy tej samej komórki. Przeniesienie punktu generującego komórkę do jej centroidy jest dowodem tego wyboru, który minimalizuje własny wkład tej komórki do całkowitej energii, przy zachowaniu stałych granic komórek – więc każdy krok Lloyda może tylko zmniejszyć lub utrzymać na stałym poziomie ogólną energię, nigdy ją nie zwiększać. Ta monotoniczna spadek gwarantuje, że proces ustabilizuje się zamiast oscylować lub rozbiegać, nawet jeśli nie ma pojęcia o kroku lub współczynniku uczenia w taki sposób jak standardowa zbieżność gradientową.

Stały punkt: tessellacja ośrodkowa Voronoi

Proces zatrzymuje się, gdy każdy punkt już znajduje się dokładnie w swoim centroidzie komórki – ponowne przenoszenie go tam jest operacją bez efektu (no-op). Ta konfiguracja nazywana jest tessellacją ośrodkowa Voronoi (CVT) i jest to punkt, do którego zbiega się algorytm Lloyda. Idealny siodokątny układ jest najbardziej znanym przykładem CVT z identycznymi komórkami, a nie przypadek – zrelaksowane punkty tendencją do wyglądania się jak siodokąty wewnątrz, z dala od dowolnej granicy: regularny siodek jest dowodem na to, że jest najefektywnszym sposobem podziału płaszczyzny na obszary o równej powierzchni i kompaktowe, minimalizując dokładnie energię z kwadratu, którą opada algorytm Lloyda.

Gdzie stosowane są rozszerzone zbiory punktów, aby uzyskać relaksację

Rozluźnienie Lloyda pojawia się wszędzie tam, gdzie potrzebne jest równomierne rozprowadzanie zbioru próbek punktowych bez widocznej struktury siatki. Generowanie siatek dla symulacji metodą elementów skończonych wykorzystuje je do uniknięcia długich, cienkich i numerycznie niestabilnych trójkątów, które powstają w wyniku nieprzeskalibrowanych losowych prób. Algorytmy stipplowania i ditheringu wykorzystują je do rozmieszczania kropek tak, aby lokalna gęstość naśladowała wartość szarości skali szaroy obrazu, unikając jednocześnie wizualnie uciążliwych skupisk i pustek spowodowanych czystą losowością - ta technika leży u podstaw popularnej metody "ważonego stipplowania Voronoi" do generowania sztuki z kropek na podstawie zdjęć. Generowanie próbek błękitnych dla renderowania i umieszczania tekstur proceduralnych opiera się na tym samym założeniu: rozluźnione punkty nadal wyglądają organicznie i nieregularnie, ale bez artefaktów skupień plagących naiwnego losowego rozmieszczenia.

Frequently asked questions

Co to jest tessellacja Voronoi centroidalna?

Jest to diagram Voronoi z wyjątkową właściwością samokonsystencji: punkt generujący każdą komórkę znajduje się dokładnie w środku masy tej samej komórki (centroid). Algorytm Lloyda jest standardowym sposobem na znalezienie takiego diagramu – jest to punkt stały, do którego dążą procesy relaksacyjne, ponieważ po tym, jak każdy punkt już znajduje się w centroidzie swojej komórki, przemieszczanie punktów do centroidów nie powoduje już żadnych zmian.

Dlaczego relaksacja Lloyda tendencyjnie produkuje heksagonalny układ?

Regularna siatka sześciokątna jest tessellacją Voronoi centroidalną, w której każda komórka jest identyczna, a jest to sprawdzony i udowodniony najbardziej efektywny sposób ułożenia płaszczyzny z równymi powierzchniami i zwartymi komórkami – minimalizuje ona średni kwadrat odległości od punktów wewnątrz komórki do jej środka masy, co odpowiada energii, którą dąży do zminimalizowania proces relaksacji Lloyda. Punkty pod wpływem równomiernego ciśnienia od wszystkich sąsiadów naturalnie zbliżają się do tego optymalnego, jednorodnego ułożenia.

Czy algorytm Lloyda zawsze zbiega się do globalnego optimum?

Nie – minimalizuje on energię, która nie jest wypukła, więc niezawodnie dąży do minimum lokalnego, a różne losowe ustawienia początkowe mogą prowadzić do różnych końcowych układów (występują szczególnie trwałe defekty, takie jak para sąsiadów 5-7 zamiast dwóch heksagonów). W praktyce wystarczy stosunkowo niewielka liczba iteracji, zazwyczaj od dziesięciu do kilkudziesięciu, aby usunąć większość widocznego zwarcia i uzyskać gładkie, naturalnie wyglądające rozłożenie, nawet bez osiągnięcia idealnej siatki heksagonalnej.

Wypróbuj na żywo

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

▶ Otwórz symulację Lloyd's Relaxation

Rozluźnianie Lloyda: Układanie Chaosu w Uroń