EFFICIENT LOCATION REFERENCING METHOD

• US 20110118971A1
• Filed: 06/29/2009
• Published: 05/19/2011
• Est. Priority Date: 06/30/2008
• Status: Active Grant

• Current Assignee: TomTom Traffic B.V. (TomTom NV)
• Original Assignee: TomTom International BV (TomTom NV)
• Inventors: Petzold, Lars, Schaefer, Ralf-Peter, Baselau, Sven
• Granted Patent: US 8,626,438 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

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.

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 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. A method according to claim 1 wherein the algorithm used in determination of the path is a shortest path algorithm.

3. A method according to claim 1 wherein in step (iii), if the deviation line or segment terminates at the end node of the last line or segment appearing in the path list, and the predecessor of the last line or segment in the shortest path does not coincide with the penultimate line or segment appearing in said path list, then a second deviation line or segment is exceptionally identified being that line or segment emanating from the last node appearing in the path list which coincides with an intersection.

4. A method according to claim 1, further comprising converting the resulting route search list into a machine-readable format represented in binary or a markup language such as XML.

5. A method according to claim 1 including at least one of:

concatenation, conversion, transposition, and validity checking, which result in a valid, ordered list of location reference points, or a machine-readable representation thereof.

6. A method according to claim 1, wherein the method includes a preliminary step of analysing each item in the path list representing said continuous path for validity, and in the event that the path list is not valid in a relevant respect, raising an exception.

7. A method according to claim 5 wherein the validity check includes a check to establish whether either or both of the start node of the first mentioned line or segment in the path list and the end node of the last mentioned in said path list coincide with a real node in the digital map and in the absence of such coincidence, the preliminary validity check includes identifying suitable real nodes and extending the continuous path accordingly by including additional lines or segments in the path list, and storing an offset representative of the distance between the real nodes and artificial nodes.

8. A method according to claim 1 further comprising imposing a restriction on the maximum distance between successive location reference points.

9. A method according to claim 8 wherein the maximum distance so imposed is 15 km.

10. A method according to claim 1 further comprising, in the encoder, determining whether a turn restriction check option is enabled, and if so enabled, assessing the location desired to be encoded for turn restrictions identified in the digital map and which may prejudice or compromise said location or make it impossible to navigate, and if such are identified, returning an error.

11. A computer program element, embodied on a non-transitory computer readable medium, comprising computer program code to execute, when run on a computer device, the method as set forth in claim 1.

12. A non-transitory computer readable medium embodying the computer program element as described in claim 11.

13. A system for encoding a continuous path location comprising:

an encoder operating as described in the method of claim 1;

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