System and method for determining routing point placement for aiding in encoding and decoding a path

• US 8,170,793 B2
• Filed: 06/29/2007
• Issued: 05/01/2012
• 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.
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): Kong, Sze-Hon
• Application Number:
  US11/772,021
• Publication Number:
  US 20090005926A1
• Time in Patent Office: 1,768 Days
• Field of Search: 701/201, 701/206, 701/207, 701/208, 701/209, 701/210, 701/211
• US Class Current: 701/411
• 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 mapping system comprising a receiver and a sender arranged to communicate with one another via a communication link, wherein

the sender includes an initial path definition defining a path, the initial path definition comprising:

a starting point, a list of intersection points, and an end point;

the sender further includes an encoder having means for encoding the initial path definition to a shortened path definition;

the receiver includes a decoder having means for decoding the shortened path definition and means for reconstructing the initial path definition;

and wherein the encoder further comprises;

means for checking whether there is a valid alternate path between the starting point and successive points of the initial path definition, wherein the valid alternate path does not contain the part of the path between the last two points included in a check;

means for completing the process of checking the initial path definition if there is no valid alternate path, and the means for checking has checked the path to the end point,

means for eliminating the valid alternate path by adding a new routing point to the initial path definition, if a valid alternate path has been determined by the means for checking,

means for repeatedly checking whether there is a valid alternate path between a newly added routing point and successive points of the initial path definition, wherein the valid alternate path does not contain the part of the path between the last two points included in a check, and

means for completing the process of checking the initial path definition by defining the final shortened path definition as a starting point, a sequence of routing points, and an ending point of the path.

2. The mapping system of claim 1, wherein the part of the path between the last two points included in the process of checking is the last segment for that check of a valid alternate path between the starting point and one of the successive points and wherein the encoder further comprises means for placing a routing point, if required, in the last segment.

3. The mapping system of claim 2, wherein the encoder further comprises means for determining where to place the routing point on the last segment by an additional search over just the last segment.

4. The mapping system of claim 1, wherein the sender further comprises means for producing a transmitted path definition by using the shortened path definition.

5. The mapping system of claim 4, wherein the receiver further comprises means for receiving the transmitted path definition.

6. The mapping system of claim 5, whereby the decoder comprises means for decoding the transmitted path definition against the same map or different map by same vendor or by different vendor.

7. The mapping system of claim 1, wherein the encoder further comprises means for checking whether there is a valid alternate path between the start and end of a currently checked section of the path.

8. The mapping system of claim 7, wherein:

the encoder further comprises means for validating the currently checked 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, if there is no valid alternate path.

9. The mapping system of claim 7, wherein the encoder further comprises:

means for

adding a new routing point within the end segment of the currently checked section to the shortened path definition, and

means for updating the currently checked section by setting the start to the new routing point, and setting the end to the next point of the initial path definition;

if there is a valid alternate path.

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

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

12. A mapping system comprising a sender and a receiver arranged to communicate with one another via a communication link, wherein

the sender includes an initial path definition defining a path, the initial path definition comprising:

a starting point, a list of intersection points, and an end point,

the sender further includes an encoder having means for encoding the initial path definition to a shortened path definition;

the receiver includes a decoder having means for decoding the shortened path definition and means for reconstructing the initial path definition;

and wherein the encoder further comprises;

means for checking whether there is a valid alternate path between the start and end of a currently checked section of the path which does not contain the end segment, the end segment being the part of the path between the last two points of the currently checked section,

means for updating the currently checked 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, if there is no valid alternate path,

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

means for repeatedly checking whether there is a valid alternate path between the start and end of a currently checked section of the path which does not contain the end segment, the end segment being the part of the path between the last two points of the currently checked section, until the end of the currently checked section is the end point of the path and the currently checked section has no valid alternate path, and

wherein the shortened path definition includes the start point, and the end point of the path and any routing point added.

