In the article it is proposed to apply computer topology methods to create effective data structures that will allow storing and processing spatial scenes in n-dimensional space. The basis for the representation of nD-geoobjects is n-dimensional simplexes. For example, the representation of spatial data of high dimension will allow us to describe the topological relationships between 3D objects in time. The mathematical foundations and software for representation and processing of spatial data of high dimension are developed. The algorithm for encoding spatial objects nD in GIS will provide an opportunity to solve a wide range of tasks for processing complex graphic information.
The development of GIS technologies in the modern world is advancing towards the use of 3D maps, multiscale, and also in the analysis of the time component. For high dimensions, those algorithms that work well for 2D and 3D cards are inapplicable. Integration in GIS of additional characteristics, such as the third spatial dimension, time, and scale, has so far been achieved mainly through special adaptations to 2D data structures, and not by creating new ones that extend the capabilities of GIS software.
The urgency of the work is that existing algorithms for processing and analyzing spatial scenes in
n- dimensional space require significant time-consuming, or expected loss of processing quality. The
integration of dimensions raises new requirements for creating new methods and algorithms for
processing spatial data. The use of topological data analysis is a promising direction in GIS. The paper
proposes to apply the topology of computer techniques to create efficient data structures that will store
and process spatial scene in a single n-dimensional spatial [
For the destruction of objects in the GIS, there are different sets of data structures [
The paper [
In [
OBS has the following key features: 1. The object is a logical block of memory that contains object data, object attributes, and methods; 2. the interface of the object is a simple method, such as creating, deleting, opening, closing, reading, writing, etc.; 3. OBS allows intelligent devices, including device and data management, object structure and interpretation relationships, access patterns and security settings.
Advantages of OBS: 1. high performance; 2. security; 3. scalability.
Disadvantages of this method is the inability to work with nD objects, since the functional does not provide for storing the properties of these objects.
The article [
Isolated nodes. The spatial topology data model allows you to integrate isolated nodes into the topology. An important advantage of this is that isolated nodes inside can be identified through links to the database and not resorting to spatial search.
Coordination of storage of the connected nodes. There is a small amount with Oracle's spatial topology data model. Coordinates for connecting nodes are stored twice. This is because the spatial topology data model stores each edge as an Oracle Spatial SDO_Geometry data type. This SDO_Geometry for the edge includes all coordinates, including those that correspond to the start and end nodes.
Thus, for these initial and final nodes, the latitude / longitude coordinate is stored twice; once as part of the SDO_Geometry and once on the connection node record. The API for the Oracle Spatial Topology Data Model manages this data transparently for the user and keeps it consistent.
The authors of Ref. [
But these algorithms are not designed for nD objects, including for storing information about the scale of maps and the time of changing objects on the map. Since they allow you to store either only geometric information, or specific topological features.
The basis of representation nD geoobjects can be put n-dimensional simplexes. For example, the representation of spatial data of high dimension will allow to describe topological relations between 3D objects in time. There is a need to develop mathematical bases and software for the presentation and processing of spatial data of high dimensionality. The algorithm for coding nD spatial objects in the GIS will make it possible to solve a wide range of tasks for processing complex graphic information.
Vector representations of nD objects exclude the following problems: they are usually more compact, they can describe boundaries more accurately than raster ones, and represent object attributes directly. This makes them particularly interesting for more advanced GIS, even if they wer e explored as data structures. Usually, the objects used in the 2D vector GIS are not considered in other dimensions. However, there are various multidimensional geometric and topological structures that were developed in other areas and can be used for these purposes. Even with the fact that they are difficult to implement and use, and often require additional computation to support some aspects of real data. Therefore, they were almost never used in practice. It was for these objects that a data storage structure was developed based on a compressed simplex tree.
A simplex is a convex hull of n + 1 points of an affine space (dimension n or greater) that are assumed to be affine independent (that is, they do not lie in a subspace of dimension n - 1). These points are called the vertices of a simplex. An example of a simplex is shown in figure 1.
A simplicial complex is a topological space represented as a union of sets homoeomorphic to a simplex and forming a triangulation of this space such that: 1. with any of the simplexes in this set all its faces enter; 2. any two simplexes either do not have a common point at all, or intersect only along a whole face of some dimension, and only one face; 3. for any point x of the complex there is a neighbourhood U such that if it U intersects with the simplex of the complex then x .
Let be K { 0 i } a simplicial complex, which is shown in figure 2. i {xi , yi , zi , m j , t j } where xi , yi , zi the set of coordinates of the object in the set, i {1n} , m j - is the scale on which the object is displayed, and t j is the time interval in the set into j {1n} which the object on the map was changed.
A simplicial tree of an undirected graph G is the spanning tree of a graph G with a distinguished root with the property that any two adjacent vertices in the graph G are related to each other by an ancestor / child relation. All search trees in depth and all the hamiltonian paths are simplex trees.
In finite graphs, although depth-first searches are inherently sequential, simplex trees can be constructed by a randomized parallel algorithm with a complexity class.
Simplicial trees can be used to determine the depth of the graph tree and as part of the planarity test for checking whether the graph is planar. The description of trees by the one-place logic of secondorder graphs makes it possible to recognize the graph-dependent properties of orientation effectively for graphs with bounded tree width using the Course theorem. Not every infinite graph has a tree of simplexes and graphs, which have no such tree, can be described by forbidden minors.
A tree of simplexes exists in any graph with a countable number of vertices, even if the version of infinite depth search cannot successfully verify all vertices of the graph. In an infinite graph a tree must have exactly one infinite path for each ray of the graph and the existence of a simplicial tree characterizes graphs whose topological completions, formed by adding an infinitely distant point for each ray, are metric spaces.
To represent a compressed tree of simplexes K , we store the corresponding numbers in the tree that satisfy the following properties:
1. The nodes of a tree are in a bijection with simplexes of all dimensions of the complex. The first level is associated with an empty face.
2. Each node of the tree, except the first, preserves the label of the vertex. In particular, the node N associated with the simplex retains the label of the extreme vertex ( ).
3. Vertexes, whose labels occur along the path from the first level of the tree to the node N , are
connected with the simplex , are vertices . The labels are sorted in ascending order along the
given path, and each label appears only once. This data structure is called a simplicial tree K [
Consider the simplex tree in figure 3, which contains the following sublevels: 1. the card; 2. scale; 3. The object; 4. coordinates of the object; 5. Time; 6-7. other sublevels
It should be noted that in this figure an area is created, beginning with sublevel 2. These objects are compressed, identical and are on different scales.
The purpose of compression is to identify the common parts of the object and save them only once. More specifically, if the same subtree is located on two different nodes of the simplex tree, then the subtree is stored only once, and the two root nodes now point to a unique copy of the subtree. As a consequence, the nodes are no longer in a bijection with the nodes of the complex, but we still have the property that the paths from the root are in a bijection with simplexes.
Access to all the heirs of a compressed simplex tree can be realized similarly to the usual simplex tree. Allowing an ascending traversal in the tree is also possible (with additional pointers from descendants to ancestors), and this improves the efficiency of some operations, such as surface searches. However, in the compressed simplex tree, the ancestors are not unique. To accommodate this, we mark the ancestors that were available, and use this to return in the upward direction.
Figure 4 shows the images of the object on different scales, which changed over time.
The main search takes place on the largest scale, on the remaining scales of the maps, a search is performed and selection of previously found objects by the identifier. Detailed search only occurs in the corresponding buffer zones, and not across the entire map, which allows you to significantly reduce the time to find the right objects.
The result of the operation of the nD coding algorithm is shown in figure 5 as a graph showing the objects on scales of 1:1000 and 1:1500.
Green on the chart highlighted the object "2" on a scale of 1:1500, red highlighted the object "2" on a scale of 1:1000, the lines that unite them form simplexes.
The work of the algorithm was tested when searching for objects on different scales of the map. To
search for objects, an algorithm was used to search for spatial objects based on specified criteria based
on buffer zones in multi-scale GIS [
The graph in Figure 6 shows the search for objects on different scales. Where the axis X is the scale of the map (1:500, 1:1000 and 1:1500), Y is the number of objects on the map. On the basis of the work, a graph was constructed in which an increase in the number of found objects using the developed algorithm by 10% is observed with respect to the search for objects without using it.
Also a graph was constructed based on the search of objects for a certain period of time.
Figure 7 shows a graph with the search for objects in different periods of time. Where the axis X is the time period in years (2009, 2013 and 2016), Y is the number of objects on the map. The graph shows an increase in the number of found objects using the developed algorithm with an efficiency of 15% relative to the search for objects without using it.
The algorithm of encoding of nD spatial objects in GIS is developed in the article. A data structure based on a simplex tree was also developed and analogs of data structures for multi-scale GIS were considered.
This algorithm can be used in construction, for example, when testing soil changes in recent years. Also, the algorithm can be used to bypass obstacles, for example a quadcopter, which will analyze the presence of an obstacle in its path on the basis of the map.
[1] Eremeev S V, Andrianov D E and Komkov V A 2013 Algorithms for the formation of a graph model of urban territory in the GIS Geoinformatics 4 19-24 (in Russian)