10 
The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B6b. Beijing 2008 
brings problems of maintenance of integrity and consistency of 
maps with different map scales. Thirdly, there inevitably exists 
redundancy among maps with different scales. Massive spatial 
data make redundancy great. And last, the multi-version 
technology can only provide maps with maps with several 
predefined scales. It cannot generate maps with any scale. A 
compromising way is to pre-process the map with large map 
scale by map generalization methods to generate a series of 
maps with different map scales. The results are managed in a 
hierarchical data structure and build vertical indexes among 
maps with different map scales. For the one hand, this method 
gets the high access efficiency as that in multi-version map 
database, for another hand, it also avoids the problems of 
maintenance of data integrity and reduces the redundancy. 
There are two kinds of multi-scale data structures. One is object 
collection hierarchical structure and another one is object detail 
hierarchical structure. The object collection hierarchical 
structure is on the spatial object level, which is corresponding 
to selection and merging operators in map generation. The 
spatial object appears or doesn’t appear in some hierarchy of 
the tree according the weight of the spatial object in the spatial 
object collection. This kind of data structure includes Reactive 
tree, GAP tree etc. spatial objects own inner structure and the 
details of the spatial objects varies according to the map scales. 
Object detail hierarchical structures represent the degree of the 
detail of line objects in different scales. Object detail 
hierarchical structures simplify the line in different scales, and 
stores the details structures into multi-scale structures like Strip 
tree[2], BLG tree, etc. However, both Strip-tree and BLG-tree 
are binary trees. The details with the same scales scatter in the 
different levels of the trees. So the paper design a new 
hierarchical structure, named multi-scale line tree (MSLT) [3], 
to mange multi-scale line generates by line simplification 
algorithms. 
The details with same scale lie in the same tree hierarchy. Only 
the complete coarse skeleton line is stored in the first hierarchy 
of the MSLT. And only increment data are stored in the other 
levels of the tree. So the MSLT also supports progressive 
transmission of vector data across Web. When the user request 
line data with finer scales, the system only need to transmit 
increment data and integrate with the existing data in the client 
to restore the complete line in the finer scale So as to avoiding 
repeating transmission. It’s very useful in network environment 
with limited bandwidth. 
2. GENERALIZATION ALGORITHM OF THE 
MULTI-SCALE LINES 
2.1 Generalization algorithm of the multi-scale lines 
A geographical line is a complicated entity made up of lines 
with different resolution, in which the line with high resolution 
contains the information in the line with low resolution. 
Therefore, a line can be represented as a coarse skeleton and a 
series of details with different resolution. 
C=C X @L\ © • • '®D n 
The generalization of multi-scale is a process to iteratedly 
simplify details with different resolution. There are many 
algorithms in map generalization to simplify lines, among 
which Visvalingam-Whyatt(VW) is an algorithm to simplify 
lines from bottom to top. At first, the algorithm eliminates the 
most detailed, namely the least important, vertices from the 
original line, and then iteratedly eliminate the most 
unimportand points from the current line. The VW algorithm is 
a progressive line simplification in according with the congition 
of human being in the zoom in and zoom out of the map. In this 
paper, we use VW algorithm to generate the multi-scale 
structure of the lines. 
At, first, a threshold list {e \ ei, £¡<£¡+¡1 under different scales 
is predefined and they are applied into the line simplification in 
turn from beginning of the smallest one. At the beginning, £„ is 
used to simplify the line C and get the result line Cn and the 
detailed increment data Dn. Then simplify Cn with threshold e„. 
j. Iteratedly simplify the line with threshold in the list until 
reaching £ h and we can get a skeleton line Cj of C and a series 
of increment data D, according to threshold e,. 
According to the level of each vertex in the line in the threshold 
list, we assign a level id for each vertex. And we define the 
level id of the corasest skeleton is 1, and that in the most 
detailed level is n+1. based on the level id of the vertices, we 
can construct the hierarchical structure of the line. 
1 3 2 2 2 4 •” 3 3 1 
2.2 Topological consistency in line simplification 
VW algorithm does not take topological relationships into 
account. So after simplification, lines may intersect themselves 
or other lines. For example, two lines separating from each 
other may be intersected. 
c 
Figure 1 Topological inconsistency 
Line simplification is a process of vertex elimination, so 
topological inconsistency comes from wrong vertex elimination 
(Fig 1). There are two kinds of vertices in the line, the vertices 
which can be eliminated and the vertices which cannot be 
eliminated. The first kind of vertices can just affect the 
precision of the line, while the second kind of vertices may 
cause inconsistency in topological relationships. 
Uneliminatable vertices can be summarized into following two 
categories: 
1) endpoints of the arc, 
2) inner vertices of the arc.