基于安卓平台的河网建模与可视化研究

贾露 王杰华 朱晓辉 刘婉 喻纪文

摘要：利用信息化技术对河网水质进行实时监测可及时发现污染事件并定位污染源，是水污染控制和治理的一个重要手段，对监测区域河网进行可视化建模是水环境监测系统一个重要研究内容。提出将河网抽象为有向图进行计算机建模，设计新的图遍历算法遍历河网模型、获取河道路径，同时基于安卓平台和GIS（地理信息系统）技术可实现河网可视化。通过曲线拟合技术进一步优化可视化界面，改善用户体验。实验结果表明，基于安卓平台和GIS技术实现河网可视化，可以显示较为清晰的河网可视化界面和监测点分布情况。

关键词：河网；建模；可视化；图遍历算法；曲线拟合

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）07-0206-04

Abstract：Using information technology to monitor water quality of river networks in real time can detect pollution events and locate pollution source in time， which is a significant means of water pollution control and governance. Visualization of the river network in monitoring area is a vital research issue in water environment monitoring system. In this paper， the river network is abstracted as a directed graph for computer modeling， and a new graph traversal algorithm is designed to traverse the river network model and obtain the river path. The river network is visualized based on Android platform and GIS （Geographical Information System） technology. The visualization performance is also further improved using curve fitting technology to enhance the user experience. Experimental results show that visualizing the river network based on Android platform and GIS technology can display the interface of river network and the distribution of monitoring points clearly.

Key words：river network； modeling； visualization； graph traversal algorithm； curve fitting

我国水污染严重，研究江河源区河网结构对我国水资源持续利用具有重大意义[1]，而研究河网建模及其可视化，对于后续分析河网结构、监测水质变化和管理水环境等具有重要价值。

目前国内外在水系河网建模及分析方面，已有许多研究成果。Wu等[2]基于复杂网络理论将河网抽象为有向复杂网络模型，并对河网模型的节点重要度的度指标进行统计分析。Qu等[3]研究一种基于不规则三角网数字高程模型的水系流域特征自动提取算法，该算法可以高效地生成连通性强的水系河网。唐志贤等[4]提出一种面向水系河网的建模与索引方法，该方法基于图论进行数字流域水系河网建模，重点关注如何对水系河网进行有效分析并提高对水利领域数据的访问效率。陈星等[5]基于图论将河网概化为图模型，探讨利用图模型可达性特征对水系规划前后的河网连通性做出定量评价。钱真等[6]基于河网矩阵标识法，从图论角度描述河网拓扑结构，提出更为通用、灵活的面向对象的矩阵标识法。以上研究成果多数在对河网进行建模后，重点关注基于模型分析河网结构、连通性、访问效率以及节点重要度等，忽视了河网模型遍历及后续可视化问题。

本文基于图论开展水系河网的计算机建模研究，设计新的图遍历算法实现对河网模型的遍历，获取河网中的河道路径，同时基于安卓平台和GIS（Geographical Information System）技术，以电子地图为底图，将河道路径以覆盖物的形式绘制出来，实现河网模型的可视化，并对水质监测点位置进行标记，便于分析河网结构特征和模拟河网，为复杂河网的水质监测提供可视化界面支持，对于水污染的治理具有重要现实意义。

1 河网建模

河网结构反映了一个流域区域或地区的水系空间分布，是分析河流形态与功能的重要基础[7]。水系河网中河流众多且分布复杂，具有一定的网络结构特征。图论是建立数学模型与网络拓扑结构联系的有效工具，规格化研究问题，有效使用计算机的优越性解决问题[8]。因此，本文基于图模型对河网进行计算机建模，通过分析河网结构，把河流中的分叉点、汇合点、弯曲点抽象为图的顶点，把河道抽象为图的边，把河流流向抽象为顶点之间的连线方向，将河网抽象建模为有向图，如图1所示，利用有向图性质研究河网。图结构是一种较线性表和树更为复杂的数据结构，任意两个结点之间都可能存在关系[9]，因此，图状结构可以用来描述许多复杂的数据对象。

