Nothing Special   »   [go: up one dir, main page]

CN113500791B - 一种基于骨架线的填充路径生成方法 - Google Patents

一种基于骨架线的填充路径生成方法 Download PDF

Info

Publication number
CN113500791B
CN113500791B CN202110814710.8A CN202110814710A CN113500791B CN 113500791 B CN113500791 B CN 113500791B CN 202110814710 A CN202110814710 A CN 202110814710A CN 113500791 B CN113500791 B CN 113500791B
Authority
CN
China
Prior art keywords
line
skeleton
contour
offset
lines
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
CN202110814710.8A
Other languages
English (en)
Other versions
CN113500791A (zh
Inventor
朱俊杰
金育安
傅李达
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Henan University of Science and Technology
Original Assignee
Henan University of Science and Technology
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Henan University of Science and Technology filed Critical Henan University of Science and Technology
Priority to CN202110814710.8A priority Critical patent/CN113500791B/zh
Publication of CN113500791A publication Critical patent/CN113500791A/zh
Application granted granted Critical
Publication of CN113500791B publication Critical patent/CN113500791B/zh
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B29—WORKING OF PLASTICS; WORKING OF SUBSTANCES IN A PLASTIC STATE IN GENERAL
    • B29C—SHAPING OR JOINING OF PLASTICS; SHAPING OF MATERIAL IN A PLASTIC STATE, NOT OTHERWISE PROVIDED FOR; AFTER-TREATMENT OF THE SHAPED PRODUCTS, e.g. REPAIRING
    • B29C67/00—Shaping techniques not covered by groups B29C39/00 - B29C65/00, B29C70/00 or B29C73/00
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02T—CLIMATE CHANGE MITIGATION TECHNOLOGIES RELATED TO TRANSPORTATION
    • Y02T90/00—Enabling technologies or technologies with a potential or indirect contribution to GHG emissions mitigation

Landscapes

  • Engineering & Computer Science (AREA)
  • Mechanical Engineering (AREA)
  • Image Analysis (AREA)

Abstract

一种基于骨架线的填充路径生成方法，包括以下步骤：步骤1：根据设定的路径间距对输入的二维轮廓集合进行偏置，得到偏置轮廓；步骤2：将偏置轮廓集合生成连通区域集合；步骤3：获得每个连通区域的骨架线；步骤4：根据骨架线对单个连通区域进行分割，获得若干个子区域；步骤5：根据设定的路径间距在每个子区域内部生成子填充路径；步骤6：对子填充路径进行连接，得到整个连通区域的填充路径。本方法可以避免现有常用填充路径方法中存在较多空走路径的问题，为具有特殊工艺要求的路径规划提供解决方案。该方法适用于各种形状的区域，同时具有算法简单与通用性好的特点，对填充路径在多个领域的发展与普及具有一定的推动作用。

Description

一种基于骨架线的填充路径生成方法
技术领域
本发明属于填充路径技术领域，具体说的是一种基于骨架线的填充路径生成方法。
背景技术
填充路径规划方法是机床切割和增材制造等多个领域中的关键技术之一。在路径规划时不仅要考虑一些共性问题，比如提高加工效率和降低加工误差，还需要充分考虑制造工艺的特殊性，比如减少空走路径、减少有效路径的数量等。常用的两种路径规划方法是平行往复法与偏置轮廓偏置法，这两种算法已经得到了广泛的应用，但在面对不同的应用时会存在一些难以避免的问题。
在挤出型增材制造中，空走路径不仅会降低加工效率，还需要材料不断地被挤出与吸回，当成型材料的流动性较大时，这种频繁的开启与断开非常不利于提高打印质量。
发明内容
为解决上述技术问题，本发明提供一种基于骨架线的填充路径生成方法，每个闭合区域仅由一条填充路径实现区域覆盖。
为实现上述技术目的，所采用的技术方案是：一种基于骨架线的填充路径生成方法，包括以下步骤：
步骤1：根据设定的路径间距对输入的二维偏置轮廓集合进行偏置，得到偏置轮廓；
步骤2：将偏置轮廓集合生成连通区域集合；
步骤3：获得每个连通区域的骨架线；
步骤4：根据骨架线对单个连通区域进行分割，获得若干个子区域；
步骤5：根据设定的路径间距在每个子区域内部生成子填充路径；
步骤6：对子填充路径进行连接，得到整个连通区域的填充路径。
本发明所述步骤2中，将偏置轮廓集合生成连通区域集合的具体步骤如下：
步骤2-1：遍历所有偏置轮廓，确定每个偏置轮廓的父偏置轮廓数量；
步骤2-2：父偏置轮廓数量为偶数的为外偏置轮廓，父偏置轮廓数量为奇数的为内偏置轮廓，并对偏置轮廓的方向进行调整，外偏置轮廓为逆时针，内偏置轮廓为顺时针；
步骤2-3：父偏置轮廓数量不大于1的内偏置轮廓的外偏置轮廓为有效父偏置轮廓，对父偏置轮廓数量大于1的内偏置轮廓进行处理，具体方法为遍历其所有父偏置轮廓，将距离该内偏置轮廓最近的父偏置轮廓作为其有效父偏置轮廓，最终确保每个内偏置轮廓的有效父偏置轮廓的数量小于等于1；
步骤2-4：将每个有效父偏置轮廓与其包含的内偏置轮廓进行组合，构成一个连通区域。
本发明所述步骤4中，根据骨架线对单个连通区域进行分割的具体步骤如下：
步骤4-1：将骨架线按照是否有一端在偏置轮廓上分成两组，第一组为两端都不在偏置轮廓上的主骨架线，第二组为有一个端点在偏置轮廓上的端骨架线，主骨架线由多条主骨架分段线组成，端骨架线由多条端骨架分段线组成；
步骤4-2：划分主骨架分段线，确保每条主骨架分段线的首、尾连接有至少一条主骨架分段线和/或至少一条端骨架分段线；
步骤4-3：对所有端骨架分段线进行遍历，删除与偏置轮廓线连接的端点对应的两侧偏置轮廓线夹角大于150o的端骨架分段线；
步骤4-4：将首或尾只连接有一条端骨架分段线的主骨架分段线拷贝到端骨架线中，并从主骨架线中删除；
步骤4-5：将端骨架分段线按照其偏置轮廓上的端点在偏置轮廓中的索引从小到大依次排序，并将排序后的同区域内相邻的端骨架分段线进行组合，得到两两组合的集合D；
步骤4-6：将集合D的每组端骨架分段线组与相接的主骨架分段线和偏置轮廓进行连接构成一个闭合的多边形。
本发明所述步骤4-3中，删除端骨架分段线的具体步骤如下：
步骤4-3-1：对组成连通区域的偏置轮廓上的点进行遍历，计算每个点相邻两条偏置轮廓的夹角α；
步骤4-3-2：遍历所有端骨架分段线，删除端骨架分段线与偏置轮廓线连接点所在夹角α大于150o的端骨架分段线；
步骤4-3-3：判断是否存在首或尾悬空的主骨架分段线，如果存在则需要从删除的端骨架分段线中恢复与其首或尾连接的端骨架分估线，确保该悬空端点连接有且只有一条端骨架分段线；
步骤4-3-4：判断连通区域中的每条偏置轮廓上是否都至少有一条端骨架分段线，如果没有则需要从删除的端骨架分段线中恢复一条端点在其偏置轮廓上的端骨架分段线。
本发明所述步骤4-6中，将集合D中每组端骨架分段线组利用主骨架分段线和偏置轮廓进行连接构成一个闭合的多边形偏置轮廓的具体步骤如下：
步骤4-6-1：取出集合D中一组端骨架分段线组的任一条端骨架分段线作为当前骨架线T，将该条端骨架分段线不在偏置轮廓上的端点作为当前点P；
步骤4-6-2：判断该当前点P是否是集合D中另一条端骨架分段线的端点，若是，则将集合D中该组端骨架分段线以及两者相连的偏置轮廓相连，组成闭合的多边形偏置轮廓，若否，执行步骤4-6-3；
步骤4-6-3：遍历所有主骨架分段线，搜索端点为P的主骨架分段线集合；
步骤4-6-4：若搜索到的端点为P的主骨架分段线只有一条，将其连接到当前骨架线T上，更新点P为当前骨架线T的最后一个点，返回步骤4-6-2，继续寻找，若搜索到的端点为P的主骨架分段线集合大于一条，从集合中寻找在当前骨架线T的最右侧的主骨架分段线，将其连接到当前骨架线T上，更新点P为当前骨架线T的最后一个点，返回步骤4-6-2，继续寻找，直至当前骨架线T的最后一点为集合D中另一条端骨架分段线的端点，循环终止，将集合D中该组端骨架分段线、两者相连的偏置轮廓以及当前骨架线T相连，得到闭合多边形偏置轮廓；
步骤4-6-5：重复步骤4-6-1至步骤4-6-4，直至集合D中每组端骨架分段线组均形成闭合多边形偏置轮廓。
本发明所述步骤5中，根据设定的路径间距在每个子区域内部生成子填充路径的具体步骤如下：
步骤5-1：将每个子区域的多边形偏置轮廓分成两条多线段，第一条由主骨架分段线和端骨架分段线组成，第二条是偏置轮廓组成，两条多线段首尾相同；
步骤5-2：根据设定的路径间距依次在两条多线段上采样，对偏置轮廓上的采样点沿着连接线向内偏移设定间距的一半，然后对采样点进行Z字形连接，获得该子区域的填充路径。
本发明所述步骤6中，对子填充路径进行连接的具体步骤为：对具有相同端点的子区域的填充路径进行连接，确保每条偏置轮廓对应一条子区域的填充路径，并将连通区域中的路径在最近处进行连接，最终获得整个连通区域的填充路径。
本发明有益效果是：本发明通过对骨架线进行筛选与连接，将闭合区域划分成若干个子区域，然后将每个子区域的偏置轮廓多边形分成两条多线段，在两条多线段上根据设定的路径间隔进行采样，生成子区域的填充路径，最后对闭合区域中的子路径进行连接，获得整个连通区域的填充路径。该方法可以避免现有常用填充路径方法中存在较多空走路径的问题，为具有特殊工艺要求的路径规划提供解决方案。该方法适用于各种形状的区域，同时具有算法简单与通用性好的特点，对填充路径在多个领域的发展与普及具有一定的推动作用。
附图说明
图1为本发明基于骨架线的填充路径生成方法的流程图；
图2为内偏置轮廓的父偏置轮廓为1的偏置轮廓示意图；
图3为内偏置轮廓的父偏置轮廓大于1的偏置轮廓示意图；
图4为本发明生成主骨架线与端骨架线示意图；
图5为本发明端骨架分段线与偏置轮廓线连接的端点对应的夹角示意图；
图6为主骨架分段线首或尾连接且只有一条端骨架分段线时，处理方式示意图；
图7为内偏置轮廓的父偏置轮廓为1的偏置轮廓删除部分端骨架分段线后的骨架线示意图；
图8为骨架线T的最右侧主骨架分段线的查找示意图；
图9为一个闭合的多边形偏置轮廓的子区域偏置轮廓示意图；
图10为一个闭合的多边形偏置轮廓的子区域填充路径图；
图11为内偏置轮廓的父偏置轮廓为1的连接子区域路径后的填充路径示意图；
图12为采用本方明方法生成的复杂偏置轮廓填充路径示意图；
图13为采用本方明方法生成的另一复杂偏置轮廓填充路径示意图。
具体实施方式
为了使本技术领域的人员更好的理解本发明方案，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整的描述。
图1所示为本发明内部填充路径生成方法的流程图。以附图2中的二维偏置轮廓为例，来阐明内部填充路径生成方法，该图形的尺寸为84.5mm*137.5mm，以附图2、图3中的二维偏置轮廓为例，来阐明内部填充路径生成方法，该图形的尺寸为137.5mm*137.5mm。
一种基于骨架线的填充路径生成方法，包括以下步骤：
步骤1：根据设定的路径间距对输入的二维偏置轮廓集合进行偏置，得到偏置轮廓；本实施案例中，路径间距为1mm，首先对输入偏置轮廓进行0.5mm的向内偏置，得到偏置轮廓，如图2、图3中虚线所示，图2共得到两个偏置轮廓，记为偏置轮廓L1和偏置轮廓L2，图3共得到四个偏置轮廓，记为偏置轮廓N1、N2、N3、N4；该步骤1中对偏置轮廓集合的偏置可利用现有多边形偏置算法实现。
步骤2：利用偏置轮廓构建连通区域集合，具体实现方法为：
步骤2-1：遍历所有偏置轮廓，确定每个偏置轮廓的父偏置轮廓数量，其中图2中，偏置轮廓L1的父偏置轮廓数量为0，偏置轮廓L2的父偏置轮廓数量为1，图3中，偏置轮廓N1的父偏置轮廓为0，偏置轮廓N2的父偏置轮廓为1，偏置轮廓N3的父偏置轮廓为2，偏置轮廓N4的父偏置轮廓为3；
步骤2-2：父偏置轮廓数量为偶数的为外偏置轮廓，即偏置轮廓L1为外偏置轮廓，父偏置轮廓数量为奇数的为内偏置轮廓，即偏置轮廓L2为内偏置轮廓，对偏置轮廓的方向进行调整，偏置轮廓L1为逆时针，偏置轮廓L2为顺时针；
步骤2-3：如图2由于偏置轮廓L1和偏置轮廓L2的父偏置轮廓数量均不大于1，故不需要进行调整，父偏置轮廓数量不大于1的内偏置轮廓的外偏置轮廓为有效父偏置轮廓，即偏置轮廓L1为偏置轮廓L2的有效父偏置轮廓；将偏置轮廓L1和偏置轮廓L2进行组合，构成一个连通区域，如图2中阴影部分所示。
如图3所示，父偏置轮廓数量为偶数的为外偏置轮廓，即N1，N3为外偏置轮廓。父偏置轮廓数量为奇数的为内偏置轮廓，即N2，N4为内偏置轮廓，对偏置轮廓的方向进行调整，轨迹N1，N3为逆时针，轨迹N2，N4为顺时针。由于内偏置轮廓N4的父偏置轮廓大于1，需要进行调整，偏置轮廓N2的父偏置轮廓为1，不需要调整，偏置轮廓N1为偏置轮廓N2的有效父偏置轮廓，遍历N4的所有父偏置轮廓，将距离N4最近的父偏置轮廓（在图中为N3）作为N4的有效父偏置轮廓。将每个有效父偏置轮廓与其包含的内偏置轮廓进行组合，构成一个连通区域。在3中，出现内偏置轮廓的父偏置轮廓数量大于1的情况，在该示例中，共形成两个独立的连通区域，如图3中阴影部分所示。这两个连通区域分别进行填充路径生成。
步骤3：利用现有骨架提取方法获得每个连通区域的骨架线，如图4所示，当输入偏置轮廓点数量过多时，可以考虑对多边形采用简化算法进行处理，减少偏置轮廓点数量，降低计算骨架线的时间。
步骤4：根据骨架线对单个连通区域进行分割，获得若干个子区域，具体实现方法为：
步骤4-1：将骨架线按照是否有一端在偏置轮廓上分成两组，第一组为两端都不在偏置轮廓上的主骨架线，在图4中用点划线表示，第二组为有一个端点在偏置轮廓上的端骨架线，主骨架线由多条主骨架分段线组成，端骨架线由多条端骨架分段线组成，该部分端骨架线在图4中用实线表示；
步骤4-2：划分主骨架分段线，建立主骨架分段线的首、尾连接情况，每条主骨架分段线的首、尾连接有至少一条骨架线主骨架分段线和/或至少一条端骨架分段线，如图4所示，以某条主骨架分段线f 1为例，可知与其首相连的骨架线包括主骨架分段线f 2和端骨架分段线f 3，而与其尾相连的骨架线包括主骨架分段线f 6和端骨架分段线f 4和f 5。
步骤4-3：对所有端骨架分段线进行遍历，删除与偏置轮廓连接的端点对应的两侧偏置轮廓线夹角大于150o的端骨架分段线，具体实现方法为：
步骤4-3-1：对组成连通区域的偏置轮廓L1和偏置轮廓L2上的点进行遍历，计算每个点两侧偏置轮廓线的夹角α，α角度取值范围为[0o ，180o]，其中两条端骨架分段线的端点对应的夹角如图5中α1和α2所示。
步骤4-3-2：遍历所有端骨架分段线，当其与偏置轮廓连接的端点对应的夹角大于150o时，将该条端骨架分段线从端骨架线中暂时删除，并同时更新主骨架分段线的首尾连接情况；
步骤4-3-3：判断主骨架线中是否存在首或尾悬空的主骨架分段线，如果存在，说明是在步骤4-3-2中删除掉的，需要从删除的端骨架分段线中恢复一条与其首或尾连接的端骨架分段线，确保该主骨架分段线的悬空端点连接有且只有一条端骨架分段线；
步骤4-3-4：判断连通区域中的每条偏置轮廓L1和偏置轮廓L2是否都至少有一条端骨架分段线的端点在其偏置轮廓上，如果没有则需要从删除的端骨架分段线中恢复一条端点在其偏置轮廓上的端骨架分段线，在此案例中，都存在不止一条端骨架分段线与偏置轮廓相连。
步骤4-4：遍历所有主骨架分段线，当其首或尾连接只连接有一条端骨架分段线时，将其拷贝到端骨架线中，并从主骨架线中删除，将所有满足该条件的主骨架分段线从主骨架线中删除，并添加到端骨架线中。如图6左侧中α3和α4大于150o，删除两条端骨架分段线（图中实线），删除后如图6中间所示，主骨架分段线t3首段或尾端连接只有一条端骨架分段线，将主骨架分段线t3从主骨架线中删除，添加到端骨架线中，结果如图6右侧所示。
步骤4-5：将端骨架分段线按照其偏置轮廓上的端点在偏置轮廓中的索引从小到大依次排序，索引在图7已标出，将同一区域内相邻的两条端骨架分段线构成一个组合，具体为：[D 1,D 2],[D 2,D 3]，[D 3,D 4]，[D 4,D 1],[E 1,E 2]，[E 2,E 1]，所有的组合构成集合D。
步骤4-6：将集合D的每组端骨架分线段组利用主骨架分段线和偏置轮廓L1和偏置轮廓L2进行连接构成一个闭合的多边形偏置轮廓，具体实现方法为：
步骤4-6-1：取出集合D中一组端骨架分段线组的任一条端骨架分段线作为当前骨架线T，将该条端骨架分段线不在偏置轮廓上的端点作为当前点P，如图7中所示，取[D 1,D 2]为例，当前骨架线T为D 1 ，当前点P为p4，取[D 4,D 1]为例，当前骨架线T为D 4 ，当前点P为p1；
步骤4-6-2：判断该当前点P是否是集合D中另一条端骨架分段线的端点，若是，则将集合D中该组端骨架分段线以及两者相连的偏置轮廓相连，组成闭合的多边形偏置轮廓，若否，执行步骤4-6-3，[D 1,D 2]中p4是D 2 的端点，即D 1 、D 2 、d 1 d 2 组成闭合的多边形偏置轮廓，[D 4,D 1]中p1相连的为t0和t1，继续向下执行；
步骤4-6-3：遍历所有主骨架分段线，搜索端点为P的主骨架分段线集合，[D 4,D 1]中p1相连的主骨架分段线为t0和t1；
步骤4-6-4：若搜索到的端点为P的主骨架分段线只有一条，将其连接到当前骨架线T上，更新点P为当前骨架线T的最后一个点，返回步骤4-6-2，继续寻找，若搜索到的端点为P的主骨架分段线集合大于一条，从集合中寻找在当前骨架线T的最右侧的主骨架分段线，将其连接到当前骨架线T上，更新点P为当前骨架线T的最后一个点，返回步骤4-6-2，继续寻找，直至当前骨架线T的最后一点为集合D中另一条端骨架分段线的端点，循环终止，将集合D中该组端骨架分段线、两者相连的偏置轮廓以及当前骨架线T相连，得到闭合多边形偏置轮廓，[D 4,D 1]中查找到两条主骨架分段线，以图8所示，位于骨架线T最右侧的主骨架公段线为t1，将t1加入D 4 ,更新p3为P点，继续寻找，此时p3并非D 1 的端点，查找p3相连的主骨架分段线，位于最右侧的主骨架分段线为p3p4，再将p3p4加入骨架线T，更新p4为P点，此时，p4为D 1 的端点，循环结束，如图7中的d4、p1、p3、p4、d1、d4构成的闭合多边形（阴影部分）即为搜索[D 4,D 1]所得。
步骤4-6-5：重复步骤4-6-1至步骤4-6-4，直至集合D中每组端骨架分段线组均形成闭合多边形偏置轮廓。
步骤5：根据设定的路径间距在每个子区域内部生成子填充路径:
步骤5-1：将每个子区域的多边形偏置轮廓分成两条多线段，第一条由主骨架分段线和端骨架分段线组成，第二条是偏置轮廓组成，两条多线段首尾相同,如图9所示的两条线段；
步骤5-2：根据设定的路径间距依次在两条线段上采样，对偏置轮廓上的采样点沿着连接线向内偏移设定间距的一半，然后对两组采样点进行Z字形连接，获得该子区域的填充路径，如图10所示。
步骤6：对子填充路径进行连接，得到整个连通区域的填充路径。该步骤6的具体方法是：对具有相同端点的子区域的填充路径进行连接，确保每条偏置轮廓对应一条子区域的填充路径，并将连通区域中的路径在最近处进行连接，最终获得整个连通区域的填充路径。最终路径如图11所示。图12为利用本方法实现的复杂汉字图形偏置轮廓的填充路径；图13均为利用本方法实现的另一复杂汉字图形偏置轮廓的填充路径。
所述的实施方式，并不构成对该技术方案保护范围的限定。任何在上述实施方式的精神和原则之内所作的修改、等同替换和改进等，均应包含在该技术方案的保护范围之内。

Claims (2)

1.一种基于骨架线的填充路径生成方法，其特征在于：包括以下步骤：
步骤1：根据设定的路径间距对输入的二维轮廓集合进行偏置，得到偏置轮廓；
步骤2：将偏置轮廓集合生成连通区域集合；
步骤3：获得每个连通区域的骨架线；
步骤4：根据骨架线对单个连通区域进行分割，获得若干个子区域；
步骤5：根据设定的路径间距在每个子区域内部生成子填充路径；
步骤6：对子填充路径进行连接，得到整个连通区域的填充路径;
所述步骤2中，将偏置轮廓集合生成连通区域集合的具体步骤如下：
步骤2-1：遍历所有偏置轮廓，确定每个偏置轮廓的父轮廓数量；
步骤2-2：父轮廓数量为偶数的为外轮廓，父轮廓数量为奇数的为内轮廓，并对偏置轮廓的方向进行调整，外轮廓为逆时针，内轮廓为顺时针；
步骤2-3：父轮廓数量不大于1的内轮廓的外轮廓为有效父轮廓，对父轮廓数量大于1的内轮廓进行处理，具体方法为遍历其所有父轮廓，将距离该内轮廓最近的父轮廓作为其有效父轮廓，最终确保每个内轮廓的有效父轮廓的数量小于等于1；
步骤2-4：将每个有效父轮廓与其包含的内轮廓进行组合，构成一个连通区域;
所述步骤4中，根据骨架线对单个连通区域进行分割的具体步骤如下：
步骤4-1：将骨架线按照是否有一端在偏置轮廓上分成两组，第一组为两端都不在偏置轮廓上的主骨架线，第二组为有一个端点在偏置轮廓上的端骨架线，主骨架线由多条主骨架分段线组成，端骨架线由多条端骨架分段线组成；
步骤4-2：划分主骨架分段线，确保每条主骨架分段线的首、尾连接有至少一条主骨架分段线和/或至少一条端骨架分段线；
步骤4-3：对所有端骨架分段线进行遍历，删除与偏置轮廓线连接的端点对应的两侧偏置轮廓线夹角大于150o的端骨架分段线；
步骤4-4：将首或尾只连接有一条端骨架分段线的主骨架分段线拷贝到端骨架线中，并从主骨架线中删除；
步骤4-5：将端骨架分段线按照其偏置轮廓上的端点在偏置轮廓中的索引从小到大依次排序，并将排序后的同区域内相邻的端骨架分段线进行组合，得到两两组合的集合D；
步骤4-6：将集合D的每组端骨架分段线组与相接的主骨架分段线和偏置轮廓进行连接构成一个闭合的多边形;
所述步骤4-3中，删除端骨架分段线的具体步骤如下：
步骤4-3-1：对组成连通区域的偏置轮廓上的点进行遍历，计算每个点相邻两条偏置轮廓的夹角α；
步骤4-3-2：遍历所有端骨架分段线，删除端骨架分段线与偏置轮廓线连接点所在夹角α大于150o的端骨架分段线；
步骤4-3-3：判断是否存在首或尾悬空的主骨架分段线，如果存在则需要从删除的端骨架分段线中恢复与其首或尾连接的端骨架分估线，确保该悬空端点连接有且只有一条端骨架分段线；
步骤4-3-4：判断连通区域中的每条偏置轮廓上是否都至少有一条端骨架分段线，如果没有则需要从删除的端骨架分段线中恢复一条端点在其偏置轮廓上的端骨架分段线;
所述步骤4-6中，将集合D中每组端骨架分段线组利用主骨架分段线和偏置轮廓进行连接构成一个闭合的多边形轮廓的具体步骤如下：
步骤4-6-1：取出集合D中一组端骨架分段线组的任一条端骨架分段线作为当前骨架线T，将该条端骨架分段线不在偏置轮廓上的端点作为当前点P；
步骤4-6-2：判断该当前点P是否是集合D中另一条端骨架分段线的端点，若是，则将集合D中该组端骨架分段线以及两者相连的偏置轮廓相连，组成闭合的多边形轮廓，若否，执行步骤4-6-3；
步骤4-6-3：遍历所有主骨架分段线，搜索端点为P的主骨架分段线集合；
步骤4-6-4：若搜索到的端点为P的主骨架分段线只有一条，将其连接到当前骨架线T上，更新点P为当前骨架线T的最后一个点，返回步骤4-6-2，继续寻找，若搜索到的端点为P的主骨架分段线集合大于一条，从集合中寻找在当前骨架线T的最右侧的主骨架分段线，将其连接到当前骨架线T上，更新点P为当前骨架线T的最后一个点，返回步骤4-6-2，继续寻找，直至当前骨架线T的最后一点为集合D中另一条端骨架分段线的端点，循环终止，将集合D中该组端骨架分段线、两者相连的偏置轮廓以及当前骨架线T相连，得到闭合多边形轮廓；
步骤4-6-5：重复步骤4-6-1至步骤4-6-4，直至集合D中每组端骨架分段线组均形成闭合多边形轮廓;
所述步骤5中，根据设定的路径间距在每个子区域内部生成子填充路径的具体步骤如下：
步骤5-1：将每个子区域的多边形轮廓分成两条多线段，第一条由主骨架分段线和端骨架分段线组成，第二条是偏置轮廓组成，两条多线段首尾相同；
步骤5-2：根据设定的路径间距依次在两条多线段上采样，对偏置轮廓上的采样点沿着连接线向内偏移设定间距的一半，然后对采样点进行Z字形连接，获得该子区域的填充路径。
2.如权利要求1所述的一种基于骨架线的填充路径生成方法，其特征在于，所述步骤6中，对子填充路径进行连接的具体步骤为：对具有相同端点的子区域的填充路径进行连接，确保每条偏置轮廓对应一条子区域的填充路径，并将连通区域中的路径在最近处进行连接，最终获得整个连通区域的填充路径。
CN202110814710.8A 2021-07-19 2021-07-19 一种基于骨架线的填充路径生成方法 Expired - Fee Related CN113500791B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202110814710.8A CN113500791B (zh) 2021-07-19 2021-07-19 一种基于骨架线的填充路径生成方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202110814710.8A CN113500791B (zh) 2021-07-19 2021-07-19 一种基于骨架线的填充路径生成方法

Publications (2)

Publication Number Publication Date
CN113500791A CN113500791A (zh) 2021-10-15
CN113500791B true CN113500791B (zh) 2023-01-24

Family

ID=78013223

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202110814710.8A Expired - Fee Related CN113500791B (zh) 2021-07-19 2021-07-19 一种基于骨架线的填充路径生成方法

Country Status (1)

Country Link
CN (1) CN113500791B (zh)

Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN104325638A (zh) * 2014-05-14 2015-02-04 浙江大学 基于分区的3d打印填充路径生成方法
US20150151494A1 (en) * 2007-10-10 2015-06-04 Materialise Nv Method and apparatus for automatic support generation for an object made by means of a rapid prototype production method
CN106825570A (zh) * 2017-03-29 2017-06-13 湖南华曙高科技有限责任公司 用于三维物体制造的切片扫描处理方法及系统
CN107818195A (zh) * 2017-08-24 2018-03-20 宁波大学 一种基于关联树的3d打印填充路径生成方法
CN108460174A (zh) * 2017-11-30 2018-08-28 武汉理工大学 一种电弧熔丝增材制造技术中的混合填充路径产生方法
CN108859128A (zh) * 2018-06-14 2018-11-23 武汉理工大学 复杂多空洞区域的路径规划填充方法
CN109732928A (zh) * 2019-01-25 2019-05-10 华中科技大学 一种实时可变宽度的3d打印路径构造方法

Patent Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20150151494A1 (en) * 2007-10-10 2015-06-04 Materialise Nv Method and apparatus for automatic support generation for an object made by means of a rapid prototype production method
CN104325638A (zh) * 2014-05-14 2015-02-04 浙江大学 基于分区的3d打印填充路径生成方法
CN106825570A (zh) * 2017-03-29 2017-06-13 湖南华曙高科技有限责任公司 用于三维物体制造的切片扫描处理方法及系统
CN107818195A (zh) * 2017-08-24 2018-03-20 宁波大学 一种基于关联树的3d打印填充路径生成方法
CN108460174A (zh) * 2017-11-30 2018-08-28 武汉理工大学 一种电弧熔丝增材制造技术中的混合填充路径产生方法
CN108859128A (zh) * 2018-06-14 2018-11-23 武汉理工大学 复杂多空洞区域的路径规划填充方法
CN109732928A (zh) * 2019-01-25 2019-05-10 华中科技大学 一种实时可变宽度的3d打印路径构造方法

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
《快速成型中基于直骨架原理的轮廓偏置算法》;罗恒;《计算机辅助设计与图形学学报》;20111130;1908-1914 *

Also Published As

Publication number Publication date
CN113500791A (zh) 2021-10-15

Similar Documents

Publication Publication Date Title
CN111323037B (zh) 一种移动机器人新型骨架提取的Voronoi路径规划算法
CN109886877A (zh) 一种航点拟合和分段航线拼接的方法
WO2021062736A1 (zh) 划分方法、编码器、解码器以及计算机存储介质
CN113500791B (zh) 一种基于骨架线的填充路径生成方法
Ferreira et al. Amortized-delay algorithm for listing chordless cycles in undirected graphs
CN111125470A (zh) 一种提升异常数据挖掘筛选的方法
WO2022222367A1 (zh) 基于压入与重标记可提前终止的最大流最小割求解算法
WO2023040057A1 (zh) 一种获取指定顶点拓扑序列的方法和设备
CN110097495A (zh) 一种改进的Zhang并行图像细化算法
CN112509025B (zh) 一种基于三维欧氏距离的岩石空间结构距离图的计算方法
Hossain et al. Monotone grid drawings of planar graphs
Cole et al. A fast algorithm for computing steiner edge connectivity
JP6259058B2 (ja) データ分析装置及び方法及びプログラム
CN114399428A (zh) 面状人工要素降维处理方法
Gudmundsson et al. Cubic upper and lower bounds for subtrajectory clustering under the continuous Fréchet distance∗
CN112348935B (zh) 线框渲染方法、终端设备及计算机可读存储介质
CN108537858B (zh) 一种基于绘画时序的笔划线条动态合并方法
Georgiadis et al. Incremental $2 $-Edge-Connectivity in Directed Graphs
CN110555444B (zh) 一种基于局部聚类的特征匹配筛选算法
Bandyopadhyay et al. Axioms to characterize efficient incremental clustering
Cinel et al. A distributed heuristic algorithm for the rectilinear steiner minimal tree problem
CN113032888B (zh) 一种基于二分法和分层最低点的断面插值加密方法
CN108109150B (zh) 图像分割方法、终端
Duncan et al. Planarity-preserving clustering and embedding for large planar graphs
Karim et al. On a class of planar graphs with straight-line grid drawings on linear area

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
CF01 Termination of patent right due to non-payment of annual fee
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20230124