EFFICIENT LOCATION REFERENCING METHOD

• US 20130294702A1
• Filed: 01/11/2012
• Published: 11/07/2013
• 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
• Granted Patent: US 9,697,426 B2
• Time in Patent Office: Days
• US Class Current: 382/199
• 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 utilising 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, said method comprising the steps of:

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 utilising an attribute of said lines or segments; and

encoding the continuous path using the determined path.

2. The method of claim 1, wherein the attribute comprises a functional road class (FRC) of the lines or segments.

3. The method of claim 1, wherein the attribute comprises a lowest functional road class (LFRC) for a line location.

4. The method of claim 3, wherein the algorithm uses a softened LFRC value for the line location, the softened LFRC value being a value less important than a calculated actual LFRC value for the line location.

5. The method of claim 1, wherein an LFRC attribute is used in the path determining step such that no line or segment with a lower functional road class (FRC) value than a current LFRC value is considered for inclusion in the determined path.

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

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

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 7, comprising calculating an associated LRFC value for the or each shortest path that is determined.

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

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

15. 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, said method 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,

(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 utilising an attribute of said lines or segments,

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

16-25. -25. (canceled)

26. 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, said encoding comprising the steps of:

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 utilizing an attribute of said lines or segments; and

encoding the continuous path using the determined path.

29. A navigation device comprising the encoder of claim 26.

30. The encoder of claim 26, wherein the attribute comprises a lowest functional road class (LFRC) for a line location.

31. The encoder of claim 26, wherein an LFRC attribute is used in the path determining step such that no line or segment with a lower functional road class (FRC) value than a current LFRC value is considered for inclusion in the determined path.

32. The method of claim 26, 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.

27-28. -28. (canceled)