图常用的存储结构有邻接矩阵和邻接表，邻接矩阵是把图中顶点的数据信息保存在一个一维数组中，通过矩阵表示图中各顶点之间的邻接關系，容易确定图中任意两个顶点之间是否有边相连；邻接表是将所有顶点的邻接表表头放入数组构成图的邻接表，容易找到任意顶点的第一个邻接点和下一个邻接点。由于需要对河网模型进行遍历，经常会查询某个顶点的邻接点，这时邻接矩阵的优势就突显出来，因此采用邻接矩阵的存储方式。图1中的有向图其邻接矩阵arcs 如式（1）所示：

式（1）中的矩阵行列数均为12，表示河网模型的顶点数为12；非零元素共有13个，表示河网模型共有13条有向边；零元素表示对应顶点间不存在边。

2 河网模型遍历算法

在对河网进行建模并存储后，需要遍历河网模型获取所有河道路径，有向图的遍历一般有深度优先搜索（DFS）和广度优先搜索（BFS）两种方式。DFS从图的某个顶点出发，遍历某一分支的所有顶点后再遍历另一分支。结合河网特征，可以发现河流按照各自所在分支运动，这与DFS遍历过程十分相似，而BFS则是遍历过某层的所有顶点后再遍历下一层次，这与河网运动特点不相符，对河网遍历时不如DFS优势突出，因此采用DFS算法搜索河道路径。

采用DFS算法对图1有向图进行深度优先遍历，从河流结点A出发访问各个结点，所得结果为A→B→C→E→J→D→F→H→G→I→K→L。通过观察分析图1发现，河流源头为顶点A，从顶点A流经结点B，在结点B处分出两条支流，分别流向结点C、D，结点C处的支流流经结点E，最终到达终点J，河流经过的路径A→B→C→E→J就是其中一条河道路径，类似地可以找出其余4条河道路径，因此，实际形成的河道路径是（1）A→B→C→E→J，（2）A→B→D→F→H→J，（3）A→B→D→G→H→J，（4）A→B→D→G→I→K，（5）A→B→D→G→I→L。对比DFS算法结果和实际结果，可以发现二者存在明显不同，究其原因是DFS在搜索过程中遍历完一条分支后就会跳转到下一条分支，而实际中河流从初始源头沿着河流分支连续流动，遍历得到一条河道路径后，应该从河流源头结点重新开始遍历。

因此，为了解决DFS算法结果和实际结果的差别，本文在DFS算法基础上，对DFS算法进行重新设计，根据河网结构特点，采用递归思想，重新设计并实现了新的图遍历算法SearchRiver（vertex，arcs），算法描述如下：

算法1 SearchRiver（vertex，arcs）

输入：河网顶点集合数组vertex，邻接矩阵数组arcs

输出：河道路径集合pathList

1.初始化河道路径集合pathList为空

2.初始化河道路径集合对应的长度集合pathLengthList为空

//记录河道路径的长度，此处暂用邻接矩阵中的“1”表示邻接结点间的距离

3.计算河流分支数目pathNumber

4.for i←0 to pathNumber-1 do

5.初始化当前路径edges为空，pathLength←0 //变量pathLength表示当前河道路径长度

6.noNext←false //记录当前顶点是否还有邻接结点的标志

7.DFS（0， 0， edges）

8.把edges添加至pathList并且把pathLength添加至pathLengthList

9.if pathList.size（） > 1

10.if pathList.get（pathList.size（） - 1）=pathList.get（pathList.size（） - 2） // 若获取的路径相同，提前结束循环

11.then pathList.remove（pathList.size（） - 1） //移除重复路径

12.pathLengthList.remove（pathList.size（） - 1）

13.break

14.把pathList按照长度降序排序

15. return pathList

算法2 DFS（begin， length， edges）

输入：遍历开始结点begin，begin结点边上权值length，当前路径edges

输出：遍历得到新的河道路径edges

