Алгоритм Форчуна
Алгоритм Форчуна — це алгоритм замітання прямою для побудови діаграми Вороного для множини точок на площині за час із використанням простору[1][2]. Алгоритм вперше оприлюднив Стів Форчун у статті «Алгоритм лінійної розгортки для діаграми Вороного»[3].
Оптимальність
Оскільки задача сортування дійсних чисел зводиться до задачі обчислення діаграми Вороного, то маємо, що довільний алгоритм для обчислення діаграми Вороного потребує часу в найкращому випадку. Отже, алгоритм Форчуна — оптимальний.
Базова структура
Нехай буде множиною точок на площині. Позначимо діаграму Вороного для як Як також позначимо тільки ребра і вершини розбиття. Комірку яка відповідає точці позначимо як
Для двох точок та на площині ми визначаємо бісектор для та як перпендикулярний бісектор відрізку . Цей бісектор розбиває площину на дві півплощини. Позначимо півплощину, що містить як , а іншу півплощину, що містить , як Зауважимо, що тоді і тільки тоді, якщо відстані З цього випливає таке спостереження:
Отже, є перетином півплощини і, звідси, можливо необмеженим відкритим опуклим полігональним регіоном з не більше ніж вершиною і не більше ніж ребром.
Теорема колінеарних точок: Нехай буде множиною з точок на площині. Якщо всі точки лежать на одній прямій, то складається з паралельної лінії. Інакше, зв'язна і її ребра це будуть або відрізки, або промені.
Теорема вершин і ребер: Для діаграми Вороного правильно таке:
- Точка є вершиною , якщо найбільше порожнє коло має три або більше точок у себе на границі.
- Бісектор між точками і визначає ребро тоді і тільки тоді, якщо існує що лежить не ньому для якої має саме ці дві точки на своїй границі і жодного іншого.
Теоретичне підґрунтя
Для обчислення діаграми Вороного в алгоритмі Форчуна використовується метод лінійної розгортки. Ми маємо Нашу лінію розгортки ми позначимо як У перебігу алгоритму ми повинні рухати нашу пряму розгортки згори додолу і під час цього руху підтримувати перетин із цією лінією. Але це не так просто, оскільки частина залежить частково і від точок, що розташовані під
Позначимо замкнену півплощину над як відстань від до будь-якої точки під більша ніж відстань від до самої Отже, найближча до точка не може бути нижчим від якщо щонайменше так близько до якогось місця як близько до Геометричне місце точок, які ближче до деякої точки ніж до обмежене параболою, оскільки її ексцентриситет дорівнює 1. Ми будемо називати послідовність таких параболічних дуг береговою лінією.
Спостереження: берегова лінія є монотонною, тобто кожна вертикальна пряма перетинає її саме в одній точці.
Зауважимо, що точки зустрічі різних параболічних дуг лежать на ребрах діаграми Вороного. Ці точки точно відслідковують поки лінія розгортки рухається додолу. Отже, замість підтримування перетину діаграми з ми будемо відслідковувати берегову лінію. Ми не будемо зберігати параболи явно і не будемо відслідковувати берегову лінію неперервно, натомість ми будемо відслідковувати появу і зникнення дуг на ній.
Параболічні дуги задаються так:
Тобто, найнижча точка параболи у а множник переводить дугу з суто вертикальної прямої у момент появи точки на до все ширшої і ширшої параболи з тим як рухається додолу.
Назвемо подією місця, подію коли пряма розгортки зустрічає точку. У цей момент утворюється нова дуга.
Лема появи дуги: Єдиним способом появи нової дуги на береговій лінії є подія місця.
Назвемо подію коли берегова пряма досягає найнижчої точки кола на границі якого є не менше трьох точок, що визначають послідовні дуги на береговій лінії подією кола.
Лема зникнення дуги: Єдиним способом зникнення дуги з берегової лінії є подія кола.
Лема: Кожна вершина виявлена за допомогою події кола.
Щоб виявити подію кола щодо певної дуги місця , треба перевірити, чи збігаються точки зустрічі цієї дуги з сусідніми дугами місць та тобто чи буде точка перетину прямих та на яких лежать ребра діаграми Вороного, лежати нижче берегової лінії. Оскільки лінії і перпендикулярні відповідно відрізкам та а їхні напрямки узгоджені (див рис.), то ця умова еквівалентна тому, що . Це, у свою чергу, свідчить про лівоорієнтованість трикутника . З властивостей орієнтованої площі трикутника виплоиває, що точки зустрічі збігаються тоді і тільки тоді, коли
Структури для алгоритму
Ми хочемо обчислити діаграму Вороного, отже нам потрібні структури, які зберігають частину діаграми яку ми вже обчислили. Також нам потрібні дві стандартні для алгоритмів лінійної розгортки структури: черга подій і структура яка представляє статус лінії розгортки
- Ми зберігаємо діаграму Вороного під час побудови як подвійно зв'язаний список ребер. Однак, діаграма Вороного не є правильним розбиттям площини, тому що вона має нескінченні ребра, і подвійно зв'язаний список ребер не може представити таку структуру. Під час побудови це не проблема, оскільки представлення берегової лінії наведене далі уможливить ефективний доступ під час побудови до необхідних частин подвійно зв'язаного списку ребер. Для виправлення цього, ми додамо великий обмежувальний прямокутник навколо сцени. Кінцеве розбиття, яке ми обчислимо, складатиметься з обмежувального прямокутника і діаграми Вороного всередині.
- Берегова лінія представлена збалансованим деревом пошуку це і статус-структура. Її листи відповідають дугам берегової лінії, які монотонні, впорядкованим чином: найлівіший лист представляє найлівішу дугу, і т. д. Кожен лист зберігає точку, що визначає дугу на береговій лінії. Внутрішні вузли представляють точки зустрічі на береговій лінії. Точка зустрічі зберігається у вузлі як впорядкований кортеж точок де визначає параболу ліворуч від точки зустрічі, а визначає параболу праворуч. Використовуючи це представлення, ми можемо знайти за дугу на береговій лінії, що лежить над новим місцем. У внутрішньому вузлі ми просто порівнюємо координати точок і точки зустрічі, яку можна обчислити з кортежу точок і позиції прямої розгортки у константний час.
- У ми також зберігаємо вказівники на інші дві структури даних використовувані впродовж розгортки. Кожен лист представляє дугу зберігає зберігає вказівник до вузла в черзі подій, який представляє подію кола в якій зникне. Якщо такої події немає, то вказівник нульовий. Нарешті, кожен внутрішній вузол має вказівник на одне з півребер ребра, що відслідковується точкою зустрічі представленою
- Черга подій реалізована як черга з пріорітетом, де пріоритет це координата. Вона зберігає надхідні події, що вже відомі. Для події місця ми просто зберігаємо місце. Для події кола ми зберігаємо найнижчу точку кола із вказівником на лист що представляє дугу, яка зникне у події.
Алгоритм
Тут ми опишемо алгоритм лінійної розгортки детально. Зауважимо, що після обробки всіх подій, коли черга подій спорожніла, берегова лінія ще не зникла. Точки зустрічі, що досі присутні відповідають до ребер-променів діаграми Вороного. Оскільки подвійно зв'язаний список ребер не може представляти напів-нескінченні ребра, ми повинні додати обмежувальний прямокутник до якого можна буде прикріпити ці ребра.
Алгоритм ДіаграмаВороного На вході: Множина точок на площині. На виході: Діаграма Вороного усередині обмежувального прямокутника представлена за допомогою подвійно зв'язаного списку ребер
|
ОбробитиПодіюМісця
|
ОбробитиПодіюКола
|
Примітки
- Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry (вид. 2nd revised). Springer-Verlag. ISBN 3-540-65620-0. Section 7.2: Computing the Voronoi Diagram: pp.151—160.
- Austin, David. Voronoi Diagrams and a Day at the Beach. Feature Column. American Mathematical Society..
- Steven Fortune. A sweepline algorithm for Voronoi diagrams. Proceedings of the second annual symposium on Computational geometry. Yorktown Heights, New York, United States, pp.313—322. 1986. ISBN 0-89791-194-6. ACM Digital LibrarySpringerLink[недоступне посилання]