Особливості реалізації алгоритму форчуна для побудови діаграми Вороного на мові програмування Python

Размещено на http://www.allbest.ru/

Житомирський державний університет імені Івана Франка

ОСОБЛИВОСТІ РЕАЛІЗАЦІЇ АЛГОРИТМУ ФОРЧУНА ДЛЯ ПОБУДОВИ ДІАГРАМИ ВОРОНОГО НА МОВІ ПРОГРАМУВАННЯ PYTHON

Іванов Артем Олександрович здобувач освіти

Кривонос Олександр Миколайович кандидат педагогічних наук, доцент,

Жуковський Сергій Станіславович кандидат педагогічних наук, доцент

м. Житомир



Анотація

Дана робота присвячена вивченню особливостей реалізації алгоритму Форчуна для побудови діаграми Вороного на мові програмування Python. Алгоритм Форчуна є ефективним методом для розділення простору на області, названі областями Вороного, на основі набору точок у просторі. Діаграма Вороного має широкі застосування в областях геометрії, графікі, комп'ютерного зору та інших наукових дисциплінах.

В роботі описано поняття діаграми Вороного, її варіації і їх прикладне застосування. Дане розбиття знайшло широке використання в біології, географічних інформаційних системах, матеріалознавстві, комп'ютерній графіці тощо. Показано, що ця діаграма є досить важливою частиною як для природничих наук, так і для обчислювальної геометрії, представлено зв'язок діаграми з іншими геометричними структурами.

Робота розглядає теоретичні аспекти алгоритму Форчуна та його реалізацію на мові програмування Python. Вона досліджує структуру алгоритму, його етапи та ключові кроки, необхідні для отримання точної діаграми Вороного. Автори розглядають способи оптимізації та врахування особливостей мови Python для покращення продуктивності алгоритму.

Представлений окремий аналіз різних алгоритмів комп'ютерної побудови діаграми Вороного, а саме: поступова вставка сайтів, «розділяй і володарюй», побудова через тріангуляцію Делоне, алгоритм Форчуна - дано опис алгоритмів, оцінка ефективності по використанню часу і пам'яті, складності реалізації. Запропонована реалізація алгоритму Форчуна для 2-вимірного випадку з асимптотичною складністю 0(п²) на мові програмування Python. Описано основні структури даних та змінні, необхідні для реалізації алгоритму. В даній роботі для реалізації алгоритму використано двозв'язні списки, проте алгоритм можна вдосконалити, використовуючи бінарні збалансовані дерева пошуку, тим самим зменшивши асимптотичну складність до 0(п log п). програмування вороний алгоритм форчун

Ключові слова: обчислювальна геометрія, діаграма Вороного, алгоритм Форчуна, замітаюча пряма, Python.



Annotation

Ivanov Artem Oleksandrovych Student, Zhytomyr Ivan Franko State University, Zhytomyr

Kryvonos Oleksandr Mykolaiovych Candidate of Pedagogical Sciences (PhD in Pedagogy) Docent Department of Computer Science and Information Technology, Zhytomyr Ivan Franko State University, Zhytomyr

Zhukovskyi Serhii Stanislavovych Candidate of Pedagogical Sciences (PhD in Pedagogy) Docent Department of Computer Science and Information Technology, Zhytomyr Ivan Franko State University, Zhytomyr

PECULIARITIES OF IMPLEMENTATION OF THE FORTUNE'S ALGORITHM FOR GENERATING A VORONOI DIAGRAM IN THE PYTHON PROGRAMMING LANGUAGE

This article deals with the peculiarities of implementing the Fortune's algorithm for generating Voronoi diagrams in Python programming language. The Fortune's algorithm is an efficient method for dividing a space into regions, called Voronoi regions, based on a set of points in space. The Voronoi diagram is widely used in the fields of geometry, graphics, computer vision, and other scientific disciplines.

The paper describes the concept of the Voronoi diagram, its variations and their application. This diagram is widely used in biology, geographic information systems, materials science, computer graphics, etc. It is shown that this diagram is a rather important part of both natural sciences and computational geometry, and the connection of the diagram with other geometric structures is presented.

The study considers the theoretical aspects of the Fortune's algorithm and its implementation in the Python programming language. It explores the algorithm's structure, its stages, and the key steps required to obtain an accurate Voronoi diagram. The authors consider ways to optimise and take into account the peculiarities of the Python language to improve the algorithm's performance.

