Растрові клітини Вороного · Релаксація на основі центроїдів · Накладання дуального графа Делоне
Діаграма Вороного розбиває площину на області ("клітини") відповідно до набору розсіяних точок, які називаються точками-центрами (sites): кожна точка в заданій клітині ближча до центру цієї клітини, ніж до будь-якого іншого центру. Ця симуляція обчислює діаграму безпосередньо растеризацією — для кожної точки вибірки по всій канві вона виконує повний перебірний пошук найближчого центру серед усіх центрів і забарвлює цю вибірку за індексом переможного центру, що є найпростішим можливим способом побудувати математично коректну діаграму Вороного без реалізації алгоритму зметної прямої чи розділяй-і-володарюй.
Алгоритм Ллойда (також званий релаксацією Ллойда) повторно покращує розташування точок: для кожної клітини він обчислює центроїд (середню позицію) кожної растрової вибірки, наразі призначеної цій клітині, а потім переміщує точку в цей центроїд. Повторне обчислення діаграми після кожного переміщення та повторення цього процесу призводить до того, що теселяція сходиться до центроїдної теселяції Вороного (ЦТВ) — конфігурації, де кожна точка розташована точно в центрі мас власної клітини, утворюючи клітини, однорідніші за розміром і ближчі до правильних шестикутників.
Релаксація Ллойда має реальні застосування далеко за межами гарних візерунків. У комп'ютерній графіці та сітках скінченних елементів вона використовується для генерування добре сформованих трикутних чи багатокутних сіток з меншою кількістю дефектів і однорідніших розмірів елементів, що покращує числову стабільність. У обробці зображень зважений стипплінг Вороного (популяризований Адріаном Секордом у 2002 році) використовує релаксацію Ллойда, щоб розсіяти точки стипплінгу так, щоб щільніші області зображення отримали більше точок, а кожна точка залишалася рівномірно розподіленою відносно сусідів, імітуючи вигляд намальованого вручну пуантилістичного мистецтва. Можливо, найдивовижніше, що Стюарт Ллойд описав по суті ту саму ітеративну схему — призначення точок до найближчого центру, повторне обчислення кожного центру як середнього призначених точок, повторення — як для неперервної релаксації Вороного, так і для того, що стало відомо як алгоритм кластеризації k-середніх, у технічному звіті Bell Labs 1957 року про квантування імпульсно-кодової модуляції (широко не публікувався до 1982 року). Релаксація Вороного та k-середні є, по суті, одним і тим самим алгоритмом, застосованим до різних видів даних.
Цей симулятор обчислює діаграми Вороного, растеризуючи канву та, для кожної вибірки, виконуючи повний перебірний пошук найближчого з до 150 випадкових точок-центрів. Натискання Запустити релаксацію Ллойда переміщує кожен центр у справжній центроїд растрових вибірок, наразі призначених йому — справжня реалізація алгоритму Ллойда — і повторення цього штовхає розташування до центроїдної теселяції Вороного з однорідними, схожими на шестикутники клітинами.
Сканується позаекранна сітка вибірок (приблизно одна вибірка на блок 3×3 пікселі); кожна вибірка знаходить свій найближчий центр за евклідовою відстанню й забарвлюється відповідно, тоді як її координати накопичуються в поточну суму центроїда цього центру. Сусідні вибірки, призначені різним центрам, позначають ці два центри як суміжні, що керує накладанням Делоне.
Встановіть повзунок Кількість точок і натисніть Випадкові точки, щоб засіяти нові центри. Виберіть Ітерацій/клік і натисніть Запустити релаксацію Ллойда, або увімкніть Авто-релаксацію, щоб спостерігати неперервну збіжність. Перемикайте Показати накладання тріангуляції Делоне, щоб побачити дуальний граф, і спостерігайте, як статистика Однорідності (коефіцієнт варіації площі клітин) падає, коли клітини вирівнюються.
Звіт Стюарта Ллойда 1957 року з Bell Labs, що описує цю схему релаксації центроїдів, — той самий алгоритм, нині відомий як кластеризація k-середніх — призначення до найближчого центру, повторне обчислення центру як середнього, повторення. Це також основа техніки зваженого стипплінгу Вороного Секорда 2002 року для генерування зображень у пуантилістичному стилі.
Діаграма Вороного ділить площину на області, по одній на кожен вхідний центр, так що кожна точка всередині області ближча до центру цієї області, ніж до будь-якого іншого центру. Ця симуляція будує діаграму, вибираючи канву по сітці та, для кожної вибірки, повним перебором перевіряючи відстань до кожного центру, щоб знайти найближчий.
Для кожного центру вона обчислює центроїд — середню координату x та y — усіх растрових вибірок, наразі призначених клітині цього центру, а потім переміщує центр у цей центроїд. Повторне обчислення діаграми Вороного після кожного переміщення та повторення процесу — це повний алгоритм Ллойда; це не випадковий поштовх, він справді усереднює растрові вибірки клітини.
Переміщення кожного центру в центр мас власної клітини зменшує різницю в тому, наскільки компактні чи перекошені клітини. Ітеративне повторення цього збігається до центроїдної теселяції Вороного, де кожен центр збігається з центроїдом своєї клітини, а клітини прямують до подібних площ і приблизно шестикутних форм, подібно до візерунків, що спостерігаються в біологічній упаковці клітин і мильних пінах.
Замість запуску окремого алгоритму Делоне, симуляція використовує дуальність: під час сканування растрової сітки, коли дві сусідні вибірки належать різним центрам, ці два центри записуються як суміжні. Малювання лінії між кожною суміжною парою відтворює тріангуляцію Делоне, яка математично є дуальним графом діаграми Вороного.
Це коефіцієнт варіації (стандартне відхилення, поділене на середнє) площ клітин, де площа кожної клітини наближається кількістю растрових вибірок, призначених їй. Значення, близьке до нуля, означає, що всі клітини близькі за розміром; значення зазвичай зменшується з більшою кількістю ітерацій релаксації Ллойда.