Для заданого набору опорних точок діаграма Вороного розбиває простір так, що кожна точка в комірці ближча до опорної точки цієї комірки, ніж до будь-якої іншої. Вона зустрічається у візерунках жирафа, мікроструктурі кісток, міському плануванні та епідеміології.
Комірки Вороного обчислюються в реальному часі за алгоритмом замітаючої прямої Фортуна (O(n log n)). Двоїстий граф — тріангуляція Делоне — відображається накладанням: вона максимізує мінімальний кут усіх трикутників, оптимальна сітка для методу скінченних елементів та рендерингу рельєфу.
Натисніть будь-де, щоб додати опорну точку. Перетягуйте точки, щоб спостерігати оновлення тесселяції в реальному часі. Перемикайте накладання Делоне. Спробуйте кнопку релаксації Ллойда, щоб ітерувати комірки до рівномірного розподілу — процес, що породжує центроїдальні діаграми Вороного.
Знаменита карта холери Джона Сноу 1854 року була ранньою діаграмою Вороного: він провів межі навколо водяних колонок і показав, що смерті групувалися всередині клітини однієї колонки. Зняття її ручки зупинило спалах — ранній тріумф просторового аналізу даних.
Діаграма Вороного розбиває площину навколо набору опорних точок так, що кожне місце належить області своєї найближчої точки. Цей інтерактивний генератор малює ці комірки в реальному часі та підтримує релаксацію Ллойда, яка ітеративно переміщує кожну точку до центроїда її комірки, вирівнюючи розкладку, а також дає вибір між евклідовою, манхеттенською чи чебишовою метрикою відстані й опційне накладання тріангуляції Делоне.
Тесселяції Вороного трапляються всюди в природі та науці — від тріщин у висохлому мулі й клітин на шкурі жирафа до територій тварин і будови пін та кристалів. Вони лежать в основі обчислювальної геометрії й живлять такі застосування, як пошук найближчого сусіда, побудова сіток, процедурне текстурування, просторова інтерполяція та планування зон обслуговування — наприклад, шкіл чи лікарень.
Що таке діаграма Вороного?
Для заданого набору опорних точок діаграма Вороного ділить площину на області так, що кожна область містить усі місця, ближчі до її точки, ніж до будь-якої іншої. Кожна комірка — це «територія» однієї точки, а межі комірок рівновіддалені від сусідніх точок.
Що таке релаксація Ллойда?
Алгоритм Ллойда багаторазово перераховує діаграму Вороного і переміщує кожну точку до центроїда її комірки. Повторення цього процесу дає центроїдальну тесселяцію Вороного з більш рівномірними, однаково розташованими комірками, корисну для семплювання й побудови сіток.
Що роблять різні метрики відстані?
Евклідова відстань дає області з найближчою точкою по прямій лінії та плавними межами. Манхеттенська відстань вимірюється вздовж осей сітки, утворюючи кутасті комірки з ромбоподібними краями, а чебишова відстань враховує більшу з різниць по осях, даючи області, схожі на квадрати. Кожна метрика по-своєму формує комірки.
Тріангуляція Делоне з'єднує точки, чиї комірки Вороного мають спільне ребро, і є геометрично двоїстою до діаграми Вороного. Її накладання показує, як точки пов'язані між собою, і вона сама широко використовується для побудови якісних трикутних сіток.
Кожна межа лежить точно посередині, за обраною метрикою, між двома сусідніми точками. За евклідової відстані це серединні перпендикуляри до відрізків, що з'єднують сусідні точки, які сходяться у вершинах, рівновіддалених від трьох і більше точок.
Вони виникають у тріщинах висохлого мулу, мильній піні, межах зерен кристалів, розташуванні клітин листя, візерунках шкури тварин (наприклад, жирафів) та територіальних поділах — адже багато процесів росту й упаковки природно мінімізують відстань до найближчих центрів.
Вони підтримують пошук найближчого сусіда, виявлення зіткнень, побудову сіток, процедурні текстури й карти для ігор, просторову інтерполяцію даних та планування зон обслуговування — наприклад, зон покриття веж, шкіл чи лікарень.
Більше точок створює більше, менших за розміром комірок і тонший поділ площини. Середня площа комірки зменшується приблизно обернено пропорційно до кількості точок, а межі стають щільнішими та складнішими.
Переміщення кожної точки до центроїда її комірки розсуває скупчені точки й заповнює розріджені проміжки. Повторні ітерації наближаються до комірок подібного розміру та компактної, майже шестикутної форми, зменшуючи нерегулярність випадкового розміщення.
Це двоїсті структури: кожна вершина Вороного відповідає центру описаного кола трикутника Делоне, а ребра Вороного перпендикулярні до ребер Делоне. Обчислення однієї структури фактично дає й іншу, і обидві є центральними в обчислювальній геометрії.