The article presents a separate analysis of various algorithms for computer construction of Voronoi diagrams, specifically: gradual insertion of sites, divide and conquer, construction through Delaunay triangulation, Fortune's algorithm - the description of algorithms, assessment of efficiency in terms of time and memory usage, and complexity of implementation are given. This paper proposes an implementation of Fortune's algorithm for the 2-D case with asymptotic complexity O(n^A2) in Python programming language. It describes the main data structures and variables required to implement the algorithm. In this article, we use two-linked lists to implement the algorithm, but the algorithm can be improved by using balanced binary search trees, thereby reducing the asymptotic complexity to O(n logn).

Keywords: computational geometry, Voronoi diagram, Fortune's algorithm, sweeping line, Python.



Постановка проблеми

Представимо одну з найвідоміших задач в цій області аналітичної геометрії, так звану задачу поштових офісів: на площині задано п фіксованих точок - сайтів (site). Для довільної точки на цій площині необхідно знайти найближчий сайт в евклідовій метриці. Пошук такого сайту «в лоба» - перевіркою всіх відстаней від точки до сайтів - є досить неефективним, особливо при великій кількості сайтів.

Для вирішення цієї задачі будується діаграма Вороного - розбиття площини на області Вороного (region). Кожному сайту діаграми відповідає своя область Вороного, кожна точка якої є ближчою до цього сайту, ніж до інших. Більш формально це визначення виглядає наступним чином: де рі - відповідний сайт, х - довільна точка у d-вимірному просторі. Тоді діаграма Вороного буде множиною всіх цих областей: [гед(р₁), гед(р₂),..., гед(р_п)}. Пошук найближчого сайту є лише одним з багатьох прикладів застосування діаграми Вороного, вони також активно використовуються для моделювання структур кристалів, побудови найкоротших шляхів, аналізу географічних об'єктів, виявлення колізій, для розв'язання низки задач в обчислювальній геометрії та теорії графів і багато іншого.

Аналіз останніх досліджень і публікацій

Провели комплексний аналіз діаграми Вороного та методів її побудови, також провели опис розв'язання інших завдань з використанням діаграми Вороного в сучасному погляді такі науковці, як F. Aurenhammer, A. Dobrin, S. K. Dey, M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf.

Мета статті - аналіз алгоритмів побудови діаграми Вороного та реалізація алгоритму Форчуна на мові програмування Python.



Матеріали та методи дослідження

Для вирішення поставлених задач були використані такі теоретичні методи, як систематизація наукових знань та їх порівняння, моделювання. Серед загальнонаукових методів були використані наступні методи: аналіз, дедукція та індукція для опрацювання інформації.

Виклад основного матеріалу

Для знаходження найближчого сайту для довільної точки необхідно провести попередній аналіз всього набору сайтів, а саме - побудувати діаграму Вороного, також відома як зони Вігнера-Зейтца (в біології, хімії та кристалографії), полігони Тіссена (в геоінформатиці), або мозаїка Діріхле.

Ця діаграма дозволяє за константний час виконати пошук найближчого сайту для довільної точки. Сама діаграма представляє собою набір ребер (edge), які є рівновіддаленими від 2 сайтів. Декілька ребер сходяться у вершині (vertex), які є точками, рівновіддаленими від 3 або більше сайтів (див. рис. 1). Розглянемо основні алгоритми побудови, а також їхні переваги та недоліки.

Алгоритм Гріна-Сібсона (Green-Sibson algorithm), також відомий як метод поступової вставки сайтів (incremental insertion of sites), полягає у тому, щоб поступово збільшувати діаграму додаванням нових вершин, корегуючи її відповідним чином. Для цього для кожної нової точки перебираються всі інші. Кожен цикл додавання сайту виконується 0(і) часу, де і - кількість доданих сайтів на даному етапі. Підсумовуючи, отримуємо очікувану алгоритмічну складність даного методу 0(п²). Можливе покращення алгоритму шляхом простої евристики, рандомізації додаваних сайтів тощо.



Рис. 1 Діаграма Вороного та основні її елементи: сайти, ребра та вершини

Рис. 2 Злиття двох діаграм Вороного

