The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B4. Beijing 2008 
182 
3. CONSTRUCTION OF SINGLE-LINE RIVER 
NETWORK 
Before performing further analysis, a single-line river network 
must be constructed by replacing double-line rivers and lakes 
with their centerlines, and its topology structure is supposed to 
be constructed. 
3.1 Data Analysis 
Topographic data are vector-based that represent river as 
polygonal lines. Depending on data scale, rivers are classified 
as narrow or wide. Narrow rivers are represented in the 
computer as single polygonal lines, and they are referred to 
single-line rivers. Wide rivers are represented in the computer 
are represented as polygonal lines that are tagged as either left 
or right banks, so they are referred to double-line river. Lakes 
are also represented as sets of polygonal lines, and they are 
treated as wide and possibly short wide rivers. 
A polygonal line, or polyline, is defined by a sequence of points 
P = {pi, p 2 , ... , p n }, called vertices, and line segments, called 
edges, that join consecutive vertices. We assume that the only 
intersections between segments happen when consecutive 
edges share their common endpoint. A polygon is a circular 
sequence of points that can also be considered as a polyline 
with a last vertex that is identical to the first. The topographic 
data do not have information indicating the distinguish flow 
direction. 
3.2 Extraction of Centerlines for Double-line Rivers and 
Lakes 
3.2.1 Centerline Approximation: 
The river centerline can be automatically generated using 
medial axis. The medial axis is a well-studied structure. It is 
studied both in image analysis and in computational geometry. 
Image analysis algorithms obtain the medial axis through 
computing which pixels, in a rectangular gird of pixels, are in 
the medial axis. This is not a good fit with the input vector data, 
which describes our rivers by sequences of unevenly scattered 
vertices. It is difficult to define the topological connections of 
the output. 
Computational geometry has developed theoretically optimal 
algorithms to compute the structure for polygons. The medial 
axis can be found by computing Voronoi diagrams or 
constrained Delaunay traingu-lations. The Voronoi diagram for 
a set of point sites {xl,x2,...,xn}in the plane is the 
decomposition of the plane into maximally connected regions 
that have the same set of closest sites. Mathematically, the 
Voronoi diagram and the Delaunay triangulation are duals. 
The approximations to the medial axis centerline based on the 
Voronoi diagram of the discrete boundary. Segments can be 
discretized as a set of points, so their Voronoi diagram can be 
approximated by the Voronoi diagram of points. Thus, we 
discretize the boundary of the river and lake, compute the 
Voronoi diagram of these points, and approximate the medial 
axis from the result. Based on Voronoi diagram we mark 
Delaunay triangles to identify banks between tributaries. By 
marking the triangles, we can extract only the subset of the 
medial axis that joins tributaries. 
We use the midpoint line approximation to compute the medial 
axis. This approximation joins the midpoints of adjacent and 
marked Delaunay triangles into paths. Midpoints are points lie 
inside marked Delaunay triangle ABC with coordinates 
(A+B+2C)/4 where A, B, C are the vertices of the triangle and 
edge c is the shortest edge of the triangle. Geometrically, if d is 
the midpoint of c, then the point (A+B+2C)/4 is the midpoint of 
line segment C to D. 
C 
Figurel. The midpoint of a triangle. 
The midpoint line approximation shows very good convergence 
to the medial axis. 
3.2.2 Cases of islands in wide rivers and lakes: 
Large river often has distributaries which flow away from it 
and flow into it at end, on the other word, it often has loops. In 
order to obtain a tree-like single-line river network we must cut 
the loops. This requires a manual decision of how to cut these 
loops. Here we can use the three factors to make decision. As 
shown in figure 3, we reserve the centerline of the tributary 
(solid line) and delete the relatively smaller distributary’s 
centerline (dashed line). For small loops, arbitrary decision can 
be use to select the centerline to be reserved, for this will hardly 
affect the calculation result. 
Lakes and wide rivers often are large enough to contain islands. 
For the islands have limited impact to the river length, when 
computing centerlines we don’t respect the islands inside wide 
rivers and lakes. Before the extraction of centerline, we can 
delete these islands through the attribute that is put for island.