王遵義 仲梁維

摘? 要：對(duì)于熱流道系統(tǒng)，將軟管改為硬管可以節(jié)約成本，同時(shí)也提高了其外觀及品質(zhì)。但是，硬管的手工折彎導(dǎo)致裝配成本更高，因此基于熱流道3D模型開(kāi)發(fā)一款插件，能夠在三維軟件中自動(dòng)對(duì)熱流道三維模型提取特征，程序自動(dòng)生成硬管管道的最優(yōu)路徑。利用VB.NET對(duì)Solidworks進(jìn)行二次開(kāi)發(fā)，提取熱流道系統(tǒng)的框架特征，運(yùn)用迪杰斯特拉算法求解最短路徑，最后將最短路徑坐標(biāo)以表格的形式顯示在三維軟件中。

關(guān)鍵詞：特征提取;迪杰斯特拉算法;最短路徑

中圖分類(lèi)號(hào)：TP391.7? ? ?文獻(xiàn)標(biāo)識(shí)碼：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）

近幾年，由于計(jì)算機(jī)技術(shù)的高速發(fā)展，各種軟件和算法層出不窮，未來(lái)人工智能將大有作為[1]。而人工智能應(yīng)用的基礎(chǔ)是對(duì)智能算法的深入研究，其中最短路徑問(wèn)題對(duì)各行各業(yè)有著深入的影響，比如地圖和智能導(dǎo)航系統(tǒng)都需要使用智能算法解決最短路徑的問(wèn)題[2]。

目前熱流道系統(tǒng)軟管的成本比較高，而硬管的成本相對(duì)較低，且使用壽命更長(zhǎng)、更可靠，同時(shí)提高了熱流道系統(tǒng)的外觀和品質(zhì)。因此將熱流道系統(tǒng)軟管換成硬管不僅可以節(jié)約成本，而且保證了熱流道系統(tǒng)的品質(zhì)。但是目前的熱流道上的硬管都是采用折彎的方式進(jìn)行裝配，雖然硬管的成本低，但是裝配手工折彎的時(shí)間更長(zhǎng)，從而導(dǎo)致裝配成本增加。因此，利用軟件自動(dòng)計(jì)算并生成熱流道系統(tǒng)硬管的最短路徑，然后直接加工硬管管道，從而跳過(guò)手動(dòng)折彎裝配環(huán)節(jié)，這樣既可以節(jié)約成本，又可以提高熱流道系統(tǒng)的品質(zhì)，增加使用壽命。所以利用軟件和智能算法自動(dòng)計(jì)算并生成硬管管道的最短路徑就顯得尤為重要[3]。

2? ?特征提取（Feature extraction）

利用三維軟件Solidworks打開(kāi)熱流道系統(tǒng)的裝配體文件，對(duì)熱流道系統(tǒng)進(jìn)行特征提取，獲得所需要的點(diǎn)坐標(biāo)和框架，并將數(shù)據(jù)存儲(chǔ)到軟件中。特征提取的工作流程圖如圖1所示。

2.1? ?讀取裝配體文件

對(duì)于熱流道系統(tǒng)，首先需要用三維軟件Solidworks打開(kāi)，然后對(duì)Solidworks進(jìn)行二次開(kāi)發(fā)，讀取當(dāng)前已打開(kāi)的裝配體文件。這里應(yīng)用VB.NET程序語(yǔ)言對(duì)Solidworks進(jìn)行二次開(kāi)發(fā)，首先要獲得Solidworks的接口，連接成功后，Solidworks一共有三種文件類(lèi)型：零件（PartDoc）、裝配體（AssemblyDoc）和工程圖（DrawingDoc）。這里需要讀取的是裝配體（AssemblyDoc）文件的名稱(chēng)、屬性和部件[4]。

2.2? ?遍歷特征樹(shù)

每個(gè)熱流道系統(tǒng)裝配體都有幾十個(gè)甚至上百個(gè)部件，首先需要找到包含目標(biāo)草圖的部件，因?yàn)榘繕?biāo)草圖的部件有通用的名稱(chēng)，可以根據(jù)名稱(chēng)找到目標(biāo)部件。每個(gè)部件又有上百個(gè)特征，需要遍歷目標(biāo)部件的特征樹(shù)。判斷每個(gè)特征中是否含有草圖特征，如果沒(méi)有草圖特征則繼續(xù)遍歷下一個(gè)特征;如果含有草圖特征則判斷該草圖特征是否為目標(biāo)草圖。根據(jù)目標(biāo)草圖中草圖點(diǎn)和草圖線段之間特有的關(guān)系，將目標(biāo)草圖從眾多特征中篩選出來(lái)。

2.3? ?獲得草圖點(diǎn)

提取目標(biāo)草圖中的草圖點(diǎn)并且將草圖點(diǎn)按照框架的走勢(shì)進(jìn)行排序，最后儲(chǔ)存到程序中。如圖2所示，根據(jù)API函數(shù)獲得的草圖點(diǎn)是亂序的，需要程序自動(dòng)將獲得的草圖點(diǎn)按照如圖2標(biāo)識(shí)所示進(jìn)行排序并存儲(chǔ)到二維數(shù)組中。目標(biāo)草圖中草圖點(diǎn)的類(lèi)型有很多，比如線段端點(diǎn)、線段中點(diǎn)、單獨(dú)點(diǎn)等，可以根據(jù)草圖點(diǎn)的類(lèi)型和數(shù)量對(duì)草圖點(diǎn)進(jìn)行排序。將排序后得到的草圖點(diǎn)三個(gè)坐標(biāo)值存儲(chǔ)到二維數(shù)組中。

3? ?迪杰斯特拉算法（Dijkstra）

3.1? ?算法概述

迪杰斯特拉（Dijkstra）算法是典型的求解單源最短路徑的一種算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑。迪杰斯特拉算法的核心是循環(huán)遍歷除了起點(diǎn)之外的其他所有節(jié)點(diǎn)，并計(jì)算它們到起點(diǎn)的距離，根據(jù)排序計(jì)算出距離起點(diǎn)最近的節(jié)點(diǎn)并存儲(chǔ)到起點(diǎn)所在的集合中[5]。這是遍歷循環(huán)的第一層，算法會(huì)遍歷循環(huán)計(jì)算除起點(diǎn)之外集合中所有的節(jié)點(diǎn)，每計(jì)算一個(gè)節(jié)點(diǎn)，都需要排序計(jì)算出距離起點(diǎn)最近的節(jié)點(diǎn)并存儲(chǔ)到起點(diǎn)所在的集合中。

3.2? ?算法原理

在圖論中有一種圖叫帶權(quán)有向圖，帶權(quán)有向圖最常見(jiàn)的問(wèn)題是求解兩點(diǎn)之間最短路徑[6]，迪杰斯特拉算法是最典型的求解帶權(quán)有向圖最短路徑問(wèn)題的算法，很多其他求解圖論中最短路徑的算法都是迪杰斯特拉算法的變體。

首先，假設(shè)表示帶權(quán)有向圖的集合為F=（I，D），其中I表示有向圖中節(jié)點(diǎn)的集合，D表示各節(jié)點(diǎn)的權(quán)重[7]。把節(jié)點(diǎn)集合I分成兩組，一組為Q，表示已經(jīng)求出的最短路徑節(jié)點(diǎn)的集合，起初集合Q只有一個(gè)起點(diǎn);另一組為Z，表示除Q外，集合I中剩余的節(jié)點(diǎn)集合。在求解最短路徑時(shí)，每求得一個(gè)最短路徑的節(jié)點(diǎn)，都將該節(jié)點(diǎn)加入集合Q中，并將該節(jié)點(diǎn)從集合Z中刪除，直到遍歷循環(huán)集合Z中所有的節(jié)點(diǎn)，算法結(jié)束。在將計(jì)算出的節(jié)點(diǎn)從集合Z中移動(dòng)到集合Q時(shí)，需要始終保持起點(diǎn)到Q各節(jié)點(diǎn)的最短路徑長(zhǎng)度不大于起點(diǎn)到集合Z中各點(diǎn)的最短路徑長(zhǎng)度。迪杰斯特拉算法原理流程圖如圖3所示。

4? ?最短路徑（Shortest path）

4.1? ?確定起點(diǎn)、終點(diǎn)坐標(biāo)和方向

計(jì)算最短路徑時(shí)，首先需要確定起點(diǎn)和終點(diǎn)。在熱流道系統(tǒng)中分為油路和水路，本文只研究油路的走勢(shì)和最短路徑。一般來(lái)說(shuō)，油路都是從一個(gè)電磁閥的接口連接到另一個(gè)電磁閥或者控制閥的接口。在提取特征時(shí)，獲得的是電磁閥接口草圖的原點(diǎn)坐標(biāo)和接口的方向向量，因此需要根據(jù)點(diǎn)坐標(biāo)和方向向量計(jì)算與草圖框架的交點(diǎn)，從而確定最短路徑的起點(diǎn)和終點(diǎn)。

起點(diǎn)的坐標(biāo)和方向向量如圖4所示，根據(jù)點(diǎn)坐標(biāo)和方向向量可以構(gòu)建起點(diǎn)射線的方程，然后根據(jù)線段端點(diǎn)坐標(biāo)構(gòu)建線段1→2、2→3、3→4、4→5的方程。由平面幾何知識(shí)可知，平面內(nèi)任意兩條不平行的直線必有交點(diǎn)，如圖4所示，交點(diǎn)1和交點(diǎn)2即需要求解的點(diǎn)。

求解步驟：

（1）構(gòu)建起點(diǎn)射線方程和框架四條線段的方程。

（2）將方程系數(shù)存儲(chǔ)到數(shù)組中，建立行列式。

（3）由線性代數(shù)行列式知識(shí)可得，行列式可以表示方程，對(duì)行列式求解，所得的解即是兩條直線的交點(diǎn)坐標(biāo)。

（4）如圖4所示，求解方程得到交點(diǎn)1和交點(diǎn)2，但是只有一個(gè)交點(diǎn)是我們需要的交點(diǎn)坐標(biāo)。

