Воро́нські діаграми: Фортуна та алгоритм Sweep Line, Delaunay та Lloyd Relaxation

Визначення та властивості

Нехай P = {p₁, …, pₙ} — це n різних початкових точок у ℝ². Клітинка Вороного для початкової точки pᵢ позначена як V(pᵢ) і визначається як {x ∈ ℝ² | d(x, pᵢ) ≤ d(x, pⱼ) для всіх j ≠ i}, де використовується стандартна евклідова відстань (інші метрики призводять до екзотичних варіантів). Межі між сусідніми клітинками є бісекторами — кожний край є перпендикулярною бісектрисою двох початкових точок, і три клітинки зустрічаються в вершині Вороного, яка є обертовою серединою трикутника, утвореного цими трьома початковими точками. Як перетин півпросторів, кожна клітинка Вороного є опуклою, і для однорідного процесу розподілу точок із випадковим розташуванням середнє число сторін має бути рівним 6.

Від грубого методу до алгоритму Фортуна

Найбільш прямий підхід — це грубий метод найближчого сусіда: для кожного пікселя скануйте всі n насіння та розфарбовуйте його кольором найближчого — O(W·H·n), що добре підходить для невеликих n, але обмежує продуктивність при високій роздільній здатності з тисячами насіння. Алгоритм Стівена Фортуна 1987 року обчислює точний діаграма за O(n log n) часу шляхом переміщення горизонтальної лінії вниз по площині, підтримуючи чергу подій (подія на місці та подія кола) і пляжну лінію з параболічних дуг — кожна дуга є дотичною від даного пікселя та лінії перетину. Коли виникає подія на місці, дуга над новим насінням ділиться і вставляється нова дуга; коли виникає подія кола, три збіжні дуги стискаються до вершини діаграми Вороної.

Algorithm              Time            Space   Notes
Brute force (raster)   O(W·H·n)        O(W·H)  Simple; GPU-parallel
Fortune's algorithm    O(n log n)      O(n)    Exact; reference implementation
Bowyer-Watson (dual)   O(n log n) avg  O(n)    Via Delaunay triangulation

Делаunay триангуляція — дуальна графа

Делаunay триангуляція DT(P) є прямолінійною двійницею діаграми Voronoї: з’єднуйте два насіння, коли їхні комірки розділені ребром. Її визначальна властивість — критерій порожнього вписаного кола — жодне насіння не лежить строго всередині описаного кола будь-якого трикутника у DT(P) — що робить її оптимальним вибором для мінімізації кута між всіма можливими триангулюваннями множини точок, і саме тому це стандартний варіант для кінцевих елементів та числових симуляцій сіток, де сріплені трикутники знижують точність. Алгоритм Bowyer-Watson інкрементально будує її, вставляючи точки по черзі, видаляючи всі трикутники, описані кола яких містять нову точку, та перетриангулюючи отримане отвору.

Центральне перекриття з Voroї діаграмою (CVT) — розподіл центроїдів

Центральне перекриття з Voroї діаграмою (CVT) є особливою Voroї діаграмою, де кожен центр відповідає центроїду власної комірки. Алгоритм Ллойда ітеративно наближається до CVT шляхом чергування: обчислення Voroї діаграми з поточними центрами та переміщення кожного центру у центроїд своєї комірки — середнє положення, розраховане за вагою. Після 10–30 ітерацій центри розподіляються рівномірно, створюючи характерну пінисту, шестигранну структуру з рівними площинами, яка зустрічається в біологічних тканинах, виборчому поділі на округи та техніці хафтолінгу. Зважування кожного пікселя за ступенем темряви перед розслабленням створює Voroї стіблення — техніку у вигляді крапок, популяризовану Адріаном Серкодом у 2002 році.

Застосування в науці, іграх та візуалізації

Об’єднано з діаграмою Делоне, точні запити найближчого сусіда виконуються за часом O(log n). Процедурні генератори рельєфу ділять площину на полігональні "пластини" або біоми через тесселяцію Ворноя + розслаблення Ллойда, призначаючи висоту та вологість кожній клітинці для створення миттєво правдоподібної географії. Біологічні клітини — епітеліальна тканина, піна від мила, соти — всі вони приблизно відповідають тесселяції Ворноя з центром у ядерній клітинці. У проблемі розміщення об’єктів для логістики, знаходження n місць для складування, що мінімізують середню відстань подорожі клієнтів, є точною задачею про тесселяцію Ворноя на центріоїдах, а в реальному часі симуляція руйнування використовує комірки Ворноя для визначення уламків розриву, що полягає у зрізанні сітки вздовж меж клітинок.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте the simulation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.