Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (32): 189-192.DOI: 10.3778/j.issn.1002-8331.2009.32.060

• 工程与应用 • Previous Articles     Next Articles

Improvement on Douglas-Peucker algorithm for non-topology vector data

XIE Yi-cai1,LI Yan2   

  1. 1.Scholol of Computer,South China Normal University,Guangzhou 510631,China
    2.Spatial Information Research Center,South China Normal University,Guangzhou 510631,China
  • Received:2008-12-01 Revised:2009-03-06 Online:2009-11-11 Published:2009-11-11
  • Contact: XIE Yi-cai

Douglas-Peucker算法在无拓扑矢量数据压缩中的改进

谢亦才1,李 岩2   

  1. 1.华南师范大学 计算机学院,广州 510631
    2.华南师范大学 空间信息技术与应用研究中心,广州 510631
  • 通讯作者: 谢亦才

Abstract: The paper analyzes the reason of graphic distortion phenomenon when compressing the non-topology vector graphics by classical Douglas-Peucker algorithm.The reason is that the common boundary is compressed with Douglas-Peucker algorithm more than one time.Based on this,an improvement on Douglas-Peucker named common boundary objected Douglas-Peucker improving algorithm is put forward.To implement it,first this paper designs a new algorithm for extracting common boundary between two polygons.Then it adopts the idea of OOP,packages the common boundary to be a class with other information showed in figure two.Finally,on the basis of the class,it applies classical Douglas-Peucker to the common boundary and non-common boundary of polygons respectively to compress vector graphics.At last,the validity of the new compressing algorithm is proved by experiment with SVG graph.And the advantages in space and time efficiency are analyzed by contrast with the other Douglas-Peucker improving algorithm showed in table one and two.

Key words: Douglas-Peucker algorithm, vector data compressing, Scalable Vector Graphics(SVG), common boundary objected Douglas-Peucker improving algorithm

摘要: 分析了常规Douglas-Peucker算法压缩无拓扑矢量数据时产生公共边“裂缝”现象的原因,即公共边被两次或可能更多次压缩,而每次运用Douglas-Peucker算法压缩时所选择的初始点和终点不同造成的。为此,提出了公共边对象化Douglas-Peucker改进算法。为实现此算法,首先设计了新的公共边提取算法来提取公共边,然后使用OOP技术,把公共边的相关信息封装成类,最后根据公共边对象提供的信息对多边形的公共边和非公共边分别进行Douglas-Peucker压缩。以广东省行政界线的SVG矢量图为实验对象验证了该算法的有效性,分析了该算法相对于其他Douglas-Peucker改进算法在所需辅助空间和时间效率上的优势。

关键词: Douglas-Peucker算法, 矢量数据压缩, 可缩放矢量图形(SVG), 公共边对象化Douglas-Peucker改进算法

CLC Number: