112年度GIS專題中心暑期實習生成果介紹（4）

專題題目：動態路徑規劃演算法與WebGIS系統開發實務

實習學生：楊研茂（國立臺灣海洋大學資訊工程學系）

指導老師：郭巧玲 助研究員

郭巧玲老師指導實習學生楊研茂同學，研究圖形網路結構與路徑規劃演算法，運用NetworkX和OpenLayers開發出一可執行動態路徑規劃演算法之WebGIS系統，並以臺北市範圍為例。實作中將路網資料轉成圖形網絡，並設計了合適之最短路徑演算法，在圖形網絡中進行路徑走訪，最後繪製路徑顯示在地理資訊系統。

1.研究方法

a.Shapefile檔轉圖形網絡：利用shp2graph工具，將臺北市的路網資料(shp檔)轉成大型圖形網絡。

b.最短路徑演算法：採取Dijkstra演算法在圖形網絡中進行路徑走訪，Dijkstra演算法是一個從單一起點到其餘各個節點的最短路徑演算法，可解決有向圖最短路徑問題。

c.處理點落在路網外之情況： 若路徑規劃的起點終點落在路網以外，則透過近鄰分析找到離該點最近的道路。

2.研究成果：路徑規劃功能

將起點和終點的經緯度坐標輸入，並點擊按鈕，最後產生藍色的最短路徑；以下為系統針對大安森林公園到捷運松山機場站路徑規劃結果。

3.其他功能

a.測量功能：點擊起點和終點產生黑色的直線，線段軌跡不會消失，黃色的框框會顯示距離數，也可以畫多邊形，顯示面積。

b.定位功能：點擊定位旁的框框，會彈出對話視窗，問使用者是否接受讓網站知道所在位置，點擊允許，定位到使用 者目前位置，並顯示淺藍色的點到現在位置。

c.顯示鼠標坐標功能：顯示滑鼠鼠標目前的經緯度，若鼠標的位置調整，坐標也會動態改變。