CN112051796A - 一种连接二维随机封闭图形生成最短路径的规划方法 - Google Patents

Abstract

本发明公开了一种连接二维随机封闭图形生成最短路径的规划方法，该方法把随机生成的众多二维封闭图形(图形不存在相交，且距离较远)，将图形的质心作为数据点集合P排序的基础，首先确定某个图形质心为起始点，逐个连接剩余二维图形，优化路径，以最短路径为目标输出，采用改良贪心算法得到最优路径；相关参数包括路径长度L，点P_i与P_j之间的距离D_ij，点P_i到其他点的总距离S_i，曲线方程l。本发明实现了开环二维加工图形路径规划，与一般的智能算法相比，减少了时间复杂度，提高了路径规划最优性，大幅提高了加工效率。

Description

一种连接二维随机封闭图形生成最短路径的规划方法

技术领域

本发明属于数控加工技术领域，具体涉及一种在数控加工中连接大量二维封闭图形生成最短路径的规划方法。

背景技术

数控加工中，路径规划是数据处理中重要的组成部分，合理的加工路径规划能够很好的提高加工效率。对于CAM生成的加工路径一般采用最近邻搜索算法，由于其算法具有短视性的缺点，很难做到全局的优化。精确求解算法求解时间会随问题的复杂度呈指数型增长，对于实际复杂问题不够实用。目前对二维加工轨迹规划的算法一般采用智能优化算法，如遗传算法、蚁群算法、退火算法等，这些算法在特定的应用场合效果较好，但是时间复杂度较高，且容易陷入局部最优，离最优解相差可能很多，求解效果不是很理想。

发明内容

本发明针对数控加工，提供了一种在数控加工中连接大量二维封闭图形生成最短路径的规划方法，该方法输入为大量随机封闭图形，输出为最短路径。

本发明采用如下技术方案来实现的：

一种连接二维随机封闭图形生成最短路径的规划方法，该方法把随机生成的众多二维封闭图形，将图形的质心作为数据点集合P排序的基础，首先确定某个图形质心为起始点，逐个连接剩余二维图形，优化路径，以最短路径为目标输出，采用改良贪心算法得到最优路径；相关参数包括路径长度L，点P_i与P_j之间的距离D_ij，点P_i到其他点的总距离S_i，曲线方程l。

本发明进一步的改进在于，具体包括如下步骤：

1)起始点的选择

对于n个图形的质心集合点P，D_ij为点P_i与点P_j之间的距离，其中D_ii＝0，Si为点P_i到其他点的距离之和，如下：

取max{S_i}，得某点Pi为起始点；

2)点对点优化初始路径

利用最近邻搜索算法得到初始优化路径，其中最近邻搜索算法具有短视性，遍历初始优化路径，对于存在路径交叉的情况，如果两段路径交叉，交换其中两个点的点序，重新生成路径，若这两点之间存在其他点序，则翻转其顺序，重新生成路径，再次遍历，直至路径中不存在交叉情况，保存新的优化路径；

3)点对线段再次优化路径

对于2)优化后的点序，选取P_i，i＝1,2,…n-2，将剩下的路径

倒序处理，得到新的路径

判断路径总长度L是否缩短，若是则确定新的点序并保存，并在此重复上述步骤；若否，则继续下一个点，直至倒数第三个点P_n-2；依次选取P_j，j＝1,2,…n，插入其余两点之间的序列中，形成新的点序列，判断总路径长度L是否有所缩短；若路径缩短则生成新的点序并保存，生成新的点序之后需要重复上述步骤，直至遍历所有点且L不再变化，保存新的优化路径；

4)线段对线段进一步优化路径

对于3)生成后的点序路径，得到最优路段，以最优路径

为整体，按照3)的步骤重新排序，直至L不再减小，保存新的优化路径。

本发明进一步的改进在于，还包括以下步骤：

5)拟合图形轮廓

对于加工图形的轮廓进行曲线拟合，得到每个加工图形的曲线方程；

6)连接图形路径

得到5)排序后的加工图形顺序，以相邻的三个加工图案Q_i-1，Q_i，Q_i+1为一组，先计算加工图案Q_i的入刀点；取Q_i-1和Q_i+1的质心P_i-1：(x_i-1,y_i-1)和P_i+1：(x_i+1,y_i+1)，当Q_i为二次曲线时：l_i:ax²+bxy+cy²+dx+ey+f＝0；

联立是K₁，K₂，K₃方程，求解得(x,y)，替换Q_i的质心点序列Pi，保存新的路径序列，依次处理(Q₂,Q₃,…Q_n-1)以图案上的入刀点替换质心点；用Q₂的入刀点求取距离Q₁上最短路径的入刀点，Q_n-1的入刀点求取Q_n上的最短路径入刀点，重复上述的过程，直至L变化在0.5％内，保存加工路径。

本发明进一步的改进在于，步骤4)中最优路段定义：指某几个相邻点形成的路段，若路段

比其余任意路段长度要小，则定义

