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 dicult objects are represented as a set of linear ones [14]. Thus, simplication 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 simplication 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 dicult 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 simplication (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 Classication 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 . Denition 1. Two spatial scenes consisting of two spatial objects are topologi- cally correct if the condition is satised: (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 satised 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: Denition 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 satised 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 dicult 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 simplication // 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 simplication // 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 Simplication 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 simplication / in VIII Brazilian Symposium on GeoInformatics, Advances in Geoinformatics, P. 117.  Berlin: Springer-Verlag, 2007.