唐長鐵

AutoCAD作為當(dāng)前一種最通用的計(jì)算機(jī)輔助設(shè)計(jì)軟件，在測繪、規(guī)劃和制圖中得到廣泛應(yīng)用，當(dāng)前幾乎所有的城市規(guī)劃圖都是采用AutoCAD軟件進(jìn)行繪制的。ObjectARX是Autodesk公司針對AutoCAD平臺的二次開發(fā)推出的一個功能強(qiáng)大的軟件開發(fā)包，它支持面向?qū)ο缶幊蹋蚕鞟utoCAD的地址空間，與以往的AutoCAD開發(fā)工具AutoLisp和VBA開發(fā)的應(yīng)用程序相比，能更快地訪問AutoCAD圖形數(shù)據(jù)庫，大大提高應(yīng)用程序的運(yùn)行速度。

物流配送是現(xiàn)代物流系統(tǒng)的一個重要環(huán)節(jié)，合理選擇配送路徑，對加快配送速度、提高服務(wù)質(zhì)量、降低配送成本及增加經(jīng)濟(jì)效益都有較大影響。本文通過VC++和ObjectARX的結(jié)合實(shí)現(xiàn)在AutoCAD圖中直接提取道路數(shù)據(jù)，并確定兩點(diǎn)間最短路徑，為物流配送方案提供一種有價值的選擇。

1 算法基本思路

配送最短路徑的實(shí)現(xiàn)其主要解決的問題就是道路數(shù)據(jù)的提取和兩點(diǎn)間最短路徑的確定。在ObjectARX開發(fā)環(huán)境中，針對AutoCAD數(shù)據(jù)庫中的數(shù)據(jù)對象都有相應(yīng)的類存在，并且每個類都封裝了相應(yīng)的屬性和方法供用戶使用，利用相應(yīng)的類就可以實(shí)現(xiàn)在AutoCAD圖中直接提取道路數(shù)據(jù)。兩點(diǎn)最短路徑的確定是計(jì)算機(jī)科學(xué)與地理信息科學(xué)等領(lǐng)域研究的熱點(diǎn)，最短路徑算法有很多種，目前最具有代表性的有Dijkstra算法、A*算法和Floyd算法。本文通過格式化存儲提取的道路數(shù)據(jù)進(jìn)行相關(guān)運(yùn)算建立道路距離矩陣，改進(jìn)周文峰等提出的最短距離選擇模型，采用Floyd算法，實(shí)現(xiàn)兩點(diǎn)間最短路徑的確定。

2 實(shí)現(xiàn)算法

2.1 道路數(shù)據(jù)提取

AutoCAD是以數(shù)據(jù)庫的方式組織圖形數(shù)據(jù)的，存儲在數(shù)據(jù)庫中的數(shù)據(jù)都是以對象的形式存在。每一個實(shí)體對象在創(chuàng)建時數(shù)據(jù)庫都會分配一個唯一的ID號，并返回給用戶。通過使用一個對象ID，用戶可以獲得一個指向一個實(shí)際數(shù)據(jù)庫的指針，從而對對象執(zhí)行操作。因此通過獲取道路實(shí)體對象ID，就可以實(shí)現(xiàn)在道路實(shí)體對象上提取所需要的數(shù)據(jù)。在AutoCAD數(shù)據(jù)庫中，所有的可見幾何實(shí)體都存儲在模型空間塊表記錄中，因此只要遍歷這個塊表記錄便可獲得所有實(shí)體對象ID。在ObjectARX中，每個實(shí)體對象都有相應(yīng)的屬性和方法，利用相應(yīng)的方法就可以提到每個實(shí)體對象的坐標(biāo)及其各種屬性。

為了實(shí)現(xiàn)在AutoCAD圖形中直接提取道路，必須要求道路繪制在一個特定的圖層上，且用多段線繪制，那么提取道路的過程就是在模型空間塊表記錄中搜尋出處于特定圖層的多段線，然后調(diào)用多段線對象相應(yīng)的方法來獲取道路控制點(diǎn)數(shù)據(jù)。實(shí)現(xiàn)步驟如下:

第1步:道路ID的獲取。首先獲取當(dāng)前數(shù)據(jù)庫的對象，通過數(shù)據(jù)庫對象得到塊表對象，然后定義塊表記錄遍歷器，遍歷模型空間塊表記錄所有對象，獲取處于道路中心線圖層的所有實(shí)體ID。其主要實(shí)現(xiàn)代碼如下:

第2步:獲取道路控制點(diǎn)數(shù)據(jù)。為了建立道路關(guān)系所對應(yīng)的距離矩陣，需要獲取道路起點(diǎn)、終點(diǎn)、道路轉(zhuǎn)折點(diǎn)以及道路交點(diǎn)。其主要實(shí)現(xiàn)過程如下:

對道路轉(zhuǎn)折點(diǎn)的獲取，ObjectARX并沒有提供相應(yīng)的方法來實(shí)現(xiàn)，只提供了用來獲取頂點(diǎn)的方法，但頂點(diǎn)既包括轉(zhuǎn)折點(diǎn)同時也包括我們所不需要的點(diǎn)。這樣只能通過利用現(xiàn)有的方法來間接得到所需要的數(shù)據(jù)點(diǎn)。經(jīng)過分析發(fā)現(xiàn)在道路轉(zhuǎn)折點(diǎn)處，兩個方向的直線斜率是不相等的，利用這個特性，我們通過排除法就能得到多段線上所有轉(zhuǎn)折點(diǎn)的數(shù)據(jù)。通過以上兩個過程，所有的道路關(guān)鍵點(diǎn)數(shù)據(jù)已經(jīng)存儲到AcGePoint3dArray類型的一維數(shù)組中，其中每元素對應(yīng)著一條多段線上所有的控制點(diǎn)。

