周鑫¹, 赖晓阳¹, 孟祥群², 王堃², 唐厚君¹()

1.上海交通大学 电气工程系,上海 200240
2.上海方菱计算机软件有限公司,上海 200241

收稿日期:2020-07-06出版日期:2021-05-28发布日期:2021-06-01
通讯作者:唐厚君E-mail:hjtang@sjtu.edu.cn
作者简介:周 鑫(1995-),男,湖北省宜昌市人,硕士生,研究方向为机器视觉和自动化系统控制.

Promotion of a No Fit Polygon Algorithm Based on Trajectory

ZHOU Xin¹, LAI Xiaoyang¹, MENG Xiangqun², WANG Kun², TANG Houjun¹()

1. Department of Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
2. Shanghai Fangling Software Co., Ltd., Shanghai 200241, China

Received:2020-07-06Online:2021-05-28Published:2021-06-01
Contact:TANG Houjun E-mail:hjtang@sjtu.edu.cn

摘要/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


PDF全文下载地址:

点我下载PDF