二维异形件排版算法介绍(一)

举报
我爱吃芒果 发表于 2020/06/16 18:57:24 2020/06/16
【摘要】 排样问题(Nesting Problem)又称为下料问题(Cutting and stock problems)或填充问题(Packing Problem),其目标是在材料切割过程中寻找一个较高的材料利用率。排样问题属于经典的NP-Hard问题,其时间复杂度随着问题规模的增加迅速上升,难以在合理时间内精确求解大规模实例。

算法简介

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

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

1. 排样算法关键技术

NFP求解算法

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

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

2. 临界多边形概念(图片来源:参考文献[2]

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

3. 特殊NFP场景:a. 空腔NFPb. 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所示,首先根据多边形AB当前时刻的靠接状态,得到B下一步的移动方向,在该移动方向上,计算出AB之间的最小碰撞距离,从而得到移动距离,根据移动方向和移动距离,将B移动到新的位置,然后重复以上过程,直至绕完一圈,回到初始位置。该算法比较容易实现,但是该算法总的时间复杂度较高,达到(O(m+n)mn)。此外,该算法可以处理空腔NFP和退化NFP等特殊场景。

4. 移动碰撞法计算NFP(图片来源:参考文献[2]

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

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

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

6. 轨迹线法NFP算法原理图(图片来源:参考文献[2]

总结

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

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

1. 4NFP求解算法对比


时间复杂度 能否处理内部空腔 能否处理退化场景
凸化分解法 >O(m3+n3) Yes No
移动碰撞法 O((m+n)mn) Yes Yes
明科夫斯基矢量和法 O(m2n2log(mn)) Yes Yes
轨迹线法 O(mn) Yes Yes

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

参考文献

[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.



【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。