为最优路段。

本发明进一步的改进在于，步骤5)中，拟合图形轮廓的具体方法如下：若加工图案是简单的几何图形，对于图案的直线轮廓用一次函数拟合：l₁:y+ax+b＝0，曲线轮廓用二次曲线分段拟合：l₂:ax²+bxy+cy²+dx+ey+f＝0，将其保存在对应的图案中Q_i中；若加工图案复杂，则将图案分段拟合：l_i:ax²+bxy+cy²+dx+ey+f＝0，且误差ε＜0.5％。

本发明具有如下有益的技术效果：

1、时间复杂度低：一般遗传算法解TSP问题时间复杂度高，计算时间较长，而该算法按步骤优化，时间复杂度远远低于一般遗传算法。

2、优化程度高：相比于一般遗传算法有可能陷入局部优化而不能更好的继续优化，其平均的优化程度比解析解算法低。

3、提高了精确性：相比于加工图形入刀点采用节点代替的方法，轮廓拟合更能缩短加工路径。

4、确定性：对于遗传算法存在随机性，所以每次的结果都不稳定，而解析解算法具有确定的唯一解。

5、可扩展性强：该方法还可以应用在其他非闭环的行程规划类问题上，例如公交行程规划等，应用面广泛。

附图说明

图1为本发明一种在连接随机数据点生成最短路径规划方法的流程图。

图2为简单多几何图形的加工路径规划示意图。

图中：1为二维数据点，2为二维平面，3为规划路径，4为点，5为交叉路径，6为优化交叉路径结果，7为点对线段路径未优化末端部分，8为点对线段路径未优化中间部分，9为点对线段路径末端部分优化结果，10为点对线段路径中间部分优化结果，11为最优线段，12为线段对线段路径优化结果；

13为初始图形质心，14—21为加工图形，22为初始优化路径，23为拉格朗日优化迭代后的优化路径，24为优化迭代后的优化节点，25为末尾图形质心。

具体实施方式

以下结合附图和实施例对本发明进一步说明。由于二维点轨迹规划和二维封闭图形不易结合表示，故将两种方法分开附图表示。

如图1所示：本发明提供一种应用于连接二维平面数据点最短路径规划方法，该方法以二维数据点1为输入，在二维平面2上得到的开环最短路径L为输出，并用改化贪心算法最优化总路径。参数包括路径长度L，点P_i与P_j之间的距离D_ij，点P_i到其他点的总距离S_i，曲线方程l。

二维数据点路径规划步骤具体如下：

1)起始点的选择

对于n个图形的质心集合点P，其中D_ii＝0；

取max{S_i}，得点P_O为起始点。

2)优化初始路径(点对点)

以点4为起点，利用最近邻搜索算法得到初始优化路径3，由于最近邻搜索算法具有短视性，遍历初始优化路径3，对于存在路径交叉的情况，交叉路径5中

和

交叉，交换P_X和P_N的点序，由于P_X和P_N这两点之间存在其他点，翻转其他点的顺序，重新生成路径，如优化交叉路径结果6，再次遍历，直至路径中不存在交叉情况，保存新的优化路径。

3)再次优化路径(点对线段)

对于2)优化后的点序，对于点对线段路径未优化末端部分7，选取P_i(i＝1,2,…n-2)，将剩下的路径

倒序处理，得到点对线段路径末端部分优化结果9，判断路径总长度是否缩短，若是则确定新的点序并保存，并再次重复上述步骤；若否，则继续下一个点，直至到P_n-2。对于点对线段路径未优化中间部分8，依次选取P_j(j＝1,2,…n)，插入其余两点之间的序列中，形成新的点序列，判断总路径长度L是否有所缩短。若路径缩短则生成新的点序并保存点对线段路径中间部分优化结果10，生成新的点序之后需要重复上述步骤，直至遍历所有点且L不再变化，保存新的优化路径。

4)进一步优化路径(线段对线段)

对于3)生成后的点序路径，寻找最优路段。路径

比其余任意路径长度要小，则定义

为最优路径。以最优路段11为整体，按照3)的步骤重新排序，直至L不再减小，得到线段对线段路径优化结果12，保存新的优化路径。

如图2所示：本发明提供一种应用于连接二维平面加工图形最短路径规划方法，该方法以根据质心排序后的二维加工图形14-21，得到的连接最短路径L为输出，并用局部格朗日乘数法优化总路径。参数包括曲线方程l，路径长度L。

5)拟合图形轮廓

加工图形14-21是简单二维加工图形，对于图形14,17,21的直线轮廓用一次函数拟合：l₁:y+ax+b＝0，图形15,16,18,19,20的曲线轮廓用二次曲线分段拟合：l₂:ax²+bxy+cy²+dx+ey+f＝0，将其保存在对应的图形中Q_i中。若加工图形比较复杂，则可以考虑将图形分段拟合：l_i:ax²+bxy+cy²+dx+ey+f＝0，且要求误差ε＜5％。

6)连接图形路径

