n 
i 
a 
if 
1 
fl 
| 
EEE ETES 
  
RASTER ALGORITHMS FOR SURFACE MODELLING 
L. Tang 
Chair for Photogrammetry and Remote Sensing 
Technical University Munich 
Arcisstr. 21, D-8000 Munich 2, Germany 
Tel: + 49-89-2105 2671; Fax: + 49-89-280 95 73; Telex: 522854 tumue d 
E-mail: tang@photo.verm.tu-muenchen.de 
Commission ITI 
ABSTRACT: 
Two raster algorithms for solving problems in surface 
modelling are presented. A raster-based triangulation 
allows for a simple consideration of constraint edges 
and thus improves computational complexion of the 
constrained triangulation to a great extent. A medial 
axis method derives geomorphological elements, e.g. 
peaks, pits, saddle points, ridge and drainage lines, 
from a given set of contours and actually assists in 
generating a high-quality digital terrain model from 
contours. Examples demonstrate the efficiency of a 
joint use of the two algorithms in terrain modelling. 
Keywords: raster algorithm, surface modelling, Delau- 
nay triangulation, Voronoi diagram, distance trans- 
formation, medial axis, geomorphological element, 
digital terrain model. 
1. INTRODUCTION 
Digital terrain models (DTMs) find more and more 
applications in a variety of branches of science and 
management of today. This leads to the fact that de- 
mand for high-quality DTMs (HQ-DTMs) is increas- 
ing. A HQ-DTM here means that the DTM ought to 
restore the terrain surface as exactly as possible, both 
in geometry and geomorphology. Once the acquired 
primary data are available, a rigorous consideration of 
geomorphological information which represents the 
terrain relief in form of distinctive points (e.g. pits, 
peaks and saddle points), breaklines and ridge or 
drainage lines becomes then the first essential of 
generation of a HQ-DTM. It means that the HQ- 
DTM should keep this information as good as given. 
A possible way to achieve this is to triangulate the 
given sets of points and lines. However, triangulating 
points and lines (so-called constrained triangulation, a 
common issue in surface modelling) is quite difficult 
to be implemented with respect to algorithms and 
computationally even quite time-consuming in case 
where a large number of constraint edges exists 
(Lee/Lin, 1986; Wang/Schubert, 1987; de Floria- 
ni/Puppo, 1988). A question arises: 
(1) Can the constraint edges be considered in a 
simple manner so that the computational com- 
plexion of the constrained triangulation can be 
improved to some extent ? 
Digitized contours are usually used as primary data 
for DTM generation. However, generating a HQ- 
DTM from contours depends to a great extent on the 
availability of the geomorphological information 
(Clarke et al, 1982; Christensen, 1987; Ebner/Tang, 
1989; Aumann et al, 1990; Tang, 1991, 1992). Ac- 
tually, it is quite difficult to acquire this kind of infor- 
mation in a direct manner since c.g. it is usually not 
contained in a topographic map explicitly. Neverthe- 
less, geomorphological elements such as peak and pit 
regions, saddles, ridges and valleys find their express- 
ion in contours and can even possibly be derived from 
contours (e.g. Finsterwalder, 1986; Tang, 1991). An- 
other question is here of interest: 
(2) How can geomorphological elements or at least 
their approximations be derived from contours 
automatically and then be used for HO-DTM 
generation ? 
Answers to this question as well as the first one will be 
given in following sections. 
2. ARASTER-BASED TRIANGULATION 
To answer the question (1) in the last section a raster- 
based triangulation was developped and will be de- 
scribed in the following. 
> 1. Basic id 
In surface modelling, object surface can be described 
by a triangulated irregular network (TIN), which con- 
sists of planar, nonoverlapping, and irregularly shaped 
triangular facets on the given data sets. In this way the 
3-dimensional problem of surface description is then 
reduced to a 2-dimensional one, i.e. establishing the 
adjacency relationships among the given data points