The article describes the algorithm for creating three-dimensional Barcodes to represent nD features. The algorithm is based on computer topology methods using the 3D sweep hull algorithm for computing convex hulls and Delaunay triangulation. The result of the algorithm are 3D Barcodes of features. 3D Barcode graphs were built that reflect their time differences.. The algorithm for constructing 3D Barcodes will allow analyzing spatial nD objects at different time intervals.
Currently, geographic information systems mainly work with vector 2D maps. But now, the information on 2D maps is not enough for a more detailed analysis of the terrain, so GIS is increasingly beginning to include the ability to process 3D maps.
The relevance of the work lies in the fact that the existing algorithms for processing and storing 3D
map data work exclusively with coordinates, which significantly increases the processing time of such
objects. It is proposed to apply computer topology methods using the 3D sweep hull algorithm to
develop an algorithm for constructing 3D Barcodes that will allow storing and quickly processing data
on spatial objects in GIS [
There are various algorithms for handling nD features. In [
The authors of [
This approach led to a new theory and method for geodata, as well as technologies that implement multidimensional partitioning. Integration of multidimensional geodata concepts allows to use of common geometry and embedded topological, temporal and scale structures through full 3D + time + scale splitting.
But these algorithms are based on the use of coordinates of objects, which significantly slows down their processing.
In this work, three-dimensional Barcodes will be built on the basis of data from spatial objects from a 3D map. The resulting Barcodes will be compared with 2D Barcodes for vector maps. The advantages of the developed algorithm can be considered as the speed of work, the ability to work with three-dimensional maps, as well as to store object changes over time.
The algorithm of building 3D Barcodes is based on the 3D sweep hull algorithm [
The algorithm generates Delaunay triangulation together with a three-dimensional convex hull for a set of points.
The construction of the Barcode itself takes place by analogy with 2D Barcodes as described in
[
A distinctive feature is the addition of the third component in the Barcode which is a time t . Taking into account the added time, Barcodes for different periods of time are combined on each radius into a single component.
Accordingly, 3D Barcodes, built on the basis of data on nD objects, will look like this:
B = {(xi , li , t i )} , where ti is a certain period of time in which the object was changed [
Also 3D Barcode can have another third component line, for example, scale s .
Then the Barcode will look like: B = {(xi , li , si )} , where si is the scale on which the feature is displayed.
3D Barcode can be built not only for one object, but also for their group. In this case, the coordinates of the entire group of objects will be perceived as a single object.
Consider the construction of 3D Barcode on an example. Figure 1 shows a 3D feature. Figure 2 shows the 3D Barcode for the object shown in Figure 1.
The graph of Figure 2 shows the Barcode length on the axis x, the Barcode radius on the axis y, and the year of change on the axis z.
To carry out the experiment of building 3D Barcode, a tablet of the 1990s was taken, reflected in Figure 3 (a) with the image of a map of the city's terrain. Some of the objects were built in 3D, and Barcode was built for them. Then the plot from this area was taken from Yandex maps for 2018. This area is reflected in Figure 3 (b). For these objects was also built 3D Barcode shown in Figure 3 (c). c) Figure 3. A group of objects and their 3D Barcodes: a-b) Objects that change over time; c) 3D
Barcodes of objects in different time intervals.
For comparison, 2D Barcodes were constructed for the objects from Figure 3 (a, b). These Barcodes are shown in Figure 4 (a, b).
When comparing 2D and 3D Barcode graphs, we can conclude that 3D Barcodes are more informative, store more information, and, unlike 2D Barcodes, allow you to quickly access the desired nD object on the map. One of the advantages of the algorithm's performance is the use of Delaunay triangulation for constructing holes of objects, which significantly reduces the processing time of objects.
An algorithm for constructing 3D Barcode for nD features developed in the article. It can be applicable to all vector maps, including 3D maps.
Unlike 2D Barcode, this algorithm takes into account an additional characteristic which is a time. This allows to track changes in nD features over the years.
In the future, the algorithm will also be able to use the scale as an additional characteristic, which will significantly reduce labor costs when working with vector maps.
The developed algorithm is also useful in real estate. It will allow to search for the best terrain for building buildings, estimate the time of building objects, as well as analyze areas for missing buildings.
The reported study was funded by RFBR and Vladimir region according to the research project № 1747-330387.