Journal of Shanghai Jiao Tong University ›› 2021, Vol. 55 ›› Issue (5): 536-543.doi: 10.16183/j.cnki.jsjtu.2020.208

Special Issue: 《上海交通大学学报》2021年12期专题汇总专辑 《上海交通大学学报》2021年“自动化技术、计算机技术”专题

Previous Articles     Next Articles

Promotion of a No Fit Polygon Algorithm Based on Trajectory

ZHOU Xin1, LAI Xiaoyang1, MENG Xiangqun2, WANG Kun2, TANG Houjun1()   

  1. 1. Department of Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
    2. Shanghai Fangling Software Co., Ltd., Shanghai 200241, China
  • Received:2020-07-06 Online:2021-05-28 Published:2021-06-01
  • Contact: TANG Houjun


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: