Efficient location referencing method
First Claim
1. A method of encoding a continuous path within a road network, said path being completely represented within a digital map and expressible as a path list of at least one of lines and segments existing in said digital map and consecutively ordered, said method comprising:
- (i) storing a start position in a route search list, said start position being one of;
the line or segment first appearing in said path list or, where the start node of said first line or segment in said path list is artificial, the first line or segment appearing in said digital map having a real start node and which leads directly to said first line or segment optionally through other artificial nodes,a most recently identified deviation line or segment also appearing in said path list,(ii) determining a path from the start node of the start position and including said start position to an end node of the last line or segment in the path list within said digital map, said 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 said digital map but not being the line or segment first appearing in said 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 said deviation line or segment, and(iv) storing the last line or segment in the path list in said route search list if not already stored.
2 Assignments
0 Petitions
Accused Products
Abstract
A efficient method of encoding a continuous path within a road network in which the path to be encoded is expressible as a path list of lines and/or segments existing in a digital map and consecutively ordered. The method comprises the steps of: (i) storing a start position in a route search list; (ii) determining a path from a start node of the start position and including said start position to an end node of the last line or segment in the path list within said digital map, said path being determined according to a shortest path algorithm; (iii) comparing the shortest path so determined to the path list, and identifying at least one deviation line or segment being part of the path list and having a start node representative of an intersection in said digital map but not being the line or segment first appearing in said 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 said deviation line or segment; and (iv) storing the last line or segment in the path list in said route search list if not already stored.
-
Citations
12 Claims
-
1. A method of encoding a continuous path within a road network, said path being completely represented within a digital map and expressible as a path list of at least one of lines and segments existing in said digital map and consecutively ordered, said method comprising:
-
(i) storing a start position in a route search list, said start position being one of; the line or segment first appearing in said path list or, where the start node of said first line or segment in said path list is artificial, the first line or segment appearing in said digital map having a real start node and which leads directly to said first line or segment optionally through other artificial nodes, a most recently identified deviation line or segment also appearing in said path list, (ii) determining a path from the start node of the start position and including said start position to an end node of the last line or segment in the path list within said digital map, said 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 said digital map but not being the line or segment first appearing in said 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 said deviation line or segment, and (iv) storing the last line or segment in the path list in said route search list if not already stored. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A system for encoding a continuous path location comprising:
-
an encoder, wherein the encoder stores a start position in a route search list, said start position being one of;
the line or segment first appearing in said path list or, where the start node of said first line or segment in said path list is artificial, the first line or segment appearing in said digital map having a real start node and which leads directly to said first line or segment optionally through other artificial nodes and a most recently identified deviation line or segment also appearing in said path list, and wherein the encoder determines a path from the start node of the start position and including said start position to an end node of the last line or segment in the path list within said digital map, said path being determined according to an algorithm, compares 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 said digital map but not being the line or segment first appearing in said 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, repeats using said deviation line or segment, and stores the last line or segment in the path list in said route search list if not already stored, anda database for storing pre-encoded locations and the results of previous attempts at encoding those locations, wherein the system, on receiving a location to be encoded, first queries the database to establish whether that location or a part of it, forms a part of or is identical to a location having been previously stored within said database, said system returning either the previously encoded location or a part of it in the case of encoding having already been effected, or alternatively passing the continuous path location to the encoder, the output of which is in any event stored in said database together with that continuous path location.
-
Specification