導航系統圖資前置處理

Abstract

近年來，全球定位系統的使用率大增，在結合地理資訊系統下，汽車導航產業蓬勃發展，大眾運輸工具不斷的發展而形成複雜的交通網，需要個人導航與行程規劃系統協助方能有效使用；然而，市面上的導航與行程規劃系統多為汽車駕駛者所量身打造，相較之下可提供大眾運輸乘客導航與行程規劃服務之工具幾乎屈指可數；在導航系統最主要的核心即是最短路徑演算法，本研究實作出不僅能夠適用於大眾運輸的行程規劃系統，一般的導航系統也能使用的前置處理。 我們實作一個針對在小型手持裝置中，可以改善查詢最短路徑效率的前置處理演算法(preprocessing algorithm)—arc-flags，並且把arc-flags與一些不同方法(雙層切割、Bloom filter)相結合，組成不同的資料結構，以降低空間的需求。以便在小型手持裝置的實務應用方面，把經過前置處理之後得到有輔助資訊的圖資，放在小型手持裝置中，增加額外少量的空間，幫助小型裝置加速計算的時間。並以不同的基準來比較出不同方法的優劣。