International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004 
  
2. CONSTRUCTION OF TOPOLOGICAL RELATION 
OF CONTOUR LINES 
Most research used contour trees to represent the relation 
among contour lines. In the tree structure, node denotes contour 
line or the region between two neighbouring contour lines. If 
two nodes are connected in the tree, the corresponding contours 
or regions are adjacent consequently (figure 1). We can see that 
this kind of adjacency is continuous in the interested area and 
starting on one contour a sequential traversal can be done over 
the entire map. By this observation, the degree of automation 
can be improved by passing local known information to the rest 
part of the map considering the inherent property between 
neighbouring contour lines. On the other hand, the elevation of 
point on the contour lines is all same and the two sides are 
either higher or lower than the contour's elevation. Then, the 
local region that is monotone at the normal direction of a 
contour line can be determined at some degree, and further this 
property illustrates contour line is directional at 2-d plane, 
exactly, it is "left high and right low" or “left low and right 
high”. In vector data model, the direction is denoted by the 
points’ order constituting contour line. This paper takes “left 
high and right low” direction, as contour lines a and b shown in 
figure 1(a). 
2.1 Triangulation on Contour Lines 
Triangulated Irregular Network (TIN) is a very useful tool in 
spatial analysis of GIS and among them Delaunay Triangulation 
(DT) which is the dual of Voronoi Diagram has wonderful 
characteristics and is most frequently used to get proximal 
relation between geographic objects. In this paper, constrained 
Delaunay Triangulation (CDT) is employed to get the spatial 
relation between neighbouring contour lines. 
(a) 
  
   
  
Sr tl 
  
Figure 2 Iterative construction of CDT (the black 
nodes are inserted by the algorithm) 
The algorithm for constructing CDT has two steps. First, all 
nodes of all contour lines are used as scattered points to 
construct DT. In this step an incremental approach is employed. 
Then, the edges of contour lines are inserted one by one, during 
which intersection between contour line's edge and DT edge 
may arose. There are various strategies to deal with this 
situation and this paper uses the one elaborated by Tsai (Tsai, 
1993) which inserts the intersecting point into the contour lines 
at intersection. There is one situation that should be noted is in 
this research the CDT is on multiple objects, after a latter 
contour line's edge is inserted and the intersection is handled, 
the affected DT edges may intersect former inserted contour 
line’s edges, as in figure 2(a) when inserting C; after C, and C; 
intersection arose again. In order to eliminate all possible 
intersections, the second step is iterated to insert new 
intersection points until there is not any intersection (as in 
figure 2(b)). 
2.2 Topological Relation of Contour Lines 
Contour line is one dimension curve and the topological relation 
between them only can be disjoint. But considering the 
geomorphologic semantics the relation model should be 
extended to incorporate the geometric information and the 
elevation information at the same time. 
First the edges of CDT on contour lines are classified into three 
classes. The first type includes edges whose two end nodes on 
same contour line and the two nodes’ corresponding nodes of 
the contour line are adjacent in order, as edge P,P; in figure 2, 
we name it as object edge; the second includes edges whose two 
end nodes on same contour line and the two nodes’ 
corresponding nodes of the contour line are not adjacent in 
order, as edge P,P; in figure 2, we name it as flat edge; the third 
type includes edges whose two end nodes on different contour 
lines, as edge P,P, in figure 2, we name it as linking edge. 
The elevation of two contour lines c, and c» is denoted as H(c;) 
and H(c5). The elevation interval is denoted as ZH. 
Definition 1 Proximal Contour Line. Two contour lines c; and 
care proximal if there are linking edges whose two nodes are 
on them respectively. Further: 
If H(c;)-H(c;)70 is true, then denote: No(cj)y7c», No(c»)7c1;. 
If H(c»)-H(c,)= AH is true, then denote: N,(c,)Fe2, N_(c>)=c,. 
We call the two contour lines are proximal contour pair if they 
satisfy relation Ng or Ny or Nj, alternatively denote: 
0, c, and c; are 0 - order proximal 
( 
Nd 
— 1 or l, c, and c arel - order proximal 
We denote M(*) as a modal function and further define M 
(No)-0(0-order proximal) which corresponds contour pair with 
equal elevation, M(N,)=M(N,,)=1(1-order proximal) which 
corresponds contour pair with 4H difference. There exist. 
|. If contour lines c;. c» and c; satisfy: N,(c)Fe,, 
Ny(c:)=e; (or Ny(e>)=e;, N.(c2)=e;, then: Nole;)=ess 
No(c3)=C/. 
2. f contour lines c;, c» and c; satisfy: No(c,)=C2 
Ni(c»)7c; (or N.(c2)763). and c, and c, are on the same 
side of c», then: Ni(c;)7c; (or N.a(c,;)7c;) 
As in figure l(a), H(5)-H(a)-H(c)-H(5)-H(d)-H(c)* 4H: 
H(c)=H(e), then the following is true: 
N,(a)=b; N.(b)Fa, N,(b)#c, Ny(b)Fe: Na(c)y»b, N«cFe 
N,(c)=d; N.(d)=c, N.1(e)=b, No(e)#c. 
To two contour lines c; and c», if N(c;)7c» (k70, 1 or —]) is not 
true, then denote Ni(c;, c;)-0. 
Definition 2 Valid Node. Assume one of the nodes, P, of à 
linking edge is on contour c; and the other one node of this 
linking edge is on contour cz, then we call P is a valid node ol 
c, to c». As in figure 2(b), P, P; and P; are valid nodes ol 
contour c, to contour cs. P; and P5 isa valid nodes of contour C/ 
to contour c;. But P; is not a valid node of contour c, t0 Cs. 
1198 
Intern 
Defin 
whose 
| Nu» { 
valid 1 
t0 c5 1: 
And tl 
| And tl 
| 23€ 
| By co 
| mean | 
direct! 
| structu 
relatioi 
triangu 
node s 
record 
below. 
who h 
respect 
proxim 
contou 
| saddle 
| be deri 
| the rec 
| type € 
Contour 
can sec 
Ni(d)=« 
are on 
then v 
No A=e 
(a)