- 相關(guān)推薦
有關(guān)基于Mapx的最短路徑選擇算法的實現(xiàn)
摘 要：最短路徑分析是智能交通系統(tǒng)和GIS道路網(wǎng)絡(luò)分析中的重要組成部分。要實現(xiàn)最短路徑的選擇，必須具有道路、弧段和節(jié)點的拓撲信息，而Mapx的圖形數(shù)據(jù)并不具有拓撲結(jié)構(gòu)，因此在進行路徑選擇時必須先生成道路網(wǎng)的拓撲關(guān)系，再利用Dijkstra算法找出最短路徑。
關(guān)鍵詞：Dijkstra算法，Mapx，access，拓撲關(guān)系，最短路徑引言軟件技術(shù)的日新月異極大地推動了GIS的發(fā)展，如今組件式GIS的開發(fā)已成為GIS開發(fā)的潮流之一。組件式GIS的基本思想是把GIS的各大功能模塊分為幾個控件，每個控件完成不同的功能。各個GIS控件之間，以及GIS控件與其他非GIS控件之間，可以方便地通過可視化的軟件開發(fā)工具集成起來。這種開發(fā)方式不但可以實現(xiàn)GIS的絕大部分功能，而且開發(fā)成本較低，也使開發(fā)人員無需掌握專門的GIS開發(fā)語言。Mapx是MapInfo公司開發(fā)的一個GIS控件，它使用與MapInfo一致的地圖數(shù)據(jù)格式，并實現(xiàn)了MapInfo的大多數(shù)功能，如：tab格式地圖的顯示、地圖的放大、縮小、拖動、專題圖的制作、數(shù)據(jù)綁定、圖層控制等[1]。
數(shù)據(jù)處理主要采用Tab表數(shù)據(jù)，地圖數(shù)據(jù)按照內(nèi)容的不同以圖層(Layer)的形式存儲，而道路網(wǎng)又可按照道路等級的不同進行分層存儲。為了打印和存儲的方便，需要把所有的道路圖層中的圖元及圖元名稱Clone到一個圖層中。
最短路徑分析中道路交叉點是系統(tǒng)實現(xiàn)的關(guān)鍵數(shù)據(jù)，確保道路在交叉處確實相交，并具有一個交叉節(jié)點。對于互穿的道路，可以利用intersectionpoints方法，把flags參數(shù)設(shè)置為來捕獲一個交點，而對于在交叉口斷開的道路，需要利用MapInfo的捕捉功能，使兩條或多條道路在交叉口處交于一點，以消除道路網(wǎng)中的斷點。
由于地圖編輯中的失誤，可能產(chǎn)生只有一個坐標點的線圖元，在建立拓撲關(guān)系之前需要利用feature的Length屬性把ftr.Length=0的線圖元剔除。
基于Mapx的拓撲關(guān)系的構(gòu)建最短路徑分析是道路網(wǎng)絡(luò)分析中的一個基本內(nèi)容，其中的關(guān)鍵是建立道路網(wǎng)中各個弧段之間、節(jié)點之間和道路之間的拓撲關(guān)系。但Mapx最大的不足之處就是不能建立地圖數(shù)據(jù)的拓撲結(jié)構(gòu)，所以在進行最短路徑分析時首先需要建立節(jié)點、弧段和道路之間的拓撲關(guān)系。
為獲得適于道路搜索的路網(wǎng)圖，必須將在交叉點處將道路拆分成最基本的路段，使其只在端點處與其他路段相交。拆分后的基本路段對應(yīng)于路網(wǎng)圖中的弧，其端點就是圖中的頂點。
路網(wǎng)中的拓撲關(guān)系可以用三個二維表格分別存放頂點相關(guān)信息和弧段相關(guān)信息，如表1、表、表3。
表設(shè)置pnts點集和pnt點變量，利用feature的parts屬性來獲得道路圖層中所有組成道路節(jié)點的坐標Node_X和Node_Y并把節(jié)點按遞增的順序進行編號。但是對于兩條或多條道路交叉點不是道路已有節(jié)點的情況，就要利用Mapx的IntersectionPoints屬性來獲取道路的交叉點添加到Nodes表中。代碼如下：
表主要利用Nodes表中的Type1字段生成。在Type1字段中字段值為1的點為道路的交叉點，道路在交叉點斷開為基本的弧段，獲得弧段的FromNode、ToNode編號和Edgename編號，而EdgeLength利用兩兩之間的節(jié)點距離相加而得。如圖1：有四條道路，其中道路一節(jié)點的編號為1—11，被分成1—5、5—9、9—11三段弧，其中1—5弧段的長度為表利用ARC表生成，保存所有道路節(jié)點和弧段信息，主要是為了加快搜索速度。
算法在GIS中的實現(xiàn)算法原理算法是典型的最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。
主要通過為每個頂點V保留目前為止所找到的從S到V點的最短路徑來工作，首先以起始點為中心向外層擴展，，直到擴展到終點為止[2]。初始時，源點S的路徑長度被賦為0(d[s]=0)，同時把所有其他頂點的路徑長度設(shè)為無窮大(d[V]= ∞)，即表示不知道任何通向這些頂點的路徑。當(dāng)結(jié)束時，d[V]中存儲的便是從S到V的最短路徑，如果d[V]是無窮大說明從點到點V無可通的路徑。Dijkstra算法的基本操作是邊的拓展，如果存在一條從U到V的邊，那么從S到V的最短路徑可以通過將邊(U，V)添加到尾部來拓展一條從S到V的路徑。這條路徑的長度是d[U]+W(U,V)(從頂點U到V的非負花費值)。如果這個值比目前已知的的值要小，可以用新值來替代當(dāng)前d[V]中的值。拓展邊的操作一直執(zhí)行到所有的d[V]都代表從S到V最短路徑的花費[3]。
算法的實現(xiàn)算法利用VB來實現(xiàn)，首先設(shè)置graph()二維數(shù)組來記錄任意i點到其他所有頂點的距離，distance1()數(shù)組來記錄起始點到其他所有頂點的距離，visited()來記錄頂點的訪問情況。
最短路徑的顯示利用Dijstra算法中返回的最短路徑中所遍歷的點生成最短路徑。如圖2：
由Dijkstra算法獲取所遍歷的頂點;利用遍歷的相鄰頂點的編號，在Nodes表中查找道路上所對應(yīng)節(jié)點的編號;利用createline方法在圖層dijkstra中創(chuàng)建最短路徑所對應(yīng)的線圖元。
結(jié)論和展望本文通過對道路數(shù)據(jù)的處理、拓撲關(guān)系的創(chuàng)建、Dijkstra算法的實現(xiàn)等一系列研究工作，建立了道路數(shù)據(jù)庫及其結(jié)點，弧段，道路三個表，構(gòu)造了節(jié)點、弧段和道路之間的拓撲關(guān)系，實現(xiàn)了最短路徑分析，增強了基于Mapx組件式二次開發(fā)的空間分析能力，但該問題的處理還有許多不足之處：
效率低：由于Dijkstra算法在搜索時要遍歷所有的頂點，并且在創(chuàng)建拓撲關(guān)系時要遍歷道路中的所有節(jié)點，計算量大、耗時長，有待于進一步改進。
數(shù)據(jù)的限制：在進行最短路徑選擇時，起始點和終點的坐標必須與道路上某一節(jié)點的坐標相同，在算法上需要進一步改善。
【基于Mapx的最短路徑選擇算法的實現(xiàn)】相關(guān)文章：
基于SOPC的LMS自適應(yīng)濾波算法實現(xiàn)08-24
基于Cyclone系列FPGA的1024點FFT算法的實現(xiàn)09-30
基于MapX的城市GIS的初步建立08-06
基于GPRS網(wǎng)絡(luò)的圖像傳輸自適應(yīng)算法及實現(xiàn)06-02
圖像拼接算法及實現(xiàn)07-23
基于人性化管理分析旅游酒店管理的路徑選擇05-24
FFT算法的研究與DSP實現(xiàn)09-23