1.本发明涉及几何计算领域，具体而言，涉及基于最优化能量求解线段距离方法、系统及终端设备。
背景技术：2.在集成电路设计软件中，线段间距离计算是一种高频操作，加快线段距离的求解可以显著加速软件对电路的仿真计算。
3.现有技术中求解线段距离的方法需要计算线段各个端点和其他线段的距离信息，最后比较获取其中最小值即是线段距离。其过程需要计算四次点到线段的距离，而最终只能得到一个有效结果，这大大拖慢了计算速度。还有一些技术专注于计算线段是否相交，但是对于能否计算出线段距离没有十分快速而有效的方法。
4.因此，现有技术中存在以下问题需要解决：
5.1.存在多余无用的计算，影响计算速度；
6.2.仅专注于相交问题，不能计算出线段间距离。
技术实现要素：7.本发明的目的在于提供基于最优化能量求解线段距离方法、系统及终端设备，以解决现有技术中存在多余无用的计算，影响计算速度，仅专注于解决相交问题，不能计算出线段间距离的不足。
8.为解决上述问题，本发明首先提供了基于最优化能量求解线段距离方法，包括以下步骤：
9.对线段距离问题构造能量函数，并求全局最优解；
10.运用所述全局最优解和所述能量函数对各参数的偏导数关系，得到约束最优解位置；
11.利用所述能量函数和所述约束最优解的参数值，计算线段距离。
12.进一步的，构造能量函数包括以下步骤：
13.建立待计算距离线段的信息，c1(p1，p2)，c2(p3，p4)，c1，c2分别表示待计算距离的两线段，p1，p2为线段c1的两端点，p3，p4为线段c2的两端点；
14.利用直线参数表示方法，分别表示线段c1，c2上任意点的位置：
15.pu＝(1-u)p1+up2，pv＝(1-v)p3+vp4，pu，pv分别表示线段c1，c2上任意一点， u为pu在线段c1上位置的参数，v为pv在线段c2上位置的参数；
16.通过pu，pv的距离建立两线段距离的所述能量方程：
17.e＝((1-u)p1+up2)((1-u)p1+up2)
t
，e表示构造的所述能量函数。
18.进一步的，对所述能量函数求全局最优解的包括以下步骤：
19.分别计算所述能量函数e(u，v)对u，v的偏导数等于0的直线：
20.21.l1表示能量e(u，v)对u偏导数等于0的直线，l2表示能量e(u，v)对v 偏导数等于0的直线；
22.计算直线l1，l2的交点，交点记作x
*
＝(u
*
，v
*
)，交点对应的参数值u
*
，v
*
为所述全局最优解。
23.进一步的，获得所述约束最优解位置包括以下步骤：
24.在参数域(u，v)上依据可行域边界，将所述参数域划分为九个区域；
25.判断所述全局最优解在所述参数域区域划分中的位置；
26.利用所述全局最优解在所述参数域中的位置，判断所述全局最优解点对于可行域的可视边界；
27.计算直线l1，l2与所述可视边界的交点，通过交点得到所述约束最优解对应位置及其对应的参数值uc，vc。
28.进一步的，所述全局最优解对可行域的所述可视边界应满足如下条件，所述全局最优解与所述可视边界上点的连线与可行域其他边界不相交。
29.进一步的，当所述全局最优解位于可行域外时，所述约束最优解一定位于所述全局最优解对可行域的所述可视边界上；
30.当所述全局最优解位于可行域内时，所述约束最优解等于所述全局最优解。
31.进一步的，计算线段距离包括以下步骤：
32.当所述约束最优解在可行域内时，线段距离为0；
33.当所述约束最优解在可行域边界上时，将所述约束最优解(uc，vc)带入到所述能量函数e(u，v)中，获取最优距离能量e
*
＝e(uc，vc)，其中e
*
表示最优距离能量，uc，vc分别代表所述约束最优解对应的参数值；
34.通过所述能量函数计算线段距离，d
*
为两线段之间待求距离。
35.为解决上述问题，本发明还提供了基于最优化能量求解线段距离系统，包括构造能量函数模块，全局最优解求解模块、约束最优解求解模块和线段距离求解模块；
36.所述构造能量函数模块，利用参数方程表示线段上任意点，并构造线段距离问题的能量函数；
37.所述全局最优解求解模块，计算所述能量函数对参数u，v的偏导数等于零的直线l1，l2，并通过计算两直线l1，l2的交点得到全局最优解；
38.所述约束最优解求解模块，利用所述全局最优解在参数域上的位置，判断可行域对于所述全局最优解的可视边界，通过计算l1，l2对与所述可视边界的交点，得到约束最优解的值；
39.所述线段距离求解模块，利用所述约束最优解的值和所述能量函数，判断所述约束最优解的区域位置，通过代入所述约束最优解到能量函数得到线段的距离。
40.为解决上述问题，本发明还提供了终端设备，包括存储器、处理器以及计算机程序，所述计算机程序存储在所述存储器中并在所述处理器上运行，所述处理器执行所述计算机程序时实现上述技术方案中的基于最优化能量求解线段距离方法的步骤。
41.根据本发明提供的基于最优化能量求解线段距离计算方法，通过有目标的计算最优解，避免冗余计算点线距离，有效降低线段距离计算时间复杂度，可作为eda(电子设计自动化)软件底层加速的重要依据。
42.本实施例在构造线段距离能量函数并对其进行最优化计算基础上，提出了对参数域分块，并根据能量函数关于各参数偏导数等于零的直线与全局最优解对可行域可视边界的交点，直接得出约束最优解的位置，计算简单迅速，具有实用性。并且，利用直线求交点代替点距离的计算，降低了问题需要进行的乘法次数，有效的降低了计算所需时间，在大量调用求解直线距离的eda(电子设计自动化)软件中，速度能够得到明显的提升，具有速度快、通用性强、易于实现等优点。
附图说明
43.为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据提供的附图获得其他的附图。
44.图1为本发明实施例提供的基于最优化能量求解线段距离方法的流程图；
45.图2为本发明实施例提供的基于最优化能量求解线段距离方法的两待求距离线段及其信息示意图；
46.图3为本发明实施例提供的基于最优化能量求解线段距离方法的能量函数空间图像及其在参数域平面上的等值线投影示意图；
47.图4为本发明实施例提供的基于最优化能量求解线段距离方法的能量函数在参数域平面上对各参数偏导数等于0的直线和能量等值椭圆位置关系及交点处等值线椭圆切线和能量函数梯度方向关系示意图；
48.图5为本发明实施例提供的基于最优化能量求解线段距离方法的参数域分块划分示意图；
49.图6为本发明实施例提供的基于最优化能量求解线段距离方法的全局最优解位于区域1示意图；
50.图7为本发明实施例提供的基于最优化能量求解线段距离方法的全局最优解位于区域2示意图；
51.图8为本发明实施例提供的基于最优化能量求解线段距离方法的全局最优解位于区域3示意图；
52.图9为本发明实施例提供的基于最优化能量求解线段距离方法的全局最优解位于区域4示意图；
53.图10为本发明实施例提供的基于最优化能量求解线段距离方法的全局最优解位于区域5示意图；
54.图11为本发明实施例提供的基于最优化能量求解线段距离方法的全局最优解位于区域6示意图；
55.图12为本发明实施例提供的基于最优化能量求解线段距离方法的全局最优解位于区域7示意图；
56.图13为本发明实施例提供的基于最优化能量求解线段距离方法的全局最优解位于区域8示意图；
57.图14为本发明实施例提供的基于最优化能量求解线段距离方法的全局最优解位
于区域9示意图。
具体实施方式
58.为使本发明的上述目的、特征和优点能够更为明显易懂，下面结合附图对本发明的具体实施例做详细的说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。
59.下面结合附图对本实施例做进一步详细描述：
60.结合附图1所示，本实施例首先提供了基于最优化能量求解线段距离方法，包括以下步骤：
61.1.构造线段距离问题能量函数，并求解全局最优解；
62.1.1结合附图2所示待计算两线段包括如下信息：
63.c1(p1，p2)
64.c2(p3，p4)
65.其中c1，c2分别表示待计算距离的两线段，p1，p2为线段c1的两端点。 p3，p4为线段c2的两端点；
66.1.2结合附图2所示，根据直线参数表示方法，分别表示两待计算距离线段上任意点的位置：
67.pu＝(1-u)p1+up268.pv＝(1-v)p3+vp469.其中pu，pv分别表示线段c1，c2上任意一点，u为pu在线段c1上位置的参数，v为pv在线段c2上位置的参数；
70.1.3结合附图2中虚线所示，根据pu，pv的距离建立两线段距离能量方程：
71.e＝((1-u)p1+up2)((1-u)p1+up2)
t
72.其中e表示构造的距离能量函数；
73.1.4能量函数图像和等值线投影如附图3所示，分别计算能量e(u，v) 对u，v的偏导数等于零的直线，如附图4中所示直线即为能量e(u，v)对u， v的偏导数等于零的直线，如附图4中所示椭圆表示能量函数某一等值线在u，v平面上投影，由于能量函数二次型及其系数矩阵正定性质，能量函数等值线在参数域上投影一定为椭圆；
[0074][0075][0076]
其中l1表示能量e(u，v)对u偏导数等于0的直线，l2表示能量e(u，v) 对v偏导数等于0的直线；
[0077]
1.5计算直线l1，l2的交点，交点记作x
*
＝(u
*
，v
*
)，该交点即为全局最优解；
[0078]
结合附图4所示，通过计算能量e(u，v)对u，v偏导数形成的直线l1，l2的交点，求得能量e(u，v)全局最优解。
[0079]
2.通过全局最优解和能量函数对各参数的偏导数关系，得到约束最优解位置；
[0080]
2.1在参数域(u，v)上依据可行域及其边界，将参数域划分为九个区域，如图5所
示；
[0081]
2.2判断全局最优解在上述参数域区域划分中的位置；
[0082]
2.3根据全局最优解参数域中的位置，计算直线l1，l2和该点对于可行域可视边界所在直线的交点，依据直线l1，l2和可视边界的交点得到约束最优解对应的位置及其对应的参数值uc，vc，以下情况为例：
[0083]
2.3.1结合附图6所示，若全局最优解在区域1上，全局最优解对应可行域边界的可视边界为线段(0，0)到(0，1)再到(1，1)的部分；
[0084]
计算直线l1与直线v＝1交点，
[0085]
若直线l1与直线v＝1交于(1，1)右侧，则约束最优解为(1，1)；
[0086]
若直线l1与直线v＝1交于(1，1)和(0，1)之间，则直线l1与直线v＝1 的交点即为约束最优解；
[0087]
若直线l1与直线v＝1交于(0，1)左侧，则计算l2与直线u＝0交点；若直线l2与直线u＝0交于(0,0)和(0,1)之间，则约束最优解为直线l2与直线u＝0交点；若直线l2与直线u＝0交于(0,0)下方，则约束最优解为(0,0)。
[0088]
2.3.2结合附图7所示，若全局最优解在区域2上，全局最优解对应可行域边界的可视边界为线段(0，1)再到(1，1)的部分；
[0089]
计算直线l1与直线v＝1交点，
[0090]
若直线l1与直线v＝1交于(1，1)右侧，则约束最优解为(1，1)；
[0091]
若直线l1与直线v＝1交于(1,1)和(0,1)之间，则直线l1与直线v＝1 的交点即为约束最优解；
[0092]
若直线l1与直线v＝1交于(0，1)左侧，则约束最优解为(0，1)。
[0093]
2.3.3结合附图8所示，若全局最优解在区域3上，全局最优解对应可行域边界的可视边界为线段(0，1)到(1，1)再到(1，0)的部分；
[0094]
计算直线l1与直线v＝1交点，
[0095]
若直线l1与直线v＝1交于(0，1)左侧，则约束最优解为(0，1)；
[0096]
若直线l1与直线v＝1交于(0,1)和(1,1)之间，则直线l1与直线v＝1 的交点即为约束最优解；
[0097]
若直线l1与直线v＝1交于(1，1)右侧，则计算l2与直线u＝1交点；若直线l2与直线u＝1交于(1,0)和(1,1)之间，则约束最优解为直线l2与直线u＝1交点；若直线l2与直线u＝1交于(1,0)下方，则约束最优解为(1,0)。
[0098]
2.3.4结合附图9所示，若全局最优解在区域4上，全局最优解对应可行域边界的可视边界为线段(0，0)到(0，1)；
[0099]
计算直线l2与直线u＝0交点，
[0100]
若直线l2与直线u＝0交于(0，1)上方，则约束最优解为(0，1)；
[0101]
若直线l2与直线u＝0交于(0,0)和(0,1)之间，则直线l2与直线u＝0 的交点即为约束最优解；
[0102]
若直线l2与直线u＝0交于(0，0)下方，则约束最优解为(0,0)。
[0103]
2.3.5结合附图10所示，若全局最优解在区域5上，即在可行域内，则此时约束最优解等于全局最优解。
[0104]
2.3.6结合附图11所示，若全局最优解在区域6上，全局最优解对应可行域边界的可视边界为线段(1，0)到(1，1)；
[0105]
计算直线l2与直线u＝1交点，
[0106]
若直线l2与直线u＝1交于(1，1)上方，则约束最优解为(1，1)；
[0107]
若直线l2与直线u＝1交于(1,0)和(1,1)之间，则直线l2与直线u＝1 的交点即为约束最优解；
[0108]
若直线l2与直线u＝1交于(1，0)下方，则约束最优解为(1,0)。
[0109]
2.3.7结合附图12所示，若全局最优解在区域7上，全局最优解对应可行域边界的可视边界为线段(0，1)到(0，0)再到(1，0)的部分；
[0110]
计算直线l1与直线v＝0交点，
[0111]
若直线l1与直线v＝0交于(1，0)右侧，则约束最优解为(1，0)；
[0112]
若直线l1与直线v＝0交于(0,0)和(1,0)之间，则直线l1与直线v＝0 的交点即为约束最优解；
[0113]
若直线l1与直线v＝0交于(0，0)左侧，则计算l2与直线u＝0交点；若直线l2与直线u＝0交于(0,0)和(0,1)之间，则约束最优解为直线l2与直线u＝0交点；若直线l2与直线u＝0交于(0,1)上方，则约束最优解为(0，1)。
[0114]
2.3.8结合附图13所示，若全局最优解在区域8上，全局最优解对应可行域边界的可视边界为线段(0，0)到(1，0)；
[0115]
计算直线l1与直线v＝0交点，
[0116]
若直线l1与直线v＝0交于(0，0)左侧，则约束最优解为(0，0)；
[0117]
若直线l1与直线v＝0交于(0,0)和(1,0)之间，则直线l1与直线v＝0 的交点即为约束最优解；
[0118]
若直线l1与直线v＝1交于(1，0)右侧，则约束最优解为(1,0)。
[0119]
2.3.9结合附图14所示，若全局最优解在区域9上，全局最优解对应可行域边界的可视边界为线段(0，0)到(1，0)再到(1，1)的部分；
[0120]
计算直线l1与直线v＝0交点，
[0121]
若直线l1与直线v＝0交于(0，0)左侧，则约束最优解为(0，0)；
[0122]
若直线l1与直线v＝0交于(0,0)和(1,0)之间，则直线l1与直线v＝0 的交点即为约束最优解；
[0123]
若直线l1与直线v＝0交于(1，0)右侧，则计算l2与直线u＝1交点；若直线l2与直线u＝1交于(1,0)和(1,1)之间，则约束最优解为直线l2与直线u＝1交点；若直线l2与直线u＝1交于(1,1)上方，则约束最优解为(1，1)。
[0124]
此外，全局最优解对可行域的可视边界应该满足如下条件，全局最优解与可视边界上点的连线与可行域其他边界不相交，可行域如图10中区域 5所示。并且，在全局最优解位于可行域外时，所得约束最优解一定在全局最优解对可行域的可视边界上。
[0125]
3.利用能量函数和约束最优解参数值，计算出线段距离；
[0126]
3.1若约束最优解在可行域内，则线段距离为0；
[0127]
3.2若约束最优解在可行域边界上，则将约束最优解(uc,vc)带入到能量函数e(u,v)中，获取最优距离能量：
[0128]e*
＝e(uc,vc)
[0129]
其中，e
*
表示最优距离能量，uc,vc分别代表约束最优解对应的参数值， e为距离能量函数；
[0130]
3.3通过能量函数计算线段距离：
[0131][0132]
其中，d
*
为两待求交线段之间距离，uc,vc为求取的约束最优解，e为距离能量函数。
[0133]
本实施例还提供了基于最优化能量求解线段距离系统，能量函数求解模块，偏导数求解模块和距离计算模块；
[0134]
能量函数求解模块用于对线段距离问题构造能量函数，并求全局最优解；
[0135]
偏导数求解模块运用全局最优解和能量函数对各参数的偏导数关系，得到约束最优解位置；
[0136]
距离计算模块利用能量函数和约束最优解的参数值，计算线段距离。
[0137]
本实施例还提供了终端设备，包括存储器、处理器以及计算机程序，计算机程序存储在存储器中并在处理器上运行，处理器执行计算机程序时实现上述基于最优化能量求解线段距离方法的步骤。
[0138]
在本实施例的描述中，需要说明的是，本领域技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令控制装置来完成，所述的程序可存储于一计算机可读取的存储介质中，所述程序在执行时可包括如上述各方法实施例的流程，其中所述的存储介质可为存储器、磁盘、光盘等。
[0139]
虽然本发明披露如上，但本发明并非限定于此。任何本领域技术人员，在不脱离本发明的精神和范围内，均可作各种更动与修改，因此本发明的保护范围应当以权利要求所限定的范围为准。
[0140]
最后，还需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个
……”
限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。
[0141]
本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。
[0142]
对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。
技术特征：1.基于最优化能量求解线段距离方法，其特征在于，包括以下步骤：对线段距离问题构造能量函数，并求全局最优解；运用所述全局最优解和所述能量函数对各参数的偏导数关系，得到约束最优解位置；利用所述能量函数和所述约束最优解的参数值，计算线段距离。2.根据权利要求1所述的基于最优化能量求解线段距离方法，其特征在于，构造能量函数包括以下步骤：建立待计算距离线段的信息，c1(p1，p2)，c2(p3，p4)，c1，c2分别表示待计算距离的两线段，p1，p2为线段c1的两端点，p3，p4为线段c2的两端点；利用直线参数表示方法，分别表示线段c1，c2上任意点的位置：p
u
＝(1-u)p1+up2，p
v
＝(1-v)p3+vp4，p
u
，p
v
分别表示线段c1，c2上任意一点，u为p
u
在线段c1上位置的参数，v为p
v
在线段c2上位置的参数；通过p
u
，p
v
的距离建立两线段距离的所述能量方程：e＝((1-u)p1+up2)((1-u)p1+up2)
t
，e表示构造的所述能量函数。3.根据权利要求2所述的基于最优化能量求解线段距离方法，其特征在于，对所述能量函数求全局最优解的包括以下步骤：分别计算所述能量函数e(u，v)对u，v的偏导数等于0的直线：l1表示能量e(u，v)对u偏导数等于0的直线，l2表示能量e(u，v)对v偏导数等于0的直线；计算直线l1，l2的交点，交点记作x
*
＝(u
*
，v
*
)，交点对应的参数值u
*
，v
*
为所述全局最优解。4.根据权利要求1所述的基于最优化能量求解线段距离方法，其特征在于，获得所述约束最优解位置包括以下步骤：在参数域(u，v)上依据可行域边界，将所述参数域划分为九个区域；判断所述全局最优解在所述参数域区域划分中的位置；利用所述全局最优解在所述参数域中的位置，判断所述全局最优解点对于可行域的可视边界；计算直线l1，l2与所述可视边界的交点，通过交点得到所述约束最优解对应位置及其对应的参数值u
c
，v
c
。5.根据权利要求4所述的基于最优化能量求解线段距离方法，其特征在于，所述全局最优解对可行域的所述可视边界应满足如下条件，所述全局最优解与所述可视边界上点的连线与可行域其他边界不相交。6.根据权利要求4所述的基于最优化能量求解线段距离方法，其特征在于，当所述全局最优解位于可行域外时，所述约束最优解一定位于所述全局最优解对可行域的所述可视边界上；当所述全局最优解位于可行域内时，所述约束最优解等于所述全局最优解。7.根据权利要求1所述的基于最优化能量求解线段距离方法，其特征在于，计算线段距离包括以下步骤：当所述约束最优解在可行域内时，线段距离为0；
当所述约束最优解在可行域边界上时，将所述约束最优解(u
c
，v
c
)带入到所述能量函数e(u，v)中，获取最优距离能量e
*
＝e(u
c
，v
c
)，其中e
*
表示最优距离能量，u
c
，v
c
分别代表所述约束最优解对应的参数值；通过所述能量函数计算线段距离，d
*
为两线段之间待求距离。8.基于最优化能量求解线段距离系统，其特征在于，包括构造能量函数模块，全局最优解求解模块、约束最优解求解模块和线段距离求解模块；所述构造能量函数模块，利用参数方程表示线段上任意点，并构造线段距离问题的能量函数；所述全局最优解求解模块，计算所述能量函数对参数u，v的偏导数等于零的直线l1，l2，并通过计算两直线l1，l2的交点得到全局最优解；所述约束最优解求解模块，利用所述全局最优解在参数域上的位置，判断可行域对于所述全局最优解的可视边界，通过计算l1，l2对与所述可视边界的交点，得到约束最优解的值；所述线段距离求解模块，利用所述约束最优解的值和所述能量函数，判断所述约束最优解的区域位置，通过代入所述约束最优解到能量函数得到线段的距离。9.终端设备，包括存储器、处理器以及计算机程序，所述计算机程序存储在所述存储器中并在所述处理器上运行，其特征在于，所述处理器执行所述计算机程序时实现权利要求1至7任一所述基于最优化能量求解线段距离方法的步骤。
技术总结本发明提供了基于最优化能量求解线段距离方法、系统及终端设备，通过对线段距离问题构造能量函数，得到全局最优解；利用全局最优解和能量函数对各参数的偏导数关系，得到约束最优解位置；根据所述能量函数和所述约束最优解的参数值，计算出线段距离。本发明利用直线求交点代替点距离的计算，降低了问题需要进行的乘法次数，有效的降低了计算所需时间，在大量调用求解直线距离的EDA(电子设计自动化)软件中，速度能够得到明显的提升，具有速度快、通用性强、易于实现等优点。易于实现等优点。易于实现等优点。
技术研发人员：李伯宇 杨义军 曾薇 张航城 杜阿安
受保护的技术使用者：中设数字技术股份有限公司
技术研发日：2021.12.24
技术公布日：2022/7/4
