Фісуненко Андрій Леонідович. Побудова генератора геометричних об'єктів із заданими властивостями на площині

Краткое описание

Фісуненко Андрій Леонідович. Назва дисертаційної роботи: "Побудова генератора геометричних об'єктів із заданими властивостями на площині "

Київський національний університет
імені Тараса Шевченка
На правах рукопису
ФІСУНЕНКО АНДРІЙ ЛЕОНІДОВИЧ
УДК 004.021:004.023:004.054:519.16
ПОБУДОВА ГЕНЕРАТОРА ГЕОМЕТРИЧНИХ ОБ’ЄКТІВ
ІЗ ЗАДАНИМИ ВЛАСТИВОСТЯМИ НА ПЛОЩИНІ
01.05.01 – теоретичні основи інформатики та кібернетики
Дисертація на здобуття наукового ступеня
кандидата фізико-математичних наук
Науковий керівник:
Терещенко Василь Миколайович,
фізико-математичних наук,
професор
Київ – 2016
1
ЗМІСТ
ПЕРЕЛІК СКОРОЧЕНЬ.......................................................................................... 4
ВСТУП ..................................................................................................................... 5
РОЗДІЛ 1. ПОСТАНОВКА ЗАДАЧІ ТА АНАЛІЗ ІСНУЮЧИХ ПІДХОДІВ
ДО РОЗВ’ЯЗКУ ЗАДАЧ ПОРОДЖЕННЯ ГЕОМЕТРИЧНИХ ОБ’ЄКТІВ..... 12
1.1. Попередні зауваження.............................................................................. 12
1.2. Загальні означення та основні припущення. ......................................... 13
1.3. Складність алгоритмів та модель обчислень......................................... 17
1.4. Узагальнена постановка задач ................................................................ 19
1.5. Аналіз існуючих підходів до розв’язку окремих випадків задач ........ 23
Висновки до Розділу 1....................................................................................... 30
РОЗДІЛ 2. АПАРАТ ДЛЯ АНАЛІЗУ ВХІДНИХ ДАНИХ ТА РОЗВ'ЯЗАННЯ
ЗАДАЧ ПОРОДЖЕННЯ ГЕОМЕТРИЧНИХ ОБЄКТІВ................................... 32
2.1 Вступні відомості ..................................................................................... 32
2.2 Діаграми еквівалентності зіркових розбиттів........................................ 36
2.3 Граф взаємної видимості вільних точок ................................................ 40
Висновки до Розділу 2....................................................................................... 41
РОЗДІЛ 3. МЕТОДИ ПОРОДЖЕННЯ ДОВІЛЬНИХ ПРОСТИХ
МНОГОКУТНИКІВ.............................................................................................. 43
3.1 Доцільність оптимізації методів з повним перебором ......................... 43
3.2 Повний перебір з перевіркою самоперетинів........................................ 44
3.3 Повний перебір з відсіканням зворотних послідовностей................... 48
3.4 Повний перебір з перевіркою ланцюга на самоперетини .................... 52
3.5 Повний перебір та граф взаємної видимості вільних точок ................ 55
Висновки до Розділу 3....................................................................................... 82
РОЗДІЛ 4. МЕТОДИ ПОРОДЖЕННЯ ОКРЕМИХ ТИПІВ
МНОГОКУТНИКІВ.............................................................................................. 83
4.1 Побудова зіркових многокутників.......................................................... 83
4.2 Побудова простих многокутників нарощуванням опуклих оболонок 84
4.3 Квітко-подібні многокутники і метод їх породження .......................... 88
2
4.4 Побудова простих многокутників нарощуванням трикутниками....... 90
Висновки до Розділу 4....................................................................................... 93
РОЗДІЛ 5. ПРАКТИЧНА РЕАЛІЗАЦІЯ............................................................. 95
5.1 Загальна архітектура програмної реалізації генератора геометричних
об’єктів................................................................................................................ 95
5.2 Формат вхідних даних................................................................................. 96
5.3 Формат вихідних даних............................................................................... 97
5.3 Приклади роботи генератора геометричних об’єктів та засобів
візуалізації .......................................................................................................... 99
5.4 Застосування точного розв’язку Задачі 1 для отримання точного
значення оптимальної конфігурації при N=7 ............................................... 101
5.5 Застосування точного розв’язку Задачі 1 для оцінювання жадібного
алгоритму знаходження простого многокутника мінімальної площі........ 102
Висновки до Розділу 5..................................................................................... 103
ВИСНОВКИ......................................................................................................... 104
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ........................................................... 107
ДОДАТКИ............................................................................................................ 115
Додаток А. Порівняння точного і наближеного розв’язків задачі про
простий многокутник найменшої площі. ...................................................... 115
Додаток Б. Вихідний код окремих частин практичної реалізації генератора
геометричних об’єктів..................................................................................... 123
3
ПЕРЕЛІК ПОЗНАЧЕНЬ
E
d
- Евклідовий простір розмірності d.
S - S={p1, p2, …, pN} – скінчена множина точок
евклідового простору E
d
, де i-а точка pi – це dплекс (x1, x2, …, xd), що складається з дійсних
чисел xi(i=1, …, d).
CH(S) Опукла оболонка (convex hull) множини
точок S.
 для будь-якого
 існує
