数字线划图的冗余点检查方法比较研究

易俊华，许泉立

(1.昆明冶金高等专科学校测绘学院，云南 昆明 650033；2.云南师范大学地理学部，云南 昆明 650500)

0 引 言

数字线划图(Digital Line Graphic，DLG)，是运用矢量数据采集手段分层提取各地表要素并编辑、保存到计算机的矢量数据集[1-2].它保存了地理空间要素的空间关系信息和相关属性信息，是GIS数据生产过程中最重要的矢量数据形式之一。数字线划图数据质量的优劣直接影响到GIS系统的运行和使用效率。但数字线划图的生产过程不可避免地会产生大量冗余数据，如空置图层、重复属性信息、线冗余点等。其中线划冗余点是造成数据量大，传输和处理效率低的关键问题。

冗余数据一方面来源于数据采集过程，另一方面来源于数据的处理和应用过程[3-4]。很多学者或研究机构针对数字线划图的冗余点问题进行了大量研究，无论是检测算法还是检查系统都取得了一些成果。比如：1971年，美国开发了具有地图数据拓扑一致性及完整性检测功能的独立地图编码系统[5]，1973年，Douglas D等[6]提出经典的道格拉斯-普克算法；1996年，乌迪内大学开发了“GIS数据质量控制软件”[3，5]。相对于国外，我国对空间数据质量检查的研究相对较晚，但研究成果积累较快：2001年，解放军信息工程大学研制了“航测数字化矢量数据检查验收系统”[5]；2004年，陕西测绘局开发了一款集4D功能于一个系统内的数据质量检查软件——“4D-Checker”[3]，该软件检查功能全面，但对硬件设备要求较高，检查效率低；2007年，国家测绘产品质检中心研制了基于ArcEngine 9.2开发平台的l∶5万DLG质量检查系统[5]；2010年，浙大万维科技有限公司开发了名为“Walk Check”的质检软件；北京吉威时代软件股份有限公司开发的针对3D数据的质量检查软件，以工程项目作为驱动，可以自定义和组合检查规则；2012年，龙胜春[7]提出基于面积阈值的曲线矢量数据压缩方法；2014年，王飞提出了一种以累积偏移量为主要内容的矢量数据实时压缩算法。

综上可述，冗余点检测在理论上已有相对成熟的算法，各空间数据质量检查软件中对冗余点检测功能也进行了集成和封装。但这些检查软件，特别是一些大型的质量检查软件由于检查功能多、检查内容丰富、检查项设置复杂，对单一检查项目设置不够深，检查算法不可见，导致对冗余点检测的针对性不强、检测方法不可选、灵活性不高，检测结果不直观等问题，从而降低了冗余点检查效率。

因此，针对数字线划图冗余点检测问题，本文选择了间隔取点法、垂距法、角度限值法、道格拉斯—普克算法4种方法进行分析与对比，最终选取了垂距法和角度限值法，采用ArcEngine组件开发技术，设计并实现了针对数字线划图冗余点交互式检查软件；并通过运行软件对实验数据进行检测，对比分析检测结果，进而对上述算法的有效性和适用性进行检验与评价，研究出各检测方法适宜的数据种类。

1 冗余点检查算法比较

1.1 冗余点概念与检查原则

在数字线划图生产过程中，由于线状要素及面状要素边界常会出现线段上节点过多的情况，从而造成数据冗余，给地图分析、地图数据存储和地图数据传输使用造成了一定的困难，因此需要对冗余点进行检查并删除。数字线划图冗余点检查在数据分析、处理、存储、应用以及网络传输等方面都非常重要。根据空间数据质量检查规范，冗余点检查的原则是：在保留线状要素必要特征点的前提下，对线状要素进行冗余点检测，所检测到的冗余点应尽可能多，且对冗余点删除后不改变图形形状特征。

1.2 冗余点检查方法介绍

目前，冗余点检查方法主要有：间隔取点法、垂距法、角度限制法、道格拉斯—普克法。

1)间隔取点法：间隔取点法是4种方法中操作最简单的方法[8,16]。基本思想是：从线段的起点开始，每隔n个点取1点为特征点保留，或每隔一段规定的距离取1点为特征点保留，但首末点必须保留，没有被保留的点即为冗余点。

