在处理矢量化数据时,记录中往往会有很多重复数据,对进一步数据处理带来诸多不便。多余的数据一方面浪费了较多的存储空间,另一方面造成所要表达的图形不光滑或不符合标准。因此要通过某种规则,在保证矢量曲线形状不变的情况下, 最大限度地减少数据点个数,这个过程称为抽稀。
基本概念
数据经过抽稀后,数量大量减少,并且基本保证能反映原图形或曲线的基本形状特征,能够为进一步的处理节省空间和时间。
抽稀在GIS矢量数据处理,图形数据压缩处理中有广泛的应用。
算法介绍
曲线抽稀的关键是定义抽稀因子,抽稀因子的不同决定的抽稀算法的多样性,在现有抽稀理论中,有按步长,线段长度,垂距等来定义抽稀因子。
步长法
步长法是沿连续曲线每隔一定的步长抽取一点,其余点全部压缩掉,然后在相邻抽取点间用直线连续或曲线拟合逼近。这种方法主要有两点不足:一,曲线上的特征点,如曲线拐弯处,曲线变化较大的点可能因抽稀被压缩掉,导致曲线变形;二,在某些情况下,仍会留下部分多余点无法删除,如曲线中有一段比较直,而步长又较小,会导致此段直线上有多个抽取点,而实际上只要保留直线段的首尾点即可。因此,抽取后的曲线与原曲线有一定的误差,误差大小与步长的设置及曲线拟合方法有关。如果能综合考虑步长和曲率,可能会有更好的效果,但目前对步长和曲率没有明确的规定,一般是由编程人员根据实际情况自行决定。
线段过滤法
线段过滤法是指当某一段的长度小于某一过滤值时,就以该段的中点代替该段,如同此段的两端退化到中点一样。线段过滤法同步长法一样,过滤值的大小决定着抽稀算法的精度,一般也是由编程人员自行确定。
道格拉斯-普克算法
Douglas-Peuker算法(DP算法)一般从整体角度来考虑一条完整的曲线或一段确定的线段,其基本思路为:
1.对曲线的首末点虚连一条直线,求曲线上所有点与直线的距离,并找出最大距离值dmax,用dmax与事先给定的阈值D相比:
2.若dmax<D,则将这条曲线上的中间点全部舍去;
若dmax≥D,保留dmax对应的坐标点,并以该点为界,把曲线分为两部分,对这两部分重复使用该方法,即重复1,2步,直到所有dmax均<D,即完成对曲线的抽稀。
显然,本算法的抽稀精度也与阈值相关,阈值越大,简化程度越大,点减少的越多,反之,化简程度越低,点保留的越多,形状也越趋于原曲线。
DP算法的抽稀精度与上两种方法相比,有明显提高,一因其阈值一般取相应地物最大允许误差,二因算法能做到在删除与保留之间达到较好的平衡,即能充分减少点的数量,又能尽量保留特征点,但由于在编程实现时要用到循环或递归,当点数很多时,效率会受到影响。
垂距限值法
垂距限值法与DP算法原理一样,但其并非从整体角度考虑一条完整曲线,而是从第一点开始依次筛选,去除冗余点。即以第一点为起点,计算第二点至第一点和第三点连线的垂直距离,若此距离大于某阈值,则保留第二点,并将其作为新起点,计算第三点至第二点和第四点连线的距离;否则,去除第二点,计算第三点至第一点和第四点连线距离,依次类推,直至曲线上最后一点。其阈值一般取相应地物最大允许误差或更小。
垂距限值法抽稀精度与DP算法一样,但循环简单,易于编程处理。是一种较理想的抽稀算法。