（5）將交點(diǎn)1和交點(diǎn)2分別和起點(diǎn)建立方程，判斷起點(diǎn)→交點(diǎn)1的方向與起點(diǎn)的方向向量方向是否一致，如果一致則是我們需要的交點(diǎn);如果不一致，則運(yùn)用同樣的方法對(duì)交點(diǎn)2進(jìn)行判斷。交點(diǎn)到起點(diǎn)的方向與起點(diǎn)方向向量的方向一致的交點(diǎn)才是我們需要的，實(shí)際計(jì)算過(guò)程中，由于草圖框架比較復(fù)雜，求得的交點(diǎn)往往不止兩個(gè)，方向一致的交點(diǎn)也可能有不止一個(gè)。

（6）當(dāng)方向一致的交點(diǎn)個(gè)數(shù)大于一個(gè)時(shí)，計(jì)算所有交點(diǎn)到起點(diǎn)的距離，并且運(yùn)用冒泡法對(duì)距離進(jìn)行從小到大排序，距離最近的交點(diǎn)是我們需要的點(diǎn)。

4.2? ?計(jì)算最短路徑

首先計(jì)算出熱流道系統(tǒng)一共有多少條管道，然后利用循環(huán)語(yǔ)句，循環(huán)次數(shù)為管道的條數(shù)，循環(huán)體為生成管道最短路徑。

計(jì)算步驟：

（1）輸入特征提取的目標(biāo)草圖框架。

（2）輸入起點(diǎn)坐標(biāo)、終點(diǎn)坐標(biāo)及管道數(shù)。

（3）編寫(xiě)迪杰斯特拉算法程序，作為循環(huán)體。

（4）輸出最佳路徑坐標(biāo)，并存儲(chǔ)到數(shù)組中。

（5）將最佳路徑系列坐標(biāo)顯示在DataGridView中。

4.3? ?結(jié)果評(píng)估

給定起點(diǎn)和終點(diǎn)，測(cè)試程序自動(dòng)生成的最短路徑測(cè)試結(jié)果如表1所示。Path_name是最短路徑的名稱(chēng)，越復(fù)雜的熱流道系統(tǒng)，管道連接的數(shù)量越多，因此加以命名，以便區(qū)分;Point_name是點(diǎn)的名字，便于人工檢測(cè)最短路徑是否正確;X、Y、Z是點(diǎn)的三個(gè)坐標(biāo);Type是點(diǎn)的類(lèi)型，用于程序識(shí)別點(diǎn)的種類(lèi)。經(jīng)過(guò)檢測(cè)，程序獲得的最短路徑與人工設(shè)計(jì)的路徑完全吻合，結(jié)果正確。

5? ?結(jié)論（Conclusion）

本文基于熱流道系統(tǒng)三維模型，對(duì)三維軟件Solidworks進(jìn)行二次開(kāi)發(fā)，開(kāi)發(fā)一個(gè)插件，能夠?qū)崿F(xiàn)在三維軟件中自動(dòng)計(jì)算并生成硬管管道最短路徑，最后將最短路徑結(jié)果以表格（DataGridView）的形式顯示在三維軟件中。最短路徑的獲得是根據(jù)圖論中典型的單源最短路徑算法——迪杰斯特拉算法（Dijkstra）實(shí)現(xiàn)的[8]。自動(dòng)生成的硬管管道熱流道系統(tǒng)不僅降低了系統(tǒng)的成本，而且提高了系統(tǒng)的質(zhì)量和品質(zhì)，同時(shí)降低了工人安裝管道的復(fù)雜程度，并且硬管管道相比軟管也更加美觀。

參考文獻(xiàn)（References）

[1] 趙美勇，宋思睿.三種最短路算法的比較[J].數(shù)碼世界，2019（06）：77.

[2] 劉汝佳.算法競(jìng)賽入門(mén)經(jīng)典[M].2版.北京：清華大學(xué)出版社，2014：56.

[3] 賴(lài)志剛.求解最短路問(wèn)題的一個(gè)計(jì)算機(jī)算法解析[J].中國(guó)新通信，2019，21（20）：133.

[4] 曾慶紅，楊橋艷.最短路問(wèn)題算法綜述[J].保山學(xué)院學(xué)報(bào)，2019，38（05）：44-46.

[5] （美）CORMEN T H， LEISERSON C E， RIVEST R L，等.算法導(dǎo)論[M].殷建平，徐云，王剛，等，譯.北京：機(jī)械工業(yè)出版社，2012：45-46.

[6] （美）SEDGEWICK R， WAYNE K.算法[M].4版.謝路云，譯.北京：人民郵電出版社，2012：23-25.

[7] 吳昕宇，羅雪穎.基于Dijkstra算法的旅游路線規(guī)劃研究[J].數(shù)碼世界，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.

作者簡(jiǎn)介：

王遵義（1993-），男，碩士生.研究領(lǐng)域：計(jì)算機(jī)輔助設(shè)計(jì)與智能制造.

仲梁維（1962-），男，碩士，教授.研究領(lǐng)域：計(jì)算機(jī)輔助設(shè)計(jì)，企業(yè)信息化.本文通訊作者.