淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0707201015344600
中文論文名稱 產生景點重要指引道路地圖之研究
英文論文名稱 Research on Generation of a Guiding Road Map for Scenic Spots
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 98
學期 2
出版年 99
研究生中文姓名 林聖棠
研究生英文姓名 Sheng-Tang-Lin
電子信箱 bear0221.lin@mail.im.tku.edu.tw
學號 697630746
學位類別 碩士
語文別 中文
口試日期 2010-05-29
論文頁數 48頁
口試委員 指導教授-魏世杰
委員-魏世杰
委員-李鴻璋
委員-陳穆臻
中文關鍵字 Dijkstra最短路徑演算法  景點圍繞框  高低階路網 
英文關鍵字 Dijkstra Shortest Path Algorithm  Surrounding Box Around A Scenic Spot  High-Level and Low-Level Road Networks 
學科別分類 學科別社會科學管理學
學科別社會科學資訊科學
中文摘要 隨著所得提高,生活水準提升,人們越來越重視休閒旅遊活動。面對眾多的旅遊景點,如何簡明扼要的導引旅客到達不熟悉景點遂成為一項課題。就不熟悉景點而言,雖然我們可以查詢電子或紙本地圖,知道如何到達此景點的路徑,但也希望除了最短路徑資訊以外,能獲得景點周邊重要道路資訊的提示。故本研究目標是希望提供到達景點的周邊交通簡易圖,方法則以改良戴氏演算法為基礎進行規劃。步驟上先給定台灣區景點住址,經由GoogleMap定址服務找出景點對應的經緯度及十字路口。再透過運研所數值地圖找出附近高階路網入口點,產生高階路網圍繞框。接著找出附近國道及省道入口點,標出各入口點到景點沿途的重要高階及低階道路。
本文選擇高雄地區景點當作各演算法步驟的示範範例,另選取台北地區,台中地區,台南地區,花東地區,布袋地區,共六處景點進行結果展示。本文特色有三,在問題定義上,有別於過去研究著重於簡化道路形狀,長度,角度上,本研究在簡圖產生上,著重於重要道路及圍繞框的生成及標示。在演算法創新上,提供各種以戴氏為基礎的道路指引演算法,如附近高階路網指引演算法,國道指引演算法,省道指引演算法,復原國省道與原點間路徑演算法,復原低階路網演算法等。在系統整合上,結合Google Map的查詢底圖,及經緯度功能,以及上述產生景點圍繞框等演算法,提供一套查詢景點周圍重要路網的雛型系統。
英文摘要 With the increasing income and level of living standards, people are willing to spend more leisure time in tour activities. As the scenic spots grow more and more, it has become a major issue for tourists to travel to an unfamiliar spot in an easy way. Tourists usually find the way to the spot by consulting the map.While the map can show the shortest path, tourists often find that extra tips showing important roads surrounding the scenic spot will help. Based on the Dijkstra shortest path algorithm, this work aims to provide such a schematic road map around the desired spot. Given the address of a scenic spot in Taiwan, its latitude and longitude are first found by Google Map. Then based on the Institute of Transportation (IOT) Road Network Digital Atlas, a surrounding box around the desired spot and its entry points are identified on the high-level road network. Finally the nearest access points of the national and provincial highways are located and the access paths are shown from those access points to the desired spot.
For depiction of the algorithms used, a test spot in the Kaohsiung area is selected. Other demonstrations include spots in urban and suburban areas of Taipei, Taichung, Tainan, Hualien and Taitung, and Butai. There are 3 features in this work. First, in terms of problem definition, it focuses on generation of the high-level surrounding box instead of the traditional simplification on road shape and length. Second, in terms of algorithmic novelty, it proposes several Dijkstra-based algorithms for generation of guiding roads. They include algorithms which generate the nearby high-level surrounding box, find the nearest national and provincial highway access points, mark the path leading from the access points to the surrounding box,and restore the proper low-level road network connecting the surrounding box to the desired spot inside. Third, in terms of system integration, this work has completed a prototypical system which can input the spot address, query its coordinate by Google Map, identify the nearest intersection, and run the proposed algorithms mentioned above to generate a useful guiding road map for scenic spots.
論文目次 目錄
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究架構 2
第二章 文獻探討 4
2.1 簡圖(Schematic Route Map) 4
2.2 產生簡圖 5
2.3 地圖路段簡化 5
2.4 最短路徑搜尋演算法 5
2.5 戴氏演算法 6
2.6 Google Map API 6
第三章 方法介紹 8
3.1 問題定義 8
3.2 本研究採用演算法設定 10
3.3 符號定義 11
3.4 各種演算法說明 12
第四章 31
4.1 實驗環境 31
4.2 系統展示 31
第五章 結語與未來發展 45

