The Embedded Gps Navigation Engine And Implementation

Embedded GPS navigation engine using embedded operation system as its platform, it is combing Global Positioning System and Geographic Information System. It is an ideal solution to realize navigation, location, geography information query and spatial data management.At present, all kinds of GPS navigation products on the market commonly use professional GIS software, such as ArcGIS, MapInfo etc, to realize basic function of GIS at first, later develop other functions on the general software development platform. Although the development cycle is greatly reduced by using this mode, but it is very difficult to decrease development cost and product cost.In this thesis, the building of navigation map's topotaxy and the planning of shortest path have been analyzed. Base on indepth analysis both topotaxy and shortest path, novel improvement on the topotaxy's data structure and algorithm of shortest path are explored and investigated.The main results are as follows:1. The building of navigation map's topotaxy and the relationship of different topo's element are investigated in detail. First refer to polyvert's blue print and the real condition of city's road improved topotaxy's data structure. Then focus on the polygon's topotaxy, in which developed the program of search polygon and improved algorithm about the relationship between point and polygon.2. The merits and drawbacks of the classic algorithm of shortest path are discussed in detail. Such as: Algorithm of Dijkstra. An improved classic Dijkstra algorithm on the basis of priority queue based on quad-heap, and then considered the real condition of city's road, added the function of direction priority. The new algorithm is more efficient than classic Dijstra algorithm. So it meets the requirement of shortest path computation under the navigation.