Алгоритм «розділяй та володарюй» («divide and conquer») є одним з найбільш популярних типів ефективних алгоритмів, які мають лінеаритмічну алгоритмічну складність - 0(п log п). Ідея даного алгоритму схожа до алгоритму Гріна-Сібсона, але має деякі відмінності: тут виконується злиття декількох діаграм Вороного (див. рис. 2). Тим самим, впорядкований набір сайтів розділяється на 2 окремих набора, кожен з яких рекурсивно розділяється відповідним чином. Таким чином досягається алгоритмічна складність алгоритму 0(п log п). Мінусом алгоритму є складність розуміння механізму злиття і його реалізація.

Рис. 3 Діаграма Вороного Рис. 4 Центр описаного кола

(червона) та тріангуляція Делоне тріангуляції Делоне в вершині (синя) діаграми

Інший алгоритм базується на попередній побудові дуального графа до Вороного - тріангуляції Делоне (див. рис. 3). Тріангуляція Делоне (Delauney triangulation) - розбиття набору точок на трикутники таким чином, щоб будь-яке описане коло навколо будь-якого трикутника не містило в собі інших точок з набору. Дуальність цієї тріангуляції до діаграми Вороного виражається у тому, що обидві геометричні структури можна легко отримати одне з одного.

Доведення. Ребро діаграми Вороного це відрізок/промінь/пряма, що рівновіддалений від двох сайтів; як відомо, геометричне місце точок, рівновіддалених від двох заданих є серединний перпендикуляр відрізку, що з'єднує ці точки. Отже, ребра Вороного перпендикулярні ребрам трикутників тріангуляції Делоне, і ділять їх навпіл. Також зауважимо, що вершина Вороного це точка, рівновіддалена від 3 або більше сайтів, тобто, нема ні одного сайту, який знаходиться ближче, що відсилає нас до визначення тріангуляції Делоне. Ефективні алгоритми тріангуляції Делоне працюють за час 0(п logп). Слід зазначити, що для невироджених діаграм Вороного (nondegenerate Voronoi diagram) - степінь вершин яких рівна 3 - існує єдина тріангуляція Делоне, на відміну від вироджених діаграм Вороного (degenerate Voronoi diagram) (див. рис. 5).

Рис. 5 Одна з тріангуляцій Делоне у виродж еній діаграмі Вороного

Рис. 6 Рух замітаючої лінії

