while 
1ged. 
set of 
ginal 
both 
OTM 
100th 
ed to 
1 (or 
. the 
idual 
tion, 
and 
from 
gged 
the 
and 
scale 
DTM by applying DTM filtering to the first intermediate 
DTM and again using the generalized skeleton as a 
constraint; e) verifying and finally arriving at a target 
(generalized) DTM. Figure 1 illustrates the whole process. 
4. OBTAINING A DTM FROM DIGITIZED 
CONTOURS 
Although different methods are available for obtaining 
DTM data, contour maps, however, still represent a very 
important source of data since much of the earth's surface 
has been mapped in this way (Mark, 1986). Triangulating 
digitized contours from existing maps hence is one of the 
most economic ways to obtain a DTM. The Delaunay 
triangulation is a common approach. 
Delaunay triangulation, however, implies the danger of 
creating flat triangles at those locations where a contour line 
forms a loop or sharp turns, or two adjacent contour lines 
have the same elevation. Flat triangles create artificial 
terraces that lead to a poor DTM and will cause problems in 
generalization decision-making and contouring. 
However, these flat triangles, on the other hand, provide 
important information about the structural characteristics of 
terrain surfaces: flat triangles normally occur at 
morphological locations such as ridge, drainage, peak, pit 
and passage. In other words, flat triangles tend to be located 
at (or close to) skeleton locations. Our approach to improve 
the DTM and at the meantime solve the problem of flat 
triangles is based on this characteristic, thus can be refered 
to as a "self-diagnostic" approach. The following outline the 
process: 
€ checking flat triangles and forming flat regions (to be 
discussed later); 
© if a flat region contains only one triangle (called "single 
flat triangle"), then applying "triangle swapping"; 
€ approximating the skeleton for each flat region; 
® determining the elevation for each newly introduced 
"skeleton" point; 
® checking the elevation consistency for the whole flat 
region; 
€ inserting the new "skeleton" points and locally updating 
the network; 
* applying "triangle swapping" for any "single flat 
triangle" left; 
® dealing with flat edges. 
1) Flat region: a flat region is defined as a subset of 
adjacent flat triangles with a) any two adjacent triangles 
sharing a common edge that is not part of any contour 
line, and b) only one triangle in the set can be adjacent to 
a triangle (of the same set) of which the three adjacent 
triangles are all flat triangles. Such a flat triangle is 
called node-triangle. It is an important concept in this 
approach as it represents a junction where several 
Skeleton lines meet. Conditions a) and b) together ensure 
that each flat region corresponds to only one skeleton 
651 
branch. A flat triangle with two edges being part of a 
contour line is called end-triangle, and a flat triangle 
with only one edge being part of a contour line is called 
chain-triangle. A flat region can be detected through a 
recursive process using topological relationship. 
2) "Triangle swapping": for a flat region containing only 
one triangle T,, in most of the cases we can find an 
adjacent triangle T;, such that the common edge is not 
part of any contour line, and the quadrangle formed by 
the two adjacent triangles is a convex one. If such a T, 
exists, then the flat triangle can be eliminated by simply 
swapping the two diagonals of the quadrangle. The new 
common edge of the two new triangles is likely part of a 
skeleton line, therefore should be marked. Exceptions 
normally occur along the fringe areas of a network. 
3) Skeleton approximation: for each flat region, the skeleton 
can be determined or approximated using the component 
triangles of the flat region. For this purpose, first the 
triangles must be sorted and put in sequence. Then 
several methods can be used to determine the planimetry 
of the vertexes or "skeleton" points that make up the 
skeleton: a) using centroid for each node-triangle and 
end-triangle, and for each chain-triangle using the middle 
point of a line connecting the two middle points of the 
two edges that are not part of any contour line, b) using 
the centroid of each triangle and applying smoothing 
operation, c) using the center of the circumcircle of each 
triangle. The example in Figure 2 shows that while 
methods a) and b) provide reasonable results , the result 
offered by method c) largely depends on the distribution 
of the digitized contour points, and may violate one of 
the consistency rules (to be discussed later). Method a) 
…, 1s recommended 
for its simplicity. 
Figure 2: The 
planimetric 
locations of 
the "skeleton" 
points by the 
three different 
methods. (A) 
Top: Using 
the middle of 
triangle edges. 
(B) Middle: 
Using the 
centroid of 
each triangle. 
(C) Bottom: 
Using the 
circumcircle 
of each 
triangle. 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B4. Vienna 1996