计算机工程与应用 ›› 2016, Vol. 52 ›› Issue (14): 167-171.

• 图形图像处理 • 上一篇    下一篇

一种改进的多边形近似算法

廖志芳,高兴锐,蔡  飞,马小会   

  1. 中南大学 软件学院,长沙 410075
  • 出版日期:2016-07-15 发布日期:2016-07-18

Improved approximate algorithm of polygon

LIAO Zhifang, GAO Xingrui, CAI Fei, MA Xiaohui   

  1. School of Software, Central South University, Changsha 410075, China
  • Online:2016-07-15 Published:2016-07-18

摘要: 多边形近似是曲线矢量数据压缩技术中的一种,其实质是多边形信息压缩问题,目的在于减少多边形曲线数据的冗余信息,释放所占用的空间,达到高效、快速地显示图形。通过分析基于显著点删除的多边形近似算法的特性,发现基于显著点删除算法由于没有考虑多边形与多边形之间的联系以及多边形中特殊点的问题,以至于在处理具有孤立点等情况时的多边形近似效果不理想。为了更好地解决上述缺陷,提出了一种改进的多边形近似算法。通过分析现有算法,发现在处理特殊孤立点、边界处裂缝、多点处于同一直线时处理效果不理想,针对这些问题,通过孤立点单独处理、边界点建立索引以及根据多边形形状忽略处于同一直线上的多点方法,对算法进行改进。同时利用数据集对改进算法性能进行分析,实验结果表明,改进的算法在多边形近似处理效率和效果上更加明显。

关键词: 多边形近似, 显著点删除, 平面曲线, 曲线矢量压缩

Abstract: Polygonal approximation is a curve of vector data compression technology, it is a polygon information compression problem, its purpose is to reduce the polygon curve data redundant information, release the resource, and get the high-efficiency. This paper first analyzes the features of dominant point deletion algorithms, finds that the algorithm does not consider the relationship between the polygon and special point, so the effect is not ideal for these conditions, especially on processing outlier, boundary cracks, multi-point in the same straight line. In order to solve the defects, this paper proposes an improved approximate polygon algorithm. The algorithm presents several methods to deal with these problems, as processing outliers alone, making index for boundary cracks and ignoring the multi-point. Experimental results show the improved algorithm gets more excellent efficiency and effect.

Key words: polygonal approximation, dominant point deletion, planar curves, curve vector compression