本发明公开了一种基于分区的3D打印填充路径生成方法，包括：确定需加工实体的SLC文件和填充路径间距；生成轮廓偏置路径并保存最内层轮廓偏置路径；确定扫描线倾角；根据扫描线与最内层偏置轮廓的偏置多边形的交点数目将加工区域进行第一次分区；进一步将第一次分区的结果根据交点数目进行第二次分区，获得子区域集；根据扫描线与最内层偏置轮廓的偏置多边形的交点以及子区域之间关系生成子区域路径；对子区域路径进行调整；利用样条曲线对剩下的子路径进行衔接，获得最终的内部填充路径。本发明基于分区的3D打印填充路径生成方法，鲁棒性强，适应于各种形状的模型，同时易实现，通用性好，更容易嵌入到3D打印设备中，实现商业化。
1.一种基于分区的3D打印填充路径生成方法，其特征在于，包括如下步骤：步骤1：根据层高得到需加工实体的SLC文件；
步骤2：根据相应的3D打印设备以及打印材料确定填充路径间距；
步骤3：根据填充路径间距生成轮廓偏置路径并保存最内层轮廓的偏置路径，记作偏置多边形Ω；
步骤5：根据偏置多边形Ω的几何特征对SLC文件中每层的加工区域进行第一次分区；
步骤6：将第一次分区的结果根据交点数目进行第二次分区，得到若干子区域，对得到的子区域按照扫描方向进行排序，得到子区域集；
步骤7：根据扫描线与偏置多边形Ω的交点以及子区域之间关系生成子区域集对应的子区域路径集；
步骤8：对生成的子区域路径集中的每个子区域路径进行特征识别，确定可调整的子区域路径，并对存在可以连接的潜在起点的子区域路径的起点进行调整和连接，得到调整后的子区域路径集；
步骤9：采用贪心算法利用样条曲线对调整后的子区域路径集中的子区域路径进行衔接，获得最终的内部填充路径；
步骤5中，第一次分区的具体过程为：根据步骤3中的偏置多边形Ω的几何特征获得偏置多边形Ω中存在的与扫描线方向平行的轮廓段和轮廓极值点，对距离所述轮廓段和轮廓极值点最近的扫描线进行标识，利用标识的扫描线对加工区域进行第一次分区；
步骤6.1：对某一个区域，首先判断该区域内扫描线与偏置多边形Ω的交点数量，去掉与偏置多边形Ω相切或者与偏置多边形Ω轮廓段重合的交点；
步骤6.2：对该区域中其余交点进行如下处理，按照扫描方向，对某一个区域与偏置多边形Ω的交点进行排序，分别为第1、2、…、n组交点，n为该区域内某一扫描线与偏置多边形Ω交点数，n大于1且为整数，其中，第1组交点是该区域按照扫描方向与偏置多边形Ω首次相交的一组点，其余类推；按照交点顺序对该区域进行分区，得到子区域集{(1，2)，(3，
4)，…，(n-1，n)}，其中第一个子区域(1，2)为第1组交点与第2组交点之间的区域，其余类推；
步骤6.3：对所有区域均进行步骤6.1和步骤6.2的分区，最后得到若干子区域。
2.根据权利要求1所述的基于分区的3D打印填充路径生成方法，其特征在于，步骤3中，生成轮廓偏置路径时，偏置圈数为2-4圈。
3.根据权利要求1所述的基于分区的3D打印填充路径生成方法，其特征在于，步骤4中，扫描线倾角确定时，采用平行填充路径总长度最短的原则进行确定。
4.根据权利要求1所述的基于分区的3D打印填充路径生成方法，其特征在于，步骤7中，得到子区域路径集的具体方法为：步骤7.1：选取当前子区域集中最靠前的子区域，并将该子区域中的第一条扫描线的一个端点作为起点；
步骤7.2：利用扫描线与偏置多边形Ω的交点生成平行往复的填充路径，形成当前子区域对应的子区域路径；该步骤中，子区域路径是由若干相互平行的直线段以及将这些直线段依次连接的衔接段组成；
步骤7.3：将当前子区域从子区域集中删除，同时获得当前子区域路径的终点；
步骤7.4：判断当前区域集中是否为空：若判断结果为是，则将当前得到的子区域路径添加到最终的子区域路径集中，结束步骤7；若判断结果为否，则进入步骤7.5；
步骤7.5：在当前子区域集中搜索是否存在与当前子区域路径可连接的潜在起点：首先定义如下两个点：第一个点为当前子区域路径的终点；第二个点为某一子区域的可能起点；
如果同时满足上述(1)-(3)，则认为存在可连接的点；进入步骤7.6；否则，则将当前生成的子区域路径添加到最终子区域路径集中，返回步骤7.1；
步骤7.6：将当前子区域路径的终点与可连接点进行连接；
步骤7.7：利用扫描线与偏置多边形的交点生成平行往复的填充路径，返回步骤7.3中；
如此反复，直至当前子区域集为空，完成所有子区域路径的生成，得到完整的子区域路径集。
5.根据权利要求1所述的基于分区的3D打印填充路径生成方法，其特征在于，步骤8中，包括：步骤8.1：对当前子区域路径集中不能调整的子区域路径和能够调整的子区域路径分别进行标识；
步骤8.2：将标识后的子区域路径集中不能调整的子区域路径添加到最终输出的调整后子区域路径集中；
步骤8.3：将标识后的子区域路径集中可以调整的子区域路径进行调整，输出最终调整后的子区域路径集。
6.根据权利要求5所述的基于分区的3D打印填充路径生成方法，其特征在于，步骤8.3具体过程为：步骤8.3.1：首先判断当前标识后的子区域路径集中元素是否为空：如果判断结果为是，则输出最终调整后的子区域路径集；如果判断结果为否，则进入步骤8.3.2；
步骤8.3.2：判断当前标识后的子区域路径集中某一子区域路径是否可以调整：如果判断结果为是，则进入步骤8.3.3；如果判断结果为否，则返回步骤8.3.1；
步骤8.3.3：对该子区域路径，在当前标识后的子区域路径集中寻找其相邻的潜在连接点：如果存在这样的潜在连接点，则进入步骤8.3.4；如果不存在这样的潜在连接点，则将当前子区域路径从标识后的子区域路径集中删除，同时将当前子区域路径添加到最终调整后的子区域路径集中，返回步骤8.3.1；
步骤8.3.4：对当前子区域路径的端点进行调整，并添加到所述潜在连接点所在的子区域路径中，同时将添加后的子区域路径删除，并将当前得到的子区域路径添加到最终调整后的子区域路径集中，返回步骤8.3.1。
7.根据权利要求6所述的基于分区的3D打印填充路径生成方法，其特征在于，步骤9的具体步骤为：步骤9.1：将步骤8输出的调整后的子区域路径集中具有最大y坐标值的子区域路径添加到最终输出的路径集中，并将该子区域路径的起点作为最终输出的路径起点；
步骤9.2：将当前子区域路径在调整后的子区域路径集中删除；
步骤9.4：在调整后的子区域路径集中寻找距离当前终点最短的子区域路径的端点；
步骤9.5：将距离最短的端点所在的子区域路径添加到最终输出的路径集中，并将其从调整后的子区域路径集中删除；
步骤9.6：判断调整后的子区域路径集中是否为空，如果判断结果为是，则结束程序，输出最终的路径集；如果判断结果为否，则返回步骤9.3。
基于分区的3D打印填充路径生成方法
技术领域
[0001] 本发明涉及3D打印技术路径生成方法领域，尤其涉及基于分区的3D打印填充路径生成方法。
背景技术
[0002] 3D打印作为快速成形技术的一种，以实体数字模型文件为基础，采用成型材料，通过逐层打印的方式来构造三维实体。由于3D打印技术无需机械加工和任何模具，可在一定程度上缩短产品的研发周期和降低生产成本，目前已在建筑、航空航天、机械、生物医学等领域得到较为广泛的应用。对于3D打印技术，为保证精度，分层厚度很小，分层的层片数量很大，而每个层片的填充都需要耗费一定的喷涂填充时间，所以在轮廓内部的填充路径生成是降低零件成型时间，提高生产效率的关键技术之一。所有的内部填充路径包含两个部分：打印路径与空走路径。其中打印路径是喷头填充成型材料的路径，而空走路径是连接各打印路径且需要关闭喷头的路径。空走路径不仅会增加填充时间，降低成型效率，还会导致喷头的频繁通断。因此生成的填充路径应尽量减少空走路径的数量和总长度。
[0003] 目前常用的3D打印内部填充路径主要包括两种。一种是平行往复直线路径，这种路径是用具有一定间距的直线轨迹来填充零件截面的实体部分，然后提取这些直线与轮廓交点数据信息并生成相应的路径轨迹，因此这种路径的主体部分是等距平行的线段。这种路径生成方法由于对数据的处理简单可靠，生成路径速度快，而且路径由直线段组成，打印填充速度快。但是由于存在大量的连接拐角，填充精度较低；另外一种是轮廓平行路径，这种路径是利用零件截面的轮廓进行一定间距的偏置得到的路径轨迹，这种路径填充精度高，并且能够较好地避免成型过程中的成型材料应力集中的问题。但是其也存在以下问题：对于型腔较多的复杂零件，这种路径生成算法就要处理轮廓偏置后出现的自相交、互相交等问题，涉及多边形布尔运算问题，使算法相对复杂，路径生成速度较慢，并且生成的路径轨迹中存在大量的曲线，填充速度较低，影响填充速度。目前已有的路径生成方法基本是将以上两种路径相结合，对于截面轮廓边缘采用轮廓平行路径，以保证填充精度，而对于内部填充，采用平行往复直线路径，提高填充效率。
[0004] 但是目前没有关于内部填充路径生成的具体算法，尤其是平行往复路径生成所涉及的分区、子路径连接等问题，这些都是在较为复杂的模型中常见的问题。这样会导致3D打印路径生成方法很难通用化，无法进一步加快3D打印技术的发展。
发明内容
[0005] 本发明的目的在于提出一种基于分区的3D打印填充路径生成方法，在采用轮廓平行路径与平行往复路径相结合的基础上，对分区路径进行两次连接，旨在减少填充路径中空走路径的次数以及长度。本发明提供了一种适合于各种3D打印技术的通用内部填充路径生成方法，鲁棒性强，可以生成任何截面形状模型的填充路径，尤其是结构复杂、多型腔的模型也适用。
[0006] 一种基于分区的3D打印填充路径生成方法，包括如下步骤：
[0007] 步骤1：根据层高得到需加工实体的SLC文件；
[0008] 步骤2：根据相应的3D打印设备以及打印材料确定填充路径间距；
[0009] 步骤3：根据填充路径间距生成轮廓偏置路径并保存最内层轮廓的偏置路径，记作偏置多边形Ω；
[0010] 步骤4：确定扫描线倾角；
[0011] 步骤5：根据偏置多边形Ω的几何特征对SLC文件中每层的加工区域进行第一次分区；
[0012] 步骤6：将第一次分区的结果根据交点数目进行第二次分区，得到若干子区域，对得到的子区域按照扫描方向进行排序，得到子区域集；
[0013] 步骤7：根据扫描线与偏置多边形Ω的交点以及子区域之间关系生成子区域集对应的子区域路径集；
[0014] 步骤8：对生成的子区域路径集中的每个子区域路径进行特征识别，确定可调整的子区域路径，并对存在可以连接的潜在起点的子区域路径的起点进行调整和连接，得到调整后的子区域路径集；
[0015] 步骤9：采用贪心算法利用样条曲线对调整后的子区域路径集中的子区域路径进行衔接，获得最终的内部填充路径。
[0016] 所述步骤1中需要得到SLC文件，SLC文件可以通过切片软件获得，如MagicRP等，其文件特点是用设定层厚进行均分分层得到的。
[0017] 所述步骤2中每个3D打印设备的结构配置以及所用打印材料的成型参数等不同，其打印路径间距也不同，需要根据具体的设备配置与材料参数确定合适的路径间距。
[0018] 所述步骤3中需根据设定的偏置圈数对实体切片文件中各层轮廓(包括外轮廓和内轮廓)进行偏置获得偏置路径，该填充路径具有填充精度高的特点，同时保存最内层偏置路径。根据对精度的要求不同，可对偏置圈数进行调整，作为优选，步骤3中，生成轮廓偏置路径时，偏置圈数为2-4圈.
[0019] 所述步骤4中需要根据具体场合确定较优的扫描线倾斜角度，其需要考虑填充效率以及填充精度。为提高选择效率，作为优选，步骤4中，扫描线倾角确定时，采用平行填充路径总长度最短的原则进行确定。
[0020] 所述步骤5利用扫描线与步骤3中保存的最内层偏置路径的偏置多边形Ω的交点数目进行第一次分区，每一块区域中的扫描线拥有相同的交点数。作为优选，步骤5中，第一次分区的具体过程为：根据步骤3中的偏置多边形Ω的几何特征获得偏置多边形Ω中存在的与扫描线方向平行的轮廓段和轮廓极值点，对距离所述轮廓段和轮廓极值点最近的扫描线进行标识，利用标识的扫描线对加工区域进行第一次分区。
[0021] 步骤6中，每一块子区域中扫描线拥有且仅拥有两个交点，各子区域中的第一条与最后一条扫描线的端点均为该区域的潜在起点，各子区域拥有四个潜在起点。作为优选，步骤6中，第二次分区的具体过程为：步骤6.1：对某一个区域，首先判断该区域内扫描线与偏置多边形Ω的交点数量，去掉与偏置多边形Ω相切或者与偏置多边形Ω轮廓段重合的交点；步骤6.2：对该区域中其余交点进行如下处理，按照扫描方向，对某一个区域与偏置多边形Ω的交点进行排序，分别为第1、2、…、n组交点，n为该区域内某一扫描线与偏置多边形Ω交点数，大于1且为整数，其中，第1组交点是该区域按照扫描方向与偏置多边形Ω首次相交的一组点，其余类推；按照交点顺序对该区域进行分区，得到子区域集{(1，2)，(3，4)，…，(n-1，n)}，其中第一个子区域(1，2)为第1组交点与第2组交点之间的区域，其余类推；
[0022] 步骤6.3：对所有区域均进行上述分区，最后得到若干子区域。
[0023] 作为优选，步骤7中，得到子区域路径集的具体方法为：步骤7.1：选取当前子区域集中最靠前的子区域，并将该子区域中的第一条扫描线的一个端点作为起点；步骤7.2：利用扫描线与偏置多边形Ω的交点生成平行往复的填充路径，形成当前子区域对应的子区域路径；该步骤中，子区域路径是由若干相互平行的直线段以及将这些直线段依次连接的衔接段组成；步骤7.3：将当前子区域从子区域集中删除，同时获得当前子区域路径的终点；步骤7.4：判断当前区域集中是否为空：若判断结果为是，则将当前得到的子区域路径添加到最终的子区域路径集中，结束步骤7；若判断结果为否，则进入步骤7.5；步骤7.5：在当前子区域集中搜索是否存在与当前子区域路径可连接的潜在起点：首先定义如下两个点：第一个点为当前子区域路径的终点；第二个点为某一子区域的可能起点；进行如下判断：(1)两个点在扫描线垂直方向上的距离为路径间距；(2)两个点是扫描线与同一偏置多边形的交点；(3)两个点是同一偏置多边形上相邻的两个交点；如果同时满足上述(1)-(3)，则认为存在可连接的点；进入步骤7.6；否则，则将当前生成的子区域路径添加到最终子区域路径集中，返回步骤7.1；步骤7.6：将当前子区域路径的终点与可连接点进行连接；步骤7.7：利用扫描线与偏置多边形的交点生成平行往复的填充路径，返回步骤7.3中；如此反复，直至当前子区域集为空，完成所有子区域路径的生成，得到完整的子区域路径集。
[0024] 所述步骤8中首先对步骤7中生成的子区域路径进行特征识别，如若存在同时满足以下两个条件的路径：(1)该路径所有与扫描线平行的直线段部分的左(右)端点都在同一个偏置多边形轮廓上；(2)该路径所有与扫描线平行的直线段部分的左(右)端点是同一个偏置多边形上连续的交点，即在偏置多边形上它们之间不再存在其它交点。该路径的起点可以更换为与起点在同一条扫描线段的另一个端点，不满足上述两个条件的路径不具备该性质。如果更换起点之后的路径的始末点与其他路径的始末点满足可连接的条件，则改变该条路径的起点并将其与相邻路径连接。作为优选，步骤8中，具体步骤包括：步骤8.1：对当前子区域路径集中不能调整的子区域路径和能够调整的子区域路径分别进行标识；步骤8.2：将标识后的子区域路径集中不能调整的子区域路径添加到最终输出的调整后子区域路径集中；步骤8.3：将标识后的子区域路径集中可以调整的子区域路径进行调整，输出最终调整后的子区域路径集。
[0025] 作为进一步优选，步骤8.3具体过程为：步骤8.3.1：首先判断当前标识后的子区域路径集中元素是否为空：如果判断结果为是，则输出最终调整后的子区域路径集；如果判断结果为否，则进入步骤8.3.2；步骤8.3.2：判断当前标识后的子区域路径集中某一子区域路径是否可以调整：如果判断结果为是，则进入步骤8.3.3；如果判断结果为否，则返回步骤8.3.1；步骤8.3.3：对该子区域路径，在当前标识后的子区域路径集中寻找其相邻的潜在连接点：如果存在这样的潜在连接点，则进入步骤8.3.4；如果不存在这样的潜在连接点，则将当前子区域路径从标识后的子区域路径集中删除，同时将当前子区域路径添加到最终调整后的子区域路径集中，返回步骤8.3.1；步骤8.3.4：对当前子区域路径的端点进行调整，并添加到所述潜在连接点所在的子区域路径中，同时将添加后的子区域路径删除，并将当前得到的子区域路径添加到最终调整后的子区域路径集中，返回步骤8.3.1。
[0026] 所述步骤9利用贪心算法对最终的各子路径进行排序以确定局部最优的最短衔接路径顺序，最后利用样条曲线连接各路径从而使连接线与路径衔接处保证相切相关。步骤9的具体步骤为：步骤9.1：将步骤8输出的调整后的子区域路径集中具有最大y坐标值的子区域路径添加到最终输出的路径集中，并将该子区域路径的起点作为最终输出的路径起点；步骤9.2：将当前子区域路径在调整后的子区域路径集中删除；步骤9.3：得到子区域路径的终点；步骤9.4：在调整后的子区域路径集中寻找距离当前终点最短的子区域路径的端点；
步骤9.5：将距离最短的端点所在的子区域路径添加到最终输出的路径集中，并将其从调整后的子区域路径集中删除；步骤9.6：判断调整后的子区域路径集中是否为空，如果判断结果为是，则结束程序，输出最终的路径集；如果判断结果为否，则返回步骤9.3。
[0027] 本发明是3D打印中的内部填充路径生成方法，具体的有益效果是：
[0028] 通过读取SLC文件获得零件各层截面形状，首先根据设定圈数对轮廓进行偏置获得轮廓平行路径，在确定最优扫描线倾角的基础上，利用扫描线与最内层轮廓平行路径的偏置多边形的交点初步生成平行往复填充路径，再根据相邻子路径的特征将可连接路径进行连接以进一步减少空走路径的数量，最后利用贪心算法连接各子路径，从而确定局部最优的连接顺序，利用样条曲线对子路径进行连接。该方法鲁棒性强，适应于各种形状的模型，尤其是对结构复杂、较多型腔的模型有效果，同时简单，易实现，通用性好，更容易嵌入到3D打印设备中，实现商业化。
附图说明
[0029] 图1为本发明基于分区的3D打印填充路径生成方法的流程图；
[0030] 图2为本发明根据扫描线与最内层偏置轮廓多边形的交点以及子区域之间关系生成加工路径的流程图；
[0031] 图3为填充路径结构示意图；
[0032] 图4为本发明对子路径特征识别并将其中可调整路径进行起点调整与相邻子区域连接流程图；
[0033] 图5为本发明对子区域路径进行连接所采用的贪心算法流程图；
[0034] 图6为本发明基于分区的3D打印填充路径生成方法的具体应用的示意流程图。
具体实施方式
[0035] 下面结合附图和具体实施例对本发明做进一步说明。
[0036] 图1所示为本发明3D打印技术通用内部填充路径生成方法的流程图。以附图6(a)中的零件截面为例，来阐明内部填充路径生成方法。
[0037] 步骤1、根据零件精度需要设定层高0.5mm，利用切片软件获得零件各层片轮廓信息，图6(a)为其中某一截面轮廓；
[0038] 步骤2、根据采用的3D打印设备以及打印材料确定合适的填充路径间距为0.8mm；
[0039] 步骤3、设定轮廓偏置路径的圈数为2(一般为2-4圈)，根据偏置距离生成轮廓平行填充路径，获得如图6(b)所示的路径，并将最内层偏置路径进行偏置后的偏置多边形Ω保存；
[0040] 步骤4、根据平行填充路径总长度最短的原则确定最优扫描线倾角为135°，可采用现有技术进行确定；
[0041] 步骤5、根据步骤3中的偏置多边形Ω的几何特征获得偏置多边形Ω中存在的与扫描线方向平行的轮廓段和轮廓极值点，对距离与扫描线方向平行的轮廓段和轮廓极值点最近的扫描线进行标识，利用标识的扫描线对加工区域进行第一次分区，获得如图6(c)的分区效果图，一共包括8个分区；经过步骤5分区后，每个分区内扫描线与偏置多边形Ω的交点数量相同；步骤6、根据步骤5获得的每个分区中扫描线与多边形Ω的交点数目(n)将其划分成n/2个区域，获得如图6(d)的分区效果图，一共包括16个分区；
[0042] 具体处理过程为：
[0043] 步骤6.1：对某一个区域，首先判断该区域内扫描线与偏置多边形Ω的交点数量，去掉与偏置多边形Ω相切或者与偏置多边形Ω轮廓段重合的交点；
[0044] 步骤6.2：对该区域中其余交点进行如下处理，按照扫描方向，对某一个区域与偏置多边形Ω的交点进行排序，分别为第1、2、…、n组交点，其中，第1组交点是该区域按照扫描方向与偏置多边形Ω首次相交的一组点，其余类推；按照交点顺序对该区域进行分区，得到子区域集{(1,2)，(3,4)，…，(n-1，n)}，其中第一个子区域(1，2)为第1组交点与第2组交点之间的区域，其余类推；
[0045] 步骤6.3：对所有区域均进行上述分区，最后得到所有的16个子区域。
[0046] 进行步骤7前，按照扫描方向，对得到的子区域进行排序，形成子区域集；
[0047] 步骤7、根据附图2所示的根据扫描线与最内层偏置轮廓的偏置多边形Ω的交点以及子区域之间关系生成加工路径的流程图生成子区域路径，子区域路径的个数为5个，获得如图6(e)的路径；具体步骤为：
[0048] 步骤7.1：选取当前子区域集中的最靠前的子区域，并将该子区域中的第一条扫描线的左端点(右端点)作为起点；
[0049] 步骤7.2：利用扫描线与偏置多边形Ω的交点生成平行往复的填充路径，形成当前子区域对应的子区域路径；该步骤中，如图3所示，子区域路径是由若干相互平行的直线段L以及将这些直线段依次连接的衔接段C组成，衔接段既可以是直线也可能是曲线，与扫描线与偏置多边形Ω交点处的偏置多边形Ω的轮廓段形状有关；
[0050] 步骤7.3：将当前子区域从子区域集中删除，同时获得当前子区域路径的终点；
[0051] 步骤7.4：判断当前区域集中是否为空：若判断结果为是，则将当前得到的子区域路径添加到最终的子区域路径集中，结束步骤7；若判断结果为否，则进入步骤7.5；
[0052] 步骤7.5：在当前子区域集中搜索是否存在与当前子区域路径可连接的潜在起点：首先定义如下两个点：第一个点为当前子区域路径的终点；第二个点为某一子区域的可能起点(该子区域第一条扫描线的左端点或者右端点)；进行如下判断：
[0053] (1)两个点在扫面线垂直方向上的距离为路径间距；
[0054] (2)两个点是扫描线与同一偏置多边形的交点；
[0055] (3)两个点是该偏置多边形轮廓上相邻的两个交点；
[0056] 如果同时满足上述(1)-(3)，则认为存在可连接的点；进入步骤7.6；否则，则将当前生成的子区域路径添加到最终子区域路径集中，返回步骤7.1；
[0057] 步骤7.6：将当前子区域路径的终点与可连接点进行连接；
[0058] 步骤7.7：利用扫描线与偏置多边形的交点生成平行往复的填充路径，返回步骤7.3中；
[0059] 如此反复，直至当前子区域集为空，完成所有子区域路径的生成，得到完整的子区域路径集，分别是A1A2、B1B2、C1C2、D1D2、E1E2。
[0060] 步骤8、如图4所示，对步骤7中已生成的5块子区域路径进行特征识别，确定子区域路径C1C2，E1E2可以调整起始点，但E1E2的相邻区域子路径中不存在可以连接的潜在起点，故对其中的子区域路径C1C2中的起点进行调整并与子区域路径D1D2进行连接，区域路径个数减为4，获得如图6(f)的路径；
[0061] 具体步骤为：
[0062] 步骤8.1：对当前子区域路径集进行标识，具体步骤为：
[0063] 步骤8.1.1：首先判断当前子区域路径集中元素是否遍历完毕：如果判断结果为是，则输出标识后的子区域路径集，进入步骤8.2；如果判断结果为否，则进入步骤8.1.2；
[0064] 步骤8.1.2：选取当前子区域路径集中未遍历的一个子区域路径，判断该子区域路径中所有与扫描线平行的直线段部分的左端点或右端点是否都在同一个偏置多边形轮廓上(即左端点同时在一个偏置多边形上，右端点在另一个偏置多边形上)：如果判断结果为否，则说明该子区域路径无法调整，返回步骤8.1.1；如果判断结果为是，则进行步骤8.1.3；
[0065] 步骤8.1.3：对步骤8.1.2得到的判断结果为是的子区域路径进一步判断：该子区域路径所有与扫描线平行的直线段部分的左端点或右端点是否是同一个偏置多边形上连续的交点：如果判断结果为否，则说明该子区域路径无法调整，返回步骤8.1.1；如果判断结果为是，则说明该子区域路径可以调整，对该子区域路径进行标识，返回步骤8.1.1；
[0066] 步骤8.2：将标识后的子区域路径集中不能调整的子区域路径添加到最终输出的调整后子区域路径集中，具体步骤为：
[0067] 步骤8.2.1：首先判断当前标识后的子区域路径集是否遍历完毕：如果判断结果为是，则进入步骤8.3；如果判断结果是否，则进入步骤8.2.2；
[0068] 步骤8.2.2：对当前标识后的子区域路径集未遍历的一个子区域路径，判断是否是可以调整的子区域路径，如果判断结果为是，则返回步骤8.2.1；如果判断结果为否，则不能调整的子区域路径添加到最终输出的调整后子区域路径集中，返回步骤8.2.1步骤8.3：将标识后的子区域路径集中可以调整的子区域路径进行调整，输出最终调整后的子区域路径集，具体过程为：
[0069] 步骤8.3.1：首先判断当前标识后的子区域路径集中元素是否为空：如果判断结果为是，则输出最终调整后的子区域路径集；如果判断结果为否，则进入步骤8.3.2；
[0070] 步骤8.3.2：判断当前标识后的子区域路径集中某一子区域路径是否可以调整：如果判断结果为是，则进入步骤8.3.3；如果判断结果为否，则返回步骤8.3.1；
[0071] 步骤8.3.3：对该子区域路径，在当前标识后的子区域路径集中寻找其相邻的潜在连接点：如果存在这样的潜在连接点，则进入步骤8.3.4；如果不存在这样的连接点，则将当前子区域路径从标识后的子区域路径集中删除，同时将当前子区域路径添加到最终调整后的子区域路径集中，返回步骤8.3.1；
[0072] 步骤8.3.4：对当前子区域路径的端点进行调整，并添加到所述潜在连接点所在的子区域路径中，同时将添加后的子区域路径删除，并将添加后的子区域路径添加到最终调整后的子区域路径集中，返回步骤8.3.1；
[0073] 步骤9、利用附图5中的贪心算法确定子路径的连接顺序，采用样条曲线进行连接作为非填充路径，获得如图6(g)的路径，其中图6(g)中101和102区域的局部放大图分别为图6(g)右侧的101和102图示。具体步骤为：
[0074] 步骤9.1：将步骤8输出的调整后的子区域路径集中具有最大y坐标值的子区域路径添加到最终输出的路径集中，并将该子区域路径的起点作为最终输出的路径起点；
[0075] 步骤9.2：将当前子区域路径在调整后的子区域路径集中删除；
[0076] 步骤9.3：得到子区域路径的终点；
[0077] 步骤9.4：在调整后的子区域路径集中寻找距离当前终点最短的子区域路径的端点；
[0078] 步骤9.5：当距离最短的端点所在的子区域路径添加到最终输出的路径集中，并将其从调整后的子区域路径集中删除；
[0079] 步骤9.6：判断调整后的子区域路径集中是否为空，如果判断结果为是，则结束程序，输出最终的路径集；如果判断结果为否，则返回步骤9.3。
