基于有向图理论的循环水系检测方法研究与制图试验

倪文辉，李维庆，甘元芳

（国家测绘地理信息局 第三地理信息制图院，四川 成都 610100）

0 引 言

2013年至2015年开展的第一次全国地理国情普查开启了我国测绘地理信息工作的一个新领域，地理国情信息为科学制定经济社会发展重大战略、长远规划和宏观政策提供了一种新的基础信息。地理国情普查数据采集工作完成后，以及随着常态化地理国情监测的开展，在未来很长一段时间内，地理国情普查成果及地理国情监测成果的转化应用将是测绘地理信息部门的一项重要工作。各类型地理国情专题图产品制作便是地理国情普查成果图形化展示的有效途径。

地理国情专题制图最大的工作量集中在制图综合阶段。地理国情数据制图综合既包含地表覆盖图斑制图综合，也包括水系、道路、构筑物等实体要素的制图综合。其中水系实体要素是地理国情普查成果的重点线状国情要素，其特点是数量大、图形结构形态多样，节点多、流向复杂[1]。水系实体要素实现自动综合是地理国情普查图制作过程中首先要解决和亟需解决的问题。水系实体要素的综合处理主要是通过对水系实体要素的矢量方向进行遍历，并根据制图比例尺需求，按照舍弃次要水系，保留主要水系，舍弃无名称水系，保留有名称水系，舍弃密集区短小水系，保留稀疏区源头水系等原则进行综合处理。然而，软件工具自动综合处理时，一旦遇到水系实体要素形成闭合环路，就会在局部形成遍历“死循环”，导致程序无法继续处理。针对这个问题，本文将有向图基本理论与方法应用到循环水系检测中，对传统深度优先遍历(DFS)算法改进形成循环水系检测的技术流程和方法，并结合生产实践针对性地研发出实用性软件工具，解决了地理国情普查图制作水系实体自动综合的技术问题，极大地提高了制图生产效率。

1 研究区及数据源

考虑到不同地域水系形态特征，本文选取四川地区的县市和江苏地区县市开展试验。四川地区位于中国西南腹地，地处长江上游，全省河网密布、水资源丰富，水系主要呈树状分布，大小支流众多。江苏地区跨江濒海，地势平坦，水网发达，河渠纵横且呈格网状分布。选取上述两个研究区进行试验具有一定的代表性和广泛性。

本文研究所用数据的来源为第一次全国地理国情普查的地表覆盖和国情要素数据成果。该成果现势性2015年，包括不分区（分为地理单元数据、构筑物要素数据、交通数据、水域数据及元数据）和分区（分为地表覆盖数据、交通数据、水域数据）两类。

2 水系有向图构建

随着计算机图形学及相关技术的发展和在地图制图中的深入应用，推动了地图综合的发展及地图概括的自动化进程。线状要素的自动综合成为制图综合领域研究的热点与重点，用于制图综合的模型和算法也日益增多，研究取得了一些阶段性成果。在地物要素简化方面，制图综合研究人员陆续提出基于自然规律的线划要素的化简方法，基于Snake技术的线光滑与位移方法，基于约束点的曲线一致性化简方法，并建立了道格拉斯-普克法、James法、光栏法等一系列经典的要素简化算法，并基于这些算法衍生出适应于不同环境下的算法[2]。本文基于有向图理论研究建立了DFS改进算法，并应用于制图生产。

2.1 水系有向图构建方法

有向图D是一个有序的三元数组(V(D)，E(D)，ψ(D))，其中V(D)为非空的顶点集，E(D)为边集合，ψ(D)称为关联函数，它使D的每条边对应D的有序顶点对[3]。如果e是D的一条边，而u与v是使得ψ(u,v)=e的顶点，那么称e是由u连接到v，标为e=(u,v)，同时称u为e的起点，v为e的终点。

设D=(V，E)是有向图，其中，V={v1,v2,…,vn},E={e1,e2,…,em}，A(D)=(aij)mxn是D的邻接矩阵，aij是以vi为始点vj为终点的边的条数，1≤i≤n,1≤j≤n。水系实体具有明显的方向特性，水系中的每个要素(Feature)都是从起点到终点的连接线，可以从from point和to point获取其起点和终点的坐标[4]，如图1所示。

图1 水系实体要素的矢量方向Fig.1 Vector directions of water entity

水系有向图构建的方法：

1）读取水系实体要素数据(HYDL)，并遍历水系实体的每个要素(Feature)。

2）获取构建有向图的顶点数据集V。首先获取第1个要素的from point（起点）和to point（终点）坐标，编号为0和1，并存储到顶点数据集V中；再遍历第2个要素的from point（起点）和to point（终点），分别判断该顶点是否已经存储在V中，如果V中存在，则V中不加入该顶点，否则作为新的顶点加入到V中；同样的方法遍历完水系实体的所有要素，获得水系有向图的顶点集V和顶点数量N(D)。

3）获取水系有向图的有向边E。对每个遍历的水系实体要素，将要素的起点和终点记录在有向边E中，如{[起点编号，终点编号]}，得到水系有向图的边集E和边的数量N(E)。

4）通过得到的V和E点集，计算水系有向图邻接矩阵A(D)。

2.2 拓扑排序

