河网数据拓扑一致性简化方法

操震洲姜林燕吴煜心

（1.南京工业大学测绘科学与技术学院，江苏 南京211816;2.江苏省金威遥感数据工程有限公司，江苏 南京210000）

0 引 言

在传统制图综合领域，对河流选取与简化等问题有较深入的研究。在河流选取方面，一般通过一元回归模型、多元回归模型、开方根规律等确定河流的总体选取数量[1]。在具体选取时，通常根据河流的长度、级别等指标确定河流的重要程度，然后选取较重要河流、舍去较次要河流。例如，张青年，艾廷华，姜莉莉等[1-3]分别提出以河流等级、汇水区域面积、流域为选取指标的水系综合方法。窦世卿等[4-7]对河流的简化进行了研究，河流简化主要涉及到简化算法和简化后数据的拓扑一致性维护问题。Douglas-Peucker算法[8]是所有曲线简化算法中公认最优秀的，但其时间复杂度高。为提高Douglas-Peucker算法的时间性能，艾波等[7]提出采用线性BLG树结构事先存贮结点偏离量的方法。采用该线性BLG树能有效缩短曲线的简化时间。在图形简化过程中，空间目标之间的拓扑关系也会发生变化[9]，主要表现为出现拓扑不一致。简化后数据的拓扑一致性必须得到保证，这是数据可用性的前提。Saalfeld[10]对简化后数据的拓扑不一致问题进行了研究并提出了解决方法，但Saalfeld的方法是有局限性的。Da Silva ACG 等[11-12]对Saalfeld的方法进行了改进和完善，使之可适用于点、线、面的拓扑一致性维护。河流选取既要考虑河流的尺寸大小，也要考虑河流的主、支流关系。当支流被选取时，主流也应被选取。在以上研究中，都未能同时顾及这两个因素。另外，河流的简化和拓扑一致性处理费时较长，目前已有算法在时间性能上不够理想，不适合实时性要求高的应用。

1 河流选取的指标

面向电子显示设备的要素选取通常基于要素尺寸，如牛方曲等[13]提出的以要素屏幕面积作为选取指标的面要素多尺度显示方法。在河流的选取中，河流尺寸是河流选取时应考虑的第一个因素。在小尺度河网数据中，只需要显示较大尺寸的河流，在大尺度河网数据中，则可显示较小尺寸的河流。另外，河流分为主流与支流，主、支流之间构成层次关系。例如，图1中的河流1与河流2、3、4分别构成了主流与支流的上下层关系（图1的河流号标记在各河流的首尾两端处），河流2和河流5也构成了主、支流层次关系。在选取时，若选取支流，则对应的主流也应被选取。因此，河流的层次性是选取时要考虑的第二个因素。

本文综合考虑河流的尺寸与层次性，并统一量化为权重指标，以该指标作为河流选取的标准。权重指标的计算方法为:首先计算各河流的最小外接矩形，以最小外接矩形的长边值作为对应河流的初始权重值;然后按河流层次关系建立河系树，树结点值为河流的初始权重值;对河系树中各父子结点值进行检查并调整，从叶结点开始，若结点权重值大于其父结点值，则将其父结点权重修改为该结点的值，若结点权重值小于对应父结点值，则无需调整。按调整后的权重大小选取河流，这样既保证了尺寸大的河流先被选取，又保证当某支流被选取后，其对应的主流也一并被选取。

河流权重指标计算方法下所示（图1）。

图1 河流权重的计算方法

2 河网多尺度组织结构

