Transactions of Materials and Heat Treatment

Title：Pixelated expression algorithm of parts under background of two-dimensional irregular layout

Authors： Liu Xiao Wang Yufan Liu Jiamin

Unit： South China University of Technology Shenyang University of Technology

KeyWords： irregular layout pixelization vector illustration conflict detection material utilization ratio

ClassificationCode：TP391.73

year,vol(issue):pagenumber：2021,46(8):44-48

Abstract：

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.

Funds：

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

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

Reference：

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

Service：

【This site has not yet opened Download Service】【Add Favorite】