1.pathLength←pathLength+length

2.把结点begin添加至路径edges

3.初始化回滚结点值rollBackNum←-1

4. for a←0 to vertexNum-1 //vertexNum是顶点数目

5.if arcs[begin][a] > 0 //如果顶点a是顶点begin的邻接结点

6.then if 路径集合pathList已经包含了添加顶点a之后的edges

7.then从edges移除顶点a并令rollBackNum←a

8.Continue

9.else从edges移除顶点a

10.DFS（a， arcs[begin][a]， edges）

11.if noNext=true then return

12.if rollBackNum>-1

13. then DFS（rollBackNum， matrix[begin][rollBackNum]， edges）

14. else noNext ←true

將河网模型遍历算法应用于图1中的有向图，输入有向图对应的顶点和邻接矩阵，调用算法进行遍历，算法输出结果如图2所示，图2中的5条河道路径与实际河道路径结果相符，验证了算法的正确性。

3 河网可视化

如图3所示，这是流经南京市的某段长江河流，根据河流形状特点在图中选取并用字母标记出若干结点用于建模，并将结点对应的经纬度坐标存储至数据库，其中，结点A为此段河流源头结点，在结点D处出现分支，并于结点F处汇合。首先，将河网抽象为有向图，把河流结点抽象为有向图的顶点，把河道抽象为有向图的边，然后调用河网模型的图遍历算法，获取所有河道路径，共有2条河道路径，分别是A→B→C→D→E→F→G→H和A→B→C→D→I→J→K→F→G→H。电子地图是以GIS技术为基础的数字地图，基于安卓平台通过API编程方式调用地图服务网站数据库中的信息，并通过地图API接口获取电子地图[10]，以覆盖物的形式在地图上绘制河道路径，通常情况下，以覆盖物表示河道，圆形图标表示水质监测点，河网模型的可视化效果如图4所示，可显示河道与水质监测点的分布情况。

4 实验结果分析与优化

4.1 实验环境

本文河网可视化界面开发环境为Android Studio1.0，服务器使用SQL Server 2012数据库对河流结点进行存储，实验时Android终端设备为oppo1107，操作系统配置为Android 4.4.4，处理器配置为四核1.2GHz，运行内存为1GB，基于上述条件对河网可视化效果进行实验测试。

4.2 实验结果分析

本文对上述实验结果进行测试，分析评价在不同缩放程度下可视化界面的清晰度与准确度。当对河网可视化界面进行放大操作时，结果如图5所示，发现河道覆盖物宽度未随放大级别发生变化，无法做到精准覆盖，造成河道大面积裸露在外，影响界面美观，实验结果仍需改进。因此，接下来研究并实现了河道覆盖物宽度与缩放级别同步变化的算法，来优化可视化界面，改善用户体验。

4.3 采集河道覆盖物宽度数据

为实现河道覆盖物宽度随地图缩放级别同步变化，首先需要得到不同缩放级别下最接近河道宽度的覆盖物宽度，其中，能清晰显示河网全貌的最低地图缩放级别是10，当地图缩放级别大于14时，河网局部被过度放大无法辨别河网结构，因此此处探讨的地图缩放级别范围为10～14。为获得最接近河道宽度的覆盖物宽度值，针对某一缩放级别，覆盖物宽度值从10开始逐渐增大，找出某一宽度值使覆盖物在最大程度上精准覆盖河道，并记录此时的河道覆盖物宽度值。对不同缩放级别逐一进行测试来采集不同缩放级别下河道覆盖物宽度值，结果如表1所示。

4.4 曲线拟合结果及界面优化

曲线拟合是用连续曲线近似地刻画或比拟平面上离散点组所表示的坐标之间的函数关系的一种数据处理方法[11]。由于上文收集到的河道覆盖物宽度数据呈现离散分布，在曲线拟合的适用范围内，因此接下来采用曲线拟合技术来求解河道覆盖物宽度和缩放级别的函数关系，通过曲线方程表示二者关系，得到不同缩放级别下精确的河道覆盖物宽度值。

