﻿ 板材排样中非拟合多边形的构造实现方法
 计算机系统应用  2019, Vol. 28 Issue (9): 168-173 PDF

1. 中国科学院大学, 北京 100049;
2. 中国科学院 沈阳计算技术研究所, 沈阳 110168;
3. 沈阳高精数控智能技术股份有限公司, 沈阳 110168

Construction and Implementation of No-Fit Polygon for Packing and Cutting Problem
MAO Liang-Xian1,2, WANG Pin2,3
1. University of Chinese Academy of Sciences, Beijing 100049, China;
2. Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110168, China;
3. Shenyang Golding NC & Intelligence Tech. Co. Ltd., Shenyang 110168, China
Foundation item: National Science and Technology Major Program (2018ZX04035001)
Abstract: The No-Fit Polygon (NFP) can be used for handling of stock packing and cutting problems with two-dimensional non-regular shape. Previously, NFP has not been widely applied because it is difficult to be implemented and is lack of generic approaches that can cope with all problem cases without specific case-by-case handling. This paper introduces an orbital method. The method can handle the typical degenerate cases, such as holes, interlocking concavities. And we make benchmark for ESICUP datasets which from the literature, proving that this approach can be efficient with almost every situation. It has certain reference significance for the research of the packing and cutting problem.
Key words: packing and cutting     no-fit polygon     orbital approach

1 非拟合多边形

1.1 多边形A与B的接触

 图 1 多边形A和B

 $\rm{{\overrightarrow {\rm{T}}} = A\_\min Y - B\_\max Y}$ (1)

1.2 移动B

1.2.1 找出接触边对

 图 2 多边形B沿T向量平移

 图 3 接触点及接触边对

1.2.2 从接触边对中找出平移向量

1.2.3 删除不可行的平移向量

 图 4 接触边对的可行弧度区间

1.2.4 修剪可行的平移向量

 图 5 多边形沿平移向量平移, 交叉

 图 6 平移向量的起点放置在B的每个顶点

 图 7 多边形B沿平移向量平移

 图 8 平移向量的修剪

1.2.5 移动多边形B

 图 9 B沿平移向量 $\overrightarrow {p1}$ (或 $\overrightarrow {p2}$ )平移情况分析

 图 10 B的参考点沿平移向量平移越过起点

1.3 找到下一个起点

1.3.1 起点搜索算法

1.4 平移向量合并生成NFP

2 案例介绍

 图 11 生成一个外部的NFP

3 测试

 图 12 生成一个外部的NFP

 图 13 生成内部和外部的NFP

 图 14 生成内部和外部的NFP

 图 15 互锁和外部的NFP

4 结论与展望

 [1] 贾志欣, 殷国富, 罗阳. 二维不规则零件排样问题的遗传算法求解. 计算机辅助设计与图形学学报, 2002, 14(5): 467-670. DOI:10.3321/j.issn:1003-9775.2002.05.020 [2] 李建涛, 黄星梅, 钟志华. 二维矩形件切割的路径优化. 机械设计与制造, 2005(4): 86-87. DOI:10.3969/j.issn.1001-3997.2005.04.040 [3] 王书文, 黄星梅, 李建涛. 二维矩形件组块优化切割的研究与实现. 苏州大学学报(工科版), 2007, 27(6): 49-52. [4] 曹德列. 不规则图形数控切割关键技术研究[硕士学位论文]. 武汉: 华中科技大学, 2012. [5] O’Rourke J. Computational Geometry in C. 2nd ed. New York: Cambridge University Press, 1998. [6] Burke EK, Hellier RSR, Kendall G, et al. Complete and robust no-fit polygon generation for the irregular stock cutting problem. European Journal of Operational Research, 2007, 179(1): 27-49. DOI:10.1016/j.ejor.2006.03.011 [7] Bennell JA, Dowsland KA, Dowsland WB. The irregular cutting-stock problem - A new procedure for deriving the no-fit polygon. Computers & Operations Research, 2001, 28(3): 271-287. [8] Dowsland K A, Dowsland WB. Packing problems. European Journal of Operational Research, 1992, 56(1): 2-14. DOI:10.1016/0377-2217(92)90288-K [9] Agarwal PK, Flato E, Halperin D. Polygon decomposition for efficient construction of Minkowski sums. Computational Geometry, 2002, 21(1-2): 39-61. DOI:10.1016/S0925-7721(01)00041-4 [10] Art Jr RC. An approach to the two dimensional irregular cutting stock problem. Massachusetts: IBM Cambridge Scientific Centre, 1966.