Алгоритм Форчуна (Fortune's agorithm), також відомий як метод замітаючої прямої (line sweep algorithm) бере свої початки з відомого алгоритму Бентлі-Оттманна (Bentley-Ottmann algorithm) для знаходження перетину відрізків на площині. В цьому алгоритмі вперше описано використання «замітаючої лінії», яка розділяє набір вхідних даних на два: оброблені, і ті, які ще потребують обробки. Стівен Форчун взяв дану ідею за основу алгоритму побудови діаграми Вороного.

Нехай замітаюча лінія буде вертикальною лінією, яка, рухаючись направо (див. рис. 6), розділяє всі сайти на три окремих набори: сайти, які вже додані до діаграми Вороного; сайти, які в процесі обробки; і сайти, які очікують обробки. Замітаюча лінія являє собою елемент діаграми, і впродовж свого руху вона бере безпосередню участь в її формуванні.

Як відомо, геометричним місцем точок, рівновіддалених від заданої точки і прямої, є парабола. Саме цю фігуру утворюють крайні точки зліва від замітаючої прямої, формуючи собою берегову лінію діаграми, яка складається виключно з дуг парабол. Для цих парабол замітаюча лінія виступає директрисою, таким чином, відстань від неї до вершини параболи рівна відстані від вершини параболи до сайту. При проходженні замітаючої лінії через новий сайт, утворюється нова парабола, яка спочатку є променем, оскільки лінія проходить через сайт. Як бачимо (див. рис. 8), при додаванні нової дуги параболи, вона може розділити дугу за собою на дві окремі дуги, які мають однаковий фокус.



Неважко помітити, що кожна пара дуг перетинаються в точці, яка рівновіддалена від обох фокусів дуг і від замітаючої лінії. Таким чином, при переміщенні замітаючої лінії, на місці перетину дуг утворюються ребра Вороного. Кожна дуга (окрім крайніх) обмежена двома ребрами Вороного, які можуть сходитись одне до одного. В такому випадку довжина дуги прямує до нуля, і в точці, де довжина дуги буде нуль, вона буде рівновіддалена від 3 або більше сайтів, що свідчить про те що ми досягли вершини Вороного (див. рис. 7).

Таким чином, маємо дві події, які змінюють структуру берегової лінії: подія точки, і подія круга. Події точки можна визначити одразу, адже положення сайтів відомі. А для визначення подій круга достатньо після кожної події перевірити три послідовні дуги і побудувати коло по трьом відповідним сайтам. Тоді подія круга відбудеться у крайній правій точці, оскільки саме в цьому випадку ребра Вороного зійдуться в вершині.

Для збереження берегової лінії в програмній реалізації було використано таку структуру даних як двозв'язний список, в якому кожен елемент має посилання на попередній і наступний, якщо такі є. Це доволі проста структура даних, але на заходження в ньому певного елементу витрачається до 0(п) операцій (в залежності від місця положення елементу). Інша структура даних, збалансоване бінарне дерево пошуку - також відоме як АВЛ-дерево - є більш складною, але дозволяє знайти елемент за 0(п log п) в найгіршому випадку. Цей факт залишає простір для вдосконалення реалізації даного алгоритму.

Для початку подивимось, які структури даних використані в ході написання програми. Вони представлені на рисунку 9.

Рис. 9 Структури даних, використані в програмі

Слід зазначити, шо ребро представлене у вигляді початкової і кінцевої точки, а також його клас має поле, яке містить посилання на дві дуги, щоб визначати, з якими сайтами межує дане ребро, а клас дуги має в собі посилання на перше і друге ребро, яким вона обмежена. Визначивши ці класи, можемо перейти до огляду самого алгоритму. Ось загальний опис алгоритму:

1: створення порожньої берегової лінії

2: пріоритетної черги для подій точки і круга: відповідно роint_e і circle_е 3: створення масиву ребер для занесення результату result

4: занесення всіх вхідних точок до point_е 5: поки point_е не порожня:

6: якщо перша за пріоритетом подія point_е має більший пріоритет ніж circle _е:

7: додати нову дугу до діаграми

8: за необхідності розділити дугу позаду на дві

9: прибрати поточну подію з черги

10: перевірити наявність нових подій круга, занести їх до circle _е 11: інакше:

12: прибрати дугу з двозв'язного списку

13: створити нове ребро, яке буде продовженням вершини

14: занести закінчені ребра до result

15: прибрати поточну подію з черги

16: поки circle_е не порожня:

17: прибрати дугу з двозв'язного списку 18: створити нове ребро, яке виходить з вершини 19: занести закінчені ребра до result 20: прибрати поточну подію з черги

21: продовжити ребра з result, які не мають кінцевої точки, до нескінченності

Розглянемо більш детально безпосередньо програмну реалізацію на мові програмування Python.

Рис. 10 Імпорт бібліотек та визначення констант

Спочатку (див. рис. 10) ми імпортуємо вбудовану бібліотеку для роботи з пріоритетними чергами heapq. Також ми визначаємо межі робочого простору, і якесь достатньо велике число у якості нескінченності.



Рис. 11 Опис класу точки

Далі (див. рис. 11) визначаємо клас точки, в середині якого описуємо метод getCircleCenter. Цей метод визначає центр кола по 3 заданим точкам. Це робиться за допомогою проведення серединних перпендикулярів між двома парами точок. ті та m2 -- коефіцієнти нахилу відрізків, які визначаються за формулою:

Коефіцієнти нахилу серединних перпендикулярів є відповідними коефіцієнтами нахилу прямих, помножених на -1. Тоді рівняння серединних перпендикулярів визначатимуться за наступною формуло:

Залишилось розв'язати систему рівнянь двох серединних перпендикулярів і визначити координати центру кола. В програмі одразу розраховується координати точки:

Звісно, номери точок вибираються адаптовано. З метою запобігання ділення на 0 в процесі, в рядках 18-23 визначаємо кращу комбінацію точок. Якщо точки лежать на одній прямій, то такого кола не існує.



Рис. 12 Опис класів події кола; дуги; та ребра Вороного

На рисунку 12 бачимо опис базових класів, який повністю відповідає схемі, зазначеній на рисунку 9. Визначено клас події, який сам по собі є подією кола, яка має два стани: валідний та інвалідний (відпрацьована подія, яку надалі слід ігнорувати). Клас дуги реалізований як елемент двозв'язного списку, який має посилання на попередній і наступний елемент, які за замовчуванням рівні None. Для класу ребра визначено метод setEnd, який дозволяє зручно встановити кінцеву точку ребра.

Рис. 13 Опис класу пріоритетної черги

На рисунку 13 показана реалізація пріоритетної черги. Вона реалізована з використанням допоміжної вбудованої бібліотеки heapq, яка надає інструменти для роботи з пріоритетними чергами, а саме додавання і видалення елементів звідти. Клас PriorityQueue адаптований для комфортної роботи з подіями.

На рисунку 15 вже визначається клас діаграми Вороного. В його ініціалізації визначаються ребра, берегова лінія, а також пріоритетні черги для кожного типу подій. До пріоритетної черги подій точки додаються всі точки, які передаються конструктору при ініціалізації. Попередньо ці точки додатково сортуються по осі у для запобігання помилок в обробці точок, що лежать на одній вертикалі.

Для початку побудови діаграми Вороного потрібно викликати метод process, який починає обробку подій. В ході обробки вибираються найлівіші події і відповідно обробляються. Після закінчення подій точки обробляються залишкові події круга, після чого крайові ребра продовжуються до нескінченності і повертаються самі ребра Вороного.

На рисунку 16 показана реалізація методів обробки відповідно подій точки і кола. Обробка події кола доволі проста. Для початку в 140 рядку створюється нове ребро Вороного яке буде виходити з точки, в яку стягується відповідна дуга (ця точка дістається з відповідної події). Далі в рядках 144-151 відбувається видалення дуги з двозв'язного списку: для цього редагуються попередня та наступна дуга таким чином, щоб вони були сусідніми одне з одним. Після закінчення ребер, які зійшлись в точці, яку описувала подія, в 153-156 рядках, сусідні дуги, що залишились, перевіряються на наявність подій кола (події кола для дуги може не бути, якщо обмежуючі ребра розходяться, а дуга збільшується).



Рис. 15 Конструктор класу діаграми Вороного та метод для її побудови



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

В рядках 171-176 перевіряється, чи є у поточної дуги наступна, і чи перетинає її промінь, який випускається горизонтально з точки. Це потрібно для коректного розділення дуги на дві частини і переадресації посилань сусідніх дуг. В рядках 177-191 створюється нова дуга та нові ребра, які її обмежують. Після цього в рядках 193-195 всі задіяні дуги перевіряються на наявність події круга. Починаючи з 201 рядка починається обробка варіанту коли замітаюча лінія в першу чергу стикається з декількома точками, розташованими вздовж вертикалі. Як ми побачимо пізніше, цей варіант є винятковим, і його треба обробляти окремо.

Рис. 18 Метод для визначення точки перетину горизонтальної прямої і параболи, гілки якої напрямлені вліво

На рисунку 18 визначено метод для знаходження точки перетину між прямою та параболою. Метод нічого не поверне у випадку якщо йому дано неіснуючу дугу, або якщо фокус дуги та поточна точка знаходяться на одній вертикалі, оскільки це призведе до того, попередня дуга не буде розділена на дві - вона буде обрізаною з однієї сторони. Саме тому для вертикального випадку необхідна окрема обробка.

Для того щоб перевіряти перетин прямої тільки з дугою параболи, використовується перевірка, здійснена в рядках 220-226. Для цього знаходяться точки перетину цієї дуги з сусідніми і порівнюються їх укоординату з заданою прямою (оскільки вона горизонтальна). І якщо пряма перетинає дугу параболи, визначається точка перетину. Вже відома укоордината точки перетину, і залишається визначити х-координату:

де L - х-координата директриси параболи (замітаючої лінії), ; У°) вершина параболи, х° - L - параметр параболи, гілки якої напрямлені вліво.