对于有向图G，若它的一个节点序列LS：v1,v2,…,vn满足这样的条件：＜vi,vj＞是G的边时，在LS中vi位于vj之前，否则(不是边时）在LS中vi与vj的前后次序任意，则称LS为图G的一个拓扑序列，求拓扑序列的操作称为拓扑排序(Topological Sorting)。一个有向无环图必须满足两个条件：

1）每个顶点出现且只出现一次；

2）若存在一条从顶点A到顶点B的路径，那么序列中顶点A出现在顶点B的前面。

通过拓扑排序可以快速检测出构建的有向图中是否存在环路，具体步骤如下：

①从有向图中选择一个没有前驱（即入度为0）的顶点并输出。

②从有向图中删除该顶点和所有以它为起点的有向边。

③重复步骤①和步骤②直到当前的有向图为空或当前图中不存在无前驱的顶点为止。否则说明有向图中必然存在环。

2.3 DFS算法理论

深度优先搜索算法（Depth-First-Search，简称DFS）是一种用于遍历或搜索树或图的算法，是沿着树的深度遍历树的节点，尽可能深地搜索树的分支[5]。当节点v的所有边都已经被遍历过，搜索将回到发现节点v的那条边的起始点，这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源点并重复以上过程，整个过程反复进行直到所有节点都被访问为止。

本文在研究水系有向图理论的基础上，改进深度优先算法(DFS)得到一种新型算法，形成了水系中环路检测的技术流程，改进DFS算法实现思路如图2所示。

图2 改进DFS算法检测水系环路流程图Fig.2 Improved DFS algorithm to detect hydrologic loop fl ow chart

1）选取水系有向图顶点集中的第一个顶点V作为起始顶点，标记其访问状态Visited为true，并将该顶点存入栈Stack中；

2）对V顶点的连接顶点采用DFS算法进行遍历，当连接顶点出度为0时出栈，出栈时判断该顶点是不是在栈中，如果是，则存在环[6]；

3）出栈时，判断该顶点是否存在另一个连接顶点，同时标记该顶点的访问状态Visited为false，这时候在继续遍历访问时，不会因为访问过某顶点而不会再进行遍历，避免了漏环的存在；

4）找到环后，通过建立水系有向图中顶点与线要素的关联规则，找到顶点所对应的边，并将该边对应的要素输出[7]。

3 制图试验

3.1 水系实体处理

以一幅区县图为例，水系实体要素达2 000多条，数据制图综合时采用软件进行自动综合处理（包括标记长度不够指标的河流、河流弯曲化简、湖泊弯曲化简等步骤），处理过程如图3所示。

图3 水系实体处理过程图Fig.3 Water entity processing chart

如果水系中存在环状流向，则程序一直保持循环遍历的状态，无法继续进行到下一个步骤，至此水系自动综合将无法实现软件自动化，只能依靠人工进行综合判断取舍，大大增加了工作量。

3.2 水系环路检测试验

本文以Microsoft Visual Studio 2010与ArcEngine10.1为开发平台，针对水系环状流向问题，改进深度优先遍历算法(DFS)形成一种新型算法，利用新型算法研发出快速、高效、可操作性强的循环水系检测工具，具体开发工具界面运行如图4所示。

图4 水系环路检测工具Fig.4 hydrologic loop detection tool

该检测工具的算法步骤为：首先通过水系环路检测工具，自动搜索地理国情普查图制图数据库中的水系要素，建立水系有向图，并利用拓扑排序检测水系有向图中有无环路；然后再通过改进DFS算法计算搜索水系中的所有环路而不是部分环路；最后利用开发的工具输出检测结果文件HYDL_error，检测结果如图5所示。

图5 水系要素中环路检测结果Fig.5 Loop detection results of hydrologic elements

为了对深度优先搜索算法(DFS)改进前后水系环路检测结果进行对比分析，本文选取了同一区域的水系数据分别采用改进前和改进后的DFS算法检测水系中的环路，结果如图6所示。

图6 DFS算法改进前后水系环路检测结果对比Fig.6 Comparison of loop detection results before and after DFS algorithm improvement

检测结果表明，改进前的DFS算法检测环路时存在明显的“漏环”现象，只能检测出水系中较少部分的环路而不能将环路全部检测出来。造成这种情况主要是由于DFS算法对水系有向图进行遍历时，访问过的节点已经被标记，当检测到外围的环路时，环路中的顶点已经被全部被标记了访问状态，当再次访问顶点的其他连接点时，不再访问，此种算法虽然能检测出部分环路，但是没有解决水系自动综合实现的问题，仍然会导致程序处于无限循环的状态。而改进后的DFS算法在处理环路时，出栈的过程中会重新修改顶点的访问状态，当再次访问到时可以继续访问其连接的其他顶点，由图6知，水系中的环路已经被全部检测出来，检测效果较好，针对检测出的环路，可对其进行局部人工反向或者程序反向修改，修改后的水系要素实体数据可重新导入普查图制图软件进行自动化处理，能够快速输出成果。因此，制图自动综合程序可快速顺利运行，不再出现循环遍历的情况。

4 结束语

本文对地理国情普查图制作工艺流程中水系自动综合处理遇到的水系环状流向造成程序“死循环”问题进行了研究，并提出了一种以有向图的基本理论为基础，对传统DFS搜索的改进形成的一种新型水系环路检测的解决方法。通过水系的矢量特征，构建水系有向图，再通过有向图的深度优先遍历算法，搜索水系中存在的环路并输出。改进前后的试验结果对比表明，改进的DFS算法能够有效检测出水系中的环路，并且检测结果更加精确。在试验成功的基础上，利用地理信息系统开发平台，研发了水系环路检测工具，并将其集成应用到地理国情普查图制作的工艺流程中，批量解决了水系综合处理过程中出现“死锁”的问题，提高了制图效率。