Efficient location referencing method

• US 9,697,426 B2
• Filed: 01/11/2012
• Issued: 07/04/2017
• Est. Priority Date: 01/11/2011
• Status: Active Grant

• Current Assignee: TomTom Traffic B.V. (TomTom NV)
• Original Assignee: TomTom Traffic B.V. (TomTom NV)
• Inventors: Baselau, Sven, Petzold, Lars, Berndt, Axel
• Primary Examiner(s): Paige, Tyler
• Application Number:
  US13/979,184
• Publication Number:
  US 20130294702A1
• Time in Patent Office: 2,001 Days
• Field of Search: 701410, 701533, 382199
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06V 20/182 Network patterns, e.g. roads or rivers
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

A method of encoding a continuous path within a road network is described, the path being completely represented within a digital map and expressible as a path list of lines and/or segments existing in said digital map and consecutively ordered, wherein said lines and/or segments have one or more attributes associated therewith. The method involves storing a start position in a route search list, and 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. The path is determined according to an algorithm utilizing an attribute of said lines or segments. The attribute may be a lowest functional road class (LFRC) of the path to be encoded or a part thereof.

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 lines and/or segments existing in said digital map and consecutively ordered, wherein said lines and/or segments have one or more attributes associated therewith including a functional road class (FRC), said method comprising the steps of:

determining a lowest functional road class (LFRC) for the lines and/or segments forming at least a portion of the continuous path to be encoded;

storing a start position in a route search list;

determining a path from the start position to an end position as indicated by the last line or segment in the path list within said digital map, said path being determined according to an algorithm, said algorithm using the determined LFRC to provide a threshold, and to not consider those lines and/or segments for inclusion in the path being determined that have a lower FRC attribute than the threshold;

encoding the continuous path using the determined path; and

storing the encoded continuous path.

2. The method of claim 1, wherein the threshold is the determined lowest functional road class (LFRC) or is a softened LFRC value that is higher than the determined LFRC.

3. The method of claim 1, comprising determining a path from a 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.

4. The method of claim 1, wherein the step of determining a path from the start position to an end position comprises determining a shortest path from the start position to the end position as indicated by the last line or segment in the path list within the digital map.

5. The method of claim 4, comprising calculating an associated LRFC value for the or each shortest path that is determined.

6. The method of claim 4, comprising determining an LFRC value for an entire line location corresponding to the continuous path to be encoded.

7. The method of claim 4, wherein a separate LFRC value is determined for each portion of the path to be encoded for which a shortest path is calculated.

8. The method of claim 1, wherein said step of determining the path from the start position to the end position comprises finding a shortest path coverage of the continuous path.

9. The method of claim 1, wherein the algorithm is a shortest path algorithm.

10. The method of claim 1, wherein said start position is one of:

the line or segment first appearing in said path list or, where the start node of said first line or segment 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.

11. The method of claim 1, comprising comparing a shortest path determined from a start node of the start position to an end node of the last line or segment in the path list within the digital map 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 the step of storing a start position using said deviation line or segment, and storing the last line or segment in the path list in said route search list if not already stored.

12. The method of claim 1, comprising the steps of:

(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 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, and wherein the algorithm is a shortest path algorithm, the method further comprising the steps of;

(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 a shortest path algorithm, said algorithm using the determined LFRC to provide a threshold, and to not consider those lines and/or segments for inclusion in the path being determined that have a lower FRC attribute than the threshold

(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.

13. The method of claim 1, further comprising provisioning services on a navigation device based on the stored digital map.

14. An encoder comprising at least one processor arranged to encode a continuous path within a road network, said path being completely represented within a digital map and expressible as a path list of lines and/or segments existing in said digital map and consecutively ordered, wherein said lines and/or segments have one or more attributes associated therewith including a functional road class (FRC), said encoding comprising the steps of:

determining a lowest functional road class (LFRC) for the lines and/or segments forming at least a portion of the continuous path to be encoded;

storing a start position in a route search list;

determining a path from the start position to an end position as indicated by the last line or segment in the path list within said digital map, said path being determined according to an algorithm, said algorithm using the determined LFRC to provide a threshold, and to not consider those lines and/or segments for inclusion in the path being determined that have a lower FRC attribute than the threshold;

encoding the continuous path using the determined path; and

storing the encoded continuous path.

15. A navigation device comprising the encoder of claim 14.

16. The encoder of claim 14, wherein the step of determining a path from the start position to an end position comprises determining a shortest path from the start position to the end position as indicated by the last line or segment in the path list within the digital map.