一种基于哈希表的散乱线段快速拼接方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN110356008A(43)申请公布日2019.10.22(21)申请号201910592869.2(22)申请日2019.07.03(71)申请人浙江大学地址310027浙江省杭州市西湖区浙大路38号(72)发明人林志伟冯嘉炜傅建中沈洪垚(74)专利代理机构杭州之江专利事务所(普通合伙)33216代理人牛世静(51)Int.Cl.B29C64/386(2017.01)B33Y50/00(2015.01)权利要求书1页说明书6页附图4页(54)发明名称一种基于哈希表的散乱线段快速拼接方法(57)摘要本发明公开了一种基于哈希表的散乱线段快速拼接方法，包括：(1)输入散乱线段序列；(2)构建链接点对，并将其分别保存到哈希表map中；(3)新建当前轮廓，并从map中找出一个未被使用的链接点作为当前轮廓起点p；(4)将p加入当前轮廓，并根据点p查询当前轮廓下一点d，令p＝d；(5)重复步骤(4)直至当前轮廓闭合，将该轮廓添加至轮廓序列；(6)重复步骤(3)～(5)，直至map中所有链接点均被使用；(7)输出已拼接的轮廓序列。本发明通过构建线段顶点和哈希表两个特殊数据结构，完整存储线段顶点之间的拓扑关系，通过哈希表查询实现散乱线段的快速拼接，该方法稳定可靠，鲁棒性强。CN110356008ACN110356008A权利要求书1/1页1.一种基于哈希表的散乱线段快速拼接方法，其特征在于，包括如下步骤：(1)输入散乱线段序列{Li}，其中i∈[1,n]，n为线段总数；(2)对{Li}中每条线段的顶点对，构建链接点对，并将其分别保存到哈希表map中；(3)新建当前轮廓，从哈希表map中找出一个未被使用的链接点作为当前轮廓起点，记为p；(4)将p加入当前轮廓，并根据点p以及哈希表map得到当前轮廓下一点d，令p＝d；(5)重复步骤4直至当前轮廓闭合，将该轮廓添加至轮廓序列{Ci}；(6)重复步骤(3)至步骤(5)，直至哈希表map中所有链接点均被使用；(7)输出已拼接的轮廓序列{Ci}。2.根据权利要求1所述的基于哈希表的散乱线段快速拼接方法，其特征在于，步骤(2)中，所述链接点数据包括如下信息：(I)对应顶点的坐标信息；(II)标识该顶点是否已经被使用的信息；(III)对应线段中该顶点所指向的另一端点信息。3.根据权利要求2所述的基于哈希表的散乱线段快速拼接方法，其特征在于，步骤(2)中，所述哈希表map由键值对组成，其中键为对应的顶点坐标信息，值为具有相同坐标的链接点对。4.根据权利要求3所述的基于哈希表的散乱线段快速拼接方法，其特征在于，步骤(2)中，对{Li}中每条线段的顶点对，构建链接点对，并将其分别保存到哈希表map中的步骤如下：步骤2.1：取{Li}中任一线段L两顶点，记为A和B；步骤2.2：建立两个链接点对象LA和LB；步骤2.3：将构建的链接点LA和链接点LB分别保存到哈希表map中。5.根据权利要求1所述的基于哈希表的散乱线段快速拼接方法，其特征在于，步骤(3)中，寻找未被使用的链接点的方法是：遍历哈希表map，寻找首个未被使用的链接点。6.根据权利要求4所述的基于哈希表的散乱线段快速拼接方法，其特征在于，步骤(4)中，根据当前点p在哈希表map中查询当前轮廓下一点的步骤如下：步骤4.1：从点p定位所在线段另一端点q；步骤4.2：对p、q标注为已被使用；步骤4.3：以q坐标信息对应的键在哈希表map中查询对应的值列表；步骤4.4：在值列表中寻找一个不同于q的点，记为d。7.根据权利要求1所述的基于哈希表的散乱线段快速拼接方法，其特征在于，所述散乱线段序列{Li}由使用一张平面截交STL模型中的三角面片得到。2CN110356008A说明书1/6页一种基于哈希表的散乱线段快速拼接方法技术领域[0001]本发明涉及计算机辅助制造CAM(Computeraidedmanufacturing)技术领域，尤其是涉及一种三维打印切片散乱线段的快速拼接方法。背景技术[0002]随着计算机技术、材料成型技术的飞速发展，三维打印技术成为了当前制造领域广泛应用的一种先进制造技术。利用分层制造的原理，三维打印技术逐层堆积材料以得到设计工件形状，特别适合制造具有复杂形状与拓扑的三维零件。三维打印技术主要包含了在计算机上实施的制造工艺规划和在设备上实际制造实体零件成型两个关键技术环节，其中制造工艺规划主要包含三个步骤：首先针对设计输入的三维几何模型，用户需要在计算机实现三维模型的分层切片；其次根据分层切片结果，用户需要生成精确可靠的切片轮廓；最后在切片的轮廓内规划三维打印路径，进而控制设备实施打印成型。[0003]当前三维打印技术领域普遍采用STL模型作为模型数据格式，ST