., China, 
m.cn 
'echanical 
ir meshes 
| inputs of 
direction 
lary-fitted 
f classical 
rithm, An 
e the flow 
vell as the 
ing, also. 
del of the 
should be 
>; another 
; at last, a 
is. Results 
algorithm 
river way, 
(TIN) is 
nd surface, 
; based on 
1cture. 
ing these 
after this 
roduced in 
each sub- 
ns of the 
n the last 
e volume- 
algebraic 
nd partial 
these three 
ages and 
d Remote 
). 
  
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004 
  
disadvantages each, among which, “algebraic method has the 
excellence of fast computation, but is hard to be self-adapted 
à 
when complicated shapes come into being”. 
Principle of the algorithm presented in this paper could 
generally be described like this: 
1. Centreline of the river way has been used to represent the 
flow direction at anywhere of the river. 
2. From beginning to end, partitioning out section-lines 
vertical to the flow direction at intervals sequentially, 
which is also the main characteristic of classical algebraic 
method. 
3. Sampling out certain amount of discrete points in each 
section-line with right-hand rule, then, calculating their 
elevation value using a certain interpolation method from 
input GRID data - DEM of the river. 
As has been expected, this newly designed algorithm has fitted 
together the simplicity and efficiency of the a/gebraic method 
and capability of spatial representation, which is main 
characteristics of GIS. 
3. ALGORITHM DESCRIPTION 
3.1 Data pre-processing and input 
The DEM data inputted in this algorithm is of GRID type, this 
based on the facts also mentioned in the references (Ren Liliang, 
2000). For the convenience of implementations carried out in 
programming, ASCII text form of the DEM data is required in 
this algorithm. Building up DEM of the surface and Exporting 
ASCII text from GRID (GIS By ESRI ™ | 2001; Fan Hong, 
2002) will not be elaborated here. 
Sometimes, it would be convenient to get those centrelines 
directly from digitized elevation map of the river, as described 
below, the centreline is very essential to represent the variation 
of the river flow direction in a measurable way, thus enables to 
generate meshes in high quality (adaptive to the river way). 
They are chosen as input of the algorithm, also, optionally 
however, for it is possible for us to extract out this kind of 
centrelines from the input GRID data automatically. 
3.2 Numerical expression of the flow direction 
As indicated by hydrodynamic experiences and researches, 
centreline is a good measure that has been used to represent the 
variation of river flow. Centrelines and all other kinds of lines 
are stored as vector line in GIS, which is composed of a series 
of single points with known coordinate value pairs, the spatial 
relationship between adjacent nodes of the line could be taken 
good use of to express the flow direction at anywhere of the 
river, then. 
An assumption is made beforehand that slope value between 
each two adjacent nodes of the centreline could well 
approximate the flow direction everywhere thereby; output 
section-lines there are vertical to the connection-line of these 
two nodes, that is, they are parallel to each other, there. More 
details about the application of this assumption are to be 
explained in 3.3. 
Some facts could well be learned from above that centreline of 
the river way is essential for the algorithm to be self-adapted 
when shape of the river part becomes very much complicated, 
however, we could not always get the centrelines from digitized 
map of the river directly but have to extract them out from the 
GRID image using some certain thinning algorithms in 
Computer Graphics (CG). Distribution of the pixels in GRID 
data has its own characteristics, as shown in Fig.1, exemplified 
by the West River of China (the wriggling bold curve in the 
middle of the picture represents the river way, horizontal or 
vertical lines are virtually constructed for image partitioning, 
which will explained later, axis X and Y together set up the 
geometric coordinate system, in which numerical coordinate 
values are measured throughout this algorithm), these natural 
rivers are narrow and serpentine, which will inevitably lead to 
mass of null values in the content of the DEM data; however, 
most of the thinning algorithms are based on the template 
processing on the entire extent of input image, hence there is 
need to save the great deal of waste of CPUs in the thinning 
process. 
Y 
2586250 
2512500 
2558750 
  
2545000 
530000 
570000 
(Unit: meter) 
Fig.1 extracting centreline of the West River from GRID data 
using thinning method based on image partitioning 
610000 650000 
Some fast thinning algorithms based on image partitioning 
(Kwon, J S. etc., 2001; Chen Guojun, etc., 2001) would like be 
recommended and discussed in the case of solving above 
problems, however, for some reasons, details about extracting 
centrelines of the river from GRID image data will not be 
covered too much here, fig.1 also gives readers an illustration 
about the ideal of this improvement. 
3.3 Partitioning algorithm of section-lines 
Partitioning section-lines at intervals throughout the river is the 
process to make the continuous terrain discrete along the flow 
direction; as there are no restrict constraints about the measures 
to take for the interval between sections, to simplify the 
problem, Euclidean distance along the centreline has been 
picked up to measure this interval in number, it is recommended 
that this interval be close to the grid size of input GRID. 
As shown in fig. 2, P1-Pn represent original mid nodes of the 
centreline, S/~Sn are intersections between the section-line 
(dashed) and the centreline (real line), they are named Sect- 
Point from now on, K1~Kn represent the slope of those sections, 
different sections between each two nodes share the same slope 
value in the algorithm; those section-lines, as their end-points 
haven’t been determined in coordinate values yet, could only be 
expressed numerically with the Seci-Point and corresponding 
slope value KX. — BE 
us d KS x , 2 KS ^k m 
4 ; : | 
    
x 
à 
ger KT s : ; 
A X » S A x 
* + ‘ 1 3 1 
ho , * 4 i 
L se a 
Fig.2 partitioning sections along the river 
453