2)垂距法：垂距法检查冗余点的原理如图1所示，基本思想是：从一条线的起始节点开始，每次顺序取线段上的3个节点，计算中间点与其前后相邻两点连线的垂直距离d，用d与预先设定的阈值D比较。若d

图1 垂距法示意Fig.1 The explanation of vertical distance method

3)角度限值法：角度限值法的原理如图2所示，基本思路是：首先设定一个角度阈值D，对于每一条线上的所有中间点，将其与前一点连接，再将其前后2点连接，然后通过判断这2条线的夹角与阈值的大小关系判断该中间点是否为冗余点。具体计算步骤：①连接点A、B与A、C，计算线段AB与线段AC的夹角，记为θ1，若θ1>D，则将点B保留；②连接点B、C与B、D，计算线段BC与线段BD的夹角，记为θ2，若θ2

4)道格拉斯—普克法：该方法是Douglas等[6,9-12]1973年提出的。其算法原理如图3所示，基本思路是：将每一条曲线的首尾点虚连一条直线，计算其余点到该直线的垂直距离d。选出最大距离与规定的阈值D相比较，若小于阈值,则直线两端点间所有点都为冗余点。否则保留最大距离对应的节点，并以该点为界，将曲线分成两部分。重复以上过程，直至处理结束。

图2 角度限制法示意 图3 道格拉斯—普克算法原理Fig.2 The explanation of angle limitation method Fig.3 The explanation of Douglas-Peucker algorithm

1.3 检查方法分析与选择

图4 冗余点检查算法设计流程Fig.4 The flow of algorithm designing for redundancy point checking

下面对4种冗余点检查方法进行分析与比较。

间隔取点法计算工作量小，可以检查出大量的冗余点，但删除这些冗余点后，曲线的形状特征很大程度上会被破坏。垂距法与角度限值法原理相似，不同之处在于垂距法以垂直距离作为判断依据，而角度限值法以角度作为判断依据。2种方法都有易于实现、检查速度快等优点，但删除冗余点后，曲线的形状特征应与设置的阈值有关。道格拉斯—普克法是一个整体算法，通常可保留弯曲程度较大的曲线上的特征点[13-16]。但局限性在于：1)在线状目标起点不确定的情况下，用该方法检查出的结果可能不一样；2)在处理2个对象的公共边时，可能会改变原始线状目标之间的拓扑关系；3)算法比垂距法复杂，计算量较大，编程实现有一定难度。

基于上述方法的对比分析，本文最终选取垂距法与角度限值法进行基于ArcEngine的数字线划图冗余点算法设计和实现。

2 数字线划图冗余点检查算法实现过程

2.1 算法流程图(图4)2.2 基于ArcEngine的算法实现

2.2.1 开发方法

本算法基于ArcEngine 10.0和Visual Studio2010开发平台，使用C#语言进行设计。ArcEngine包含一系列GIS组件，提供多种开发接口，可用来构建各种GIS应用程序。ArcEngine能实现的功能报告：

1)地理数据加载、地图显示、地图编辑和地图输出功能；

2)地图空间查询与空间分析功能；

3)专题地图制作等功能。

C#语言是Visual Studio.NET开发环境下多种常用编程语言之一，.NET环境为开发者提供了一个强大且方便的工具箱，包括所有窗体控件、通用控件、容器类控件、菜单和工具条控件、对话框控件和常用控件等基础控件。本算法的设计需要在窗体界面中添加的控件有：License Control，Map Control，Toolbar Control，TOCControl，dataGridView等控件。控件说明如下。

1)License Control：它能够保证开发的产品在其他平台上正常运行，是所有基于ArcEngine开发的软件必须添加的控件。

2)Map Control：提供一种数据可视化窗口，通过此控件可以完成地图显示、地图缩放、地图空间查询、地图要素选择等功能。

3)Toolbar Control：此控件包含了各种能实现地图基本操作的命令工具，可以根据系统设计需要，从此控件添加所需工具条目。

4)TOCControl：主要负责对各地图图层的管理和操作，通常与Map Control控件关联在一起。

5)dataGridView：提供一种可自定义属性的表格，可将不同类型的数据添加到此表格显示并对其编辑。

2.2.2 程序界面设计

设计了数据加载、数据保存、全图显示、地图平移、地图缩放、地图要素选择等常用操作功能，界面如图5所示。

