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