Рис. 19 Метод для визначення точки перетину двох парабол, гілки яких напрямлені вліво і які мають спільну директрису

На рисунку 19 показано метод для знаходження точки перетину двох парабол, які мають одну директрису - замітаючу лінію. Окремими випадками є випадки коли одна з вершин знаходиться на директрисі, і відповідна парабола являє собою промінь. Для знаходження точки перетину двох парабол будується та розв'язується система їх рівнянь. Для цього рівняння зводиться до вигляду х = ay - by - с оскільки парабола знаходиться «на боку»:



Маючи два таких рівняння, можемо відняти їх, і отримати рівняння вигляду:

де а' = а₂ -- а₁, Ь' = Ъ₂ -- Ь₁, с' = с₂ -- с₁. Це звичайне квадратне рівняння яке легко розв'язується. Оскільки обидві параболи знаходяться по одну сторону спільної директриси, таке рівняння завжди матиме розв'язок. Окремим випадком є випадок коли а' = 0, що значить, що дві параболи знаходяться на одній вертикалі, і мають єдину точку перетину, цей випадок обробляється в 250 рядку.



Рис. 20 Методи для перевірки дуги на подію круга, і для закінчення ребер

На рисунку 20 представлені останні два метода класу діаграми Вороного. Перший метод здійснює перевірку дуги на наявність події круга шляхом знаходження центру кола, проведеного через центр цієї дуги, і її сусідніх дуг. Якщо поточна дуга є крайньою, то для неї не існує події круга. Отримана подія заноситься у відповідну пріоритетну чергу.

