改进临界多边形生成算法  

Improved algorithm for No-Fit Polygon calculation

作　　者：杨卫波[1,2] 王万良[2] 

机构地区：[1]温州大学物理与电子信息工程学院,浙江温州325035 [2]浙江工业大学信息工程学院,杭州310023

出　　处：《计算机工程与应用》2013年第1期32-35,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.51175473);温州市科技计划项目(No.G20100204);浙江省重大科技专项项目(No.2009C11039)

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]