Abstract: An improved and more efficient algorithm to calculate No-Fit Polygon（NFP） is proposed and it is based on the orbital approach presented by Burke et al. The new algorithm greatly decreases the problem geometry complexity and simplifies calculation method of the minimum moving distance. Many heuristic strategies and the algorithms can be more easily combined to solve two-dimensional nesting problems. Computational results show that the improved algorithm is very efficient, and it has been used in the leather automatic nesting software.

Key words: No-Fit Polygon（NFP）, irregular shape, nesting, orbital approach

摘要： 在Burke等人提出的用于求解临界多边形的移动碰撞算法基础之上，提出了一种更加高效的求取NFP的改进算法。该算法大大降低了问题的几何复杂性，简化了计算最小移动距离的方法，使许多启发式策略可以更加容易地与该算法结合来求解二维排样问题。实例验证了改进算法是有效且可行的，已应用于皮革自动排样软件中。

关键词: 临界多边形, 不规则形状, 排样, 移动碰撞法