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

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

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

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.