二维异形件排版算法（摘抄）
算法简介
排样问题（Nesting Problem）又称为下料问题(Cutting and stock problems)或填充问题(Packing Problem)，其目标是在材料切割过程中寻找一个较高的材料利用率。排样问题属于经典的NP-Hard问题，其时间复杂度随着问题规模的增加迅速上升，难以在合理时间内精确求解大规模实例。相较于矩形排样问题，异形件排样问题的突出特点是裁片的边界轮廓复杂，计算过程中需要复杂的几何运算，其算法复杂度将进一步上升，是学术界和工业界公认的难以求解的问题。因此在大多数情况下，不规则形状排样算法主要是以启发式算法和智能搜索算法为主。
NFP求解算法
二维异形件排样算法的一个相当重要的方面是计算几何算法，其主要内容在于计算异形件之间的靠接位置、确定裁片与面料之间的包含关系、判断是否重叠以及实现二维区域之间的交、并、差等布尔运算。
为寻找一种更简便高效的靠接和重叠判断计算方法，研究人员提供了临界多边形（No-Fit Polygon，NFP）的概念[1]。临界多边形NFP的简要定义如下：给定两个多边形，其中一个固定，另一个多边形围绕固定的多边形作不旋转的刚体运动，并围绕固定多边形滑动，直到回到起点位置，在此过程中在运动多边形上选取一点作为参考点，则参考点在环绕过程中形成的轨迹就称为临界多边形，如图所示：
NFP求解还会遇到特殊场景，如图所示，图a由于多边形A存在凹槽，多边形B可以在凹槽内部移动，此时将形成空腔NFP；图b由于多边形B恰好可以沿着多边形A凹槽移动，此时NFP将退化成线；图c多边形B恰好可以放在多边形B凹槽内，此时NFP将退化成点。NFP求解算法同时要考虑这些特殊情景。
由于临界多边形的重要性质，NFP目前已成为二维不规则形状排样算法的基础性几何工具。如何快速准确的计算出NFP是异形件排样问题的关键技术。学界目前的求解算法主要有4种，分别是凸化分割法、移动碰撞法[4]、明科夫斯基矢量和法[5]以及轨迹线法[2]。
摘抄文章: