基于轨迹线改进的临界多边形算法  

Improved Algorithm for No-Fit Polygon Based on Trace Line

作　　者：韩志仁[1,2] 韩子默 贾震 HAN Zhiren;HAN Zimo;JIA Zhen(Shenyang Aerospace University,Shenyang 110136,China;Key Laboratory of Fundamental Science for National Defence of Aeronautical Digital Manufacturing Process,Shenyang 110136,China)

机构地区：[1]沈阳航空航天大学,沈阳110136 [2]航空制造工艺数字化国防重点学科实验室,沈阳110136

出　　处：《航空制造技术》2024年第9期83-88,共6页Aeronautical Manufacturing Technology

基　　金：国家自然科学基金(52001217);辽宁省自然科学基金(2019ZD0240)。

摘　　要：在异形件的下料排样问题中,最为困难的就是求解裁片在板料中的位置以保证材料较高的利用率,算法复杂度随着料片数量和料片轮廓复杂度的增加迅速上升。临界多边形算法是计算异形件之间靠接位置和重叠关系的一种基础性几何工具,临界多边形算法的性能与下料排样算法效率密切相关。本文在基于轨迹线的求解临界多边形算法基础上,提出一种求解临界多边形(NFP)的改进算法。该算法有效地将移动碰撞算法和轨迹线算法相结合,充分发挥两类算法各自的优点,提高了临界多边形求解的计算速度。仿真实例验证了改进方法的正确性和有效性。In the blanking layout problem of special-shaped parts,the most difficult thing is to determine the position of special-shaped parts for high material utilization rate,and the complexity of the algorithm increases rapidly with the increase of the quantity and boundary complexity of special-shaped parts.The critical polygon algorithm is a basic geometric tool for calculating the position and overlap between special-shaped parts,and the performance of the critical polygon algorithm is closely related to the efficiency of the blanking algorithm.In this paper,an improved and more efficient algorithm to calculate no-fit polygon(NFP)is proposed and it is based on the trace line presented.The algorithm effectively combines the mobile collision algorithm and the trajectory algorithm,and gives full play to the respective advantages of the two algorithms,thus improving the speed of calculating no-fit polygon.

关 键 词：临界多边形 轨迹线 排样 移动碰撞法 不规则形状 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]