ОБОБЩЕННЫЙ МЕТОД ПРОСТРАНСТВЕННОЙ ОБРАБОТКИ ТОЧЕЧНЫХ МНОЖЕСТВ НА ПЛОСКОСТИ

Аннотация

Работа посвящена разработке универсального подхода к решению задач пространственной обработки точечных множеств на плоскости, к которым можно отнести задачи определения соседства точек, расстояний между точками, определение взаимовлияния точек, определение вхождения точек в некоторые области произвольной геометрической формы, определение метрических и пространственных точечных характеристик. множеств, определение расположений точек на основе заданных метрических ограничений и генерация точечных множеств. В таких задачах существует необходимость эффективного с точки зрения времени вычислений решения пространственных задач на точечных множествах с большим количеством точек, например, определение расстояний между объектами, поиск ближайших или удаленных объектов, определение взаимовлияния объектов в зависимости от их взаимных расположений. Существующие методы решения подобных задач базируются на использовании методов математической оптимизации, являются затратными по времени и не предоставляют точных решений. В работе представлен обобщенный метод для решения задач пространственной обработки точечных множеств на плоскости за счет использования пространственной хэш-таблицы и массива-аккумулятора для хранения дискретизированной регулярной сетки, позволяющих за линейное от количества точек время определять все точки множества, входящие в некоторое области воздействия. Линейность достигается за счет цепных отображений координат точек из пространства хешей в пространство дискретизированной сетки. Представленный подход состоит из следующих шагов: формирование критерия взаимной досягаемости точек на основе выбранной метрики; определение размерности дискретизированной сетки; индексация точек сетки; нанесение областей воздействия заданной формы на сетку; определение точек, принадлежащих нанесенным областям; анализ весовых значений в массиве-аккумуляторе.Ключевые слова: пространственная обработка, точечное множество, взаимовлияние точек, дискретизированная регулярная сетка, пространственное хеширование.