基于启发式模拟退火的曲线多边形近似算法

Optimal Polygon Approximation of Planar Curve Using Heuristic Simulated Annealing

针对平面曲线最优多边形近似问题,结合曲线的局部和全局特征,提出一种新的基于启发式模拟退火思想的多边形近似方法。将曲线多边形近似问题转换为最小化代价函数的问题,利用模拟退火算法对其求解最优解,并采用启发式方法将曲线的局部特征作为先验知识引入退火过程加速其收敛。通过与多种局部及全局算法的实验比较表明,该方法在数据压缩率和近似误差等方面具有更好的性能,且有效地压缩了运行时间。

Combining local features and global features of the curve, a noval, method on polygon approximation of planar curve using heuristic simulated annealing was proposed. The problem of polygon approximation was formulated as one of minimizing cost function. The optimal solution was found using simulated annealing algorithm, and local features were introduced as prior knowledge into the algorithm in heuristic manner to accelerate its convergence. Compared with the conventional methods based on local features or global features, the experimental results show the algorithm obtained better approximating effect and spaced running time.