因此，利用Matlab工具解析河道覆盖物宽度和缩放级别的函数关系，输入数据和cftool命令启动曲线拟合工具箱，以缩放级别为自变量，河道覆盖物宽度为因变量，测试多种可能的函数模型，选择其中最优拟合结果，最终采用自定义函数拟合结果。

自定义函数拟合结果的函数表达式为：f（x）=a*exp（-b*x）+c，其中，a=0.0002919，b=-0.9013，c=10.69，拟合图形如图6所示，SSE（误差平方和）为26.32，R-square（确定系数）为0.9961，Adjusted R-square（校正后确定系数）为0.9948，RMSE（均方根误差）为2.095，标准误差σ=1.7102。

使用自定义函数拟合结果优化可视化界面，当用户对地图进行缩放操作时，通过安卓程序的回调函数可以获得地图缩放级别，根据自定义函数拟合结果的函数表达式计算河道覆盖物宽度，在电子地图上重新绘制河道覆盖物，图7是河网可视化界面放大前后效果对比图，基本实现对河道的精准覆盖，对可视化效果进行优化，提升了可视化界面的准确度与美观度。

5 结束语

本文将河网抽象为有向图，设计实现新的河网模型遍历算法获取河道路径，基于电子地图上绘制河道路径覆盖物，实现安卓移动端的河网可视化。实验结果表明，本文提出新的河网模型遍历算法能完成复杂河网模型的河道路径遍历，降低了河网可视化的实现难度，与现有河网建模及分析研究成果相比，重点关注被忽视的河网模型遍历问题，提出新的遍历算法获取河道路径，并基于安卓平台显示河道与监测点。同时，本研究已在安卓平台上实现河网模型可视化应用，由于水质监测是防止水污染的重要方式[12]，该可视化应用已经投入实际水质监测中使用，可清晰地显示河网和监测点，为后期显示水质监测相关结果提供可视化界面支持，基于移动平台这一特性会打破水环境监测的时空限制，对于水环境的管理具有重要社会价值。

参考文献：

[1] 王光谦，方红卫，倪广恒，等.大江大河源区河网结构与径流特性研究前沿和重要基础科学问题[J]. 中国科学基金，2016，30（1）：27-33.

[2] Wu X W， Li L， Qu Y G. Modelling and Analysis of River Networks Based on Complex Networks Theory[J]. Advanced Materials Research， 2013， 756-759（2）：2728-2733.

[3] Qu G D， Su D Y， Lou Z H. A new algorithm to automatically extract the drainage networks and catchments based on triangulation irregular network digital elevation model[J]. Journal of Shanghai Jiaotong University， 2014， 19（3）：367-377.

[4] 唐志賢，冯钧，徐曦，等.面向水系河网的建模与索引方法研究[J].电子科技大学学报，2015，44（4）：611-616+640.

[5] 陈星，许伟，李昆朋，等.基于图论的平原河网区水系连通性评价——以常熟市燕泾圩为例[J].水资源保护，2016，32（2）：26-29+34.

[6] 钱真，贾卫红，李世阳. 河网水流模拟的矩阵标识法研究[J].人民长江，2014，45（14）：85-88.

[7] 王跃峰，许有鹏，张倩玉，等. 太湖平原区河网结构变化对调蓄能力的影响[J].地理学报，2016，71（3）：449-458.

[8] 杨开林. 渠网非恒定流图论原理[J]. 水利学报，2009，40（11）：1281-1289.

[9] 严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社， 2002.

[10] 陈晓宁，马亚飞. 基于NewMap API的Web地图服务系统应用[J]. 测绘通报，2012，（3）：77-80.

[11] 丁克良，欧吉坤，赵春梅. 正交最小二乘曲线拟合法[J]. 测绘科学，2007，32（3）：18-19+17+192.

[12] 亓相涛， 周敢.基于物联网的在线水质监测系统设计[J].电脑知识与技术，2016，12（27）：185-187.