Promotion of a No Fit Polygon Algorithm Based on Trajectory

doi:10.16183/j.cnki.jsjtu.2020.208

Abstract

Abstract:

The nesting problem is how to nest objects of a specified shape in a two-dimensional space to obtain the maximum space utilization rate, which is of great significance in industrial production. The solution to the nesting problem requires frequent cross-checking of the objects to determine whether the nesting position is legal. The No Fit Polygon algorithm can be used to accelerate the procedure of cross-checking, but the algorithm cannot be used to calculate shapes containing curves, which limits its application. An algorithm based on orbit sliding can calculate No Fit Polygon between shapes which includes arc, but its effectiveness is not satisfactory. Aimed at this problem, and based on trajectory algorithm, the trajectory generation strategy and the profile algorithm are analyzed and improved. The improved algorithm can calculate the No Fit Polygon between shapes containing arc in a shorter time, solving both accuracy and effectiveness problems. Finally, the algorithm is tested in the real punch production process and the results of the test confirms the correctness and effectiveness of the algorithm.

Key words: No Fit Polygon, trajectory algorithm, nesting problem

CLC Number:

TP391

ZHOU Xin, LAI Xiaoyang, MENG Xiangqun, WANG Kun, TANG Houjun. Promotion of a No Fit Polygon Algorithm Based on Trajectory[J]. Journal of Shanghai Jiao Tong University, 2021, 55(5): 536-543.

Figures/Tables 15

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Fig.12

Tab.1

Fig.13

Tab.2

References 14

[1]	ADAMOWICZ M, ALBANO A. Nesting two-dimensional shapes in rectangular modules[J]. Computer-Aided Design, 1976, 8(1):27-33. doi: 10.1016/0010-4485(76)90006-3 URL
[2]	TERRY W, AMICO M D, IORI M. Bin packing problem with general precedence constraints[J]. IFAC-PapersOnLine, 2015, 48(3):2027-2029. doi: 10.1016/j.ifacol.2015.06.386 URL
[3]	MARTELLO S, PISINGER D, VIGO D. The three-dimensional bin packing problem[J]. Operations Research, 2000, 48(2):256-267. doi: 10.1287/opre.48.2.256.12386 URL
[4]	孙佳正. 基于不完整临界多边形的二维排样问题的研究[D]. 上海: 华东师范大学, 2018.
	SUN Jiazheng. Research on 2D Layout problem based on incomplete No-Fit Polygon[D]. Shanghai: East China Normal University, 2018.
[5]	XU J J. An optimization algorithm based on no fit polygon method and hybrid heuristic strategy for irregular nesting problem [C]//The 36th China Control Memories Collection. Dalian: Technical Committee on Control Theory, Chinese Association of Automation, 2017: 1234-1239.
[6]	YANG Q. No Fit Polygon for nesting problem solving with hybridizing ant algorithms[J]. Journal of Software Engineering and Applications, 2014, 7(5):433-439. doi: 10.4236/jsea.2014.75040 URL
[7]	VALVO E L. Meta-heuristic algorithms for nesting problem of rectangular pieces[J]. Procedia Engineering, 2017, 183:291-296. doi: 10.1016/j.proeng.2017.04.041 URL
[8]	杨卫波, 王万良. 改进临界多边形生成算法[J]. 计算机工程与应用, 2013, 49(1):32-35.
	YANG Weibo, WANG Wanliang. Improved algorithm for No-Fit Polygon calculation[J]. Computer Engineering and Applications, 2013, 49(1):32-35.
[9]	杨卫波, 王万良, 张景玲, 等. 基于遗传模拟退火算法的矩形件优化排样[J]. 计算机工程与应用, 2016, 52(7):259-263.
	YANG Weibo, WANG Wanliang, ZHANG Jingling, et al. Packing optimization of rectangles based on improved genetic annealing algorithm[J]. Computer Engineering and Applications, 2016, 52(7):259-263.
[10]	刘海明, 周炯, 吴忻生. 应用临界多边形方法与小生境遗传算法求解不规则排样问题[J]. 小型微型计算机系统, 2016, 37(5):1002-1007.
	LIU Haiming, ZHOU Jiong, WU Xinsheng. Using No Fit Polygon method and niche genetic algorithm to solve irregular layout problems[J]. Small Microcomputer System, 2016, 37(5):1002-1007.
[11]	周炯. 基于临界多边形方法的二维不规则件排样问题及其算法研究[D]. 广州:华南理工大学, 2015.
	ZHOU Jiong. Two-dimensional irregular parts layout problem based on No Fit Polygon method and its algorithm research[D]. Guangzhou: South China University of Technology, 2015.
[12]	汤德佑, 周子琳. 基于临界多边形的不规则件启发式排样算法[J]. 计算机应用, 2016, 36(9):2540-2544.
	TANG Deyou, ZHOU Zilin. No-Fit-Polygon-based heuristic nesting algorithm for irregular shapes[J]. Journal of Computer Applications, 2016, 36(9):2540-2544.
[13]	刘胡瑶, 何援军. 基于轨迹计算的临界多边形求解算法[J]. 计算机辅助设计与图形学学报, 2006, 18(8):1123-1129.
	LIU Huyao, HE Yuanjun. New algorithm for No Fit Polygon calculation[J]. Journal of Computer-Aided Design & Computer Graphics, 2006, 18(8):1123-1129.
