초록 ▼

A program and method for route calculation for use with a navigation system and used with a map database that represents a road network in a geographic region. A route calculation program is adapted to find at least one solution route between a first location on a road network and a second location

A program and method for route calculation for use with a navigation system and used with a map database that represents a road network in a geographic region. A route calculation program is adapted to find at least one solution route between a first location on a road network and a second location on the road network. The route calculation program includes a first search tree associated with the first location and a second search tree associated with the second location. Each search tree is adapted to hold gates. Each of the gates represents a physical position on the road network and a direction from the position to another location along a path on the road network. The route calculation program also includes at least one priority queue associated with one of the search trees. The priority queue assigns a priority to one of the gates in the associated search tree based upon an evaluation using a search algorithm. The gate identified as having a higher priority than any other gate in its respective search tree is expanded to determine one or more successor gates thereof. Each of these successor gates so formed is compared to the gates in the other search tree. The process of growing at least one of the search trees by expanding the gate in the search tree that has a higher priority than any other gate in the search tree is continued until a gate in one search tree corresponds to at least one gate in the other search tree.

대표청구항 ▼

[ We claim:] [1.] A route calculation program for use in a navigation system used with a map database stored on a computer readable storage medium, the route calculation program adapted to find a solution route between a first location on a road network represented by said map database and a second

[ We claim:] [1.] A route calculation program for use in a navigation system used with a map database stored on a computer readable storage medium, the route calculation program adapted to find a solution route between a first location on a road network represented by said map database and a second location on the road network represented by said map database, wherein said road network is represented in said map database by data that represent each segment of each road between endpoints thereof that correspond to intersections of said segment of road with other segments of roads, said route calculation program comprising:at least one search tree adapted to hold a plurality of gate data structures, each of said gate data structures representing a physical position on the road network represented by said map database and a direction from said position to another location on said road network represented by said map database, wherein one of said Rate data structures is a seed gate data structure that represents said first location as a position along a segment of a road between endpoints thereof and a direction from said position along said represented segment of road; anda priority queue referencing said gate data structures in said at least one search tree and assigning a priority to one of said gate data structures;wherein said route calculation program is adapted to expand said one of said gate data structures to determine successor gate data structures thereof and to compare each of said successor gate data structures to gate data structures associated with said second location.