УЗАГАЛЬНЕНИЙ ПІДХІД ДО ЗАДАЧ ПРЕДСТАВЛЕННЯ І ОБРОБКИ СІТКОВИХ ГЕОМЕТРИЧНИХ МОДЕЛЕЙ

Анотація

Роботу присвячено розробці узагальненого підходу до розв’язання задач обробки точкових множин, що представлені в вигляді дискретизованих сіткових геометричних моделей. Прикладами задач є просторові задачі, наприклад, пошук найближчих сусідів, оцінювання покриття множини, задачі розташування точок, пошук взаємозв’язків в точкових множинах тощо. Іншими задачами є моделювання людських потоків, планування міських середовищ, задачі керування рухом мобільних роботів та безпілотних транспортних засобів. Обсяг точкових даних в таких задачах постійно зростає, що вимагає пошуку більш ефективних обчислювальних моделей для розв’язку таких задач, відповідних структур даних і методів їх перетворення та обробки. Методи для розв’язання подібних задач найчастіше базуються на використання методів оптимізації, або є витратними з точки зору обчислювальної складності. В роботі представлено узагальнений метод для розв’язання задач просторової обробки точкових множин, який дозволяє досягти точних розв’язків за умови їх лінійної складності незалежно від розмірності вхідних даних. В роботі вводиться поняття сіткової геометричної моделі та її визначення для одновимірних та двовимірних просторів. Основою підходу є операції дискретизації та індексації точкових даних та операції обробки структур даних, що містять перетворені дані, такі як операції розташування та заповнення точками сіткової геометричної моделі та логічні операції над моделями. Запропоновано базові структури для зберігання та обробки точкових даних, відрізків, довільних об’єктів та операцію розширення структур для розв’язання практичних задач обробки сіткових моделей. Підхід ілюстровано практичним прикладом розв’язання задачі пошуку перетинів відрізків на площині та може бути розширений для розв’язання задач у просторах довільних розмірностей. Представлений підхід складається з наступних кроків: дискретизація вхідних даних; просторова індексація дискретизованих даних із занесенням значень у просторову хеш-таблицю; створення і обробка спискових структур даних, в яких зберігатиметься розв’язок задачі.

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