Побудова діаграми Вороного методом 'розділяй і володарюй'. Релаксація Ллойда

image
Нещодавно, на хабрахабре була опублікована стаття, цілком і повністю присвячена діаграм Вороного. У статті автор детально описує алгоритм Форчуна, що застосовується для побудови Діаграми Вороного за O(n*log(n)). Варто зазначити, що опис цього алгоритму не раз з'являлося в рунеті, в той час як про інших алгоритмах(з тієї ж асимптотикой) розказано рівним рахунком нічого. Дана стаття виправляє це непорозуміння, а також є відмінним доповненням до вже опублікованим раніше матеріалом.
Нижче я розповім про алгоритмі 'розділяй і володарюй' побудови діаграми Вороного за O(n*log(n)), а також, ґрунтуючись на своєму практичному досвіді, про по-справжньому крутих штуках, в яких це стосується. Взагалі, алгоритми типу 'розділяй і володарюй' є свого роду класикою програмування(думаю, про сортування даних методом чув кожен програміст), добре параллелятся і легко читаються(якщо, звичайно, знати основну ідею алгоритму).

Опис алгоритму 'розділяй і володарюй' побудови діаграми Вороного

Вихідне безліч точок сортується по одній з координат(наприклад, x) і ділиться на два приблизно рівних множини. Кожне з отриманих множин знову ділиться на два і так відбувається до тих пір, поки в кожному з множин залишиться не більше двох точок. Легко бачити, що таких розбиття буде не більше ніж log(n). Далі, для кожного отриманого безлічі будуються діаграми Вороного, після чого, в зворотному порядку поділу, ці діаграми об'єднуються в одну. Отримана діаграма Вороного і буде кінцевим результатом.
Щоб описаний алгоритм мав складність порядку O(n*log(n)), необхідно виконувати процес об'єднання двох діаграм Вороного за O(N). Зазначу, що для багатьох з двох точок, діаграмою Вороного буде серединний перпендикуляр відрізка утвореного цими двома точками.
Покладемо, що всі точки відсортовані по X координаті, а вихідне безліч розділене на два і для кожного побудована діаграма Вороного. Виконаємо об'єднання цих множин та їх діаграми наступним чином:
1. Для кожного з підмножин знайдемо опуклу оболонку(зауважимо, що побудова опуклої оболонки для кожного з множин можна виконувати все тим же 'розділяй і володарюй': тобто, на кожному кроці об'єднання діаграм Вороного ми об'єднуємо і опуклі оболонки даних множин за O(N))
2. Тепер, коли у нас є дві опуклі оболонки вихідних множин, знайдемо 'верхню і нижню' кордону даних множин: тобто, ми повинні знайти дві такі відрізки, які об'єднують дві дані опуклі оболонки в одну(природно, випуклу). Таким чином ми виконаємо умови кроку 1, а також отримаємо инициализирующие значення для кроку 3. Цей крок, як я і писав, можна виконати за O(N).
3. З отриманих відрізків кроці 2, виберемо будь-та позначимо через L (залишився позначимо через Q), і через його середину, перпендикулярно пускаємо нескінченний промінь. Уявімо, що цей промінь тільки входить у вихідне безліч, і знайдемо його перетину з осередками діаграм Вороного вихідних множин(вважається, що промінь тягнеться вперед, тобто у нього є напрямок). Ми перетинаємо промінь тільки з тими осередками Вороного, центрами яких є кінці відрізка перпендикулярно якому ми пускаємо промінь. Нам потрібно знайти точки перетину цього променя з відповідними осередками Вороного і вибрати серед них ту, що перетинається раніше. Позначимо цю точку за M, а клітинку яку ми перетнули запам'ятаємо і позначимо V. Далі, зробимо наступне: той кінець відрізка L, що є центром для не пересіченій комірки Вороного залишаємо в спокої, а ось той, що був центром осередку яку ми перетнули — оновлюємо: ми перетнули одну з сторін комірки Вороного, тоді новим кінцем відрізка L стане центр комірки Вороного, суміжній з цієї сторони з пересіченій осередком. В спеціальне безліч S(в ньому зберігається кордон двох Діаграм Вороного) треба додати ту частину променя, яка простягається до перетину зі стороною осередку. Повторюємо крок 3 до тих пір, поки значення кінців відрізка L, не стануть рівними значенням кінців відрізка Q. У підсумку, у множині S виявиться безперервний ламаний промінь. Доказ багатьох фактів, наведених тут(наприклад, безперервність променя в множині S), можна знайти у [1].
4. Ми отримали безліч S, яке являє собою безперервний ламаний промінь. Цей промінь є межею, що з'єднує діаграми Вороного двох множин. Для отримання фінального результату, потрібно для діаграми Вороного лівого безлічі 'затерти' ті відрізки що знаходяться праворуч від отриманого променя, а для діаграми Вороного правого безлічі 'затерти' ті що зліва. Зробити це швидко не проблема: коли ми перетинаємо клітинку променем, то очевидно, що спочатку промінь буде в неї входити, а потім, у якийсь певний момент-вийде. Нам потрібно 'відловити' ці події, і в залежності від того з діаграмою якогось безлічі ми працюємо(лівого або правого), видалити ліву або праву ланцюжка ребер комірки Вороного, яку ми перетнули променем, і додати туди потрібну частину з безлічі S.
Описаний вище алгоритм складно зрозуміти без хорошої ілюстрації(малюнки були взяті здесь):

