(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111603866.8 (22)申请日 2021.12.24 (71)申请人 中设数字技 术股份有限公司 地址 430056 湖北省武汉市汉南区武汉经 济技术开发区华人汇和科技园 （华中 智谷） 项目一期工程第E4栋10层1号房 (72)发明人 李伯宇　杨义军　曾薇　张航城　 杜阿安　 (74)专利代理 机构 北京中理通专利代理事务所 (普通合伙) 11633 专利代理师 郭金鑫 (51)Int.Cl. G06F 30/30(2020.01) G06F 30/27(2020.01) (54)发明名称 基于最优化能量求解线 段距离方法、 系统及 终端设备 (57)摘要 本发明提供了基于最优化能量求解线段距 离方法、 系统及终端设备， 通过对线段距离问题 构造能量函数， 得到全局最优解； 利用全局最优 解和能量函数对 各参数的偏导数关系， 得到约束 最优解位置； 根据所述能量函数和所述约束最优 解的参数值， 计算出线段距离。 本发明利用直线 求交点代 替点距离的计算， 降低了问题需要进行 的乘法次数， 有效的降低了计算所需时间， 在大 量调用求解直线距离的EDA(电子设计自动化)软 件中， 速度能够得到明显的提升， 具有速度快、 通 用性强、 易于实现等优点。 权利要求书2页 说明书7页 附图7页 CN 114707442 A 2022.07.05 CN 114707442 A 1.基于最优化能量 求解线段距离方法， 其特 征在于， 包括以下步骤： 对线段距离问题构造能量 函数， 并求全局最优解； 运用所述全局最优解和所述能量 函数对各参数的偏导数关系， 得到约束最优解 位置； 利用所述能量 函数和所述约束最优解的参数值， 计算线段距离 。 2.根据权利要求1所述的基于最优化 能量求解线段距离方法， 其特征在于， 构造能量函 数包括以下步骤： 建立待计算距离线段的信息， C1(p1， p2)， C2(p3， p4)， C1， C2分别表示待计算距离的两线 段， p1， p2为线段C1的两端点， p3， p4为线段C2的两端点； 利用直线参数表示方法， 分别表示线段C1， C2上任意点的位置： pu＝(1‑u)p1+up2， pv＝(1‑v)p3+vp4， pu， pv分别表示线段C1， C2上任意一点， u为pu在线段 C1上位置的参数， v为pv在线段C2上位置的参数； 通过pu， pv的距离建立两线段距离的所述能量方程： 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与所述可视边界的交点， 通过交点得到所述约束最优解对应位置及其对 应的参数值uc， vc。 5.根据权利要求4所述的基于最优化 能量求解线段距离方法， 其特征在于， 所述全局最 优解对可行域的所述可视边界应满足如下条件， 所述全局最优解与所述可视边界上点的连 线与可行域其他边界不相交。 6.根据权利要求4所述的基于最优化 能量求解线段距离方法， 其特征在于， 当所述全局 最优解位于可行域外时， 所述约束最优解一定位于所述全局最优解对可行域的所述可视边 界上； 当所述全局最优解 位于可行域内时， 所述约束最优解 等于所述全局最优解。 7.根据权利要求1所述的基于最优化 能量求解线段距离方法， 其特征在于， 计算线段距 离包括以下步骤： 当所述约束最优解在可 行域内时， 线段距离为0；权　利　要　求　书 1/2 页 2 CN 114707442 A 2当所述约束最优解在可行域边界上时， 将所述约束最优解(uc， vc)带入到所述能量函数 E(u， v)中， 获取最优距离能量E*＝E(uc， vc)， 其中E*表示最优距离能量， uc， vc分别代表所述 约束最优解对应的参数值； 通过所述能量 函数计算线段距离， d*为两线段之间待求距离 。 8.基于最优化能量求解线段距离系统， 其特征在于， 包括构造能量函数模块， 全局最优 解求解模块、 约束最优解 求解模块和线段距离求 解模块； 所述构造能量函数模块， 利用参数方程表示线段上任意点， 并构造线段距离问题的能 量函数； 所述全局最优解求解模块， 计算所述能量函数对参数u， v的偏 导数等于零的直线L1， L2， 并通过计算两直线L1， L2的交点得到全局最优解； 所述约束最优解求解模块， 利用所述全局最优解在参数域上的位置， 判断可行域对于 所述全局最优解的可视边界， 通过计算L1， L2对与所述可视边界的交点， 得到约束最优解的 值； 所述线段距离求解模块， 利用所述约束最优解的值和所述能量函数， 判断所述约束最 优解的区域 位置， 通过代入所述约束最优解到能量 函数得到线段的距离 。 9.终端设备， 包括存储器、 处理器以及计算机程序， 所述计算机程序存储在所述存储器 中并在所述处理器上运行， 其特征在于， 所述处理器执行所述计算机程序时实现权利要求 1 至7任一所述基于最优化能量 求解线段距离方法的步骤。权　利　要　求　书 2/2 页 3 CN 114707442 A 3