=Paper=
{{Paper
|id=Vol-1710/paper13
|storemode=property
|title=Checking the Topological Consistency of Maps of Different Scales
|pdfUrl=https://ceur-ws.org/Vol-1710/paper13.pdf
|volume=Vol-1710
|authors=Kirill Kuptsov,Sergey Eremeev,Dmitry Andrianov
|dblpUrl=https://dblp.org/rec/conf/aist/KuptsovEA16
}}
==Checking the Topological Consistency of Maps of Different Scales==
https://ceur-ws.org/Vol-1710/paper13.pdf
Checking the Topological Consistency of Maps of
Dierent Scales
1 1 1
Dmitry Andrianov , Sergey Eremeev , and Kirill Kuptsov
Murom Institute (branch) of Vladimir State University, Murom, Russia
AndrianovDE@inbox.ru, sv-eremeev@yandex.ru, kirill-kuptsov@rambler.ru
Abstract. Currently methods for generalization of spatial information
to obtain maps of dierent scales are actively being developed. These
methods generally process geometric information such as linear and poly-
gon objects. However, it is very important to take into consideration
the topology between objects upon transition to maps of dierent scales
since correct layout of spatial information can be lost. In this article
we determine and solve the task of converting topological relationships
between spatial objects for preserving topological correctness between
them in multiscale geographic information systems. Possible models for
transitioning topological relationships to other scales are mathematically
described. This could be deleting, saving or creating new relationships.
An algorithm which checks for topological correctness of dierent scale
maps is oered. Use of this algorithm increases the accuracy of spatial
objects layout in the case of automatic generalization of maps. Examples
of the algorithm for city maps are shown.
Keywords: generalization of maps, topological consistency of spatial
objects, topological relationships, topology.
1 Introduction
Topological relationships are widely used in geographic information systems
(GIS) [1,2,3]. One of the fundamental tasks in the area of GIS is analysis of
changes on maps [4,5]. Topological methods are very well suited for solving these
tasks. They allow for checking the correctness of an object's location on a map
and nding topological errors [6,7]. However, many methods are limited in that
they analyze changes only at one level of map scale. The analysis of topological
changes at dierent scales of a map requires new approaches.
The existing operations in this area are directed at saving topological integrity
in case of map generalization. Data models and methods are actively developed so
that, in case of automatic generalization of a map, the correctness of an object's
location at other scales is automatically checked. Methods such as extending
the functionality of nine-intersection models for nding changes [8], methods of
triangulation [9], and hierarchical structures are used for this purpose [10,11].
Generally, these methods process the linear objects [12,13] and di cult objects
are represented as a set of linear ones [14]. Thus, simpli cation of the linear
objects occures in the case of generalization so that there are no collisions.
Types of spatial objects can change upon transition to other scales, objects can
disappear, and also the topology between objects can change. This question is
of some importance for researchers. Thus, the analysis of changes of topological
relationships between spatial objects at dierent map scales requires detailed
study.
One of the tasks of the multiscale topological analysis for checking topological
correctness of objects at dierent scales is considered and realized.
Violation of topological correctness can happen for several reasons. It can be
seen in the case of automatic map generalization where there is a simpli cation
of objects that involves errors in their layout. Also it occurs on the manual
information input in case of superimposing a large number of layers where it is
rather di cult to provide the interaction of all linked objects.
For example, A will be the polygon, B will be the linear object, and A contains
B (Figure 1).
Fig. 1. Initial location of objects
The following variants are possible in case of generalization:
1. Preserving topology between A and B , and also preserving object types
despite that each object has some simpli cation (Figure 2a).
2. Preserving topology between A and B , but the type of one of the objects
changes; for example, the linear object B becomes a point (Figure 2b).
3. Disappearance of topology because of the absence of object B on the map
(Figure 2c).
4. Incorrect display of spatial objects in relationship to the initial map because
the object B is not included in the object A (Figure 2d).
5. Conversion of topology. The type of topological relationship between objects
changes, for example, B adjoins to A (Figure 2e).
If we know how objects interact at one scale, it is important to use this infor-
mation in other scales that inherit these topological relationships.
In this article we propose to research the possible behavior of map objects upon
transition to other scales. The inheritance of topology and possible changes of
types of spatial objects are considered.
a) b) c) d) e)
Fig. 2. Possible layouts of objects upon transition to another scale
For this purpose, it is necessary to develop topological rules of transitions
which will be correct for the selected type of topological relationships between
spatial objects. It will allow for increasing the accuracy of topological consistency
between objects at dierent map scales.
2 Classi cation of possible transitions in multiscale GIS
Let R(A, B) be the topological relationship between objects A and B at some
scale. Besides the value of the topological relationship we will also consider the
type of geometry of objects; that is, their dimension. This relationship will look
thus:
R(A, B) =< t, gA , gB >, (1)
where t is the type of topological relationship;
gA , gB are dimensionalities of the geometry of objects A and B , respectively,
which take the following values: 0 is a point, 1 is a line, 2 is a polygon.
Let the spatial scene after generalization be known. Then the relationship
between objects will be described as follows:
R(A0 , B 0 ) =< t0 , gA0 , gB 0 >, (2)
0 0
where A will be transformed to A , B will be transformed to B .
De nition 1. Two spatial scenes consisting of two spatial objects are topologi-
cally correct if the condition is satis ed:
(t = t0 ) ∧ (gA ≥ gA0 ) ∧ (gB ≥ gB 0 ) = 1. (3)
That is, the same type of topological relationship remains and the dimension-
ality of each object is no more than at the previous scale.
2.1 Preserving topology and object types
Let us consider the situation represented in Figure 3 where the topology and
type of objects remain the same.
Fig. 3. The linear object adjoins to a polygon at two dierent scales
Using the expression 3 we have:
t=t0 = adjunction;
gA = 1, gA0 = 1, i.e. gA ≥ gA0 ;
gB = 2, gB0 = 2, i.e. gB ≥ gB0 .
Thus, all conditions are satis ed and the two maps are topologically correct.
2.2 Preserving topology and change of object types
There are some situations when the topology remains but the spatial scene does
not always remain topologically correct to the previous scale. Let us consider
Figure 4:
a) b)
Fig. 4. (a) Incorrect transition to other scale; (b) correct transition to other scale
In the rst case (Figure 4a) the point object B will be transformed in the
polygon object that hinders the execution of the conditions in the expression
(3), i.e.
t = t0 = nesting;
gA = 2, gA0 = 2, i.e. gA ≥ gA0 ;
gB = 0, gB0 = 2, i.e. gB < gB0 .
Therefore, this case was not successful.
0
In Figure 4b objects A and A do not change the dimensionality, the "nesting"
0
relationship type also remains, but the dimensionality type of objects B and B
changes. But we see that gB = 2, gB 0 = 0 and all conditions satisfy expression
(3). This means that the transition to another scale was successful.
2.3 Disappearance of topology
Some objects, upon transition to other scales, can disappear. In this case two
situations are possible:
deleting all relationships with this object;
redistribution of relationships.
In the rst case (Figure 5) deleting object B doesn't have any consequences on
0
a new map. In this case the object A can take any dimensionality.
Fig. 5. Possible ways of generalization with deleting object B
In case of redistribution of relationships it is necessary to consider the following:
De nition 2. If the object B has relationship t with objects A and C but A and
C are not interconnected among themselves, then the new relationship between
objects A0 and C 0 with relationship type t=t0 is formed after deleting B on a map
in the case of generalization.
0
Correct transition to another scale is shown in the Figure 6a with the type t=t
= "adjunction", and incorrect transition is shown in Figure 6b with types t =
0
"adjunction" and t = "nesting".
a) b)
Fig. 6. (a) Correct formation of new relationship between A0 and C 0 ; (b) Incorrect
formation of new relationship between A0 and C 0
2.4 Conversion of topology
An exception to the rules is the situation concerning expression (3): when
another type of topological relationship between two objects upon transition to
another scale is formed and this transition is considered successful.
For example, the relationship type t between A and B in Figure 7 is "intersec-
0
tion", and after generalization t is "adjunction".
Fig. 7. Conversion of topology
Thus, at rst it is possible to show the relationship to the house, and only then
to supply communication. In order to account for such situations it is necessary
to store similar exceptions in a database for all couples of layers.
2.5 Incorrect display of topology
These are such cases when the conditions from the expression (3) are not
satis ed and such situations are not present in a database of exceptions.
For example, the house (object B ) is near the lake (object A). This is shown
0 0
in Figure 8. In the case of generalization, B appears inside A , and it is inad-
missible.
Fig. 8. Incorrect conversion of topology
Thus, the geographic information system considers such variants and controls
all possible listed cases, forbidding incorrect display of spatial data.
3 Correctness check algorithm after transition to another
scale
The algorithm will contain the following main stages:
1. Extraction of data about types and the spatial relationships of map objects
before generalization.
2. Data collection about types and the spatial relationships of objects after
generalization.
3. Search for mismatched object types.
4. Search for changes of the spatial relationships between map objects.
5. Search for new topological relationships.
6. Detection of the absent relationships (if objects were not deleted).
7. Object search at which the parent object was removed.
8. Compilation of a report about generalization errors.
4 Results
Objects of city infrastructure are shown in Figure 9. The map allows us to show
the correctness check and demonstrate the program's capabilities. We will review
some examples of checking for topological consistency of multi-scale maps.
4.1 Mismatch of an object type
Figure 9a is the initial map and Figure 9b is a map on another scale. The
reaction of the program on an incorrect transition of an object type is shown in
Figure 9b. Objects A and B (Figure 9a) incorrectly changed geometrical type
0 0
(objects A and B in Figure 9b). Object A changed type from linear to polygon,
and object B changed type from polygon to linear. Objects C and D disappeared
from the map. Object E changed form but is displayed correctly.
a) b)
Fig. 9. Map and mismatch of an object type. Initial map (a) where A, E have linear
types; B , C , D have polygon types. Result map (b): the type of object A0 is changed
(not correct); the type of object B 0 is changed correctly, C and D disappeared, and E 0
is transformed (correct).
As a result, the program informs the user of an error.
4.2 Change of the spatial relationship
The following example is reviewed by a case of change in topological relation-
ships that is incorrect, except for special cases which are provided by the list
of exceptions. From Figure 10 it is visible that object B crossed the road. This
violates the topological relationship between objects. The topological relation-
ship between object G and the linear object disappeared but the relationship
between F and the linear object was saved.
a) b)
Fig. 10. Testing of topological consistency. Initial map (a) where B does not cross the
road; F and G are connected to the linear object. Result map (b): B 0 crosses the road
(incorrect); G0 is not connected to the linear object and the topological relationship
with F 0 and the linear object also exists (correct).
The user will receive the warnings about errors related to transformations and
formation of new topological relationships based on the developed rules.
Figure 11a is the initial map and Figure 11b is a map on another scale. These
gures display only part of a map. This map contains about 30 layers and more
than 5000 objects. After operation of algorithm all topological errors are dis-
played in the separate table which contains object IDs and type of topological
mismatch. 117 transitions to the new topological relationship are revealed upon
transition from one scale to another. Disappearance (or loss) relationships be-
tween objects occurred in 209 cases. There are 483 cases of saving the topological
relationship and object types. In 262 cases the topological relationship remained,
but the type of one of objects changed. In 81 cases incorrect display of topological
relationship is made.
a) b)
Fig. 11. Operation of system on a di cult map. Initial map (a). Result map (b).
At the moment direct analogs the oered system don't exist. Therefore com-
paring of operation of our algorithm was carried with operation of the expert.
Results of research are provided in Figure 12. It is visible that our system on each
of the provided types of the topological relations nds bigger percent of errors,
than the expert. Thus, advantage of our system in comparison with operation
of the expert is obvious.
Fig. 12. Research of results
5 Conclusion
As a result of the research of possible behavior of map objects upon transition
to other scales, rules of a consistency which allow for analyzing map objects and
their spatial relationships, while taking into account inheritance of topology and
possible changes of types of spatial objects, were developed. The consequence of
these rules extend both to everyday occurences, and to exceptional situations.
The developed algorithms allow for increasing the accuracy of topological co-
herence between objects at dierent scales. This eventually increases the quality
of map generalization.
References
1. Egenhofer, Max. J., Mark, D. M. Modeling conceptual neighborhoods of topological
line-region relations // International Journal of Geographical Information Systems.
1995. Vol. 9, N. 5. P. 555565.
2. Eremeev, S. V., Andrianov, D. E., Komkov, V. A. Comparison of Urban Areas
Based on Database of Topological Relationships in Geoinformational Systems //
Pattern Recognition and Image Analysis. 2015. Vol. 25, N. 2. P. 314320.
3. Andrianov, D. E., Eremeev, S. V., Kuptsov, K. V. The review of spatial objects
recognition models and algorithms // Procedia Engineering. 2015. Vol. 129. P. 374
379.
4. Gröger, G., Plümer, L. How to Get 3-D for the Price of 2-D-Topology and Con-
sistency of 3-D Urban GIS // Geoinformatica. 2005. Vol. 9, N. 2. P. 139158.
5. Corcoran, P., Mooney, P., Winstanley, A. Planar and nonplanar topologically
consistent vector map simpli cation // International Journal of Geographical In-
formation Science. 2011. Vol. 25, N. 10. P. 16591680.
6. Süleyman, SM. Topological error correction of GIS vector data // International
Journal of the Physical Sciences. 2010. Vol. 5. P. 476483.
7. Deng, M., Cheng, T., Chen, X., Li, Z. Multi-level topological relations between
spatial regions based upon topological invariants // GeoInformatica. 2007. Vol. 11,
N. 2. P. 239267.
8. Shihong, D. Analyzing topological changes for structural shape simpli cation //
Journal of Visual Languages and Computing. 2014. Vol. 25, N. 4. P. 316332.
9. van der Poorten, P. M., Zhou, S, Jones, C. B. Topologically-Consistent Map Gen-
eralisation Procedures and Multi-Scale Spatial Databases // Geographic Informa-
tion Science. 2002. Vol. 2478. P. 209227.
10. Belussi, A., Catania, B., Podestà, P. Towards topological consistency and similar-
ity of multi-resolution geographical maps / in Proceedings of the 13th Interna-
tional Symposium on Advances in GIS, P. 220229. 2005.
11. Breunig, M., Thomsen, A., Broscheit, B., Butwilowski, E., Sander, U. Represen-
tation and analysis of topology in multi-representation databases / in PIA07.
International Archives of Photogrammetry, Remote Sensing and Spatial Informa-
tion Sciences, P. 167229. 2007.
12. Clementini, E., Di Felice, P. Topological invariants for lines // IEEE Transactions
on Knowledge and Data Engineering. 1998. Vol. 10, N. 1. P. 3854.
13. Saalfeld, A. Topologically Consistent Line Simpli cation with the Douglas-Peucker
Algorithm // Cartography and Geographic Information Science. 1999. Vol. 26, N. 1.
P. 718.
14. da Silva, A. C. G., Wu, S. T A robust strategy for handling linear features in
topologically consistent polyline simpli cation / in VIII Brazilian Symposium on
GeoInformatics, Advances in Geoinformatics, P. 117. Berlin: Springer-Verlag,
2007.