改进的临界多边形生成算法

排样问题是工业领域中亟待解决的问题,多边形最优靠接位置的求解问题以及重叠重判断问题,是排样问题中需重复计算的关键问题,快速求解NFP,已成为排样算法中的关键。在介绍NFP基本定义及移动碰撞算法的基础上,提出了一种改进NFP的滑动轨迹求解算法,对临界多边形的生成过程进行了描述,给出了算法实现过程,并以移动碰撞算法为参考,对改进算法的时间复杂度进行了实验验证。仿真结果表明,改进算法可有效降低算法的时间复杂度,为解决排样问题提供了参考。

Improved Algorithm for No-Fit Polygon Calculation

Nesting is the key problem to be solved in industrial areas. The optimal abutting position and overlapping heavy judgment of polygon are the most critical issues which need repeated calculation. The NFP’s fast calculation has become a key nesting algorithm. After an introduction to the basic definition of NFP and mobile collision algorithm,we propose an improved algorithm for solving NFP based on sliding track. Then we describe the no-fit polygon’s generation process and algorithm’s implementation process. With the mobile collision algorithm as reference,we verify the improved algorithm’s time complexity by experiments. Simulation results show that the improved algorithm can effectively reduce the time complexity of the algorithm and is therefore of value for solving the problem of nesting.