Зважений Вороний стипплінг: сотні точок самоорганізовуються через алгоритм Ллойда за функцією щільності, створюючи красиве пуантилістичне мистецтво. Оберіть шаблони щільності, налаштуйте кількість точок і спостерігайте збіжність.
Ця симуляція перетворює обрану функцію щільності на пуантилістичне мистецтво за допомогою зваженого стипплінгу Вороного. Спочатку сотні точок розкидаються методом вибіркового відхилення, а потім багаторазово релаксуються: на кожній ітерації кожна точка зміщується до зваженого за щільністю центроїда своєї комірки Вороного. Це алгоритм Ллойда — та сама ітерація, що лежить в основі кластеризації методом k-середніх. За багато кроків точки рівномірно розповзаються по світлих ділянках і скупчуються у темних, відтворюючи тон лише завдяки інтервалам та розміру окремих точок.
Полотно обчислює поле щільності на сітці 80×60. Кожна комірка сітки призначається найближчій точці (розбиття Вороного), а кожна точка зміщується на 60% шляху до зваженого середнього своєї комірки, що згладжується для запобігання коливанням. Запуск позначається як збіжний, щойно найбільше квадратичне зміщення падає нижче 0.5 пікселя. Радіус точки масштабується обернено до локальної щільності, тож розріджені ділянки отримують менше, але більших точок.
Оберіть Шаблон (Хвилі, Спіраль, Мандельброт або Зірки), щоб змінити базове поле щільності, та Стиль (Моно, Сепія або Колір) для палітри. Повзунок Точок задає кількість точок від 100 до 900, а Розмір крапки масштабує радіус від 0.5× до 2.5×. Скористайтеся кнопкою Скинути для повторного засіву, Пауза/Продовжити для зупинки циклу та Крок для виконання однієї ітерації релаксації.
Зважений стипплінг Вороного запропонував Адріан Секорд у 2002 році як спосіб автоматично відтворювати рукотворне гравіювання та штрихування тушшю. Та сама центроїдна тесселяція Вороного лежить в основі синьошумової вибірки, що застосовується в рендерингу, та навіть розташування колбочок у сітківці ока.
Це техніка, яка передає тон і форму, використовуючи лише положення та розмір маленьких точок, без неперервного затінення. Функція щільності визначає, скільки точок належить кожній ділянці, а точки розташовуються так, щоб темні ділянки були щільно заповнені, а світлі залишалися розрідженими, імітуючи традиційне стипплінг- та пуантилістичне мистецтво.
Кожна ітерація розбиває полотно так, щоб кожна вибірка сітки належала найближчій точці, утворюючи комірки Вороного. Потім симуляція обчислює зважений за щільністю центроїд кожної комірки і зміщує її точку на 60% шляху до цього центроїда. Повторення цього і є алгоритмом Ллойда, який підштовхує точки до рівномірно розташованого розкладу, що враховує щільність.
Вони перемикають функцію щільності, яка спрямовує точки. Хвилі використовують інтерферуючі синусоїдні поля, Спіраль застосовує обертовий промінь з радіальним згасанням, Мандельброт відображає кожну точку на комплексну площину й затінює за часом виходу, а Зірки сумують гаусові згустки навколо дванадцяти засіяних центрів скупчень. Кожен дає свій особливий розподіл світла й тіні.
Так, у межах своєї моделі. Розклад точок є справжньою центроїдною тесселяцією Вороного, отриманою ітерацією Ллойда — тим самим методом, що застосовується у науковому стипплінгу та синьошумовій вибірці. Заради швидкості він вибирає щільність на сітці 80×60 та використовує просторовий хеш для пошуку найближчого сусіда, тож наближає справжні неперервні комірки Вороного, а не обчислює точні межі комірок.
Алгоритм Ллойда збігається: коли точки осідають поблизу центроїдів своїх комірок, комірки стабілізуються, і подальші зміщення зменшуються. Коли найбільше квадратичне зміщення за ітерацію падає нижче 0.5 пікселя, симуляція позначає запуск як збіжний і припиняє релаксацію, залишаючи стабільний стипплінг-візерунок, доки ви не скинете чи не зміните якийсь елемент керування.