GENERALIZED APPROACH FOR SPATIAL PROCESSING OF POINT SETS ON A PLANE

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.Keywords: spatial processing, point set, interaction of points, discretized regular grid, spatial hashing.