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

第9卷　第24期　2009年12月167121819(2009)2427325204　

科　学　技　术　与　工　程

ScienceTechnologyandEngineering

　Vol19　No124　Dec.2009

Ζ　2009　Sci1Tech1Engng1

地球科学

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

黄万里　戴文远　余　珊

(福建师范大学地理科学学院,福州350007)

摘　要　面状数据的化简是空间数据多尺度表达和制图综合必须处理的关键问题,有些面状的地理要素要求简化前后面积保持一致,并且不破坏原来的拓扑关系。因此必须对原有的线化简算法做适当的改进。提出对要化简的多边形根据其与相邻多边形的邻接关系,对邻接线段分别化简,以保持原来的拓扑关系;并在采用Douglas2Peucker算法化简时,加入面积平衡的约束条件,构造“平衡线”,使化简前后保持面积一致。通过对实验数据化简结果的分析,积及拓扑的一致性,但较Douglas2Peucker算法化简结果,其化简率较小一些。关键词　面积保持　　Douglas2Peucker算法　　多边形化简中图法分类号　P231.5;　　　　文献标志码　A

　　,发生三种变化→面;②面→线;③面→点。因此,在空间数据多尺度表达或制图综合过程中必须处理面状要素的这三种形态变化,本文探讨的问题为面→面的形态变化处理时数据的化简问题,即面状(多边形)数据或图形的化简问题。

面状数据或图形化简可采用线化简的算法和思路,对组成面状的边界线进行化简。比较经典的线化简的方法有Douglas2Peucker算法Shaw算法

[3]

[1,2]

,适用于需要保证化简前后面积一致的多边形化简,如土地利用类型图斑、行政区域的化简。

1　面积保持的多边形化简思想

保持化简前后多边形面积不改变,可以理解为组成多边形的每一部分曲线在化简后都不带来原多边形面积的变化,这样的化简线称为“平衡线”。李建成等提出通过化简前后弧段剖分其自身的包络矩形所得面积比相等的原理,采用直线面积平衡算法和参数曲线面积平衡算法对多边形进行化简,解决面积平衡约束问题,由于所采用的算法约束条件较多,其在速度上较单一的经典算法慢一些

[6]

、LI2Open2

、渐进式化简方法

[4]

、斜拉式弯曲划分

化简法

[5]

等。由于不同性质面状要素的化简有不

同的要求,这些线化简的方法用于面的化简,需要在这些算法的基础上做些改进。如对于土地利用类型图斑,要求化简后面积保持与化简前相等,这就要求对已有的算法进行改进。本文提出一种基于面积保持的Douglas2Peucker改进算法的多边形

2009年10月27日收到

。

本文提出通过保证化简前后曲线与曲线首尾节点连线所构成的图形面积之差相等的方法来构造“平衡线”,实现面积保持的多边形化简。

对于化简的最小曲线单元分为两种情况:①最小曲线单元由3个节点构成(如图1所示),对于这种情况,不对其进行化简;②最小曲线单元由多于3个节点构成(如图2所示),即除了首尾两个节点外,中间有两个以上的节点,对于该曲线单元,化简

福建省教育厅科技项目(JB05305)、

福建省科技厅青年人才项目(2008F3033)资助

第一作者简介:黄万里(1977—),福建漳平人,讲师,博士研究生,研究方向:空间数据多尺度表达及尺度转换;3S集成应用。

第1页下一页