王遵义 仲梁维

摘  要：对于热流道系统，将软管改为硬管可以节约成本，同时也提高了其外观及品质。但是，硬管的手工折弯导致装配成本更高，因此基于热流道3D模型开发一款插件，能够在三维软件中自动对热流道三维模型提取特征，程序自动生成硬管管道的最优路径。利用VB.NET对Solidworks进行二次开发，提取热流道系统的框架特征，运用迪杰斯特拉算法求解最短路径，最后将最短路径坐标以表格的形式显示在三维软件中。

关键词：特征提取;迪杰斯特拉算法;最短路径

中图分类号：TP391.7     文献标识码：A

Research on the Shortest Path Method of Hard Pipe

Laying based on Hot Runner System

WANG Zunyi， ZHONG Liangwei

（University of Shanghai for Science and Technology， Shanghai 200093， China）

1270623490@qq.com; zlv@usst.edu.cn

Abstract： Replacing hoses of hot runner system with hard pipes can save costs and improve the appearance and quality of the hot runner system. However， manual bending of hard pipes leads to higher assembly costs. This paper proposes to develop a plug-in based on the three-dimensional （3D） model of the hot runner， which can automatically extract features from the 3D model of the hot runner in the 3D software and generate optimal path of hard pipes. VB.NET is used to re-develop Solidworks， frame features of the hot runner system are extracted， and Dijkstra's algorithm is used to solve the shortest path. Finally， the shortest path coordinates in the form of a table is displayed in the 3D software.

Keywords： feature extraction; Dijkstra's algorithm; shortest path

1   引言（Introduction）

近几年，由于计算机技术的高速发展，各种软件和算法层出不穷，未来人工智能将大有作为[1]。而人工智能应用的基础是对智能算法的深入研究，其中最短路径问题对各行各业有着深入的影响，比如地图和智能导航系统都需要使用智能算法解决最短路径的问题[2]。

目前热流道系统软管的成本比较高，而硬管的成本相对较低，且使用寿命更长、更可靠，同时提高了热流道系统的外观和品质。因此将热流道系统软管换成硬管不仅可以节约成本，而且保证了热流道系统的品质。但是目前的热流道上的硬管都是采用折弯的方式进行装配，虽然硬管的成本低，但是装配手工折弯的时间更长，从而导致装配成本增加。因此，利用软件自动计算并生成热流道系统硬管的最短路径，然后直接加工硬管管道，从而跳过手动折弯装配环节，这样既可以节约成本，又可以提高热流道系统的品质，增加使用寿命。所以利用软件和智能算法自动计算并生成硬管管道的最短路径就显得尤为重要[3]。

2   特征提取（Feature extraction）

利用三维软件Solidworks打开热流道系统的装配体文件，对热流道系统进行特征提取，获得所需要的点坐标和框架，并将数据存储到软件中。特征提取的工作流程图如图1所示。

2.1   读取装配体文件

对于热流道系统，首先需要用三维软件Solidworks打开，然后对Solidworks进行二次开发，读取当前已打开的装配体文件。这里应用VB.NET程序语言对Solidworks进行二次开发，首先要获得Solidworks的接口，连接成功后，Solidworks一共有三种文件类型：零件（PartDoc）、装配体（AssemblyDoc）和工程图（DrawingDoc）。这里需要读取的是装配体（AssemblyDoc）文件的名称、属性和部件[4]。

2.2   遍历特征树

每个热流道系统装配体都有几十个甚至上百个部件，首先需要找到包含目标草图的部件，因为包含目標草图的部件有通用的名称，可以根据名称找到目标部件。每个部件又有上百个特征，需要遍历目标部件的特征树。判断每个特征中是否含有草图特征，如果没有草图特征则继续遍历下一个特征;如果含有草图特征则判断该草图特征是否为目标草图。根据目标草图中草图点和草图线段之间特有的关系，将目标草图从众多特征中筛选出来。

2.3   获得草图点

提取目标草图中的草图点并且将草图点按照框架的走势进行排序，最后储存到程序中。如图2所示，根据API函数获得的草图点是乱序的，需要程序自动将获得的草图点按照如图2标识所示进行排序并存储到二维数组中。目标草图中草图点的类型有很多，比如线段端点、线段中点、单独点等，可以根据草图点的类型和数量对草图点进行排序。将排序后得到的草图点三个坐标值存储到二维数组中。

3   迪杰斯特拉算法（Dijkstra）

3.1   算法概述

迪杰斯特拉（Dijkstra）算法是典型的求解单源最短路径的一种算法，用于计算一个节点到其他节点的最短路径。迪杰斯特拉算法的核心是循环遍历除了起点之外的其他所有节点，并计算它们到起点的距离，根据排序计算出距离起点最近的节点并存储到起点所在的集合中[5]。这是遍历循环的第一层，算法会遍历循环计算除起点之外集合中所有的节点，每计算一个节点，都需要排序计算出距离起点最近的节点并存储到起点所在的集合中。

3.2   算法原理

在图论中有一种图叫带权有向图，带权有向图最常见的问题是求解两点之间最短路径[6]，迪杰斯特拉算法是最典型的求解带权有向图最短路径问题的算法，很多其他求解图论中最短路径的算法都是迪杰斯特拉算法的变体。