2.2 最短路徑實(shí)現(xiàn)

兩點(diǎn)間最短路徑的確定是計(jì)算機(jī)科學(xué)與地理信息科學(xué)等領(lǐng)域研究的熱點(diǎn)，到目前為止，前人已經(jīng)發(fā)展了多種算法，比較經(jīng)典的算法有Dijkstra算法、A*算法和Floyd算法。周文峰等根據(jù)上述算法提出了最短距離公交出行線路選擇模型，并實(shí)現(xiàn)兩個站點(diǎn)間最短距離確定。通過改進(jìn)上述模型如圖1所示，我們實(shí)現(xiàn)了在道路交通網(wǎng)中任意兩控制點(diǎn)間最短距離的確定。

圖1 改進(jìn)的兩點(diǎn)間最短距離確定模型

有了實(shí)現(xiàn)的基本思路后，這部分的主要工作就是在ARX豐富類庫的基礎(chǔ)上，結(jié)合VC++編程來完整地實(shí)現(xiàn)上述模型。實(shí)現(xiàn)步驟如下:

第1步:道路數(shù)據(jù)點(diǎn)格式化存儲。

通過道路數(shù)據(jù)提取，我們獲得了所有多段線的控制點(diǎn)，并將其按行存儲到AcGePoint3dArray類型的一維數(shù)組中。但考慮到這樣一種情況，即兩條多段線的交點(diǎn)有可能處于多段線的起點(diǎn)、終點(diǎn)或轉(zhuǎn)折點(diǎn)處，那么在前面提取到的數(shù)據(jù)點(diǎn)中就會重復(fù)提取，同時考慮到后面在建立直達(dá)距離矩陣時需將所有獲取到的道路數(shù)據(jù)按各自到起點(diǎn)的距離進(jìn)行排序，因此需要對提取的道路數(shù)據(jù)點(diǎn)進(jìn)行格式化存儲到AcGePoint3dArray數(shù)組中。部分實(shí)現(xiàn)代碼如下:

第2步:建立每條道路的直達(dá)距離矩陣。

利用循環(huán)結(jié)構(gòu)取出ptArray數(shù)組中的任意兩點(diǎn)，通過ptTotal數(shù)組來判斷是否是同一條多段線上相鄰兩點(diǎn)，如果是則調(diào)用相應(yīng)多段線求距離方法求出它們間的距離，輸出到直達(dá)距離矩陣中相應(yīng)的位置，如果不相鄰則在相應(yīng)位置輸出一個無窮大數(shù)。部分實(shí)現(xiàn)代碼如下:

第3步:構(gòu)造總的直達(dá)距離矩陣。

對所有多段線直達(dá)距離矩陣相應(yīng)元素進(jìn)行取小運(yùn)算，得到總的直達(dá)距離矩陣totalDistanceMatrix[Max］[Max］(Max為控制點(diǎn)個數(shù))。

第4步:建立任意兩點(diǎn)間最短距離矩陣。

對總的直達(dá)距離矩陣使用Floyd算法，得到任意兩點(diǎn)最短距離矩陣weight[Max］[Max］及任意兩點(diǎn)最短距離路線上所經(jīng)過的前一個控制點(diǎn)矩陣 path[Max］[Max］。

Floyd(totalDistanceMatrix，Max，weight，path);//調(diào)用 Floyd 算法給出道路控制點(diǎn)中的任意兩點(diǎn)，結(jié)合 weight[Max］[Max］和 path[Max］[Max］，就可以確定兩點(diǎn)間最短路徑依次經(jīng)過的控制點(diǎn)，也就確定了最短路徑。

3 結(jié)語

本文利用ObjectARX本身具有的技術(shù)特點(diǎn)，開發(fā)了相應(yīng)的ARX程序，實(shí)現(xiàn)了在AutoCAD圖形中提取道路數(shù)據(jù)，建立道路交通網(wǎng)的數(shù)據(jù)模型。通過改進(jìn)的最短距離選擇模型，實(shí)現(xiàn)了任意兩點(diǎn)間最短路徑的確定，從而可以為物流方案的選擇提供一個有價值的參考方案。但在實(shí)際中，物流方案的選擇需考慮的因素很多，如交通限制等，因此本程序還有待于進(jìn)一步完善。

[1]李國泰，王 祎，謝步瀛.圖形區(qū)域操作的ARX關(guān)鍵技術(shù)[J］.東華大學(xué)學(xué)報(自然科學(xué)版)，2007，33(3):367-370.

[2]徐 斐.基于VC++和ObjectARX的選線系統(tǒng)的設(shè)計(jì)與開發(fā)[J］.蘭州交通大學(xué)學(xué)報，2010，29(4):53-57.

[3]全思湘，方源敏，程永明.基于ObjectARX.net的面狀符號自動繪制的實(shí)現(xiàn)方法[J］.測繪通報，2010(10):50-52.

[4]周文峰，李珍萍，劉洪偉，等.最優(yōu)公交線路選擇問題的數(shù)學(xué) 模型及算法[J］.運(yùn)籌與管理，2008，17(5):80-84.