| 摘要 |
An efficient method of encoding a continuous path within a road network is described. Ideally the path to be encoded is capable of being completely represented within a digital map and expressible as a path list of lines and/or segments existing in the digital map and consecutively ordered. In at least one embodiment, the method includes: (i) storing a start position in a route search list, the start position being one of: (a) the line or segment first appearing in the path list or, where the start node of the first line or segment is artificial, the first line or segment appearing in the digital map having a real start node and which leads directly to the first line or segment optionally through other artificial nodes, or (b) a most recently identified deviation line or segment also appearing in the path list; (ii) determining a path from the start node of the start position and including the start position to an end node of the last line or segment in the path list within the digital map, the path being determined according to an algorithm, (iii) comparing the shortest path so determined to the path list for identity, and in the absence of identity, identifying at least one deviation line or segment being part of the path list and having a start node representative of an intersection in the digital map but not being the line or segment first appearing in the path list, and if such deviation line or segment does not terminate at the end node of the last line or segment appearing in the path list, repeating step (i) using the deviation line or segment, and (iv) storing the last line or segment in the path list in the route search list if not already stored. Most preferably, the algorithm used is a shortest path algorithm.
|
