锻压技术

二维不规则排样背景下的零件像素化表达算法

英文标题：Pixelated expression algorithm of parts under background of two-dimensional irregular layout

作者：刘虓王宇帆刘嘉敏

分类号：TP391.73

出版年,卷(期):页码：2021,46(8):44-48

摘要：

针对目前主流的零件表达方式，当零件外形呈现出凹多边形特性且顶点数目较多时，冲突检测算法明显变慢的问题，提出了一种零件像素化表达方法，即在零件包围盒上布置多个方形微粒，然后，通过二维布尔变量数组存储微粒是否被占用的信息，提出了微粒“占用”的判断算法。算例1研究了像素图生成速度与微粒边长和零件外形的关系；算例2则研究了零件像素化程度与排样性能的关系，最后，给出了推荐的微粒边长。推荐微粒边长可令排样计算速度和排样效果取得最佳的平衡。同时，算例2还与商用排样软件SigmaNest进行了对比，实验结果表明，如果使用推荐的微粒边长，本文算法得到的材料利用率高于SigmaNest算法，且计算耗时只有后者的2.8%。

For the current mainstream expression way of parts, when the shape of part exhibits concave polygonal characteristics and the number of vertices is larger, the conflict detection algorithm is significantly slower. Based on the above issue, a pixelated expression method of part was proposed, which was to arrange multiple square particles on the part bounding box, and then based on the information that whether the particles were occupied which was stored by two-dimensional Boolean variable array, the judgment algorithm of particles being occupied was proposed. Furthermore, the relationships between the speed of pixel image generation and the side length of particles and the shape of part were studied by calculation example 1, and the relationship between the pixelization degree of part and the performance of layout was studied by calculation example 2. Finally, the recommended side length of particles was given, which made the best balance between the layout calculation speed and the layout effect. At the same time, the calculation example 2 was compared with the commercial layout software SigmaNest. The experimental results show that if the recommended side length of particles is used, the material utilization ratio of algorithm in this paper is higher than that of SigmaNest, and the calculation time is only 2.8% of the latter.

基金项目：

广东省自然科学基金资助项目(2014A030313225)；上海交通大学海洋工程国家重点实验室研究基金项目(1518)

刘虓（1976-），男，博士，副教授 E-mail：liuxiao@scut.edu.cn

参考文献：

［1］王思琪. 基于遗传算法的二维模板排样算法的研究
［D］.成都:电子科技大学,2020.

Wang S Q. Research on Two-dimensional Layout Algorithm Based on Genetic Algorithm
［D］.Chengdu: University of Electronic Science and Technology of China,2020.

［2］李文学. 多约束二维排样算法研究与应用
［D］.武汉:华中科技大学,2016.

Li W X. Research and Application of Polygon’s Packing Optimization with Multiple Constraints
［D］.Wuhan: Huazhong University of Science and Technology,2016.

［3］向文欣，王宏旭，潘立武. 基于匀质块排样方式的多尺寸板材下料算法
［J］.锻压技术，2019,44(7):41-46.

Xiang W X，Wang H X，Pan L W. Blanking algorithm for multiple-size sheets based on homogeneous block layout
［J］. Forging & Stamping Technology，2019,44(7):41-46.

［4］Bezerra V M R, Leao A A S, Oliveira J F, et al. Models for the two-dimensional level strip packing problem-A review and a computational evaluation
［J］. Journal of the Operational Research Society,2020,71(4)：1-19.

［5］Wei L J, Hu Q, Lim A,et al. A best-fit branch-and-bound heuristic for the unconstrained two-dimensional non-guillotine cutting problem
［J］. European Journal of Operational Research,2018,270(2)：448-474.

［6］王静静, 瞿少成,李科林.一种基于并行交叉遗传算法的二维不规则排样问题求解
［J］.计算机应用与软件,2020,37(7):188-193.

Wang J J, Qu S C, Li K L. A two-dimensional irregular layout problem solving based on parallel cross genetic algorithm
［J］. Computer Applications and Software,2020,37(7):188-193.

［7］高荣宇. 二维不规则件排样优化系统研究与实现
［D］.长沙:湖南大学,2019.

Gao R Y. Research and Implementation of Two-dimensional Irregular Part Nesting Optimization System
［D］.Changsha: Hunan University,2019.

［8］王阳. 工艺约束下二维不规则零件排样算法研究
［D］.南宁:广西大学,2018.

Wang Y. Research on the Nesting Algorithm of Two-dimensional Irregular Parts under Process Constraints
［D］.Nanning:Guangxi University,2018.

［9］张蜜蜜. 二维不规则零件排样算法的研究与应用
［D］.北京:华北电力大学,2017.

Zhang M M. Research and Application of Two-dimensional Irregular Part Packing Algorithm
［D］. Beijing:North China Electric Power University,2017.

［10］罗立宏, 冯开平,叶家玮.基于摇瓶策略求解二维不规则件排样问题
［J］.南京理工大学学报,2015,39(2):194-201.

Luo L H, Feng K P, Ye J W. 2D irregular polygon nesting with shaking bottle strategy
［J］. Journal of Nanjing University of Science and Technology,2015,39(2):194-201.

［11］王永振. 二维不规则图形内的矩形排样研究
［D］.沈阳:沈阳建筑大学,2017.

Wang Y G.Research on Packing Rectangle Items in Two-dimensional Irregular Stone Block
［D］. Shenyang: Shenyang Jianzhu University,2017.

［12］陈志杨, 刘妍.改进粒子群搜索的二维皮革排样优化算法
［J］.浙江工业大学学报,2015,43(5):492-496.

Chen Z Y, Liu Y. Optimization algorithm of two-dimensional leather nesting based on improved PSO search
［J］.Journal of Zhejiang University of Technology,2015,43(5):492-496.

［13］徐玲玲. 不规则域皮衣衣片排样算法的研究
［D］.杭州:浙江工业大学,2015.

Xu L L. Research on Layout Algorithm of Irregular Leather Cloth
［D］.Hangzhou:Zhejiang University of Technology,2015.

［14］徐将将. 基于临界多边形的二维不规则排样算法研究
［D］.广州:华南理工大学,2018.

Xu J J. Research of Two-dimensional Irregular Nesting Algorithm Based on No Fit Polygon
［D］. Guangzhou: South China University of Technology,2018.

［15］刘虓. 基于HAPE的二维不规则零件排样算法及其性能研究
［D］.广州:华南理工大学,2011.

Liu X. Two-dimensional Irregular Packing Algorithm Based on HAPE and Its Performance Study
［D］ Guangzhou: South China University of Technology,2011.

［16］刘虓, 叶家玮,刘嘉敏.基于混合表达图形的二维不规则排样构造算法
［J］.上海交通大学学报,2018,52(7):825-830.

Liu X, Ye J W, Liu J M. Two-dimensional constructive packing algorithm based on hybrid representation graphics
［J］.Journal of Shanghai Jiaotong University,2018,52(7):825-830.

［17］Rocha P, Rodrigues R, Gomes A M, et al. Circle covering representation for nesting problems with continuous rotations
［J］. IFAC Proceedings Volumes, 2014, 47(3):5235-5240.

［18］刘虓. 排样算法、资料和程序
［EB/OL］. http://www.huagongchuanhai.cn/packing/, 2020-08-26.

Liu X.Packing algorithms, data and programs
［EB/OL］. http://www.huagongchuanhai.cn/packing/, 2020-08-26.

服务与反馈：

【本网站尚未开通全文下载服务】【加入收藏】