UK 
EnglishТипова
Polski⚪ Релаксація Ллойда
Перемістіть кожну точку в центроїд її комірки Вороного і повторюйте — точки сходяться у центроїдну тесселяцію Вороного, прекрасно рівномірну і близьку до гексагональної. Енергія E монотонно спадає.
Про цю симуляцію
Ця симуляція показує, як алгоритм релаксації Ллойда перетворює випадкове розкидання зародкових точок на центроїдну тесселяцію Вороного. Кожен кадр вона розбиває полотно на діаграму Вороного — кожен піксель призначається найближчому зародку — а потім переміщує кожен зародок до зваженого щільністю центроїда своєї власної комірки. Повторення цього кроку знову й знову веде розташування до стану, у якому центроїд кожної комірки збігається з її зародком, створюючи рівномірну, приблизно гексагональну упаковку, що дає алгоритму численні застосування в генерації сіток, стипплінгу та мистецтві розподілу точок. Поточний член енергії E = Σ ρ·|x − c|² відстежує збіжність і має монотонно спадати в міру релаксації системи.
🔬 Що показано
Пофарбована по пікселях діаграма Вороного до 400 зародкових точок, що перераховується на кожному кроці шляхом пошуку найближчого зародка для кожного пікселя. З цієї діаграми алгоритм підсумовує пікселі кожної комірки (опційно зважені полем щільності), щоб отримати її центроїд, а потім змішує кожен зародок на 85% шляху до цього центроїда. Статистика в реальному часі відстежує кількість ітерацій, загальну енергію E, середню площу комірки та стандартне відхилення площі — падіння стандартного відхилення є найяснішою ознакою того, що тесселяція стає рівномірною.
🎮 Як користуватись
Перетягуйте кількість зародкових точок (20–400), щоб змінити скільки комірок релаксується, і оберіть режим щільності — Рівномірний, Радіальний (щільніший у центрі), Градієнт (щільніший ліворуч) або Намалюйте власний, де ви малюєте щільність прямо на полотні. «Ітерацій/сек» керує швидкістю анімації, Крок/Авто/Пауза/Скинути дають ручний контроль над циклом релаксації, а прапорці показу перемикають заповнені комірки, накладання Делоне (подвійний граф суміжних комірок) та точки зародків; колір комірки може відтіняти за індексом, за площею, або показувати прості контури.
💡 Чи знали ви?
Алгоритм Ллойда спершу був розроблений Стюартом Ллойдом у Bell Labs у 1957 році для оптимального скалярного квантування в імпульсно-кодовій модуляції, а не для графіки — його використання для генерації рівномірно розподілених наборів точок і текстур синього шуму з'явилося десятиліттями пізніше. Та сама ідея ітеративного Вороного-потім-центрування лежить в основі кластеризації k-середніх, яка, по суті, є алгоритмом Ллойда, застосованим до призначення кластерів замість просторових пікселів.
Часті питання
Що таке діаграма Вороного?
Діаграма Вороного розбиває площину на області, по одній на зародкову точку, де кожне місце в області ближче до зародка цієї області, ніж до будь-якого іншого зародка. У цій симуляції розбиття обчислюється безпосередньо на пікселях: для кожної точки на полотні алгоритм знаходить найближчий зародок методом прямого порівняння відстаней і фарбує цей піксель відповідно, будуючи діаграму як сітку власників пікселів, а не як явні краї полігонів.
Що насправді робить релаксація Ллойда із зародками?
На кожному кроці вона обчислює поточну діаграму Вороного, знаходить центроїд (зважений щільністю центр мас) кожної комірки, і переміщує кожен зародок на 85% шляху від його поточної позиції до цього центроїда, а не одразу туди. Повторення цього — форма градієнтного спуску на енергії квантування E = Σ ρ·|x − c|², тож зародки поступово осідають у позиціях, де вони вже перебувають у центроїдах власних комірок.
Що таке центроїдна тесселяція Вороного і чому вона виглядає такою рівномірною?
Центроїдна тесселяція Вороного (CVT) — це нерухома точка алгоритму Ллойда: розбиття, у якому кожен зародок точно є центроїдом власної комірки Вороного. У цьому стані більше немає чистої сили, що тягне зародки, і енергія перестає спадати. CVT прагнуть до комірок подібного розміру й приблизно гексагональної форми, тому що ця конфігурація локально мінімізує енергію квантування для рівномірної щільності.
Що змінюють режими щільності?
Поле щільності ρ(x,y) зважує, наскільки кожен піксель впливає на обчислення центроїда комірки. За рівномірної щільності кожен піксель має однакову вагу, і комірки сходяться до рівних площ; за радіальної чи градієнтної щільності пікселі в щільніших областях сильніше притягують центроїди до себе, тож збіжні комірки менші й численніші там, де щільність висока. Режим малювання дозволяє намалювати довільне поле щільності мишею, яке зчитується з позаекранного полотна щоразу, коли сітка перебудовується.
Чому значення енергії продовжує падати, а потім виходить на плато?
Енергія E = Σ ρ·|x − c|² вимірює загальну (зважену щільністю) квадратичну відстань від кожного пікселя до його зародка. Оскільки кожен крок Ллойда переміщує зародки до центроїдів їхніх комірок — точок, що точно мінімізують цю суму для фіксованого розбиття — кожен крок може лише зменшити або зберегти E, ніколи не збільшити. У міру наближення тесселяції до центроїдної тесселяції Вороного покращення зменшуються, і крива енергії вирівнюється, що видно на графіку енергії на полотні.