The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B6b. Beijing 2008 
The endpoints of the arc are key vertices in topological 
relationship among spatial entities (Figl a, b). We can know 
such vertices before line simplification. When we build 
topological relationships on the spatial data without topological 
relationships, the endpoints of arcs are this kind of 
uneliminatable vertices. 
imU- Level_i+1 Lwel_i+2 Lewl_i+1 
Figure 2 . Multi-scale line structure 
The inner vertices may cause the simplified lines to intersect 
themselves or other spatial entities (Fig 1 c). Such vertices can 
only be dynamically judged in the process of line simplification. 
The regulation is that when there is a vertex p falling into the 
triangle made up of vertex /?, and his previous vertex p,_/and 
next vertex p i+J , the elimination of is doomed to intersect 
with himself or other lines, so vertex p, is a uneliminatable 
vertex. 
By the constraints of two kinds of uneliminatable vertices, we 
can preserve the consistency of the topological relationships 
after line simplification. 
3. MULTI-SCALE LINE MODEL 
3.1 Multi-scale line model 
struct ScaleNode 
{ 
float /Scale 
long ILevelCount;; 
DataBlock *pBlockList; 
}; 
f Scale is the scale of the current level node. When users request 
data, the model determines which level should be visited 
according to fScale. 
ILevelCount describes how many levels the model has. 
pBlockList points a data node list. 
In the multi-scale line mode, only the first level preserves the 
complete coarse line, while rest levels just preserve the 
increment data to the neighbouring previous level, which reduce 
the data redundant data and is easy to be maintained. 
Ill) DataBlock Node. Neighbouring vertices in the line with the 
same scale make up of a DataBlock Node. As Fig 2 shows, the 
first 4 vertices and the last 3 vertices make up of two data node 
respectively. 
The DataBlock Node is defined in C++ as following: 
struct DataBlock 
{ 
FPOINT *pPoints; 
long IPointCount; 
DataBlock *pSibling; 
DataBlock *pChild; 
long IChildCount; 
}; 
After iterated line simplification, we classify the vertices in the 
line into different scale levels. Now we can build a multi-scale 
line structure to preserve the simplification result, so that when 
users access the multi-scale line, we just need to traverse the 
multi-scale line structure rather than simplify the line on the fly. 
The multi-scale line model is a tree structure, made up of three 
kinds of nodes, the root node, level nodes and data block nodes. 
Fig2 shows the hierarchical structure. 
I) Root Node. Root node is the entrance of the multi-scale line 
mode. It encapsulates the metadata of the line, such as id of the 
line, the Minimum Bounding Box, the levels of the hierarchy, 
and the access methods of the model. When users request data 
from the model, the Root Node locate to the related scale level 
according the scale information from users and call related 
methods to generate the line or increment data according to the 
scale. 
II) Level Node. Level Nodes consist of main frame of the multi 
scale line model. All vertices with the same scale are 
aggregated into the same level node. Compared with Strip tree 
and BLG tree, the level in the model of the paper appears more 
clear and easily to be extended. 
The level node is defined as following in C++: 
pPoints recorods the coordinates of the vertices in the line. 
IPointCount describes how many vertices in the Data Block 
Node. 
pSibling points next neighbouring Data Block Node in the same 
level. 
pChild points the DataBlock Node of next level just after 
current DataBlock Node. And IChildCount describe how 
DataBlockNodes of next level from current DataBlockNode to 
his sibling DataBlock Node, which are used to build vertical 
index among levels of the multi-scale line model. 
The resolution of the vertices between two neighbouring 
DataBlockNodes are higher than those in these two 
DataBlockNodes, therefore they are simplified into a line 
segment under current scale. 
3.2 Vertical index 
We have built the tree based hierarchical structure of the multi 
scale line. And we need to know how the vertices between 
neighbouring levels are interrelated with each other, so as to 
rebuild the original line structure level by level. The vertical