王晋

【摘 要】本文主要对线性地物自动综合算法进行了探讨，并在对其中的几种算法（Lang算法，Douglas-Peucker算法，Visvalgam-Whyatt算法）进行实现的过程中有一些心得，希望与大家共享。

【关键词】自动综合；基线；搜索区域

随着计算机技术的迅速发展，计算机制图已经广泛应用于测绘领域中。但是计算机制图不可能把地面全部景物毫无遗漏地表示出来，由于空间的限制，只能用有限的空间清晰地表达制图区域的部分内容。因此，根据实际工作的需要，随着编图比例尺的缩小，需要对资料图的地类进行取舍与概括，这就是我们要提到的自动综合。

地图的自动综合是从原始的地图数据库（大比例尺）综合得到较小比例尺的地图数据库，并生成可视化的地图产品。它是实现测绘自动化非常重要的一项内容。目前，自动综合的研究类型和内容很多，其中每一类型的算法也比较多，本文主要对线性地物自动综合的几种算法进行探讨。

1.自动综合算法介绍

线性地物的自动综合是自动综合中较为重要的一项内容。其目的就是使存储量最少，保持线的弯曲特征。有的学者总结了线性要素自动综合应该遵循的4条原则：

（1）小弯曲删除，大弯曲保留。

（2）2个弯曲，3个弯曲可合并成一个弯曲，依此类推。

（3）独立性强的弯曲应保留或夸大。

（4）自然的线不能变成几何的线。

目前提出的主要具体算法有：nth点算法，Douglas-Peucker算法，垂距算法，角度算法，对于每一种算法，其评价的基本要求是：变形量最少；数据压缩量最大；目标的完整性；关系的完整性；参数尽量少；参数和地图综合结果应当明显，效果好，效率高。

1）Independ point algorithms（独立点算法）：这种算法没有考虑与相邻点的几何关系而孤立地进行取舍。例如：nth点算法，对于一条直线保留了nth个点，其余的全被消除，而且这种选取也是随机的。显尔易见，这种算法很难保持图形形状，从而产生很大的变形。因此，现在很少有人再用这种算法。

2）Local processing algorithms（局部处理算法）：顾名思义，对于一个点的取舍要根据与之相邻点的特征。研究表明：这种算法产生的变形较小，但是它不如下面的几种算法。

3）Constrained extended local processing algorithms（强制延伸局部处理算法）：这种算法的搜索区域不再局限在相邻点上，而是根据距离，角度，或顶点个数延伸。最具代表性的是Lang algorithms，它是早期开发的算法之一。这种算法中，区域的延伸要受到“ look-ahead”参数的控制，要消除的顶点个数由垂直距离允许值e决定。算法图解如图1所示：

图1

解算过程如下：

（1）首先确定一条基线，基线由起点与终点（起点+look-ahead）构成；

（2）计算每个点到基线的垂直距离，如果有一个值超出了允许值ε，重新构成基线（起点不变，终点向后退一个），重新计算，直到所有距离值都小于允许值ε。然后重新确定基线，算法继续。

对于这种算法，如果look-ahead和ε的值设置恰当，能够产生很好的综合效果，对于变形量和数据压缩可以控制；但是，参数较多，参数值的确定较难。

（3）Unconstrained extended local processing algorithms（自然延伸局部处理算法）：这种算法的搜索区域不再局限在相邻点内，但是它不象上一个算法受 “look-ahead”参数的控制，而是受图形复杂度的限制。Reumann and Witkam 描述了这种算法：

由两条平行线组成的搜索区域向前延伸，直到和某一直线相交（每条平行线到基线的距离为ε），所有落在该区域内的点（除第一点和最后一点外）都被消除，从而又产生一个新的搜索区域，算法继续。

（4）Global algorithms：其中Douglas and Peucker算法最为有名，作一条连接起点与终点的直线，作为基线，如果每个点到基线的距离都小于ε，这些点被消除，基线取代折线，否则，在距离最大的顶点处分为两部分，算法继续。算法如图2所示。

这种算法应用非常广泛，首先是the globle tolerance band 概念具有很强的直观感染力；其次，它是应用于GIS中最早的算法。

Visvalingam and Whyatt 指出了允许带宽算法的不足，他们认为：选取超过允许距离中最远距离的点作为临界点是不科学的，因为这个点可能是不准确的或是具有最小特征的点。为了保持图形的形状和特征，他们提出一种新的算法，这种算法根据各点的影响区域而对该点进行取舍。一个点的影响区域就是该点和与其相邻各点形成的三角形的面积。

图2

这种算法比较简单，图形上的每个顶点（除起、终点外）都形成一个区域三角形，具有最小影响面积的点被去掉，当某点被去掉后，与其相邻点需要重新计算。算法如图3所示：

研究表明：Visvalingam-Whyatt算法在保持线的性状方面具有优势，而Douglas-Peucler算法在数据压缩方面具有优势。

2.自动综合的算法分析

对于以上的几种算法进行比较，可以发现它们都有一定的不足之处和一定的适用范围：

（1）Mahes Visvalingam等针对大比例尺道路的综合，对Douglas-Peucker 和Visvalingam算法进行了比较，其结论是：Douglas-Peucker算法得不到弯曲特征的综合效果，在点最少的简化条件下，它比Visvalingam算法优越，通过实验，他认为压缩到40%时，两种算法对于道路（大比例尺）而言，都会产生变形。

（2）Erick.VanHom考虑地图数据库中的线在计算机显示器上显示时，由于分辨率的限制和显示比例尺的缩小，采用Douglas-Peucker方法会使线的图形产生变形，因此在用该方法之前，先用点的重定位技术，即先把点归算到最近的网格上，该方法也会产生线的自交问题，解决办法是手工纠正。

（3）Douglas-Peucker算法同USGSB算法，nth点算法，垂距算法，角度算法的比较结果是：综合时应当区分自然的线要素和人文的线要素。

3.结论

对于以上的各种算法，我们不能简单地进行评价，它们都具有各自的使用范围，因此，在线性地物自动综合中要根据实际工作的需要，采用适当的算法。

地图自动综合是一项工程性任务，必须从工程设计的角度看待地图自动综合问题，也就是说，设计的地图自动综合系统应能完成地图综合任务，生产出满足用户要求的产品。 [科]

【参考文献】

[1]乌巧伦，刘瑜，张晶等.地理信息系统—原理、方法和应用.科学出版社，2002.

[2]郭庆胜，李沛川.地图自动综合系统的概念框架设计.测绘信息与工程.杂志，1999：1.

[3]郭庆胜，李沛川.地图自动综合方法的研究进展.地图.杂志，1999：1.