SYSTEM AND METHOD FOR DETERMINING ROUTING POINT PLACEMENT FOR AIDING IN ENCODING AND DECODING A PATH

• US 20090005926A1
• Filed: 06/29/2007
• Published: 01/01/2009
• Est. Priority Date: 06/29/2007
• Status: Active Grant

• Current Assignee: Tomtom Global Content B.V (TomTom NV)
• Original Assignee: Tele Atlas North America (TomTom NV)
• Inventors: Kaubisch, Elizabeth V.C.
• Granted Patent: US 8,170,793 B2
• Time in Patent Office: Days
• US Class Current: 701/26
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G09B 29/003 Maps

Abstract

A method of encoding a shortened path definition of a path in a mapping system is described. In one embodiment, a shortened path definition includes only those routing points that are needed to eliminate valid alternate routes.

Claims

1. A method of encoding a shortened path definition of a path in a mapping system from an initial path definition consisting of a starting point, a list of intersection points, and an end point, the method comprising:

A. checking whether there is a valid alternate path between the starting point and successive points of the initial path definition, where the checking is such that the valid alternate path does not contain the part of the path between the last two points included in a check;

i) if there is no valid alternate path, and the path has been checked to the end point, completing the process

ii) if there is a valid alternate path, adding a new routing point to eliminate the valid alternate path

iii) repeating method A with the newly added routing point as the starting point

wherein completing the process means defining the final shortened path definition as the starting point, the sequence of routing points, and the ending point.

2. The method of claim 1, wherein the part of the path between the last two points included in the check is the last segment for that check of a valid alternate path between the starting point and one of the successive points and wherein a routing point, if required, is placed in the last segment.

3. The method of claim 2, wherein an additional search over just the last segment determines where to place the routing point on the last segment.

4. The method of claim 1, wherein the shortened path definition is used to produce a transmitted path definition.

5. The method of claim 4, whereby the transmitted path definition is received by a receiver

6. The method of claim 5, whereby the transmitted path definition is decoded by the decoder of the receiver against the same map or different map by same vendor or by different vendor.

7. The method of claim 1, wherein it is checked whether there is a valid alternate path between the start and end of a currently tested section of the path.

8. The method of claim 7, wherein:

if there is no valid alternate path, the currently tested section is validated by setting the end of the section to the next point of the initial path definition, thus adding a new end segment from the previous section end to the updated section end.

9. The method of claim 7, wherein:

if there is a valid alternate path, adding a new routing point within the end segment of the currently tested section to the shortened path definition, and updating the currently tested section by setting the start to the new routing point, and setting the end to the next point of the initial path definition.

10. The method of claim 1, wherein a specification determines what alternate paths are valid.

11. The method of claim 10, wherein the specification is the AGORA-C specification.

12. A method of encoding a shortened path definition of a path in a mapping system from an initial path definition, the initial path definition including a starting point, a number of intersection points, and an end point, the method comprising:

A. checking whether there is a valid alternate path between the start and end of a currently tested section of the path which does not contain the part of the path between the last two points of the currently tested section (the end segment);

i) if there is no valid alternate path, updating the currently tested section by setting the end of the section to the next point of the initial path definition, thus adding a new end segment from the previous section end to the updated section end;

ii) if there is a valid alternate path, adding a new routing point within the end segment of the currently tested section to the shortened path definition, and updating the currently tested section by setting the start to the new routing point, and setting the end to the next point of the initial path definition;

wherein step A is repeated until the end of the currently tested section is the end point of the path and the currently tested section has no valid alternate path, and wherein the shortened path definition includes the start point, the end point and any routing point added in step A.ii.

13. The method of claim 12, wherein the shortened path definition is used to produce a transmitted path definition.

14. The method of claim 13, whereby the transmitted path definition is received by a receiver.

15. The method of claim 14, whereby the transmitted path definition is decoded by the decoder of the receiver against the same map or different map by same vendor or by different vendor.

16. The method of claim 12, wherein a check for a valid alternate path excludes the end segment of the section of the path currently being tested from being part of an alternate path.

17. The method of claim 12, wherein initially the currently tested section and the end segment are the same.

18. The method of claim 12, wherein a specification defines what alternate paths are valid.

19. The method of claim 18, wherein the specification is the AGORA-C specification.

20. The method of claim 12, wherein an alternate path is valid if the cost of the alternate path is less than a function of the cost of the current section.

21. The method of claim 20, wherein the cost is determined using distance and weight values.

22. The method of claim 12, wherein, if there is an alternate path to the currently tested section, but there is no valid alternate path to the end segment of the currently tested section, then the intersection point at the start of the end segment is selected as the new routing point in step A.ii.

23. The method of claim 12, wherein, if there is an alternate path to the currently tested section, and there is an alternate path to the end segment of the currently tested section, then the mid-point of the end segment is selected as the new routing point in step A.ii.

24. The method of claim 12, wherein the first tested section is a segment from the start point of the path to the first intersection point of the path and is also the end segment.

25. A method, for Agora-C encoding, for determining routing point (RP) placement on a location, where the location comprises one or more consecutive connected road elements, each of the one or more road elements having two ends (i, i+1), each road element end terminating at a intersection (IS_i, IS_i+1), the location starting at starting routing point (RP_S), also denoted by IS₀, and ending at ending routing point (RP_E), also denoted by IS_E, the method comprising the steps of:

a. setting x=0 and y=x+1

b. determining whether y<

=E;

c. if not, skipping to step e

d. if so, determining whether there are any alternate weighted paths between RP₁ and IS_y other than the location path between RP_x and IS_y;

if so,

1. placing RP_(x+1) along the location path between [IS<sub>(y−

1)</sub> and IS_y);

2. incrementing x;

3. incrementing y;

4. returning to step b;

or

if not,

1. incrementing y;

2. returning to step b;

e. ending the routing point placement method.

26. The method of claim 25 where an alternate weighted path between RP_x and IS_y is less than (<

) 1.25 times (*) the weighted location path between RP_x and IS_y.

27. The method of claim 25 further including, after step c. 1.a.ii, the steps of:

c. 1.a.ii.i. determining whether there is an alternate weighted path between IS<sub>(y−

1)</sub> and IS_y;

the end segment, and

c. 1.a.ii.ii. if so, placing RP_(x+1) along the location path between IS<sub>(y−

1)</sub> and IS_y but not on either IS<sub>(y−

1)</sub> and IS_y;

or

c. 1.a.ii.iii. if not, determining if RP_x is at IS<sub>(y−

1)</sub> and if so, placing RP_(x+1) along the location path between IS<sub>(y−

1)</sub> and IS_y, but not on either IS<sub>(y−

1)</sub> or IS_y;

or if not, placing RP_(x+1) on IS<sub>(y−

1)</sub>.