PL 
EnglishDomyślny
Українська🕸️ Voronoi Diagrams & Lloyd's Relaxation
Generate random sites and watch a raster-computed Voronoi diagram relax toward a centroidal tessellation using real Lloyd's algorithm, with a Delaunay dual overlay and live cell-uniformity statistics.
Podobne symulacje
🕸️ Co przedstawia
Diagram Woronoja dzieli płaszczyznę na regiony („komórki”) według zbioru rozrzuconych punktów zwanych miejscami (sites): każdy punkt w danej komórce jest bliżej miejsca tej komórki niż jakiegokolwiek innego. Ta symulacja oblicza diagram bezpośrednio przez rasteryzację — dla każdego punktu próbki na płótnie wykonuje siłowe przeszukiwanie najbliższego miejsca spośród wszystkich miejsc i koloruje tę próbkę indeksem zwycięskiego miejsca, co jest najprostszym możliwym sposobem zbudowania matematycznie poprawnego diagramu Woronoja bez implementowania algorytmu zamiatania lub dziel-i-zwyciężaj.
Algorytm Lloyda (nazywany też relaksacją Lloyda) wielokrotnie poprawia układ miejsc: dla każdej komórki oblicza środek ciężkości (średnią pozycję) każdej próbki rastra aktualnie przypisanej do tej komórki, a następnie przesuwa miejsce do tego środka ciężkości. Ponowne obliczanie diagramu po każdym przesunięciu i powtarzanie tego procesu sprawia, że wypełnienie zbiega do centroidalnego wypełnienia Woronoja (CVT) — konfiguracji, w której każde miejsce leży dokładnie w środku masy swojej własnej komórki, dając komórki bardziej jednolite pod względem rozmiaru i bliższe regularnym sześciokątom.
Jak korzystać
- Przeciągnij suwak Liczba punktów (10–150), aby zmienić liczbę losowych miejsc; kliknij Losuj punkty, aby wygenerować nowy zestaw w dowolnym momencie (to również resetuje licznik iteracji).
- Ustaw Iteracje/Kliknięcie i naciśnij Uruchom relaksację Lloyda, aby wykonać tyle kroków relaksacji środka ciężkości naraz.
- Przełącz Auto-relaksację, aby ciągle wykonywać jeden krok relaksacji na klatkę animacji i obserwować, jak komórki się ustabilizują na żywo; wyłącz w dowolnym momencie.
- Włącz Pokaż nakładkę triangulacji Delaunaya, aby narysować graf dualny: linia jest rysowana między dwoma miejscami, gdy ich komórki dzielą granicę rastra, ujawniając triangulację Delaunaya, która jest matematycznie dualna do diagramu Woronoja.
- Obserwuj statystykę Jednolitość — współczynnik zmienności pól komórek — dążącą do zera wraz z kolejnymi iteracjami relaksacji, wskazując, że komórki stają się bardziej równe pod względem rozmiaru.
Czy wiesz, że?
Relaksacja Lloyda ma prawdziwe zastosowania daleko wykraczające poza ładne wzory. W grafice komputerowej i siatkowaniu metodą elementów skończonych jest wykorzystywana do generowania dobrze ukształtowanych siatek trójkątnych lub wielokątnych z mniejszą liczbą wąskich trójkątów i bardziej jednolitymi rozmiarami elementów, co poprawia stabilność numeryczną. W przetwarzaniu obrazów ważone stiplingowanie Woronoja (spopularyzowane przez Adriana Secorda w 2002 roku) wykorzystuje relaksację Lloyda do rozrzucania kropek stiplingu tak, aby gęstsze obszary obrazu otrzymywały więcej kropek, a każda kropka pozostawała równomiernie oddalona od sąsiadów, naśladując wygląd ręcznie rysowanej sztuki pointylistycznej. Być może najbardziej zaskakujące jest to, że Stuart Lloyd opisał zasadniczo ten sam iteracyjny schemat — przypisz punkty do najbliższego centrum, przelicz każde centrum jako średnią przypisanych punktów, powtórz — zarówno dla ciągłej relaksacji Woronoja, jak i dla tego, co stało się znane jako algorytm grupowania k-średnich, w raporcie technicznym Bell Labs z 1957 roku dotyczącym kwantyzacji modulacji kodowo-impulsowej (nieopublikowanym szeroko aż do 1982 roku). Relaksacja Woronoja i k-średnich to, w swojej istocie, ten sam algorytm zastosowany do różnych rodzajów danych.
O tej symulacji
Ten symulator oblicza diagramy Woronoja przez rasteryzację płótna i, dla każdej próbki, siłowe wyszukiwanie najbliższego spośród do 150 losowych miejsc. Naciśnięcie Uruchom relaksację Lloyda przesuwa każde miejsce do prawdziwego środka ciężkości próbek rastra aktualnie mu przypisanych — prawdziwej implementacji algorytmu Lloyda — a powtarzanie tego kieruje układ w stronę centroidalnego wypełnienia Woronoja o bardziej jednolitych, sześciokątopodobnych komórkach.
🔬 Co przedstawia
Skanowana jest niewidoczna siatka próbek (mniej więcej jedna próbka na blok pikseli 3×3); każda próbka znajduje najbliższe miejsce według odległości euklidesowej i jest odpowiednio kolorowana, podczas gdy jej współrzędne kumulują się w bieżącej sumie środka ciężkości tego miejsca. Sąsiadujące próbki przypisane do różnych miejsc oznaczają te dwa miejsca jako sąsiednie, co napędza nakładkę Delaunaya.
🎮 Jak korzystać
Ustaw suwak Liczba punktów i kliknij Losuj punkty, aby wygenerować nowe miejsca. Wybierz Iteracje/Kliknięcie i naciśnij Uruchom relaksację Lloyda, lub włącz Auto-relaksację, aby obserwować ciągłą zbieżność. Przełącz Pokaż nakładkę triangulacji Delaunaya, aby zobaczyć graf dualny, i obserwuj statystykę Jednolitość (współczynnik zmienności pola komórki) malejącą w miarę wyrównywania się komórek.
💡 Czy wiesz, że?
Raport Stuarta Lloyda z Bell Labs z 1957 roku, opisujący ten schemat relaksacji środka ciężkości, to ten sam algorytm znany dziś jako grupowanie k-średnich — przypisz do najbliższego centrum, przelicz centrum jako średnią, powtórz. Jest też podstawą techniki ważonego stiplingu Woronoja Secorda z 2002 roku do generowania obrazów w stylu pointylistycznym.
Najczęściej zadawane pytania
Czym jest diagram Woronoja?
Diagram Woronoja dzieli płaszczyznę na regiony, po jednym na każde miejsce wejściowe, tak że każdy punkt wewnątrz regionu jest bliżej miejsca tego regionu niż jakiegokolwiek innego miejsca. Ta symulacja buduje diagram przez próbkowanie płótna na siatce i, dla każdej próbki, siłowe sprawdzanie odległości do każdego miejsca, aby znaleźć najbliższe.
Co faktycznie robi relaksacja Lloyda?
Dla każdego miejsca oblicza środek ciężkości — średnią współrzędną x i y — wszystkich próbek rastra aktualnie przypisanych do komórki tego miejsca, a następnie przesuwa miejsce do tego środka ciężkości. Ponowne obliczanie diagramu Woronoja po każdym przesunięciu i powtarzanie procesu to pełny algorytm Lloyda; nie jest to losowe szturchnięcie, naprawdę uśrednia próbki rastra komórki.
Dlaczego komórki stają się z czasem bardziej jednolite?
Przesunięcie każdego miejsca do środka masy jego własnej komórki zmniejsza wariancję w tym, jak zwarte lub przekrzywione są komórki. Powtarzanie tego iteracyjnie zbiega do centroidalnego wypełnienia Woronoja, gdzie każde miejsce pokrywa się ze środkiem ciężkości swojej komórki, a komórki dążą do podobnych pól i w przybliżeniu sześciokątnych kształtów, podobnych do wzorców widocznych w upakowaniu komórek biologicznych i piankach mydlanych.
Jak obliczana jest nakładka triangulacji Delaunaya?
Zamiast uruchamiać osobny algorytm Delaunaya, symulacja wykorzystuje dualność: podczas skanowania siatki rastra, gdy tylko dwie sąsiadujące próbki należą do różnych miejsc, te dwa miejsca są zapisywane jako sąsiednie. Narysowanie linii między każdą sąsiadującą parą odtwarza triangulację Delaunaya, która jest matematycznie grafem dualnym diagramu Woronoja.
Co mierzy statystyka Jednolitość?
To współczynnik zmienności (odchylenie standardowe podzielone przez średnią) pól komórek, gdzie pole każdej komórki jest przybliżane liczbą próbek rastra jej przypisanych. Wartość bliska zeru oznacza, że wszystkie komórki mają zbliżony rozmiar; wartość generalnie maleje wraz z kolejnymi iteracjami relaksacji Lloyda.