04 
FORMALIZATION AND APPLICATIONS OF TOPOLOGICAL RELATION OF 
CONTOUR LINES 
Tao Wang“ 
" School of Resource and Environment Sciences, Wuhan University, Luoyu Road 129, Wuhan, 430072, China 
mapwang@tom.com 
KEY WORDS: GIS, Automation, Triangulation, Algorithms, Contour, Topological Relation, DEM/DTM 
ABSTRACT: 
This paper proposes a novel formalization framework of topological relation of contour lines and elaborates the applications based 
on it. Our idea is concentrated on the continuity of the spatial proximity and the direction among contour lines. Constraint Delaunay 
TIN on the contour lines is employed to acquire proximal relation of neighbouring contour lines. We define proximal relation 
between two contour lines c, and c» if there are TIN edges whose two end nodes are on them respectively. The proximal relations are 
distinguished into 0-order (No(c,. €2)) if the involved contour lines have same elevation, and 1-order if they have a difference of one 
elevation interval. To 1-order proximal relation, we consider the elevation increasing direction and further define Ni(c,, c?) if c; is 
higher than c», and N.,(c,, c») if c» is higher than c,. When two contour lines have 1-order proximal relation, their vector directions 
are updated to follow the rule that left area of each contour line is higher than itself and the right is lower. We describe an efficient 
method to implement this operation. The benefits of the proposed idea are demonstrated experimentally on the time-consuming and 
error-prone tasks of assigning elevation value to the contour lines and automatic connection of broken parts of contour lines resulted 
from vectorizing the raster map. 
I. INTRODUCTION 
Contour is one of the most important tools to represent 
geomorphological information in map and GIS. However, it is 
long known that acquiring vector contour data by digitizer is a 
labour-intensive and error-prone task. The procedure of semi- 
or full-automatic vectorizing scanning map improves this work 
greatly. But due to the quality of scanning and the actual 
representation of topographic maps, lots of contour are broken 
and cannot ensure the completeness by the existing automatic 
approach. At the same time only the position of contour is got, 
and the other equally important information-elevation of 
contour lines-has to be input manually, which is still tedious 
and possible to produce error. 
Previous research has been concentrated on constructing some 
tree structures to get spatial relation of the disjoint contour line 
and some of them are used to label elevation value to vectorized 
contour lines. Sircar (Sircar, 1991) took the contour map as a 
graph and converted it into an oriented tree in which the node 
denotes the region enclosed by adjacent contour lines, the root 
is the region enclosed by lowest contour lines and between two 
regions sharing same contour the higher one is son-node of the 
lower one. The depth of node is proportional to its elevation. 
(Guo, 1995; Hao, 2001; Roubal, 1985; Wang, 2002; Wu, 1995; 
Zhai, 1996) took contour lines as nodes in the contour tree and 
set the lowest contour lines as the root. There is an edge 
between two nodes if their corresponding contour lines are 
adjacent. There are other tree structures mentioned in reference 
which incorporate the contour lines and the region between 
them. Figure 1(b) and l(c) shows two kinds of contour tree of 
contour map in l(a) The algorithms for constructing the 
contour tree can be grouped into two kinds: the ones based on 
faster that employs image dilatation or erosion and the ones 
based on vector which uses polygon-in-polygon test algorithm 
lo determine the relation between contour lines. However, both 
need much manual pre-processing that can be reduced further 
and cannot ensure the consistency when there are broken 
contour lines which is often appeared in topographic maps. 
1197 
This paper first proposes a novel formalization framework to 
describe the topological relation of contour lines, which is 
constructed based on TIN of contour lines. Finally the benefit is 
demonstrated by automatically labelling elevation value to 
contour lines in which the broken contour lines are processed 
without manual work and further the broken parts are 
automatically connected. 
% (a) 
      
  
Bo co CD UN 
S. = 1130 N 
  
    
x X 
EMO __— 
      
b:110 
  
Figure 1 Contour map and corresponding contour trees.