圖目錄
圖3- 1 Google Map所提供之傳統電子地圖 8
圖3- 2窮舉法示意圖 17
圖3- 3向量角度示意圖 18
圖3- 4復原重要低階路網示意圖 22
圖3- 5景點圖 25
圖3- 6原始圖 25
圖3- 7最近高階路網指引示意圖 25
圖3- 8圍繞框演算法示意圖 26
圖3- 9國道指引演算法示意圖 27
圖3- 10省道指引演算法示意圖 27
圖3- 11復原國省道與原點間路徑示意圖 28
圖3- 12復原低階路網示意圖 29
圖3- 13 系統完成圖 30
圖4- 1系統介面圖 32
圖4- 2台北地區(台北縣政府)傳統電子地圖 33
圖4- 3台北地區(台北縣政府)系統簡圖 34
圖4- 4台北地區(台北市火車站)傳統電子地圖 35
圖4- 5台北地區(台北市火車站)系統簡圖 36
圖4- 6台中地區(台中縣政府)傳統電子地圖 37
圖4- 7台中地區(台中縣政府)系統簡圖 38
圖4- 8台南地區(永康火車站)傳統電子地圖 39
圖4- 9台南地區(永康火車站)系統簡圖 40
圖4- 10台東地區(知本火車站)傳統電子地圖 41
圖4- 11台東地區(知本火車站)系統簡圖 42
圖4- 12郊區(嘉義布袋港)傳統電子地圖 43
圖4- 13郊區(嘉義布袋港)地區系統簡圖 44

表目錄
表3- 1演算法總表 ..................................................... 10
表3- 2演算法總表說明 ...................................................... 12
表3- 3附近高階路網指引演算法第一階段(反向地圖) .......... 14
表3- 4附近高階路網指引演算法第二階段(反向地圖) ......... 15
表3- 5圍繞框指引演算法第一階段(正向地圖) ............... 16
表3- 6各節點間之距離 ................................... 17
表3- 7國道指引演算法第一階段(正向地圖) ................. 18
表3- 8省道指引演算法 ............. 20
表4- 1實驗環境 ....................... 31
參考文獻 [1] 交通部運輸研究所,路網數值圖1.1版,2004年。
[2] 陳勇仁,以GML/XML為基礎建置一套駕駛路徑資訊系統,靜宜大學資訊管理研究所碩士論文,2007。
[3] 張晉維,GIS導航路徑簡化圖示在無線通訊端應用之研究,交通大學交通運輸研究所碩士論文,2001。
[4] 聞祝達,地圖簡化目的與內涵之探討,測量學術及應用研討會,1995,43-55頁
[5] 鄧國壽,曾正雄,地圖之簡單化演算法探討,地理學期刊,2003,57-74頁
[6] 鄭宇辰,利用高低層路網加快最短路徑計算之實作,淡江大學資訊管理研究所碩士論文,2008。
[7] 謝逢鳴,有前處理最短路徑演算法之研究,淡江大學資訊管理研究所碩士論文,2006。
[8] E. W. Dijkstra,“A note on two problems in connection with graphs,” Numerische Mathematik, 1, 1959, pp. 269-271.
[9] M. Agrawala and C. Stolte, "Rendering effective route maps: Improving usability through generalization," in Proceedings of the ACM SIGGRAPH Conference on Computer Graphics, 2001, pp. 241-250
[10] M.Agrawala,and C.Stolte”A design and implementation for effective computer-generated route maps”, The Association for the Advancement of Artificial Intelligence, 2000, pp. 04-10
[11] M. Agrawala. Visualizing Route Maps. PhD thesis, Stanford University, 2001
[12] S. Maeyama, A. Ohya, and S.I. Yuta, "Outdoor landmark map generation through human assisted route teaching for mobile robot navigation," in Proceedings of IEEE International Conference on Intelligent Robots and Systems 1996, pp. 957-962.
[13] Google Maps, http://maps.google.com
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2010-07-08公開。
  • 同意授權瀏覽/列印電子全文服務,於2010-07-08起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信