4) Elevation interpolation: for each newly introduced
“skeleton” point, the elevation is determined through
linear interpolation. The basic idea is the following: first
determine the triangle that encloses the "skeleton" point
(the process can be significantly speeded up by the use of
topological relationship); then detect the closest adjacent
contour line using topological relationship and distance
comparison (note that the triangle enclosing the
"skeleton" point plays an important role in the process);
finally draw a reference line between the "skeleton" point
and the closest node on the neighbour contour line, and
make sure that the line crosses the "problem" contour
line (i.e., the contour line that forms (part) of the flat
region). The interpolation is conducted along this line.
Two aspects must be taken care of in the process: a) the
number of times that the reference line crosses the
*problem" contour line before reaching the adjacent
contour line (see Figure 3A); b) if the reference line
reaches first the adjacent contour line before crossing the
“problem” contour line, then other adjacent contour lines
(not the closest one) might be more suitable for the
interpolation (see Figure 3B). An alternative method is
to first interpolate the elevations of the first and last
points of the flat region using the method described
above, and then determine the elevation for each middle
point through linear interpolation based on the distance
and the elevations of the two “end” points. This method
eliminates local irregularities and is based on an
assumption that the slop between the two "end" points is
constant, therefore should be used with caution.
; 110
Crossing two times 100 C—g2——7V —7————3— 71
\ ZA \ \ 7
wv ~ Ve AN ^ 7 ^
* | = 110 zZ z \ !
A) > m 7 \ IM s z
> ^ ^d N
> Z e Flat, \ 2d
Kus 2 -
-
=
120 J] oe Velo
44 1;
(Wi Flat | Flat 1, 7 S
~ w^
A: The reference line crosses the contour two times B: The adjacent contour of 100 m is more suitable
Figure 3: Examples of special situation
5) Consistency checking: several rules are employed in this
approach to avoid unreasonable result:
€ All the "skeleton" points of a flat region must be
inside the region.
® The elevations of all the "skeleton" points of a flat
region must be consistent in such a way that all of
them are either larger or smaller than the height of the
contour line that forms (part) of the flat region.
€ The absolute value of the height difference between
any of the "skeleton" points of a flat region and the
contour line that forms (part) of the flat region must
not be larger than the original contour interval.
If any violation happens, adjustment and further checking
is required.
6) Network updating: the “skeleton” points are then inserted
into the original model through local updating.
7) Dealing with flat edges: if a non-flat triangle has an edge
that is not part of any contour line, but with both vertexes
having the same elevation, then “triangle swapping” is
applied in order to avoid potential problems in contour-
making. Saddle locations may be detected in this process,
If two non-flat triangles share such a flat edge, and if
“triangle swapping” cannot be conducted because
otherwise a new flat edge will be created (i.e., the two
opposite nodes of the original flat edge also have the
same height), then the quadrangle formed by the two
adjacent triangles represents a saddle area. In this case,
a new point can be introduced into the center of the area.
Its elevation can be determined by taking the average of
the four vertexes of the quadrangle.
5. TESTING OF THE ALGORITHM FOR DTM
IMPROVEMENT
The data source used to test the algorithm was digitized
from a 1:50000 topographic map covering an area of
approximately 3 km by 3 km in southern France near
Bonnieux (Pilouk, 1992). The contour interval is 20 meters.
The test was conducted using ISNAP, and the results are
shown in Figure 4. For lack of space, only about half of the
original studying area is shown in this paper. Through a
visual inspection and comparison of the hillshading displays
and derived contours, it is obvious that after the
improvement, the terrain representation becomes more
natural and the skeleton is more aapparent. The information
lost in the contouring process due to the problem of flat
triangles is recovered. Because of the use of topological
relationship, the algorithm is fast. With a DTM containing
4400 nodes, 13178 edges, 8779 triangles, and 1154 new
points, using a 486-PC (66Mz), the whole process
(including network update) took about one minute to
complete.
6. DISCUSSIONS AND OUTLOOK
Terrain relief generalization should rely on a (good) DTM
and skeleton information must play an important role in the
process. The problem of flat triangles is obvious if a DTM
is to be obtained from digitized contours. It ought to be
solved before a generalization process. Contours in a
smaller scale map should be derived from a generalized
DTM that is adapted to the new (relief) resolution
requirement. Graphic or view generalization process is then
directly applied to the contours in order to obtain a legibile
visualization. The generalization of skeleton lines is the key
aspect in the whole process, and should not be simply
treated as an issue of a 2D linear network (e.g., road
network) generalization. Elevation information, that
represents another dimension of the spatial space, must
plays a role.
The skeleton lines resulting from this method is based on
the concept of medial axis, and can only be regarded as
initial breaklines. Individual skeleton line branches need to
be connected and their planimetric locations need to be
adjusted according to the variations of the density of the
contours in the neighbourhood. Figure 5 illustrates the
problem and a possible solution that makes use of the
topological relationship. This will be implemented and
tested in the near future.
652
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B4. Vienna 1996