首先，假设表示带权有向图的集合为F=（I，D），其中I表示有向图中节点的集合，D表示各节点的权重[7]。把节点集合I分成两组，一组为Q，表示已经求出的最短路径节点的集合，起初集合Q只有一个起点;另一组为Z，表示除Q外，集合I中剩余的节点集合。在求解最短路径时，每求得一个最短路径的节点，都将该节点加入集合Q中，并将该节点从集合Z中删除，直到遍历循环集合Z中所有的节点，算法结束。在将计算出的节点从集合Z中移动到集合Q时，需要始终保持起点到Q各节点的最短路径长度不大于起点到集合Z中各点的最短路徑长度。迪杰斯特拉算法原理流程图如图3所示。

4   最短路径（Shortest path）

4.1   确定起点、终点坐标和方向

计算最短路径时，首先需要确定起点和终点。在热流道系统中分为油路和水路，本文只研究油路的走势和最短路径。一般来说，油路都是从一个电磁阀的接口连接到另一个电磁阀或者控制阀的接口。在提取特征时，获得的是电磁阀接口草图的原点坐标和接口的方向向量，因此需要根据点坐标和方向向量计算与草图框架的交点，从而确定最短路径的起点和终点。

起点的坐标和方向向量如图4所示，根据点坐标和方向向量可以构建起点射线的方程，然后根据线段端点坐标构建线段1→2、2→3、3→4、4→5的方程。由平面几何知识可知，平面内任意两条不平行的直线必有交点，如图4所示，交点1和交点2即需要求解的点。

求解步骤：

（1）构建起点射线方程和框架四条线段的方程。

（2）将方程系数存储到数组中，建立行列式。

（3）由线性代数行列式知识可得，行列式可以表示方程，对行列式求解，所得的解即是两条直线的交点坐标。

（4）如图4所示，求解方程得到交点1和交点2，但是只有一个交点是我们需要的交点坐标。

（5）将交点1和交点2分别和起点建立方程，判断起点→交点1的方向与起点的方向向量方向是否一致，如果一致则是我们需要的交点;如果不一致，则运用同样的方法对交点2进行判断。交点到起点的方向与起点方向向量的方向一致的交点才是我们需要的，实际计算过程中，由于草图框架比较复杂，求得的交点往往不止两个，方向一致的交点也可能有不止一个。

（6）当方向一致的交点个数大于一个时，计算所有交点到起点的距离，并且运用冒泡法对距离进行从小到大排序，距离最近的交点是我们需要的点。

4.2   计算最短路径

首先计算出热流道系统一共有多少条管道，然后利用循环语句，循环次数为管道的条数，循环体为生成管道最短路径。

计算步骤：

（1）输入特征提取的目标草图框架。

（2）输入起点坐标、终点坐标及管道数。

（3）编写迪杰斯特拉算法程序，作为循环体。

（4）输出最佳路径坐标，并存储到数组中。

（5）将最佳路径系列坐标显示在DataGridView中。

4.3   结果评估

给定起点和终点，测试程序自动生成的最短路径测试结果如表1所示。Path_name是最短路径的名称，越复杂的热流道系统，管道连接的数量越多，因此加以命名，以便区分;Point_name是点的名字，便于人工检测最短路径是否正确;X、Y、Z是点的三个坐标;Type是点的类型，用于程序识别点的种类。经过检测，程序获得的最短路径与人工设计的路径完全吻合，结果正确。

5   结论（Conclusion）

本文基于热流道系统三维模型，对三维软件Solidworks进行二次开发，开发一个插件，能够实现在三维软件中自动计算并生成硬管管道最短路径，最后将最短路径结果以表格（DataGridView）的形式显示在三维软件中。最短路径的获得是根据图论中典型的单源最短路径算法——迪杰斯特拉算法（Dijkstra）实现的[8]。自动生成的硬管管道热流道系统不仅降低了系统的成本，而且提高了系统的质量和品质，同时降低了工人安装管道的复杂程度，并且硬管管道相比软管也更加美观。

参考文献（References）

[1] 赵美勇，宋思睿.三种最短路算法的比较[J].数码世界，2019（06）：77.

[2] 刘汝佳.算法竞赛入门经典[M].2版.北京：清华大学出版社，2014：56.

[3] 赖志刚.求解最短路问题的一个计算机算法解析[J].中国新通信，2019，21（20）：133.

[4] 曾庆红，杨桥艳.最短路问题算法综述[J].保山学院学报，2019，38（05）：44-46.

[5] （美）CORMEN T H， LEISERSON C E， RIVEST R L，等.算法导论[M].殷建平，徐云，王刚，等，译.北京：机械工业出版社，2012：45-46.

[6] （美）SEDGEWICK R， WAYNE K.算法[M].4版.谢路云，译.北京：人民邮电出版社，2012：23-25.

[7] 吴昕宇，罗雪颖.基于Dijkstra算法的旅游路线规划研究[J].数码世界，2019（07）：33-34.

[8] QU S X. Research on dynamic route guidance system based on comparison of shortest path algorithms[J]. International Core Journal of Engineering， 2020， 6（12）：12-14.

作者简介：

王遵义（1993-），男，硕士生.研究领域：计算机辅助设计与智能制造.

仲梁维（1962-），男，硕士，教授.研究领域：计算机辅助设计，企业信息化.本文通讯作者.