基于熱流道系統(tǒng)硬管鋪設(shè)的最短路徑方法研究

王遵義 仲梁維

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

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

中圖分類號：TP391.7? ? ?文獻(xiàn)標(biāo)識碼：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ī)技術(shù)的高速發(fā)展，各種軟件和算法層出不窮，未來人工智能將大有作為[1]。而人工智能應(yīng)用的基礎(chǔ)是對智能算法的深入研究，其中最短路徑問題對各行各業(yè)有著深入的影響，比如地圖和智能導(dǎo)航系統(tǒng)都需要使用智能算法解決最短路徑的問題[2]。

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

2? ?特征提?。‵eature extraction）

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

2.1? ?讀取裝配體文件

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

2.2? ?遍歷特征樹

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

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

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

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

3.1? ?算法概述

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

3.2? ?算法原理

在圖論中有一種圖叫帶權(quán)有向圖，帶權(quán)有向圖最常見的問題是求解兩點(diǎn)之間最短路徑[6]，迪杰斯特拉算法是最典型的求解帶權(quá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只有一個起點(diǎn);另一組為Z，表示除Q外，集合I中剩余的節(jié)點(diǎn)集合。在求解最短路徑時，每求得一個最短路徑的節(jié)點(diǎn)，都將該節(jié)點(diǎn)加入集合Q中，并將該節(jié)點(diǎn)從集合Z中刪除，直到遍歷循環(huán)集合Z中所有的節(jié)點(diǎn)，算法結(jié)束。在將計算出的節(jié)點(diǎn)從集合Z中移動到集合Q時，需要始終保持起點(diǎn)到Q各節(jié)點(diǎn)的最短路徑長度不大于起點(diǎn)到集合Z中各點(diǎn)的最短路徑長度。迪杰斯特拉算法原理流程圖如圖3所示。

4? ?最短路徑（Shortest path）

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

計算最短路徑時，首先需要確定起點(diǎn)和終點(diǎn)。在熱流道系統(tǒng)中分為油路和水路，本文只研究油路的走勢和最短路徑。一般來說，油路都是從一個電磁閥的接口連接到另一個電磁閥或者控制閥的接口。在提取特征時，獲得的是電磁閥接口草圖的原點(diǎn)坐標(biāo)和接口的方向向量，因此需要根據(jù)點(diǎn)坐標(biāo)和方向向量計算與草圖框架的交點(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的方程。由平面幾何知識可知，平面內(nèi)任意兩條不平行的直線必有交點(diǎn)，如圖4所示，交點(diǎn)1和交點(diǎn)2即需要求解的點(diǎn)。

求解步驟：

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

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

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

（4）如圖4所示，求解方程得到交點(diǎn)1和交點(diǎn)2，但是只有一個交點(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)用同樣的方法對交點(diǎn)2進(jìn)行判斷。交點(diǎn)到起點(diǎn)的方向與起點(diǎn)方向向量的方向一致的交點(diǎn)才是我們需要的，實際計算過程中，由于草圖框架比較復(fù)雜，求得的交點(diǎn)往往不止兩個，方向一致的交點(diǎn)也可能有不止一個。

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

4.2? ?計算最短路徑

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

計算步驟：

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

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

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

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

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

4.3? ?結(jié)果評估

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

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

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

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

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

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

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

[4] 曾慶紅，楊橋艷.最短路問題算法綜述[J].保山學(xué)院學(xué)報，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.

作者簡介：

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

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