Encoded representation of route data

• US 9,909,897 B2
• Filed: 10/02/2015
• Issued: 03/06/2018
• 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): INGRAM, THOMAS P
• Application Number:
  US14/874,129
• Publication Number:
  US 20160097653A1
• Time in Patent Office: 886 Days
• 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

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 client executing a navigation application that provides maneuvering instructions for a route that comprises a plurality of junctures between a starting location and a destination location on a map, a method comprising:

receiving compressed route data that comprises maneuvering instructions for a subset of the plurality of junctures between the starting and destination locations;

decompressing the route data by, for each juncture of the route, determining whether the route data comprises a maneuvering instruction for the juncture; and

generating a maneuvering instruction for each juncture of the route that does not have a maneuvering instruction in the route data.

2. The method of claim 1, wherein the route data is received from a route server that generates the route data by excluding from the route data a set of maneuvering instructions that are not needed by the route client.

3. The method of claim 2, wherein said generating maneuvering instructions comprises using a set of routing rules.

4. The method of claim 3, wherein the set of routing rules comprises a set of default direction rules, wherein the route server determines to exclude from the route data a maneuvering instruction for a juncture by comparing the maneuvering instruction for the juncture to a default maneuvering instruction for the same juncture generated based on the set of default direction rules.

5. The method of claim 4, wherein the route server excludes the maneuvering instruction from the route data when the route server determines that the maneuvering instruction for the juncture is identical to the default maneuvering instruction.

6. The method of claim 5, 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 identical to the default maneuvering instruction when the outbound road segment for the maneuvering instruction is identical to the outbound road segment for the default maneuvering instruction.

7. The method of claim 5, wherein the route client uses the default maneuvering instruction to generate the maneuvering instruction for the juncture.

8. The method of claim 1 further comprising displaying only those maneuvering instructions that are included in the route data.

9. The method of claim 1, wherein generating a maneuvering instruction for a juncture comprises:

determining an outbound road segment for the juncture based on a set of default direction rules; and

generating the maneuvering instruction based on the determined outbound road segment.

10. The method of claim 9, wherein the route client and route server share the set of default direction rules.

11. The method of claim 1, wherein receiving the route data comprises:

receiving the starting and destination locations from a user;

sending the starting and destination locations to a route server; and

receiving the route data between the starting and destination locations from the route server.

12. The method of claim 1 further comprising sending the plurality of junctures each of which is associated with a maneuvering instruction to a rendering engine to render the route and the maneuvering instructions.

13. A non-transitory machine readable medium storing a navigation program for execution by at least one processing unit, the program for a route client that provides maneuvering instructions for a route that comprises a plurality of junctures between a starting location and a destination location on a map, the program comprising sets of instructions for:

receiving compressed route data that comprises maneuvering instructions for a subset of the plurality of junctures between the starting and destination locations;

decompressing the route data by, for each juncture of the route, determining whether the route data comprises a maneuvering instruction for the juncture; and

generating a maneuvering instruction for each juncture of the route that does not have a maneuvering instruction in the route data.

14. The non-transitory machine readable medium of claim 13, wherein the route data is received from a route server that generates the route data by excluding from the route data a set of maneuvering instructions that are not needed by the route client.

15. The non-transitory machine readable medium of claim 14, wherein the set of instructions for generating maneuvering instructions comprises a set of instructions for using a set of routing rules.

16. The non-transitory machine readable medium of claim 15, wherein the set of routing rules comprises a set of default direction rules, wherein the route server determines to exclude from the route data a maneuvering instruction for a juncture by comparing the maneuvering instruction for the juncture to a default maneuvering instruction for the same juncture generated based on the set of default direction rules.

17. The non-transitory machine readable medium of claim 16, wherein the route server excludes the maneuvering instruction from the route data when the route server determines that the maneuvering.

18. The non-transitory machine readable medium of claim 13, wherein the program further comprises a set of instructions for displaying only those maneuvering instructions that are included in the route data.

19. The non-transitory machine readable medium of claim 13, wherein the set of instructions for generating a maneuvering instruction for a juncture comprises a set of instructions for:

determining an outbound road segment for the juncture based on a set of default direction rules; and

generating the maneuvering instruction based on the determined outbound road segment.

20. The non-transitory machine readable medium of claim 19, wherein the route client and route server share the set of default direction rules.