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