基于面积保持的Douglas_Peucker改进算法的多边形化简.pdf

2
1 1
2 2 2 Ζ 1 1 1
2
2
2
2 2 2
2
第 9卷第 24期 2009年 12月科学技术与工程 Vol 9 No 24 Dec. 2009
1671 1819 (2009) 24 7325 04 Science Technology and Engineering 2009 Sci Tech Engng
地球科学
基于面积保持的 Douglas Peucker
改进算法的多边形化简
黄万里戴文远余珊
(福建师范大学地理科学学院,福州 350007)
摘要面状数据的化简是空间数据多尺度表达和制图综合必须处理的关键问题,有些面状的地理要素要求简化前后面积
保持一致,并且不破坏原来的拓扑关系。因此必须对原有的线化简算法做适当的改进。提出对要化简的多边形根据其与相
邻多边形的邻接关系,对邻接线段分别化简,以保持原来的拓扑关系;并在采用 Douglas Peucker算法化简时,加入面积平衡的
约束条件,构造“平衡线”,使化简前后保持面积一致。通过对实验数据化简结果的分析,改进的算法能很好保持化简前后面
积及拓扑的一致性,但较 Douglas Peucker算法化简结果,其化简率较小一些。
关键词面积保持 Douglas Peucker算法多边形化简
中图法分类号 P231. 5; 文献标志码 A
面状地理要素或现象在观测尺度由小变大或化简法,适用于需要保证化简前后面积一致的多边
由大比例尺表示转为小比例尺表示时,其形态将会形化简,如土地利用类型图斑、行政区域的化简。
发生三种变化: ①面→面; ②面→线; ③面→点。因
此,在空间数据多尺度表达或制图综合过程中必须 1 面积保持的多边形化简思想
处理面状要素的这三种形态变化,本文探讨的问题
为面→面的形态变化处理时数据的化简问题,即面保持化简前后多边形面积不改变,可以理解为
状(多边形)数据或图形的化简问题。组成多边形的每一部分曲线在化简后都不带来原
面状数据或图形化简可采用线化简的算法和多边形面积的变化,这样的化简线称为“平衡线”。
思路,对组成面状的边界线进行化简。比较经典的李建成等提出通过化简前后弧段剖分其自身的包
[ 1, 2 ]
线化简的方法有 Douglas Peucker算法、L IOpen 络矩形所得面积比相等的原理,采用直线面积平衡
[ 3 ] [ 4 ]
Shaw算法、渐进式化简方法、斜拉式弯曲划分算法和参数曲线面积平衡算法对多边形进行化简,
化简法[ 5 ]等。由于不同性质面状要素的化简有不
解决面积平衡约束问题,由于所采用的算法约束条
同的要求,这些线化简的方法用于面的化简,需要[ 6 ]
件较多,其在速度上较单一的经典算法慢一些。
在这些算法的基础上做些改进。如对于土地利用
本文提出通过保证化简前后曲线与曲线首尾节点
类型图斑要求化简后面积保持与化简前相等这
, , 连线所构成的图形面积之差相等的方法来构造“平
就要求对已有的算法进行改进。本文提出一种基
衡线”,实现面积保持的多边形化简。
于面积保持的 Douglas Peucker改进算法的多边形
对于化简的最小曲线单元分为两种情况: ①最
小曲线单元由个节点构成(如图