Для закінчення ребер, які уходять в нескінченність, берегова лінія просто віддаляється на достатньо велику відстань і потрібні ребра добудовуються.



При безпосередньому виклику програми (див. рис. 21) пропонується ввести кількість сайтів та координати сайтів з клавіатури. Далі програма побудує по ним діаграму Вороного і виведе координати ребер.

На рисунку 22 представлений спеціально розроблений десктопний додаток для комфортної роботи та візуалізації діаграми Вороного. Цей додаток пропонує наступний функціонал:

- Додавання сайтів можливе натисканням ПКМ по робочій області / вибрати в меню Edit ^ Add site для введення координати сайту вручну.

- Для побудови діаграми Вороного треба натиснути кнопку DRAW. Після цього можливість ставити точки буде заблоковано

- Після побудови діаграми в меню View доступна візуалізація відповідно вершин, кругів (з центром в вершинах діаграми, які проходять по декільком сайтам), тріангуляції Делоне.

- Для очищення робочої області необхідно натиснути кнопку CLEAR. Після цього знову можна ставити точки

Подивимось, як цей додаток реалізовано програмно.



Рис. 22 Графічний інтерфейс для роботи з діаграмами Вороного

На рисунку 23 імпортуються всі необхідні модулі і бібліотеки, а також визначається константа розміру екрану (він квадратний).

На рисунку 24 бачимо визначення класу вікна і його конструктор, де в 10-14 рядку визначаються допоміжні змінні для збереження стану робочої області та збереження геометричних структур. Далі описується саме вікно та його конфігурація. В рядках 22-31 створюється меню, його елементи, в врешті решт це меню закріплюється за головним вікном. Також ми створюємо саму робочу область. Далі для позиціонування віджетів, які розставляються у вікні за допомогою методу pack, створюється фрейм, в якому описано дві кнопки. Це забезпечує відповідний зовнішній вигляд.



Рис. 24 Ініціалізація вікна додатку

Рис. 25 Опис функціоналу елементів вкладки меню View

На рисунку 25 показано реалізацію функціоналу, який дозволяє візуалізувати деякі елементи діаграми. Відповідні геометричні структури отримуються з діаграми вороного та зберігаються у допоміжні змінні, за допомогою яких їх можна буде прибрати з вікна.

На рисунку 26 показана реалізація можливості додавання сайту шляхом задання координат. В цьому методі описані допоміжні функції для валідації форми для введення координат, і функція яка викликається при натисненні клавіші Submit Тут також створюється фрейм, який вістить в собі дві кнопки та дві мітки, під фреймом розташовується кнопка для створення відповідної точки. При її натисканні, вікно знищується а точка додається на екран.



Висновки

Проведений аналіз алгоритмів побудови діаграми Вороного дає зрозуміти, що на теперішній час найефективнішим практичним алгоритмом побудови діаграми є алгоритм Форчуна. Хоча таку ж ефективність дозволяє досягти і алгоритм «розділяй і володарюй», він є більш складним в реалізації, вимагає передбачення низки частинних випадків та досконалого розуміння механізму злиття діаграм.

