Computer Engineering and Applications ›› 2013, Vol. 49 ›› Issue (1): 32-35.

Previous Articles     Next Articles

Improved algorithm for No-Fit Polygon calculation

YANG Weibo1,2, WANG Wanliang2   

  1. 1.College of Physics & Electronic Information Engineering, Wenzhou University, Wenzhou, Zhejiang 325035, China
    2.College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023, China
  • Online:2013-01-01 Published:2013-01-16

改进临界多边形生成算法

杨卫波1,2,王万良2   

  1. 1.温州大学 物理与电子信息工程学院,浙江 温州 325035
    2.浙江工业大学 信息工程学院,杭州 310023

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的改进算法。该算法大大降低了问题的几何复杂性,简化了计算最小移动距离的方法,使许多启发式策略可以更加容易地与该算法结合来求解二维排样问题。实例验证了改进算法是有效且可行的,已应用于皮革自动排样软件中。

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