Encoded representation of route data

• US 9,171,464 B2
• Filed: 09/30/2012
• Issued: 10/27/2015
• Est. Priority Date: 06/10/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Khetan, Gaurang R., McCabe, J. Paul, Bengtsson, Nils Stefan Daniel, Prestor, Uros
• Primary Examiner(s): Jabr, Fadey
• Assistant Examiner(s): INGRAM, THOMAS P
• Application Number:
  US13/632,049
• Publication Number:
  US 20130332077A1
• Time in Patent Office: 1,122 Days
• Field of Search: 701/400, 701/410, 701/420, 701/430, 701/437
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3626 Details of the output of route guidance instructions traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G01C 21/367 Details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of current position marker
• CPC Class Codes: G01C 21/3676 Overview of the route on the road map
• CPC Class Codes: G01C 21/3694 Output thereof on a road map
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 2200/24 involving graphical user interfaces [GUIs]
• CPC Class Codes: G08G 1/0962 having an indicator mounted inside the vehicle, e.g. giving voice messages
• CPC Class Codes: G08G 1/0967 Systems involving transmission of highway information, e.g. weather, speed limits transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G08G 1/096716 where the received information does not generate an automatic action on the vehicle control
• CPC Class Codes: G08G 1/096741 where the source of the transmitted information selects which information to transmit to each vehicle
• CPC Class Codes: G08G 1/096775 where the origin of the information is a central station
• CPC Class Codes: G08G 1/096816 where the complete route is transmitted to the vehicle at once
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/096861 where the immediate route instructions are output to the driver, e.g. arrow signs for next turn
• CPC Class Codes: H05K 999/99 dummy group

Abstract

For a route server that generates route data for a route between a starting location and a destination location on a map, a method of compressing the route data that includes a maneuvering instruction for each of a plurality of junctures from the starting location to the destination location of the route is described. For a maneuvering instruction for each juncture of the route, the method determines whether the maneuvering instruction for the juncture is needed at a route client that is to receive the route data. When the maneuvering instruction for a particular juncture is determined not to be needed at the route client, the method modifies the route data by removing the maneuvering instruction for the particular juncture from the route data.

Claims

1. For a route server that generates route data, a method of encoding the route data, the method comprising:

receiving, from a route client, a request for route data for a route comprising a plurality of junctures, the route data comprising maneuvering instruction data associated with each juncture in the plurality of junctures;

determining, for each juncture of the route, whether the associated maneuvering instruction data is producible by the route client without receiving the maneuvering instruction data from the route server, said determination made by comparing the maneuvering instruction for the juncture to a default maneuvering instruction for the same juncture generated based on a set of default direction rules;

encoding the route data by excluding, from the route data, any maneuvering instruction data that is determined to be producible at the route client, when generating the route data; and

sending the encoded route data to the route client.

2. The method of claim 1, wherein the route client decodes the encoded route data received from the route server by generating the excluded maneuvering instructions data and adding the generated maneuvering instructions data to the route data.

3. The method of claim 1, wherein the maneuvering instruction data is determined to be producible at the route client when the maneuvering instruction for the juncture is deemed to be identical to the default maneuvering instruction.

4. The method of claim 3, wherein each one of the maneuvering instruction and default maneuvering instruction comprises an outbound road segment to which to advance at the juncture, wherein the maneuvering instruction for the juncture is deemed to be identical to the default maneuvering instruction when the two outbound road segments are identical.

5. The method of claim 4, wherein the maneuvering instruction data is determined not to be identical to the default maneuvering instruction when the juncture has two outbound road segments that are close to each other.

6. The method of claim 5, wherein the two outbound road segments are close to each other when the outbound road segments make an angle within a threshold degree.

7. The method of claim 4, wherein the default outbound road segment of the default maneuvering instruction for the juncture is identified based on the set of default direction rules when a set of attributes associated with an inbound road segment of the juncture matches a set of attributes associated with the default outbound road segment of the juncture.

8. The method of claim 7, wherein each set of attributes comprises at least one of a functional class attribute, a form of way attribute, and a heading attribute.

9. The method of claim 7, wherein the set of attributes associated with the inbound road segment of the juncture matches the set of attributes associated with the default outbound road segment of the juncture when each attribute in the set of attributes associated with the inbound road segment is identical to or within a close range of a corresponding attribute in the set of attributes associated with the default outbound road segment.