13. The mapping system of claim 12, wherein the sender further includes means for producing a transmitted path definition by using the shortened path definition.

14. The mapping system of claim 13, wherein the receiver further includes means for receiving the transmitted path definition.

15. The mapping system of claim 14, whereby the decoder comprises means for decoding the transmitted path definition against the same map or different map by same vendor or by different vendor.

16. The mapping system of claim 12, wherein the encoder further comprises means for excluding the end segment of the section of the path currently being checked from being part of an alternate path, while checking for a valid alternate path.

17. The mapping system of claim 12, wherein initially the currently checked section and the end segment are the same.

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

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

20. The mapping system 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 mapping system of claim 20, wherein the encoder further comprises means for determining the cost using distance and weight values.

22. The mapping system of claim 12, wherein the encoder further comprises means for selecting the intersection point at the start of the end segment as the new routing point, if there is an alternate path to the currently checked section, but there is no valid alternate path to the end segment of the currently checked section.

23. The mapping system of claim 12, wherein the encoder further comprises means for selecting the mid-point of the end segment as the new routing point, if there is an alternate path to the currently checked section, and there is an alternate path to the end segment of the currently checked section.

24. The mapping system of claim 12, wherein the first checked 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 (ISi, ISi+1), the location starting at starting routing point (RPS), also denoted by ISO, and ending at ending routing point (RPE), also denoted by ISE, such that E represents the total number of road elements of the location, the method comprising an encoder within a sender of a mapping system performing 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 RP1 and ISy other than the location path between RPx and ISy;

if so,

i.1. placing RP(x+1) along the location path between IS(y−

1) and ISy;

i.2. incrementing x;

i.3. incrementing y;

i.4. returning to step b;

or

if not,

ii.1. incrementing y;

ii.2. returning to step b;

e. ending the routing point placement method.

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

) 1.25 times (*) the weighted location path between RPx and ISy.

27. The method of claim 25 further including, after step d.i.1, the steps of:

d.i.1.i. determining whether there is an alternate weighted path between IS(y−

1) and ISy; and

d.i.1.ii. if so, placing RP(x+1) along the location path between IS(y−

1) and ISy but not on either IS(y−

1) and ISy;

or

d.i.1.iii. if not, determining if RPx is at IS(y−

1) and if so, placing RP(x+1) along the location path between IS(y−

1) and ISy, but not on either IS(y−

1) or ISy;

or if not, placing RP(x+1) on IS(y−

1).

28. A method of encoding a shortened path definition of a path from an initial path definition comprising a starting point, a list of intersection points, and an end point, the method comprising an encoder within a sender of a mapping system performing the steps of:

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

completing the process of checking the initial path definition if there is no valid alternate path and the path has been checked to the end point,

eliminating the valid alternate path by adding a new routing point to the initial path definition, if a valid alternate path has been determined during the checking,

repeatedly checking whether there is a valid alternate path between a newly added routing point and successive points of the initial path definition, wherein the valid alternate path does not contain the part of the path between the last two points included in a check, and

completing the process of checking the initial path definition by defining the final shortened path definition as a the starting point, a sequence of routing points, and an ending point of the path.

29. A sender of a mapping system arranged to communicate with a receiver via a communication link, wherein the sender includes a processor configured to:

encode an initial path definition defining a path to a shortened path definition, the initial path definition comprising;

a starting point, a list of intersection points, and an end point;

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

complete the process of checking the initial path definition if there is no valid alternate path, and the path has been checked to the end point,

eliminate the valid alternate path by adding a new routing point to the initial path definition, if a valid alternate path has been determined by the check,

repeatedly check whether there is a valid alternate path between a newly added routing point and successive points of the initial path definition, wherein the valid alternate path does not contain the part of the path between the last two points included in a check, and

complete the process of checking the initial path definition by defining the final shortened path definition as a starting point, a sequence of routing points, and an ending point of the path.