通过曲线简化方法生成多尺度河网。Douglas-Peucker算法是公认最优秀的曲线简化算法，但其时间复杂度为O（n2）（n为结点数），不适合大数据量的实时简化。为提高Douglas-Peucker算法的时间性能，先后提出了多种方法如BLG树结构、BLG树的线性表结构存贮等。本文方法是按Douglas-Peucker算法事先计算河流的各结点偏离量，并以线性BLG结构存贮，然后按存贮的结点偏离量大小筛选结点以实现河流简化的。该方法可将Douglas-Peucker算法的时间复杂度从O（n2）降为O（n）。在图形简化后，空间对象之间可能会出现拓扑不一致。拓扑不一致类型可分为两种:① 由原来的相邻、相交关系变为相离关系;② 由原来的相离关系变为相邻或相交关系。出现第一类拓扑不一致的原因是不合理删除了多要素的公共交点或邻接点，第二类拓扑不一致表现为出现不该有的线段相交和自相交。本文对河网拓扑一致性的维护方法为:① 规定约束点不可删除，这样可避免第一类拓扑不一致的发生;② 对结点删除后的新生成线段进行判断，消除不合理的相交，这样可消除第二类拓扑不一致，保证简化后河网的拓扑一致性。称河流的端点、多条河流间的交汇点为约束点，河网的多尺度组织结构可按以下方法生成。

（1）逐河流执行Douglas-Peucker算法，生成BLG树，将各结点偏离量线性存贮，生成线性BLG树结构。

（2）计算河流的最小外接矩形，计算各河流的初始权重值。

（3）按河流层次关系河系树，调整树中父子结点的权重值。

（4）为保证河流约束点在简化中不被删除，将河流约束点偏离量修改为该河流的权重值，以保证约束点在简化中总是被选取。

河流2的线性BLG树的生成过程如下所示（图2）。其中，河流2的约束点有端点P21、P27，河流交汇点P23。

图2 单条河流的结点偏离量计算过程

按以上方式建立各河流的线性BLG树后，线性BLG树的开始两个结点存贮了河流的权重值，可基于它进行河流选取，而在其他结点存贮结点偏离量信息，可基于它进行河流简化。由于该线性BLG树已按河流的层次关系调整了权重值，所以能保证当支流被选取时，其对应的主流也会被选取。同时，该线性BLG树修改了约束点的偏离量值，所以可以避免第一类拓扑不一致的发生。

对于可能出现的第二类拓扑不一致，可按Da Silva ACG等[11-12]的方法来处理。如图3所示，实线C、虚线C’分别代表简化前后的河流。线段L1L2的端点L1落在多边形v4v5v6v7内，表明出现了拓扑不一致。此时可通过恢复结点的方式消除拓扑不一致。

图3 拓扑异常判定策略

该河网组织结构可根据用户需求快速生成保持拓扑一致性的多尺度河网数据。记当前选取和简化的尺度分别为r1、r2，则当前尺度下的河网数据生成过程如下:

①根据r1检索河流，选取权重≥r1的所有河流;② 对所有选中的河流，选取偏离量≥r2的所有结点;③ 对上一步新生成的所有线段，按图3的方法检测拓扑不一致，通过恢复结点消除拓扑不一致;④ 输出当前尺度下的河网数据。

3 实验及分析

基于.NET平台开发了实验系统，测试河网多尺度组织结构的有效性。数据源为Shapefile格式文件，实验程序读取Shapefile格式河网数据，按本文方法建立河网多尺度组织结构。实验程序根据用户的设置，动态生成任意尺度的河网数据，同时对简化后河网数据执行拓扑不一致的检测与消除。以下为三个不同尺度下的河网数据视图（图4）。

图4 多尺度河网数据视图

4 结 语

河网数据多尺度简化涉及河流选取、简化算法、拓扑一致性维护等内容。本文提出的河网多尺度组织结构在满足拓扑一致性的前提下实现了河网的多尺度动态生成。该结构首先根据河流的尺寸与层次性计算河流权重，以权重作为河流选取的指标，然后逐河流建立线性BLG树，以结点偏离量作为河流的简化依据。基于河网多尺度组织结构开发了实验系统并验证了其有效性。但在拓扑一致性维护算法的时间效率方面仍有待进一步研究。