SPATIAL TRANSFORMATIONS OF POINT SETS ON INTEGER REGULAR GRIDS

Abstract

The work is devoted to the development of a generalized approach to the development of methods of spatial transformations on integer regular grids for solving the problems of time-efficient processing of point sets presented in the form of discretized data on regular grids. Examples of such transformations are spatial indexing and visualization on a two-dimensional plane. The constant growth of both the volume and dimension of the data processed in practical problems leads to an increase in the requirements for the computational efficiency of the algorithms used to solve them. There is a wide range of tasks in which the use of spatial transformations can be used to increase the efficiency of calculations, for example, storage and use of resources, fast data processing, data visualization, increasing the speed of modern algorithms for intelligent data analysis. Other examples of tasks are set coverage tasks, image search by content, geospatial data processing. Methods for optimizing computational efficiency in algorithms for solving similar problems are most often based on the use of methods for ordering point sets through the use of spatial data structures and algorithms for their processing. The paper presents a generalized approach to creating methods of spatial transformations based on methods of spatial indexing of integer regular grids, which makes it possible to reduce point data processing algorithms to linear time complexity regardless of the dimension of the input data. The paper proposes schemes of spatial transformations based on linear and power functions, as well as on the basis of determining whether points belong to a certain region of space. The basis of the approach is the operations of discretization and indexing of point data. The paper considers a way to solve the problem of exponential growth of the number of cells on an integer regular grid for storing points. Basic operations and algorithms for direct and inverse transformations in metric spaces are proposed. In the paper, the basic characteristics of transformations are given and an approach to evaluating the effectiveness of transformations based on them is given.

Keywords: spatial transformations, integer regular grid, point set, discretized data, spatial indexing, ordering of point sets, visualization.