image
image
image
image
image
image
Ну і закінчу цей підрозділ публікації на те, що якщо точки мають однакову координату X, то варто їх сортувати по координаті Y, таким чином, щоб рівномірно і послідовно їх розділити.

Застосування Діаграми Вороного — релаксація Ллойда
Релаксація Ллойда — один з дивних і 'залипательных' алгоритмів, в якому активно використовується побудова діаграм Вороного. Опишу сам алгоритм:
1. Будуємо діаграму Вороного для вихідного безлічі точок, формуємо комірки Вороного.
2. Знаходимо «Центр Мас» кожної комірки Вороного(сума координат вершин комірки Вороного, поділена на їх кількість).
3. Зрушуємо центр кожної комірки Вороного в позицію розрахованого «Центра Мас».
4. Повторюємо цю процедуру N разів: до тих пір, поки відстань зсуву не стане близьким до нуля.
Що ж ми отримуємо в результаті? Результат можна побачити на цих двох коротких відео:


Виглядає красиво, але трохи марно !? Далеко ні!
На моєму практичному досвіді, релаксація Ллойда застосовувалася в 3D моделюванні: в так званому «ремешинге сітки». Тобто, дана сітка (зазвичай після обробки дешевеньким китайським сканером) і стоїть завдання отриману 'мішанину' трикутників перетворити в щось гарне і живе: в те, на чому можна виробляти більш-менш точні обчислення(розрахунок 'кривизни сітки', апроксимація точок триангуляційної сітки нескінченно гладкими поверхнями і т. п.), намагаючись не сильно відхилитися в точності від оригінальної 'сканерной' сітки(більш того, ця точність задається користувачем, а такий 'ремешинг' називається адаптивним(adaptive). Існує ще 'ремешинг' униформный(uniform) — тут, задається не відхилення, а бажана довжина ребра в трикутнику). Я трохи заговорився і забув пояснити, що ж ми розуміємо під словом 'красива' сітка. Сітку назвемо 'красивою', якщо за своєю структурою вона складається переважно із рівносторонніх трикутників, а валентність кожної вершини у такої сітки 6(якщо вершина внутрішня, ну тобто 360. / 6. = 60 deg. — градус кута рівностороннього трикутника) або 4(якщо вершина лежить на відкритому ребрі, тобто трикутників з даною вершиною 3). Ну, і одним з важливих етапів отримання такої сітки є побудова діаграми Вороного і використання релаксації Ллойда. Власне, отримуємо щось в цьому дусі(акуратно, картинки великі !):
Картиночки результату роботи 'ремешинга', закодованого мною:
image
Після:
image
А тепер і до і після на одному зображенні:
image
До речі, можна помітити що оригінал був отриманий за допомогою алгоритму Марширують Кубів

Ну і картинки поменше, але вже з інтернету:
image
image
І… (куди ж без неї) — статуя Давида:
image
Краса, та й годі!
Завершити хотів би на те, що використання алгоритму Ллойда, справа витратна. І для отримання швидкого результату, без особливої втрати якості були розроблені так звані методи 'Мінімізації Енергії'. Почитати можна в [2]

Корисні посилання та література
[0] Крута стаття на Хабрахабр-е про діаграми Вороного
[1] Оригінал опису алгоритму, з усіма доказами
[2] Порівняння методів 'Мінімізації Енергії'
[3] Невелика стаття про 'Розділяй і володарюй' алгоритмі побудови діаграми Вороного
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.