Побудова генератора геометричних об’єктів із заданими властивостями на площині

Фісуненко Андрій Леонідович

Побудова генератора геометричних об’єктів із заданими властивостями на площині

Тип публікації :

Автореферат

Дата випуску :

2016

Автор(и) :

Фісуненко Андрій Леонідович

Мова основного тексту :

ua

eKNUTSHIR URL :

https://ir.library.knu.ua/handle/123456789/4589

Цитування :

[APA 7] Фісуненко, А. Л. (2016). Побудова генератора геометричних об’єктів із заданими властивостями на площині [Автореф. дис. канд. фіз-мат. наук, Київський національний університет імені Тараса Шевченка]. eKNUTSHIR. https://ir.library.knu.ua/handle/123456789/4589

[ДСТУ] Фісуненко А. Л. Побудова генератора геометричних об’єктів із заданими властивостями на площині : автореф. дис. … канд. фіз-мат. наук : 11 Математика та статистика. Київ, 2016. 22 с. URL: https://ir.library.knu.ua/handle/123456789/4589 (дата звернення: 25.07.2026).

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

Ключові слова: обчислювальна геометрія, простий многокутник, полігонізація, породження, генерація, нарощування опуклих оболонок.

Галузі знань та спеціальності :

11 Математика та статистика

111 Математика

Файл(и) :

Завантажити

Формат :

Adobe PDF

Розмір :

540.28 KB

Контрольна сума :

(MD5):c7411e926f03abd59df44c16bfe95a25

Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Якщо не вказано інше, ця робота розповсюджується на умовах ліцензії Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International