Узагальнений підхід до задач представлення і обробки сіткових геометричних моделей

Abstract

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

The work is devoted to the development of a generalized approach to solving problems of processing point sets presented in the form of discretized grid based geometric models. Examples of problems are spatial problems, for example, finding nearest neighbors, estimating the coverage of a set, problems of location of points, finding relationships in point sets, etc. Other tasks include the modeling of human flows, planning of urban environments, traffic control tasks for mobile robots and unmanned vehicles. The amount of point data in such problems is constantly growing, which requires the search for more efficient computational models for solving such problems, appropriate data structures and methods of their transformation and processing. Methods for solving similar problems are often based on the use of optimization methods, or are expensive in terms of computational complexity. The work presents a generalized method for solving the problems of spatial processing of point sets, which allows to achieve exact solutions under the condition of their linear complexity, regardless of the dimensionality of the input data. The paper introduces the concept of a grid-based geometric model and its definition for one-dimensional and two dimensional spaces. The basis of the approach is the operations of discretization and indexing of point data and operations of processing data structures containing data transformations, such as point location and fill operations of a grid based geometric model and logical operations on models. Basic structures for storing and processing point data, segments, arbitrary objects and the operation of expanding structures for solving practical problems of processing mesh models are proposed. The approach is illustrated by a practical example of solving the problem of finding intersections of segments on a plane and can be extended to solve problems in spaces of arbitrary dimensions. The presented approach consists of the following steps: discretization of input data; spatial indexing of discretized data with entering values into a spatial hash table; creation and processing of list data structures in which the solution of the problem will be stored.