Побудова генератора геометричних об’єктів із заданими властивостями на площині - Фісуненко Андрій Леонідович (My University, 2016)
В роботі розглядається ряд задач на побудову і підрахунок множини простих многокутників різних типів, вершинами яких є всі точки заданої скінченої множини точок і які задовольняють певним критеріям. Для аналізу вхідної множини точок і побудови простих многокутників введені діаграма еквівалентності зіркових розбиттів і граф взаємної видимості вільних точок. Досліджено їх властивості. Для вирішення задачі побудови, підрахунку множини усіх простих многокутників і породження випадкових многокутників на цій множині використано метод 17 послідовного нарощування простого ланцюга з відсіканням. Непродуктивні гілки дерева варіантів відсікаються за допомогою аналізу структури графа взаємної видимості вільних точок, що представляє собою геометричний граф. Розширено перелік необхідних і достатніх умов існування Гамільтона шляху в таких графах, як на основі аналізу їх зв'язності, так і з використанням специфічних умов побудови простого многокутника. Для аналізу гамільтоновості графа, у тому числі, використані двозв’язні компоненти і точки сполучення. Сформульовано і доведено ряд тверджень, що дозволяють прорідити граф взаємної видимості вільних точок, зменшуючи при цьому дерево варіантів. Запропонований підхід дозволяє збільшити максимальний розмір вхідної множини точок для точного повного рішення в середньому з 15 до 25- 30 в залежності від конфігурації точок. Крім того, використання графа взаємної видимості вільних точок дозволяє отримувати точне рішення для важливого окремого випадку - побудови простих многокутників при заданих областях, які заборонено перетинати ребрами многокутника. Для множин з довільною кількістю точок запропонована ефективна процедура для генерації простих многокутників - метод нарощування опуклих оболонок на місці видаленого ребра. На відміну від описаних раніше методів дана евристика гарантовано завершує побудову многокутника для будь-якої множини точок. Крім цього, процедура легко узагальнюється для просторів довільної розмірності і, по суті, є конструктивним доведенням існування поліедра для скінченої множини точок в евклідовому просторі будь-якої розмірності, з точністю до заміни поняття ребра на поняття гіпер-грані. Показано також, що деякі типи простих многокутників, зокрема спіралеподібні, можуть бути отримані за допомогою запропонованої процедури. Введено і досліджено новий тип простих многокутників - квітко-подібні. Запропонована процедури побудови, підрахунку і випадкового породження таких многокутників. При практичній реалізації генератора геометричних об'єктів використаний підхід мульти-алгоритмічного середовища: використані загальні засоби вводу-виводу і візуалізації, а також деякі загальні структури даних. Засоби візуалізації дозволяють досліджувати як прості многокутники, отримані в результаті роботи алгоритмів, так і допоміжні об'єкти: графи взаємної видимості вільних точок і діаграми еквівалентності зіркових розбиттів. Множини породжених многокутників можуть бути використані, як вхідні дані для перевірки довільних алгоритмів обробки простих многокутників. При цьому гарантується якісне покриття та варіативність даних. Ключові слова: обчислювальна геометрія, простий многокутник, полігонізація, породження, генерація, нарощування опуклих оболонок.