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

Abstract

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

The work is devoted to the development of a universal approach to solving problems of spatial processing of point sets on a plane, which include problems of determining the neighborhood of points, distances between points, determining the interaction of points, determining the occurrence of points in some areas of arbitrary geometric shape, determining metric and spatial characteristics sets, determining the location of points based on given metric constraints and generating point sets. In such problems there is a need for time efficient computation of spatial problems on point sets with a large number of points, for example, determining the distances between objects, finding the nearest or farthest objects, determining the interaction of objects depending on their mutual locations. Existing methods for solving such problems are based on the use of mathematical optimization methods, are time consuming and do not provide exact solutions. The paper presents a generalized method for solving problems of spatial processing of point sets on a plane by using a spatial hash table and an array-accumulator to store a discretized regular grid, which allows to determine all points of a set included in some areas of influence. Linearity is achieved by chain mappings of the coordinates of points from the hash space to the space of the sampled grid. The presented approach consists of the following steps: formation of the criterion of mutual reachability of points on the basis of the chosen metric; determining the dimension of the discretized grid; indexing of grid points; drawing areas of influence of a given shape on the grid; identification of points belonging to the applied areas; analysis of weight values in the array-battery.