GENERALIZED APPROACH TO THE PROBLEMS OF REPRESENTATION AND PROCESSING OF GRID-BASED GEOMETRIC MODELS

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.

Keywords: grid-based geometric model, point set, discretization of point data, spatial indexing, hash table.