Даний алгоритм може бути удосконаленим наступними шляхами: використання збалансованих бінарних дерев пошуку, оптимізація використаних структур даних та структури даних самої діаграми Вороного, що потребує додаткових досліджень. Розробка ефективного алгоритму побудови діаграми Вороного відкриває шляхи для ефективного вирішення багатьох інших задач, а також для досліджень в багатьох наукових галузях.



Література

1. H. Alt, O. Schwarzkopf, “The Voronoi Diagram of Curved Objects”, Available: https:// dl.acm.org/doi/pdf/10.1145/220279.220289

2. F. Aurenhammer, “Voronoi Diagrams -- A Survey of a Fundamental Geometric Data Structure”, Institute fur Informationsverarbeitung Technische Universitat Graz, Sch iet!stattgasse 4a, Austria, 1991

3. J.R. Sack, J. Urrutia, “Handbook of Computational Geometry”, Elsevier Science B.V., Amsterdam, Netherlands, 2000, pp. 203-280

4. A. Dobrin, “A review of properties and variations of Voronoi diagrams”, Available: https://www.whitman.edu/documents/academics/mathematics/dobrinat.pdf

5. Rex A. Dwyer, “Higher-Dimensional Voronoi Diagrams in Linear Expected Time (Extended Abstract)”, North Carolina State University, 1989

6. M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf, Computational Geometry: algorithms and applications, 2nd rev. ed., Berlin, Germany: Springer-Verlag Berlin Heidelberg, 2000, pp. 147-162

7. W. Pokojski and P. Pokojska, “Voronoi diagrams - inventor, method, applications”, Polish Cartographical Review, Val. 50, no. 3, pp. 141-150, Oct. 2018, doi:10.2478/pcr-2018-0009

8. S. K. Dey, “Voronoi diagrams in the max-norm: Algorithms, implementation, and applications”, PhD thesis, Universita della Svizzera Italiana, Lugano, Switzerland, 2015

9. L. Kucera, “Visualization of Abstract Algorithmic Ideas”, Available: https://pdfs. semanticscholar.org/ 2cbb/9df169b20ee81f2af676a32702190fcb2283.pdf

10. O. O. Svitlychnyi and S. V. Plotnytskyi, “Osnovy heoinformatyky: navchalnyi posibnyk [Fundamentals of geoinformatics: a study guide]”, Sumy, Ukraine: ВТД “Університетська книга”, 2006



References

1. H. Alt, O. Schwarzkopf, “The Voronoi Diagram of Curved Objects”, Available: https:// dl.acm.org/doi/pdf/10.1145/220279.220289

2. F. Aurenhammer, “Voronoi Diagrams -- A Survey of a Fundamental Geometric Data Structure”, Institute fur Informationsverarbeitung Technische Universitat Graz, Sch iet!stattgasse 4a, Austria, 1991

3. J.R. Sack, J. Urrutia, “Handbook of Computational Geometry”, Elsevier Science B.V., Amsterdam, Netherlands, 2000, pp. 203-280

4. A. Dobrin, “A review of properties and variations of Voronoi diagrams”, Available: https://www.whitman.edu/documents/academics/mathematics/dobrinat.pdf

5. Rex A. Dwyer, “Higher-Dimensional Voronoi Diagrams in Linear Expected Time (Extended Abstract)”, North Carolina State University, 1989

6. M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf, Computational Geometry: algorithms and applications, 2nd rev. ed., Berlin, Germany: Springer-Verlag Berlin Heidelberg, 2000, pp. 147-162

7. W. Pokojski and P. Pokojska, “Voronoi diagrams - inventor, method, applications”, Polish Cartographical Review, Val. 50, no. 3, pp. 141-150, Oct. 2018, doi:10.2478/pcr-2018-0009

8. S. K. Dey, “Voronoi diagrams in the max-norm: Algorithms, implementation, and applications”, PhD thesis, Universita della Svizzera Italiana, Lugano, Switzerland, 2015

9. L. Kucera, “Visualization of Abstract Algorithmic Ideas”, Available: https://pdfs. semanticscholar.org/2cbb/9df169b20ee81f2af676a32702190fcb2283.pdf

10. O. O. Svitlychnyi and S. V. Plotnytskyi, “Osnovy heoinformatyky: navchalnyi posibnyk [Fundamentals of geoinformatics: a study guide]”, Sumy, Ukraine:

Размещено на Allbest.ru

...