图5 冗余点检查软件主界面Fig.5 The main interface of redundancy point checking software

3 试验结果与对比分析

3.1 2种方法检查的冗余点位置比较

使用同一数据进行试验，分别对2种方法设置依次递增的阈值，筛选冗余点数量相近或相同的检查结果，试验结果如图6所示，图中圆圈标注的位置表示2种方法都同时检测到的冗余点。

通过分析2种方法检查结果发现：当检查结果中的冗余点数量相近或相同时，2种算法对应的冗余点位置分布有一定的差异。从检查结果图中可以看到，2种方法检查得到的冗余点大部分为共同点。通过整体对比发现：角度限值法检查出的冗余点在位置上比垂距法分布广；用垂距法能检查到的大部分冗余点位置，用角度限值法也同样能检查到。通过局部对比发现：在曲率变化较大且长度较长的线条上，角度限值法检查到的冗余点比垂距法的多；在较平缓的线条上，垂距法检查到的冗余点比角度限值法的多。因此，可以得出这样的结论：垂距法对较平缓的线条检查效果更好，而角度限值法对长度较长且弯曲程度较大的线条检查效果更好。

(a) 基于垂距法检查出6个冗余点 (b)基于角度限值法检查出5个冗余点 (c) 基于垂距法检查出17个冗余点 (d) 基于角度限值法检查出17个冗余点

(e) 基于垂距法检查出28个冗余点 (f) 基于角度限值法检查出27个冗余点 (g) 基于垂距法检查出45个冗余点 (h) 基于角度限值法检查出45个冗余点图6 基于2种不同检查方法检测到的冗余点位置分布Fig.6 The locations distribution of redundant points detected by two different checking methods

3.2 2种方法检查的冗余点数量比较

使用同一实验数据，分别对垂距法和角度限值法设置从小依次递增的阈值，依次进行冗余点检查，并记录冗余点数量。检查完成后，分别对2种方法的检查结果(冗余点数量)进行统计，统计结果见表1、2。

表1 利用垂距法检测的冗余点数量统计Tab.1 The statistics of the number of redundant points detected by vertical distance method

表2 利用角度限值法检测的冗余点数量统计Tab.2 The statistics of the number of redundant points detected by angle limitation method

通过统计分析2种方法的检查结果发现：当输入的阈值较小时，冗余点的数量都较少；当阈值在某个值范围内递增时，冗余点数量随阈值递增的速度较缓慢。本实验中，使用垂距法，当阈值<0.01 m 时，冗余点的数量在20以内缓慢增加；使用角度限值法，当阈值<0.1° 时，冗余点的数量同样在20以内缓慢增加。在一定的阈值范围内，冗余点的数量都保持在合理区间内。当阈值超过质量要求的极大值时，检查结果对数字线划图图形特征影响较大，此时检查结果无实用意义。对本实验数据而言，垂距法阈值不应>0.02 m；角度限值法阈值不应>0.5°。

4 结论与讨论

4.1 结 论

本文主要对数字线划图中冗余点检查问题进行了研究，介绍了4种矢量数据冗余点检查方法，并进行了分析。在垂距法和角度限值法的理论指导下，基于ArcEngine组件GIS库和Visual Studio 2010开发平台，实现了数字线划图冗余点检查算法，完成了2种方法对某区域实验数据检查结果的对比分析。通过总结可得出以下结论：

1)通过实验，发现2种方法设置的阈值对检查结果影响很大。

2)对2种检查方法的检查结果分析得出，垂距法对较平缓的线条检查效果更好，角度限值法对弯曲程度较大且长度较长的线条检查效果更好。

4.2 讨 论

数字线划图冗余点检查结果的优劣直接影响数据质量，而检查方法的选择则是导致不同检查结果的直接原因。因此，对于需进行冗余点检查的数字线划图，应先对数据进行一定评估，针对数据特点，选择最适宜的检查方法，最大限度地降低数据冗余度。同时，对于不同用途的数字线划图，其精度要求也不一致，在冗余点检查阈值设置时，应根据数据精度要求进行相应设置。当然，针对不同数字线划图精度要求，具体设置怎样的检查阈值，这是需要进一步研究的内容。最后，针对数据冗余点检查的方法还有很多，本文仅提及了4种，且只对其中2种算法进行了对比分析，更多算法的实验对比，有待进一步研究。