[14]	BURKE E K, HELLIER R S R, KENDALL G, et al. Irregular packing using the line and arc No-Fit Polygon[J]. Operations Research, 2010, 58(4):948-970. doi: 10.1287/opre.1090.0770 URL

多边形类别	临界多边形	运行时间/ms		优化效率/%
多边形类别	临界多边形	轨迹线算法	移动碰撞法	优化效率/%
简单凸多边形		0.47	0.55	15.5
凹多边形		9.15	11.21	18.4
扳手		50.91	67.25	24.3
齿轮		167.03	267.68	37.6

序号	板料类型	套料用时/ms		效率提升/%
序号	板料类型	临界多边形相交校验	常规相交校验	效率提升/%
1	眼子料	145.32	208.92	30.5
2	板料(窄)	208.73	391.41	46.7
3	板料(宽)	448.27	1013.15	55.8

[1]	WANG Wei, RUAN Yaduan, GU Peng, CHEN Qimei. Calculation of Maximum Crack Width Based on DAUNet Integrating Attention Mechanism [J]. Journal of Shanghai Jiao Tong University, 2025, 59(12): 1866-1877.
[2]	MAO Yanmei, LI Huafeng, ZHANG Yafei. Unsupervised Domain Adaptation for Cross-Regional Scenes Person Re-Identification [J]. Journal of Shanghai Jiao Tong University, 2025, 59(12): 1878-1890.
[3]	HU Dan, CUI Yuting, ZHOU Haihe, LIU Yingli. Optimization of Process Parameters Using Improved Dung Beetle Algorithm [J]. Journal of Shanghai Jiao Tong University, 2025, 59(12): 1901-1915.
[4]	ZHAN Zehui, ZHONG Ming’en, YUAN Bingan, TAN Jiawei, FAN Kang. Detection of Roadside Vehicle Parking Violations Under Random Horizontal Camera Condition [J]. Journal of Shanghai Jiao Tong University, 2025, 59(10): 1568-1580.
[5]	ZHANG Zhiyuan, HU Jisu, ZHANG Yueyue, QIAN Xusheng, ZHOU Zhiyong, DAI Yakang. Attention-Guided Multi-Task Learning for Prostate Cancer Pelvic Lymph Node Metastasis Prediction [J]. Journal of Shanghai Jiao Tong University, 2025, 59(8): 1216-1224.
[6]	JI Mian, LIN Yanping, WANG Dongmei, CHEN Li, MA Xin. Precise Foot Feature Point Localization and Automatic Parameters Measurement [J]. Journal of Shanghai Jiao Tong University, 2025, 59(5): 703-710.
[7]	WANG Hongxin, XU Degang, ZHOU Kaiwen, LI Linwen, WEN Xin. Data-Driven Method of Modeling Sparse Flow Field Data [J]. Journal of Shanghai Jiao Tong University, 2025, 59(5): 684-690.
[8]	BAO Jiahan, SUN Deshang, HUANG Jianzhong, HU Zheng. FAST Algorithm for Accurate Corner Points Detection of Section Steel Based on Adaptive Threshold [J]. Journal of Shanghai Jiao Tong University, 2025, 59(5): 691-702.
[9]	ZHANG Aoyuan, HU Xiaofeng, ZHANG Yahui. Rescheduling of Multi-Scenario and Multi-Objective Dynamic Changes of Ship Group Construction [J]. Journal of Shanghai Jiao Tong University, 2025, 59(4): 476-488.
[10]	LIU Jianxin, PAN Ruru, ZHOU Jian. Unsupervised Fabric Defect Detection Based on Under-Complete Dictionary Reconstruction [J]. Journal of Shanghai Jiao Tong University, 2025, 59(2): 283-292.
[11]	WANG Ke, LIU Yiyang, YANG Jie, LU Aiguo, LI Zhe, XU Mingliang. Landing State Recognition of Carrier-Based Aircraft Based on Adaptive Feature Enhancement and Fusion [J]. Journal of Shanghai Jiao Tong University, 2025, 59(2): 274-282.
[12]	ZHANG Tao, ZHANG Xuerui, CHEN Yong, ZHONG Kelin, LUO Qijun. Airfield Multi-Scale Object Detection for Visual Navigation in Civil Aircraft [J]. Journal of Shanghai Jiao Tong University, 2024, 58(11): 1816-1825.
[13]	NIU Guochen, SUN Xiangyu, YUAN Zhengyan. Vehicle-Road Collaborative Perception Method Based on Dual-Stream Feature Extraction [J]. Journal of Shanghai Jiao Tong University, 2024, 58(11): 1826-1834.
[14]	WANG Baokun, WANG Rulu, CHEN Jinjian, PAN Yue, WANG Lujie. Automatic Detection Method for Surface Diseases of Shield Tunnel Based on Deep Learning [J]. Journal of Shanghai Jiao Tong University, 2024, 58(11): 1716-1723.
[15]	QIN Jing, WEN Yuanbo, GAO Tao, LIU Yao. A Transformer-Based Diffusion Model for All-in-One Weather-Degraded Image Restoration [J]. Journal of Shanghai Jiao Tong University, 2024, 58(10): 1606-1617.