10. A non-transitory machine readable medium storing a program which when executed by at least one processing unit of a device generates route data for a route server, the program comprising sets of instructions for:

receiving, from a route client, a request for route data for a route comprising a plurality of junctures, the route data comprising maneuvering instruction data associated with each juncture in the plurality of junctures;

determining, for each juncture of the route, whether an associated maneuvering instruction data for the juncture is producible at a route client without receiving the maneuvering instruction data from the route server, said determination made by comparing the maneuvering instruction for the juncture to a default maneuvering instruction for the same juncture generated based on a set of default direction rules;

including in the route data only those maneuvering instructions data for junctures that are determined not to be producible at the route client; and

sending the route data to the route client.

11. The machine readable medium of claim 10, wherein the set of instructions for determining whether a maneuvering instruction data is producible at the route client further comprises a set of instructions for determining that the maneuvering instruction data for the juncture is producible when the maneuvering instruction is identical to the default maneuvering instruction.

12. The machine readable medium of claim 11, wherein the set of instructions for determining whether a maneuvering instruction data is producible at the route client further comprises a set of instructions for determining the maneuvering instruction data is not producible at the route client even when the maneuvering instruction is identical to the default maneuvering instruction only if the juncture has two outbound road segments that are close to each other.

13. The machine readable medium of claim 12, wherein the two outbound road segments are close to each other when the outbound road segments make an angle within a threshold degree.

14. The machine readable medium of claim 11, wherein each one of the maneuvering instruction and default maneuvering instruction comprises an outbound road segment to which to advance at the juncture, wherein the maneuvering instruction is identical to the default maneuvering instruction when the two outbound road segments are identical.

15. The machine readable medium of claim 14, wherein the default outbound road segment of the default maneuvering instruction for the juncture is identified based on the set of default direction rules when a set of attributes associated with an inbound road segment of the juncture matches a set of attributes associated with the default outbound road segment of the juncture.

16. The machine readable medium of claim 15, wherein each set of attributes comprises at least one of a functional class attribute, a form of way attribute, and a heading attribute.

17. The machine readable medium of claim 10, wherein the route client generates maneuvering instructions data that is not included in the route data and adds the generated maneuvering instructions data to the route data received from the route server.

18. An electronic device comprising:

a set of processing units for executing sets of instructions; and

a machine-readable medium storing a program which when executed by at least one of the processing units generates route data for a route server, the program comprising sets of instructions for;

receiving, from a route client, a request for route data for a route comprising a plurality of junctures, the route data comprising maneuvering instruction data associated with each juncture in the plurality of junctures;

determining, for each juncture of the route, whether an associated maneuvering instruction data for the juncture is producible at a route client without receiving the maneuvering instruction data from the route server, said determination made by comparing the maneuvering instruction for the juncture to a default maneuvering instruction for the same juncture generated based on a set of default direction rules;

including in the route data only those maneuvering instructions data for junctures that are determined not to be producible at the route client; and

sending the route data to the route client.

19. The electronic device of claim 18, wherein the set of instructions for determining whether a maneuvering instruction data is producible at the route client further comprises a set of instructions for determining that the maneuvering instruction data for the juncture is producible when the maneuvering instruction is identical to the default maneuvering instruction.

20. The electronic device of claim 19, wherein each one of the maneuvering instruction and default maneuvering instruction comprises an outbound road segment to which to advance at the juncture, wherein the maneuvering instruction is identical to the default maneuvering instruction when the two outbound road segments are identical.

21. The electronic device of claim 20, wherein the default outbound road segment of the default maneuvering instruction for the juncture is identified based on the set of default direction rules when a set of attributes associated with an inbound road segment of the juncture matches a set of attributes associated with the default outbound road segment of the juncture.

22. The electronic device of claim 21, wherein each set of attributes comprises at least one of a functional class attribute, a form of way attribute, and a heading attribute.

23. The electronic device of claim 19, wherein the set of instructions for determining whether a maneuvering instruction data is producible at the route client further comprises a set of instructions for determining the maneuvering instruction data is not producible at the route client even when the maneuvering instruction is identical to the default maneuvering instruction only if the juncture has two outbound road segments that are close to each other.

24. The electronic device of claim 23, wherein the two outbound road segments are close to each other when the outbound road segments make an angle within a threshold degree.

25. The electronic device of claim 18, wherein the route client generates maneuvering instructions data that is not included in the route data and adds the generated maneuvering instructions data to the route data received from the route server.