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 polygon 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.
Topological relationships are widely used in geographic information systems
(GIS) [
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 [
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). 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 information 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)
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. (1) (2) (3) 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 >; 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; B0) =< t0; gA0 ; gB0 >; where A will be transformed to A0, B will be transformed to B0. Denition 1. Two spatial scenes consisting of two spatial objects are topologically correct if the condition is satised: (t = t0) ^ (gA gA0 ) ^ (gB gB0 ) = 1:
That is, the same type of topological relationship remains and the dimensionality 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. t=t0 = adjunction; gA = 1, gA0 = 1, i.e. gA gB = 2, gB0 = 2, i.e. gB gA0 ; 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: 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.
In Figure 4b objects A and A0 do not change the dimensionality, the "nesting" relationship type also remains, but the dimensionality type of objects B and B0 changes. But we see that gB = 2, gB0 = 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 a new map. In this case the object A0 can take any dimensionality. 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 C0 with relationship type t=t0 is formed after deleting B on a map in the case of generalization.
Correct transition to another scale is shown in the Figure 6a with the type t=t0 = "adjunction", and incorrect transition is shown in Figure 6b with types t = "adjunction" and t0 = "nesting".
a) b)
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 "intersection", and after generalization t0 is "adjunction". 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.
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 in Figure 8. In the case of generalization, B0 appears inside A0, and it is inadmissible.
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
As a result, the program informs the user of an error.
Change of the spatial relationship
The following example is reviewed by a case of change in topological relationships 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 relationship between object G and the linear object disappeared but the relationship between F and the linear object was saved.
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 displayed 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 between 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.
At the moment direct analogs the oered system don’t exist. Therefore comparing 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. 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 coherence between objects at dierent scales. This eventually increases the quality of map generalization.