【转】云社区博客博客详情二维异形件排版算法介绍（一）

叁歲伎倆 2023-01-14 11:54 101阅读 0赞

转自：[https://bbs.huaweicloud.com/blogs/175385][https_bbs.huaweicloud.com_blogs_175385]

【摘要】 排样问题（Nesting Problem）又称为下料问题(Cutting and stock problems)或填充问题(Packing Problem)，其目标是在材料切割过程中寻找一个较高的材料利用率。排样问题属于经典的NP-Hard问题，其时间复杂度随着问题规模的增加迅速上升，难以在合理时间内精确求解大规模实例。

## 算法简介 ##

# #

排样问题（Nesting Problem）又称为下料问题(Cutting and stock problems)或填充问题(Packing Problem)，其目标是在材料切割过程中寻找一个较高的材料利用率。排样问题属于经典的NP-Hard问题，其时间复杂度随着问题规模的增加迅速上升，难以在合理时间内精确求解大规模实例。相较于矩形排样问题，异形件排样问题的突出特点是裁片的边界轮廓复杂，计算过程中需要复杂的几何运算，其算法复杂度将进一步上升，是学术界和工业界公认的难以求解的问题。因此在大多数情况下，不规则形状排样算法主要是以启发式算法和智能搜索算法为主。

综上所述，二维异形件排样算法涉及到的关键技术主要有三个，如图1所示，分别是高效率的几何算法、排样策略和优化算法。

![fe27783bf39f919f10a2f527396bce2c.png][]

图1. 排样算法关键技术

## NFP求解算法 ##

二维异形件排样算法的一个相当重要的方面是计算几何算法，其主要内容在于计算异形件之间的靠接位置、确定裁片与面料之间的包含关系、判断是否重叠以及实现二维区域之间的交、并、差等布尔运算。

为寻找一种更简便高效的靠接和重叠判断计算方法，研究人员提供了临界多边形（No-Fit Polygon，NFP）的概念\[1\]。临界多边形NFP的简要定义如下：给定两个多边形，其中一个固定，另一个多边形围绕固定的多边形作不旋转的刚体运动，并围绕固定多边形滑动，直到回到起点位置，在此过程中在运动多边形上选取一点作为参考点，则参考点在环绕过程中形成的轨迹就称为临界多边形，如图2所示。

![56046107d310303cd270276c23bcd086.png][]

图2. 临界多边形概念（图片来源：参考文献\[2\]）

NFP求解还会遇到特殊场景，如图3所示，图a由于多边形A存在凹槽，多边形B可以在凹槽内部移动，此时将形成空腔NFP；图b由于多边形B恰好可以沿着多边形A凹槽移动，此时NFP将退化成线；图c多边形B恰好可以放在多边形B凹槽内，此时NFP将退化成点。NFP求解算法同时要考虑这些特殊情景。

![81e8cda53e21a9f54616657cf5e11b11.png][]

图3. 特殊NFP场景：a. 空腔NFP；b. NFP退化成线；c. NFP退化成点（图片来源：参考文献\[3\]）

由于临界多边形的重要性质，NFP目前已成为二维不规则形状排样算法的基础性几何工具。如何快速准确的计算出NFP是异形件排样问题的关键技术。学界目前的求解算法主要有4种，分别是凸化分割法、移动碰撞法\[4\]、明科夫斯基矢量和法\[5\]以及轨迹线法\[2\]。简要介绍如下：

（1）凸化分割法。凸化分割法基本思路是将凹多边形分割为凸多边形，然后求得凸多边形之间的NFP，最后将凸多边形的NFP进行合并得到最终的NFP。凹多边形凸化分割的算法有多种，例如三角划分、凹点划分、条带分割、角平分线分割等。设多边形边数为n，凹点个数为r，目前最少次数分割算法时间复杂度不超过O(n+r2min(r2,n))， 当简单多边形的凹点个数达到n/2时，该分割算法的复杂度已达到O(n3)。如果再加上求解凸多边形的NFP和求解多边形并集的布尔运算，该方法的时间复杂度将进一步增加。此外，该方法可以得到内部空腔NFP，但是对于NFP退化场景，标准多边形求并运算无法得到。

（2）移动碰撞法。移动碰撞法的基本步骤如下：如图4所示，首先根据多边形A和B当前时刻的靠接状态，得到B下一步的移动方向，在该移动方向上，计算出A和B之间的最小碰撞距离，从而得到移动距离，根据移动方向和移动距离，将B移动到新的位置，然后重复以上过程，直至绕完一圈，回到初始位置。该算法比较容易实现，但是该算法总的时间复杂度较高，达到(O(m+n)mn)。此外，该算法可以处理空腔NFP和退化NFP等特殊场景。

![919593eff276caf3b877c18ececfb1f9.png][]

图4. 移动碰撞法计算NFP（图片来源：参考文献\[2\]）

（3）明科夫斯基矢量和法。两个凸多边形之间的NFP等价于计算两者的明科夫斯基矢量和，其算法复杂度为O(m+n)。其基本求解思路如下：如图5所示，首先多边形A（固定多边形）按照逆时针排列，多边形B（移动多边形）按照顺时针排列。然后，将多边形A和多边形B的所有边矢量置于原点（0,0），接着，对所有边矢量按与起始矢量的夹角从小到大排序，最后将排序后的边矢量进行串联累加，即可得到A和B的临界多边形NFPAB。然而，当两个多边形中有一个为凹多边形时，凹边的遍历次序将会被打乱，从而不能合成一个临界多边形。为解决此问题，研究人员引入了斜率图的概念来解决此问题\[5,6\]。然而，该方法实现复杂，时间复杂度也比较高，最坏情况下的时间复杂度为O(m2n2log(mn))。此外，该算法也可以处理空腔NFP和退化NFP等特殊场景。

![e5adacf3da0b6495143d65b22883c78e.png][]

图5. 明科夫斯基矢量和法求解凸多边形NFP（图片来源：参考文献\[2\]）

（4）轨迹线法。轨迹线法的基本原理是：如图6所示，首先求得多边形每个顶点相对于另一个多边形的所有轨迹线，然后从轨迹线集合中得到外围多边形和内部顺时针环，即为临界多边形。该算法从NFP的本身定义出发，算法过程简单，平均时间复杂度为O(mn)，并且能够处理内部空腔NFP和退化NFP等特殊情景。

![5077e10b9907d89c6037e93619841f00.png][]

图6. 轨迹线法NFP算法原理图（图片来源：参考文献\[2\]）

## 总结 ##

NFP是二维异形件排样算法的基础性几何工具，实现不好将严重影响排样算法性能。作者曾采用凸化分解法求解100个多边形的NFP，由于多边形平均点数较大（平均82个），单纯计算NFP的时间开销就达到半小时。因此，非常有必要对各种NFP求解算法进行比较分析，选择一种高效的NFP求解算法。表1总结了4种NFP算法的时间复杂度，以及是否可以处理特殊情景。

文献\[2, 4, 5\]是各种NFP求解算法的巅峰之作，建议初学者先从移动碰撞法\[4\]入手学习（该文实现细节讲解清楚，其余文章则较少），然后再考虑实现其他方法。

表1. 4种NFP求解算法对比

<table> 
 <tbody> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;">&nbsp;</td> 
 <td style="border-color:#000000;vertical-align:top;">时间复杂度</td> 
 <td style="border-color:#000000;vertical-align:top;">能否处理内部空腔</td> 
 <td style="border-color:#000000;vertical-align:top;">能否处理退化场景</td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;">凸化分解法</td> 
 <td style="border-color:#000000;vertical-align:top;">&gt;O(m3+n3)</td> 
 <td style="border-color:#000000;vertical-align:top;">Yes</td> 
 <td style="border-color:#000000;vertical-align:top;">No</td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;">移动碰撞法</td> 
 <td style="border-color:#000000;vertical-align:top;">O((m+n)mn)</td> 
 <td style="border-color:#000000;vertical-align:top;">Yes</td> 
 <td style="border-color:#000000;vertical-align:top;">Yes</td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;">明科夫斯基矢量和法</td> 
 <td style="border-color:#000000;vertical-align:top;">O(m2n2log(mn))</td> 
 <td style="border-color:#000000;vertical-align:top;">Yes</td> 
 <td style="border-color:#000000;vertical-align:top;">Yes</td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;">轨迹线法</td> 
 <td style="border-color:#000000;vertical-align:top;">O(mn)</td> 
 <td style="border-color:#000000;vertical-align:top;">Yes</td> 
 <td style="border-color:#000000;vertical-align:top;">Yes</td> 
 </tr> 
 </tbody> 
</table>

更多有关排版算法的介绍将在后续博客中更新，欢迎大家关注。

## 参考文献 ##

\[1\] Adamowicz M, Albano A. Nesting two-dimensional shapes in rectangular modules\[J\]. Computer-Aided Design, 1976, 8(1): 27-33.

\[2\] Huyao L, Yuanjun H, Bennell J A. The irregular nesting problem: a new approach for nofit polygon calculation\[J\]. Journal of the Operational Research Society, 2007, 58(9): 1235-1245.

\[3\] Bennell J A, Oliveira J F. The geometry of nesting problems: A tutorial\[J\]. European journal of operational research, 2008, 184(2): 397-415.

\[4\] Burke E K, Hellier R S R, Kendall G, et al. Complete and robust no-fit polygon generation for the irregular stock cutting problem\[J\]. European Journal of Operational Research, 2007, 179(1): 27-49.

\[5\] Bennell J A, Song X. A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums\[J\]. Computers & Operations Research, 2008, 35(1): 267-281.

\[6\] Ghosh P K. A unified computational framework for Minkowski operations\[J\]. Computers & Graphics, 1993, 17(4): 357-378.

登录后可下载附件，请[登录][Link 1]或者[注册][Link 2]

[https_bbs.huaweicloud.com_blogs_175385]: https://bbs.huaweicloud.com/blogs/175385
[fe27783bf39f919f10a2f527396bce2c.png]: /images/20221022/c93eabfa91df4af6847df7d91f8009e6.png
[56046107d310303cd270276c23bcd086.png]: /images/20221022/1d87de1a3d1e4bc99acde0b8671f1564.png
[81e8cda53e21a9f54616657cf5e11b11.png]: /images/20221022/af1fc5ddcc50433ab0511e570876ca66.png
[919593eff276caf3b877c18ececfb1f9.png]: /images/20221022/bc0e1aeb056247a393ef980205600160.png
[e5adacf3da0b6495143d65b22883c78e.png]: /images/20221022/dad57d8a848d49a39649a436cef00917.png
[5077e10b9907d89c6037e93619841f00.png]: /images/20221022/61f75624467e48a199769516e80ba332.png
[Link 1]: https://auth.huaweicloud.com/authui/login?service=https://bbs.huaweicloud.com/blogs/175385#attachment&locale=zh-cn
[Link 2]: https://reg.huaweicloud.com/registerui/public/custom/register.html?locale=zh-cn&service=https://bbs.huaweicloud.com#/register
[huaweicloud.bbs_huawei.com]: mailto:huaweicloud.bbs@huawei.com