基于骨架线匹配的二维不规则轮廓排样方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN111428776A(43)申请公布日2020.07.17(21)申请号202010198270.3(22)申请日2020.03.19(71)申请人燕山大学地址066004河北省秦皇岛市海港区河北大街西段438号(72)发明人郭保苏李锦瑞周圣洁(74)专利代理机构大连东方专利代理有限责任公司21212代理人赵淑梅李洪福(51)Int.Cl.G06K9/62(2006.01)G06T7/73(2017.01)权利要求书2页说明书6页附图3页(54)发明名称基于骨架线匹配的二维不规则轮廓排样方法(57)摘要基于骨架线匹配的二维不规则轮廓排样方法，该方法首先将母板和待排样件的轮廓进行多边形逼近，然后提取样件的所有骨架线；将得到的所有骨架线通过计算Hu矩匹配进行相似性检查，将形状近似的骨架线进行合并，得到轮廓简化后的骨架线；然后通过计算简化骨架线与母板轮廓之间的Hu矩，按照母板与样件的匹配程度降序并使排入样件的高度最低的原则下，确定样件的排样顺序，最终完成任意二维轮廓的排样。本发明算法实现简单，不需要多次对样件进行旋转与迭代计算，只需要一次匹配就能得到理想的排样结果，而且排样填充率高，耗费时间少，具有非常理想的技术效果。CN111428776ACN111428776A权利要求书1/2页1.基于骨架线匹配的二维不规则轮廓排样方法，其特征在于：所述方法具体包括以下步骤：步骤S1：对母板进行多边形逼近，并以环序列的形式保存；步骤S2：若母板存在空腔，则将空腔进行多边形逼近后，将生成的序列以环序列的形式保存；步骤S3：读取待排样件的轮廓，生成样件多边形序列，并以环序列的形式保存；步骤S4：若样件存在空腔，则对空腔进行多边形逼近，并以环序列的形式进行单独记录；步骤S5：通过计算得到样件中距离最远的两点作为样件的初始端点，并将两点的连线方向作为样件的主延伸方向；步骤S6：去除空腔部分的干扰，将空腔当作边缘对待，且边界外不存在剖分线，对样件进行三角剖分并将剖分三角形的中心Hi以序列的形式存储；步骤S7：根据主延伸方向和三角剖分确定主骨架线，并将经过的剖分三角形记为Hi′，并将样件的初始端点由原来的边缘位置更新为与之距离最近的剖分三角形的中心；步骤S8：对初始端点的附近采取深度优先搜索，遍历起终点附近的剖分三角形，若存在未遍历的剖分三角形，则更新Hi′序列，直到搜索结束；步骤S9：根据分支节点的对次骨架线进行提取，得到次骨架线的序列hi′，并将Hi-Hi′与hi′进行对比，若次骨架线序列hi′中的元素在Hi-Hi′中，则删除hi′中与之重复的元素，更新hi′，并按照三角剖分结果连接到主骨架线上；步骤S10：合并主骨架线与次骨架线；步骤S11：将骨架线序列中能够简化的部分进行简化，包括主骨架线与次骨架线之间的简化和次骨架线之间的简化；步骤S12：计算骨架线和母板的Hu矩；步骤S13：通过对Hu矩进行相似度匹配，确定样件排入母板的大致位置；步骤S14：采用距离检测法，确定样件排入母板的角度和精确位置，更新当前排入样件后母板的轮廓；步骤S15：判断样件是否都已经排入，如果都已排入则结束，如果没有完成，则返回待排样件序列进行排样；步骤S16：结束本次排样。2.根据权利要求1所述的基于骨架线匹配的二维不规则轮廓排样方法，其特征在于：所述步骤S1中，多边形逼近的具体过程如下：(1)确定曲线部分的起点与终点，若曲线起点与终点不同时，找到轮廓上距离起终点连线最远的点，将该点作为一个插值点，并生成新的轮廓；(2)继续寻找在插值点与起点与终点之间连线的最远点，并以此更新轮廓；(3)设定迭代精度为0.01，重复步骤(2)，直到到达精度上限停止迭代，得到多边形逼近后的轮廓。3.根据权利要求1所述的基于骨架线匹配的二维不规则轮廓排样方法，其特征在于：所述步骤S6的具体过程如下：(1)构造一个三角形，将样件所有点的序列完全包络在三角形中，放入三角形链表中；2CN111428776A权利要求书2/2页(2)将序列中的点按队列顺序依次插入，在三角形链表中找到外接圆包含当前插入点的三角形，称该三角形为影响三角形，删除两个外接圆中三角形的公共边；(3)将插入点与影响三角形各顶点相连，完成一个点的插入；(4)循环执行(2)-(3)，直到所有点插入完成。4.根据权利要求1所述的基于骨架线匹配的二维不规则轮廓排样方法，其特征在于：所述步骤S7中，由主延伸方向和三角剖分确定主骨架线的求解步骤为：(1)先通过归并排序得到样件轮廓上距离最远的两点作为主骨架线起点和终点；(2)记录三角剖分的结果，从起点开始，采用广度优先搜索的方式搜索起终点附近的剖分三角形，并将骨架线经过的剖分三角形的中心Hi′与所述步骤6得到的剖分三角形