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.