|S| міцність множини S (кількість елементів для
скінченої дискретної множини)
SP(S) SP(S)={P1(S), …, PM(S)} – множина усіх
можливих простих многокутників для
заданої множини точок S.
4
ПЕРЕЛІК СКОРОЧЕНЬ
ГО Геометричний об’єкт
ОО Опукла оболонка
RAM Random Access Memory
(пам’ять довільного доступу)
CAD Computer-Aided Design
(автоматизоване проектування)
DFS Depth First Search
(пошук в глибину)
BCC Biconnected Component
(двозв’язна компонента)
5
ВСТУП
Актуальність теми. Сучасній людині щодня доводиться мати
справу з результатами роботи алгоритмів обробки геометричних об’єктів
обчислювальними системами: в графічних інтерфейсах цифрових пристроїв, в
автоматизовано створених конструкціях, інструментах, машинах. Сучасні
технології базуються на проектуванні виробів в CAD-системах, які, в свою
чергу, зараз неможливо уявити без алгоритмів обчислювальної геометрії.
Як самостійна галузь науки, обчислювальна геометрія сформувалася в
середині 70-х років минулого століття. Разом з розвитком комп’ютерної
техніки і засобів графічного вводу-виводу потреби в результатах досліджень
цієї тематики тільки зростали. Задачам і методам ефективної обробки
геометричних об’єктів приділяли увагу такі вчені, як M. Shamos, F. Preparata,
J. O’Rourke, R. Karp, M. Overmas, B. Chazelle, J. Goodman, N. M. Amato, K.
Brown, C. Papadimitriou, S. Fekete, F. Hurtado, P. Erdos, M. Newborn, S. Akl, E.
M. Arkin, Y.-J. Chiang, M. Held, J.S.B. Mitchell, V. Sacristan, S. Skiena, T.-C.
Yang та багато інших.
Многокутники – це один з найпростіших геометричних об’єктів, але,
незважаючи на простоту, дуже багато складних задач обчислювальної
геометрії зводяться до побудови і знаходження їх певних характеристик,
перевірки властивостей.
Окрім прямого традиційного застосування в CAD-системах,
комп’ютерній графіці та системах візуалізації, многокутники інтенсивно
використовуються в розпізнаванні образів, обробці супутникових та медичних
зображень, мультимедійних та GIS-системах. Останнім часом, у зв’язку з
бурхливим розвитком таких нових прикладних міждисциплінарних напрямків,
як віртуальна та збагачена реальність, потреби в ефективних методах обробки
геометричних об’єктів стають ще більш актуальними.
Тому алгоритми обробки многокутників – один із найбільш важливих
розділів обчислювальної геометрії. Зокрема, цей напрямок досліджень
6
розвивався і вітчизняними вченими, такими як Анісімов А. В. , Шор Н.З., Ю.Г.
Стоян, М.І. Шлезінгер, Є.М. Кисельова, Ю.І. Петунін, В.П. Клименко, О.М.
Васюков, О.А. Ємець, Терещенко В. М., Клюшин Д.А., Рубльов Б. В.,
Семенова Н.В., Панкратов О. В та інші.
Водночас з практичними задачами існує низка відкритих
фундаментальних проблем обчислювальної геометрії, зокрема питання щодо
складності підрахунку усіх можливих простих многокутників для заданої
множини точок, пошуку, так званих, оптимальних конфігурацій для заданої
кількості точок, які максимізують кількість можливих простих многокутників,
породження многокутників із заданими властивостями.
Ці задачі можуть використовуватись для забезпечення якості
програмно-апаратних комплексів, що використовують такі алгоритми
обчислювальної геометрії. Наприклад, для України є дуже нагальною
проблема екологічного моніторингу лісових та інших ресурсів, оцінки та
аналіз яких здійснюються з використанням супутникових зображень, які, в
свою чергу, обробляються із застосуванням многокутників та алгоритмів над
ними [64].
Таким чином, тематика даної дисертаційної роботи, що присвячена
базисним задачам комбінаторної та обчислювальної геометрії є актуальною.
Зв’язок роботи з науковими програмами, планами, темами. Робота
є складовою частиною наукових робіт, які ведуться на кафедрі математичної
інформатики факультету кібернетики Київського національного університету
імені Тараса Шевченка при виконанні теми “Створення теоретичних основ,
методів та програмних засобів інтелектуалізації інформаційнокомунікаційних та трансформерних технологій” (№ держреєстрації –
0111U005416, 2011-2015 рр.).
Мета і задачі дослідження. Мета і задачі дослідження. Метою
дисертаційного дослідження є створення ефективних методів і алгоритмів
генерації геометричних об’єктів із заданими властивостями та їх практична
реалізація.
7
Для досягнення поставленої мети необхідно було вирішити такі основні
задачі:
1. розробка алгоритмів генерації простих многокутників із заданими
властивостями;
2. дослідження особливостей генерації простих многокутників в
залежності від конфігурації множини точок, які повинні бути
вершинами отриманих многокутників;
3. пошук оптимальних об’єктів за визначеними критеріями;
4. узагальнення методів генерації простих многокутників для
породження простих поліедрів у просторах більшої розмірності (d=3,
4,…);
5. практична реалізація алгоритмів та пов’язані задачі:
– оптимізація алгоритмів генерації;
– візуалізація алгоритмів та результатів їх роботи;
– практичне застосування розроблених алгоритмів і методів.
Об’єкт дослідження – процес породження геометричних об’єктів на
скінчених множинах точок з повним включенням усіх точок до породжених
об’єктів.
Предмет дослідження – стратегії та підходи ефективного породження
геометричних об’єктів.
Методи дослідження. Дисертаційна робота ґрунтується на:
- загальних методах прикладної теорії алгоритмів;
- методах обчислювальної геометрії;
- методах інтерактивної комп’ютерної графіки та візуалізації.
Наукова новизна одержаних результатів. У дисертаційній роботі
розвинуто методи генерації простих многокутників.
Вперше:
- розроблено метод генерації простих многокутників нарощуванням
опуклих оболонок, на основі якого доведено існування простого поліедра в
евклідовому просторі довільного виміру d для скінченої множини точок, жодні
8
d+1 з яких не лежать в одній гіперплощині, та запропоновано новий алгоритм
генерації простих поліедрів, що включають усі точки вхідної множини у якості
вершин;
- показано, що раніше відомі спіральні многокутники, можуть бути
отримані як окремий випадок методу вирізання та нарощування опуклих
оболонок;
- розширено діапазон застосування алгоритму генерації випадкових
елементів з повної множини усіх можливих простих многокутників з
використанням поняття графа взаємної видимості вільних точок;
- розроблено метод підрахунку усіх можливих простих полігонізацій
скінченої множини точок на площині;
- досліджено новий клас об’єктів - квітко-подібні многокутники і
запропоновані методи їх породження і підрахунку;
- запропоновано новий клас розташувань – діаграму еквівалентності
зіркових розбиттів та досліджено її застосування для алгоритму генерації та
підрахунку квітко-подібних многокутників.
Практичне значення одержаних результатів. Робота має як
теоретичну, так і прикладну спрямованість. Отримані результати розширюють
коло вирішених задач, що пов’язані з відкритими проблемами обчислювальної
геометрії; можуть бути застосовані при розробці та тестуванні алгоритмів
обчислювальної геометрії, які оперують простими многокутниками та їх
узагальненнями для просторів більших вимірів - поліедрів, а також для
перевірки та порівняння різних наближених розв’язків оптимізаційних задач
над множинами простих многокутників на заданій скінченій множині точок.
Результати, які отримані при проведенні роботи, можуть
використовуватись для забезпечення перевірки доведення коректності та
якості реалізації рішень оптимізаційних задач та задач генерації геометричних
об’єктів із заданими властивостями.
Особистий внесок здобувача. Всі результати, які складають суть
дисертаційної роботи, одержані здобувачем самостійно. З робіт, виконаних із
9
співавторами, на захист виносяться лише результати, одержані особисто
здобувачем.
З робіт, виконаних із співавторами, на захист виносяться лише
результати, одержані особисто здобувачем. Персональний внесок здобувача
до всіх наукових праць, опублікованих із співавторами 2), 5)-11) полягає у
застосуванні розроблених за темою дисертації методів генерації геометричних
об’єктів із заданими властивостями, як вхідні дані для перевірки програмних
реалізацій відповідних алгоритмів та вимірювання результатів чисельного
експерименту, порівняння результатів з відомими результатами попередніх
досліджень.
Апробація результатів дисертації. Основні ідеї і положення
дисертаційного дослідження обговорювалися на наукових семінарах кафедри
математичної інформатики Київського національного університету імені
Тараса Шевченка. Основний зміст дисертаційної роботи викладено та
оприлюднено у доповідях і тезах міжнародних і всеукраїнських наукових
конференцій, зокрема:
- 16th International Conference on Information Visualisation IV2012,
Montpellier, France, 11-13 July 2012 (міжнародна конференція,
Франція);
- XIX International Conference “Problems of Decision Making under
Uncertainties”, Україна, 23-27 квітня, 2012 р. (міжнародна
конференція, Україна);
- 1-а міжнародна науково-технічна конференція «Комп’ютерна графіка
та розпізнавання зображень», 17-18 травня, Вінниця. Україна, 2012 р.;
- 12th IC “Parallel Computing Technologies”, St.-Petersburg, Russia,
September 30 - October 4, 2013, PaCT 2013 – (міжнародна конференція,
РФ);
- International Conference "Parallel and Distributed Computing Systems"
PDCS 2013, Ukraine, Kharkiv, March 13-14, 2013 (міжнародна
конференція, Україна);
10
- 7th International Academic Conference “Computer Science & Engineering
2015” (CSE-2015) as a part of International Youth Science Forum “Litteris
Et Artibus”, November 26–28, 2015, Lviv, Ukraine (міжнародна
конференція, Україна).
Публікації. За результатами дослідження опубліковано 6 наукових
праць – 4 наукових статей у фахових виданнях ВАК України, 2 – у
міжнародних журналах, що індексуються у наукометричній базі SCOPUS, та
6 тез міжнародних конференцій.
Список опублікованих праць за темою дисертації.
1) Фісуненко А. Л., Модель мультиагентної системи обробки візуальної
інформації для вирішення задач реконструкції / А. Л. Фісуненко //
Вісник Київського університету. Серія: фізико-математичні науки,
№3. – 2012. – C. 261-264.
2) Фісуненко А. Л., Особливості розв’язання задач регіонального пошуку
для d-вимірного випадку / В. М. Терещенко, А. Л. Фісуненко // Вісник
Київського університету. Серія: фізико-математичні науки, №4. – 2012.
– C. 207-210.
3) Фісуненко А. Л., Генерація простих многокутників вирізанням та
нарощуванням опуклих оболонок / А. Л. Фісуненко // Вісник Київського
університету. Серія: фізико-математичні науки, спецвипуск – 2013. –
C. 190-193.
4) Фісуненко А. Л., Діаграма еквівалентності зіркових розбиттів та
генерація простих многокутників / А. Л. Фісуненко // Вісник Київського
університету. Серія: фізико-математичні науки, №2 – 2014. – С. 210-214.
5) Fisunenko A. Domain Triangulation between Convex Polytopes. /
V. Tereshchenko, S. Pilipenko, A. Fisunenko (SCOPUS Author ID:
55433978800) // Journal “Procedia Computer Science”, Volume 18, Elsevier,
2013. – P. 2500-2503.
6) Fisunenko A. Algorithm for Finding the Domain Intersection of a Set of
Polytopes / V. Tereshchenko, S. Pilipenko, A. Fisunenko (SCOPUS Author
11
ID: 55433978800) // Journal “Procedia Computer Science”, Elsevier,
Volume 18, 2013. – P. 459-464.
7) Fisunenko A. Solving the Range Searching Problem for Region Bounded by
a Convex Surface / V. Tereshchenko, O. Socolov, A. Fisunenko// Proceedings
of the 16th International Conference on Information Visualisation IV2012,
Montpellier, France, 11-13 July 2012. – P. 491- 494.
8) Фісуненко А. Л., Модель мультиагентної адаптивної обробки візуальної
інформації. / Терещенко В. М., Фісуненко А. Л. // Abstracts of the XIX
International Conference “Problems of Decision Making under
Uncertainties”, Україна, 23-27 квітня, 2012. – C. 214-215
9) Фісуненко А. Л. Триангуляція прямолінійного планарного графа
гострими кутами / Терещенко В. М., Фісуненко А. Л. // Матеріали 1-ої
міжнародної науково-технічної конференції «Комп’ютерна графіка та
розпізнавання зображень», 17-18 травня, Вінниця. Україна, 2012. – C.
184-188.
10) Fisunenko A. The Unified Algorithmic Platform for Solving Complex
Problems of Computational Geometry / V. Tereshchenko, I. Budjak,
A. Fisunenko // In Proc. of the 12th IC “Parallel Computing Technologies”
(PaCT 2013), Springer. 2013. – P. 424-429.
11) Fisunenko A. An approach to solving complex problems of
computational geometry / V. Tereshchenko, I. Budjak, A. Fisunenko // In
Proceedings of International Conference "Parallel and Distributed Computing
Systems" PDCS 2013 (Ukraine, Kharkiv, March 13-14, 2013. - P.320.
12) Fisunenko A., One Approach for Computing Simple Polygons on a
Given Point Set in the Plain / A. Fisunenko // In Proc. of 7th International
Academic Conference “Computer Science & Engineering 2015” (CSE-2015)
as a part of International Youth Science Forum “Litteris Et Artibus”, Lviv,
Ukraine, November 26–28, 2015. – P. 44-45.

