基于重心NFP的二维不规则形状排样算法

摘要

提出了一种基于重心NFP的二维不规则多边形排样算法,算法主要包括临界多边形计算和排样定位选优等内容.该算法以多边形来表示板材和待排零件,通过求解临界多边形NFP来得到多边形之间的所有靠接(排放)位置.为了在NFP中进一步得到优化的靠接位置,在NFP的基础上提出了重心NFP的概念,通过选择重心NFP中的最低重心位置来确定零件的排放位置.在零件的排样次序算法上,提出了顺序递归排样算法和遗传算法,以降低排样过程中形成的空腔所造成的浪费.该算法可处理板材和零件均为不规则形状的排样问题,允许零件在全角度范围内进行旋转,并可处理板材内部带孔洞或者边界形成空腔等特殊情况.