得到5)排序后的加工图形顺序，以相邻的三个加工图形14，15，16为一组，先计算加工图形15的入刀点。取加工图形14和加工图形16的质心(x_i-1,y_i-1)，(x_i+1,y_i+1)，以加工图形15为二次曲线为例：l_i:ax²+bxy+cy²+dx+ey+f＝0。

联立K₁，K₂，K₃方程，求解得(x,y)，优化迭代后的优化节点24替换加工序列中加工图形15的质心点，保存新的路径序列，依次处理加工图形16,17,18,19,20，以图形上的入刀点替换质心点，得到初始优化路径22。用加工图形15的入刀点求取距离加工图形14上最短路径的入刀点，替代初始图形质心13，加工图形20的入刀点求取加工图形21上的最短路径入刀点，替代末尾图形质心25，得到拉格朗日优化迭代后的优化路径23。重复上述的过程，直至路径长度L变化在0.5％内，得到保存加工路径。

Claims (5)

1.一种连接二维随机封闭图形生成最短路径的规划方法，其特征在于，该方法把随机生成的众多二维封闭图形，将图形的质心作为数据点集合P排序的基础，首先确定某个图形质心为起始点，逐个连接剩余二维图形，优化路径，以最短路径为目标输出，采用改良贪心算法得到最优路径；相关参数包括路径长度L，点P_i与P_j之间的距离D_ij，点P_i到其他点的总距离S_i，曲线方程l。

2.根据权利要求1所述的一种连接二维随机封闭图形生成最短路径的规划方法，其特征在于，具体包括如下步骤：

1)起始点的选择

对于n个图形的质心集合点P，D_ij为点P_i与点P_j之间的距离，其中D_ii＝0，Si为点P_i到其他点的距离之和，如下：

取max{S_i}，得某点Pi为起始点；

2)点对点优化初始路径

利用最近邻搜索算法得到初始优化路径，其中最近邻搜索算法具有短视性，遍历初始优化路径，对于存在路径交叉的情况，如果两段路径交叉，交换其中两个点的点序，重新生成路径，若这两点之间存在其他点序，则翻转其顺序，重新生成路径，再次遍历，直至路径中不存在交叉情况，保存新的优化路径；

3)点对线段再次优化路径

对于2)优化后的点序，选取P_i，i＝1,2,…n-2，将剩下的路径

倒序处理，得到新的路径

判断路径总长度L是否缩短，若是则确定新的点序并保存，并在此重复上述步骤；若否，则继续下一个点，直至倒数第三个点P_n-2；依次选取P_j，j＝1,2,…n，插入其余两点之间的序列中，形成新的点序列，判断总路径长度L是否有所缩短；若路径缩短则生成新的点序并保存，生成新的点序之后需要重复上述步骤，直至遍历所有点且L不再变化，保存新的优化路径；

4)线段对线段进一步优化路径

对于3)生成后的点序路径，得到最优路段，以最优路径

为整体，按照3)的步骤重新排序，直至L不再减小，保存新的优化路径。

3.根据权利要求2所述的一种连接二维随机封闭图形生成最短路径的规划方法，其特征在于，还包括以下步骤：

5)拟合图形轮廓

对于加工图形的轮廓进行曲线拟合，得到每个加工图形的曲线方程；

6)连接图形路径

得到5)排序后的加工图形顺序，以相邻的三个加工图案Q_i-1，Q_i，Q_i+1为一组，先计算加工图案Q_i的入刀点；取Q_i-1和Q_i+1的质心P_i-1：(x_i-1,y_i-1)和P_i+1：(x_i+1,y_i+1)，当Q_i为二次曲线时：l_i:ax²+bxy+cy²+dx+ey+f＝0；

联立是K₁，K₂，K₃方程，求解得(x,y)，替换Q_i的质心点序列Pi，保存新的路径序列，依次处理(Q₂,Q₃,…Q_n-1)以图案上的入刀点替换质心点；用Q₂的入刀点求取距离Q₁上最短路径的入刀点，Q_n-1的入刀点求取Q_n上的最短路径入刀点，重复上述的过程，直至L变化在0.5％内，保存加工路径。

4.根据权利要求2或3所述的一种连接二维随机封闭图案生成最短路径的规划方法，其特征在于，步骤4)中最优路段定义：指某几个相邻点形成的路段，若路段

比其余任意路段长度要小，则定义

为最优路段。

5.根据权利要求4所述的一种连接二维随机封闭图案生成最短路径的规划方法，其特征在于，步骤5)中，拟合图形轮廓的具体方法如下：若加工图案是简单的几何图形，对于图案的直线轮廓用一次函数拟合：l₁:y+ax+b＝0，曲线轮廓用二次曲线分段拟合：l₂:ax²+bxy+cy²+dx+ey+f＝0，将其保存在对应的图案中Q_i中；若加工图案复杂，则将图案分段拟合：l_i:ax²+bxy+cy²+dx+ey+f＝0，且误差ε＜0.5％。

Images