Список литературы

ВИСНОВКИ
Головним результатом дисертаційної роботи є побудова
мультиалгоритмічної платформи-генератора геометричних об’єктів на
площині, що розв’язує задачу породження простих многокутників певних
типів із визначеними властивостями на заданих скінчених множинах точок.
Основні результати дисертації.
1. Вперше застосовано поняття діаграми еквівалентності зіркових
розбиттів, та областей еквівалентності для аналізу вхідних множин
точок на площині та процедур породження декількох типів простих
многокутників.
2. Досліджено та суттєво розширено перелік необхідних і достатніх умов
існування Гамільтонового шляху в таких геометричних графах і
відповідно, перевірки можливості завершити ланцюг побудовою
простого многокутника. Умови існування Гамільтонового шляху
базуються на аналізі графу взаємної видимості вільних точок. Загальна
складність усіх перевірок умов обмежена O(N
2
) при умові використання
O(N
2
) пам’яті. Отримано прискорення алгоритму шляхом скорочення
об’єму обчислювань з плаваючою точкою на перевірки перетинів
відрізків ціною O(N
4
) пам’яті, в якій зберігається попередньо оброблена
інформація про перетині усіх пар відрізків.
3. Розроблено метод послідовного нарощування простого ланцюга з
відсіканням дерева варіантів для реалістичних розмірів вхідної
множини, який, фактично, наблизив складність обчислювань до
O(P(N)a
N
), де P(N) – поліноміальна функція від N; а – деяка константа.
4. Розроблено метод підрахунку усіх можливих простих многокутників на
заданій скінченій множині точок, який суттєво прискорює процедури
шляхом рекурсивного розбиття на під-задачі пошуку кількості
105
Гамільтонових шляхів на двозв’язних компонентах та перемноження
окремих результатів.
5. Розроблено евристичний метод породження простих многокутників
нарощуванням простих оболонок на видаленому ребрі простого
ланцюга, що будується. Доведено, що метод є одним із самих
ефективних на сьогодні, маючи часову складність O(NlogN), та
потребуючи O(N) пам’яті. Показано, що деякі з відомих типів простих
многокутників, зокрема спіральні, можуть бути отримані, як окремий
випадок запропонованого методу.
6. Узагальнено метод нарощування простих оболонок для евклідових
просторів довільної розмірності.
7. Доведено існування простого поліедру для скінченої множини точок у,
так званому, загальному розташуванні, коли жодна з d+1 точок не
знаходяться в одній гіперплощині.
8. Вперше досліджено властивості нового типу простих многокутників –
квітко-подібних (квіткових).
9. Розроблено відповідну процедуру породження квітко-подібних
многокутників з використанням діаграми еквівалентності зіркових
розбиттів.
10.Узагальнено на простори більших розмірностей жадібний метод пошуку
простого многокутника мінімальної площини, який включає усі точки
вхідної множини у якості вершин: жадібний метод пошуку простого
поліедра мінімального об’єму.
11.Виконано практичну реалізацію генератора геометричних об’єктів у
вигляді мульти-алгоритмічного середовища та засобів візуалізації
множин простих многокутників, діаграм еквівалентності зіркових
розбиттів та графів взаємної видимості вільних точок. Формати вхідних
та вихідних даних розроблені таким чином, щоб уможливити просте
використання множин точок і відповідних породжених многокутників
для перевірки алгоритмів обчислювальної геометрії.
106
12. Застосовано практичну реалізацію генератора геометричних об’єктів до
верифікації низки алгоритмів єдиного алгоритмічного середовища
розв’язування комплексу задач обчислювальної геометрії, що
розробляється на кафедрі математичної інформатики факультету
кібернетики Київського національного університету імені Тараса
Шевченка та задач, які розв’язуються в рамках проектів «Rectilinear
Crossing Number Project» і «ComPoSe: Combinatorics on Point Sets and
Arrangements of Objects» [2]. Зокрема, за допомогою точного розв’язку
Задачі 1 виконано оцінку ефективності жадібного алгоритму пошуку
простого многокутника мінімальної площі представленому в публікації
[49]. Доведено з використанням точного розв’язку Задачі 1 та діаграми
еквівалентності зіркових розбиттів, що максимальна кількість можливих
простих многокутників для будь-якої множини з 7 точок не може
перевищувати 92. Шляхом вичерпного обчислювального експерименту
показано, що для інтервалу N=4…7 виконується наступне: кожна
оптимальна конфігурація для N+1 точок може бути отримана з
оптимальної конфігурації для N точок з використанням діаграми
еквівалентності зіркових розбиттів для вичерпного перебору усіх
можливих типів розташування.