Selective download of corridor map data

• US 20060025923A1
• Filed: 07/28/2004
• Published: 02/02/2006
• Est. Priority Date: 07/28/2004
• Status: Active Grant

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: Telmap Limited (Intel Corporation)
• Inventors: Elad, Tal, Dotan, Emanuel, Kupferman, Michael Menachem
• Granted Patent: US 7,251,561 B2
• Time in Patent Office: Days
• US Class Current: 701/207
• 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/3815 Road data
• CPC Class Codes: G01C 21/3889 Transmission of selected map data, e.g. depending on route
• CPC Class Codes: G08G 1/096822 where the segments of the route are transmitted to the vehicle at different locations and times
• CPC Class Codes: G08G 1/096861 where the immediate route instructions are output to the driver, e.g. arrow signs for next turn

Abstract

A method for displaying a map on a mobile client device. The method includes storing map data on a server, the map data including road data with respect to roads of multiple different road types. The server determines a route from a starting point to a destination within an area covered by the map data, the route including one or more route segments. The server defines a corridor map including the route segments and the roads of the different road types that are within different, respective distances, determined by the road types, of the route segments. The server downloads the road data with respect to the route segments and the roads of the different road types included in the corridor map to the client device. The client device, using the downloaded road data, renders one or more images, each image comprising at least a respective portion of the corridor map.

Claims

1. A method for displaying a map on a mobile client device, the method comprising:

storing map data on a server, the map data comprising road data with respect to roads of multiple different road types;

determining a route from a starting point to a destination within an area covered by the map data, the route comprising one or more route segments;

defining a corridor map on the server, the corridor map comprising the route segments and the roads of the different road types that are within different, respective distances, determined by the road types, of the route segments;

downloading the road data with respect to the route segments and the roads of the different road types comprised in the corridor map from the server to the client device; and

rendering on the client device, using the downloaded road data, one or more images, each image comprising at least a respective portion of the corridor map.

2. The method according to claim 1, wherein determining the route comprises determining the route along which a user of the client device is to travel, and wherein rendering the images comprises rendering the images in a succession as the user travels along the route.

3. The method according to claim 2, wherein rendering the images comprises finding position coordinates of the user using a location providing device associated with the client device, and displaying the images together with a navigation aid based on the position coordinates.

4. The method according to claim 3, wherein finding the position coordinates comprises receiving an initial location reading from the location providing device, and matching the initial location reading to the downloaded road data in order to find the position coordinates with respect to the corridor map.

5. The method according to claim 2, wherein downloading the road data comprises streaming the road data to the client device as the user travels along the route.

6. The method according to claim 1, wherein downloading the portion of the map data comprises downloading the map data over a wireless link.

7. The method according to claim 6, wherein the client device comprises at least one of a cellular telephone and a personal digital assistant (PDA), which communicates with the server over a cellular telephone network that comprises the wireless link.

8. The method according to claim 6, wherein downloading the road data comprises downloading, together with the road data, a prompt associated with at least one of the route segments, so as to cause the client device to request updated information from the server as a user of the client device travels over the route in a vicinity of the at least one of the route segments.

9. The method according to claim 1, wherein a classification of the roads into the different road types corresponds to expected speeds of travel on the roads.

10. The method according to claim 9, wherein the road types comprise at least first and second road types, the first road type having a higher expected speed of travel than the second road type, and

wherein defining the corridor map comprises incorporating in the map segments the roads of the first and second road types that are within respective first and second distances of the route segments, such that the first distance is greater than the second distance.

11. The method according to claim 1, wherein the road types comprise highways and local streets, and

wherein defining the corridor map comprises incorporating in the map segments the highways that are within a first distance of the route segments and the local streets that are within a second distance of the route, such that the first distance is greater than the second distance.

12. The method according to claim 1, wherein determining the route comprises identifying junctions along the route, and associating respective measures of complexity with the junctions, and

wherein defining the corridor map comprises modifying the respective distances responsively to the measures of complexity.

13. The method according to claim 12, wherein modifying the respective distances comprises increasing the respective distances in a vicinity of the junctions that are characterized as complex junctions.

14. The method according to claim 12, wherein associating the respective measures of complexity comprises determining a junction complexity score for each junction responsively to a topology of the junction.

15. The method according to claim 12, wherein determining the route comprises defining maneuvers to be performed at the junctions along the route, and wherein associating the respective measures of complexity comprises determining a maneuver complexity score for each maneuver.

16. The method according to claim 1, wherein defining the corridor map comprises identifying junctions at which the roads comprised in the one or more map segments intersect with further roads of the different road types that are not within the respective distances, and adding one or more of the further roads to the one or more map segments.

17. The method according to claim 1, wherein determining the route comprises determining the route along which a user of the client device is to travel, and wherein defining the corridor map comprises determining a respective path to the destination from each of at least some of the roads comprised in each of the map segments, and comprising downloading the respective path to the client device in order to guide the user to the destination in the event of a deviation from the route onto one of the at least some of the roads.

18. The method according to claim 17, wherein downloading the respective path comprises associating with each of the roads in the corridor map a pointer to a subsequent road along the respective path, and downloading the pointer to the client device.

19. The method according to claim 1, wherein the corridor map has a width that is defined at each point along the route by an extent of the roads of the different road types that are comprised in the corridor map in a vicinity of the point, and wherein the width of the corridor map varies along the route responsively to the extent of the roads.

20. The method according to claim 1, wherein downloading the road data comprises sorting the roads according to a respective distance of each of the roads from a location of the client device, and downloading the road data with respect to the roads in an order responsive to the distance.

21. The method according to claim 20, wherein downloading the road data comprises streaming the road data to the client device in the order responsive to the distance as a user of the client device travels along the route.

22. The method according to claim 1, wherein downloading the road data comprises downloading data structures that represent the roads, each data structure indicating a directional link.

23. The method according to claim 22, wherein each data structure comprises one or more data fields indicating characteristics of the directional link selected from a group of characteristics consisting of a next link along an optimal route to the destination, a distance to the destination, and a time required to travel to the destination.

24. A method for displaying a map on a mobile client device, the method comprising:

storing map data on a server;

determining a route at the server from a starting point to a destination within an area covered by the map data, the route comprising a sequence of the directional links, in which each directional link is represented by a data structure containing a pointer to a succeeding directional link along the route;

downloading the route from the server to the client device; and

rendering on the client device, using the downloaded route, a map indicative of the route.

25. The method according to claim 24, and comprising generating navigation instructions for a user of the client device based on the pointer in one or more of the data structures.

26. The method according to claim 25, wherein rendering the map comprises rendering a maneuver map responsively to the navigation instructions.

27. The method according to claim 25, and comprising defining a corridor map on the server, the corridor map comprising the route and further directional links corresponding to other roads included in the map data in a vicinity of the route, and wherein generating the navigation instructions comprises guiding the user to the destination, responsively to the pointer in one or more of the data structures corresponding to the other roads, in the event of a deviation from the route onto one of the other roads.

28. The method according to claim 24, wherein rendering the map comprises rendering a single road segment to represent two of the directional links corresponding to opposing directions of travel on the single road segment.

29. The method according to claim 24, wherein the data structure representing each directional link comprises a field indicating at least one of a distance to the destination and a time to the destination from a location associated with the directional link.

30. The method according to claim 24, wherein the data structure representing at least one of the directional links comprises a prompt, so as to cause the client device to request updated information from the server as a user of the client device travels over the route at a location associated with the directional link.

31. The method according to claim 24, and comprising defining a corridor map on the server, the corridor map comprising the route and other roads included in the map data in a vicinity of the route, wherein downloading the route comprises sorting the other roads in the corridor map according to a respective distance of each of the roads from a location of the client device, and downloading the map data with respect to the other roads in an order responsive to the distance.

32. The method according to claim 31, wherein downloading the map data comprises streaming the map data to the client device in the order responsive to the distance as a user of the client device travels along the route.

33. The method according to claim 32, wherein downloading the map data comprises performing a breadth-first search of the other roads connecting to the starting point of the route, and downloading the map data with respect to the roads found by the breadth-first search immediately after defining the corridor map.

34. A method for displaying a map on a mobile client device, the method comprising:

storing map data on a server;

determining a route at the server from a starting point to a destination within an area covered by the map data, the route comprising a sequence of route segments;

associating a prompt with at least one of the route segments, so as to cause a client device to request updated information with respect to the route as a user of the client device travels over the route at a location associated with the at least one of the route segments;

downloading the route segments from the server to the client device;

rendering on the client device, using the downloaded route segments, a map indicative of the route; and

responsively to the prompt, receiving a request from the client device for the updated information, and providing the updated information with respect to the route.

35. The method according to claim 34, wherein downloading the route segments comprises downloading data to the client device over a wireless link, and wherein receiving the request comprises receiving a communication initiated by the client device over the wireless link.

36. The method according to claim 35, wherein receiving the communication comprises receiving a Hypertext Transfer Protocol (HTTP) request, and wherein providing the updated information comprises sending a HTTP response.

37. The method according to claim 34, wherein providing the updated information comprises informing the client device of a change in the route.

38. Apparatus for displaying a map on a mobile client device, the apparatus comprising:

a memory, which is arranged to store map data, comprising road data with respect to roads of multiple different road types; and

a server, which is adapted to determine a route from a starting point to a destination within an area covered by the map data, the route comprising one or more route segments, and which is adapted to define a corridor map comprising the route segments and the roads of the different road types that are within different, respective distances, determined by the road types, of the route segments, and to download the road data with respect to the route segments and the roads of the different road types comprised in the corridor map to the client device so as to enable the client device, using the downloaded road data, to render one or more images, each image comprising at least a respective portion of the corridor map.

39. The apparatus according to claim 38, wherein the server is adapted to determine the route along which a user of the client device is to travel, and to download the map segments one after another in sequence as the user travels along the route.

40. The apparatus according to claim 38, wherein the server is coupled to download the road data to the client device over a wireless link.

41. The apparatus according to claim 38, wherein a classification of the roads into the different road types corresponds to expected speeds of travel on the roads.

42. The apparatus according to claim 41, wherein the road types comprise at least first and second road types, the first road type having a higher expected speed of travel than the second road type, and

wherein the server is adapted to incorporate in the map segments the roads of the first and second road types that are within respective first and second distances of the route segments, such that the first distance is greater than the second distance.

43. The apparatus according to claim 38, wherein the road types comprise highways and local streets, and

wherein the server is adapted to incorporate in the map segments the highways that are within a first distance of the route segments and the local streets that are within a second distance of the route, such that the first distance is greater than the second distance.

44. The apparatus according to claim 38, wherein the server is adapted to identify junctions along the route, and to associate respective measures of complexity with the junctions, and to modify the respective distances responsively to the measures of complexity.

45. The apparatus according to claim 44, wherein the server is adapted to increase the respective distances in a vicinity of the junctions that are characterized as complex junctions.

46. The apparatus according to claim 44, wherein the respective measures of complexity comprise a junction complexity score that is determined for each junction responsively to a topology of the junction.

47. The apparatus according to claim 44, wherein the server is adapted to define maneuvers to be performed at the junctions along the route, and wherein the respective measures of complexity comprise a maneuver complexity score for each maneuver.

48. The apparatus according to claim 38, wherein the server is adapted to identify junctions at which the roads comprised in the one or more map segments intersect with further roads of the different road types that are not within the respective distances, and to add one or more of the further roads to the one or more map segments.

49. The apparatus according to claim 38, wherein the server is adapted to determine the route along which a user of the client device is to travel, and to determine a respective path to the destination from each of at least some of the roads comprised in each of the map segments, and to download the respective path to the client device in order to guide the user to the destination in the event of a deviation from the route onto one of the at least some of the roads.

50. The apparatus according to claim 49, wherein the server is adapted to associate with each of the roads in the corridor map a pointer to a subsequent road along the respective path, and to download the pointer to the client device.

51. The apparatus according to claim 38, wherein the corridor map has a width that is defined at each point along the route by an extent of the roads of the different road types that are comprised in the corridor map in a vicinity of the point, and wherein the width of the corridor map varies along the route responsively to the extent of the roads.

52. The apparatus according to claim 38, wherein the server is adapted to sort the roads according to a respective distance of each of the roads from a location of the client device, and to download the road data with respect to the roads in an order responsive to the distance.

53. Apparatus for displaying a map on a mobile client device, the apparatus comprising:

a memory, which is arranged to store map data;

a server, which is adapted to determine a route from a starting point to a destination within an area covered by the map data, the route comprising a sequence of the directional links, in which each directional link is represented by a data structure containing a pointer to a succeeding directional link along the route, and to download the route to the client device, so as to enable the client device, using the downloaded route, to render a map indicative of the route.

54. The apparatus according to claim 53, and comprising the client device, which is adapted to render the map and to generate navigation instructions for a user of the client device based on the pointer in one or more of the data structures.

55. The apparatus according to claim 54, wherein the map comprises a maneuver map, which is generated by the client device responsively to the navigation instructions.

56. The apparatus according to claim 54, wherein the server is adapted to define a corridor map, comprising the route and further directional links corresponding to other roads included in the map data in a vicinity of the route, and wherein the client device is adapted to guide the user to the destination, responsively to the pointer in one or more of the data structures corresponding to the other roads, in the event of a deviation from the route onto one of the other roads.

57. The apparatus according to claim 54, and comprising a location providing device, associated with the client device, for providing position coordinates of the user, wherein the client device is adapted to render the map and generate the navigation instructions based on the position coordinates.

58. The apparatus according to claim 57, wherein the client device is coupled to receive an initial location reading from the location providing device, and is adapted to match the initial location reading to the directional links in order to find the position coordinates with respect to the route.

59. The apparatus according to claim 53, wherein the data structure representing each directional link comprises a field indicating at least one of a distance to the destination and a time to the destination from a location associated with the directional link.

60. The apparatus according to claim 53, wherein the data structure representing at least one of the directional links comprises a prompt, so as to cause the client device to request updated information from the server as a user of the client device travels over the route at a location associated with the directional link.

61. The apparatus according to claim 53, wherein the server is adapted to define a corridor map comprising the route and other roads included in the map data in a vicinity of the route, and to sort the other roads in the corridor map according to a respective distance of each of the roads from a location of the client device, and to download the map data with respect to the other roads in an order responsive to the distance.

62. The apparatus according to claim 61, wherein the server is adapted to stream the map data to the client device in the order responsive to the distance as a user of the client device travels along the route.

63. The apparatus according to claim 62, wherein the server is adapted to perform a breadth-first search of the other roads connecting to the starting point of the route, and to download the map data with respect to the roads found by the breadth-first search immediately after defining the corridor map.

64. Apparatus for displaying a map on a mobile client device, the apparatus comprising:

a memory, which is arranged to store map data;

a client device; and

a server, which is adapted to determine a route from a starting point to a destination within an area covered by the map data, the route comprising a sequence of route segments, and to associate a prompt with at least one of the route segments, so as to cause the client device to request updated information with respect to the route as a user of the client device travels over the route at a location associated with the at least one of the route segments, and which is coupled to download the route segments to the client device,

wherein the client device is adapted to render an image of a map indicative of the route, using the downloaded route segments, and is further adapted, responsively to the prompt, to submit a request to the server for the updated information, and wherein the server is adapted to provide the updated information with respect to the route in response to the request.

65. The apparatus according to claim 64, wherein the server and the client device are coupled to communicate over a wireless link.

66. The apparatus according to claim 64, wherein the request comprises a Hypertext Transfer Protocol (HTTP) request, and wherein the server is adapted to provide the updated information in a HTTP response.

67. The apparatus according to claim 64, wherein the updated information comprises a notice to the client device of a change in the route.

68. A computer software product for displaying a map on a mobile client device, the product comprising a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to read map data, comprising road data with respect to roads of multiple different road types, and to determine a route from a starting point to a destination within an area covered by the map data, the route comprising one or more route segments, the instructions further causing the computer to define a corridor map comprising the route segments and the roads of the different road types that are within different, respective distances, determined by the road types, of the route segments, and to download the road data with respect to the route segments and the roads of the different road types comprised in the corridor map to the client device so as to enable the client device, using the downloaded road data, to render one or more images, each image comprising at least a respective portion of the corridor map.

69. The product according to claim 68, wherein the instructions cause the computer to determine the route along which a user of the client device is to travel, and to download the map segments one after another in sequence as the user travels along the route.

70. The product according to claim 68, wherein the instructions cause the computer to download the map data to the client device over a wireless link.

71. The product according to claim 68, wherein a classification of the roads into the different road types corresponds to expected speeds of travel on the roads.

72. The product according to claim 71, wherein the road types comprise at least first and second road types, the first road type having a higher expected speed of travel than the second road type, and

wherein the instructions cause the computer to incorporate in the map segments the roads of the first and second road types that are within respective first and second distances of the route segments, such that the first distance is greater than the second distance.

73. The product according to claim 68, wherein the road types comprise highways and local streets, and

wherein the instructions cause the computer to incorporate in the map segments the highways that are within a first distance of the route segments and the local streets that are within a second distance of the route, such that the first distance is greater than the second distance.

74. The product according to claim 68, wherein the instructions cause the computer to identify junctions along the route, and to associate respective measures of complexity with the junctions, and to modify the respective distances responsively to the measures of complexity.

75. The product according to claim 74, wherein the instructions cause the computer to increase the respective distances in a vicinity of the junctions that are characterized as complex junctions.

76. The product according to claim 74, wherein the respective measures of complexity comprise a junction complexity score that is determined for each junction responsively to a topology of the junction.

77. The product according to claim 74, wherein the instructions cause the computer to define maneuvers to be performed at the junctions along the route, and wherein the respective measures of complexity comprise a maneuver complexity score for each maneuver.

78. The product according to claim 68, wherein the instructions cause the computer to identify junctions at which the roads comprised in the one or more map segments intersect with further roads of the different road types that are not within the respective distances, and to add one or more of the further roads to the one or more map segments.

79. The product according to claim 68, wherein the instructions cause the computer to determine the route along which a user of the client device is to travel, and to determine a respective path to the destination from each of at least some of the roads comprised in each of the map segments, and to download the respective path to the client device in order to guide the user to the destination in the event of a deviation from the route onto one of the at least some of the roads.

80. The product according to claim 79, wherein the instructions cause the computer to associate with each of the roads in the corridor map a pointer to a subsequent road along the respective path, and to download the pointer to the client device.

81. The product according to claim 68, wherein the corridor map has a width that is defined at each point along the route by an extent of the roads of the different road types that are comprised in the corridor map in a vicinity of the point, and wherein the width of the corridor map varies along the route responsively to the extent of the roads.

82. The product according to claim 68, wherein the instructions cause the computer to sort the roads according to a respective distance of each of the roads from a location of the client device, and to download the road data with respect to the roads in an order responsive to the distance.

83. A computer software product for displaying a map on a mobile client device, the product comprising a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to read map data, and to determine a route from a starting point to a destination within an area covered by the map data, the route comprising a sequence of the directional links, in which each directional link is represented by a data structure containing a pointer to a succeeding directional link along the route, and to download the route to the client device, so as to enable the client device, using the downloaded route, to render a map indicative of the route.

84. The product according to claim 83, wherein the instructions cause the client device to generate navigation instructions for a user of the client device based on the pointer in one or more of the data structures.

85. The product according to claim 84, wherein the map comprises a maneuver map, which is generated by the client device responsively to the navigation instructions.

86. The product according to claim 84, wherein the instructions cause the computer to define a corridor map, comprising the route and further directional links corresponding to other roads included in the map data in a vicinity of the route, such that the client device is able to guide the user to the destination, responsively to the pointer in one or more of the data structures corresponding to the other roads, in the event of a deviation from the route onto one of the other roads.

87. The product according to claim 83, wherein the data structure representing each directional link comprises a field indicating at least one of a distance to the destination and a time to the destination from a location associated with the directional link.

88. The product according to claim 83, wherein the data structure representing at least one of the directional links comprises a prompt, so as to cause the client device to request updated information from the server as a user of the client device travels over the route at a location associated with the directional link.

89. The product according to claim 83, wherein the instructions cause the computer to define a corridor map comprising the route and other roads included in the map data in a vicinity of the route, and to sort the other roads in the corridor map according to a respective distance of each of the roads from a location of the client device, and to download the map data with respect to the other roads in an order responsive to the distance.

90. The product according to claim 89, wherein the instructions cause the computer to stream the map data to the client device in the order responsive to the distance as a user of the client device travels along the route.

91. The product according to claim 90, wherein the instructions cause the computer to perform a breadth-first search of the other roads connecting to the starting point of the route, and to download the map data with respect to the roads found by the breadth-first search immediately after defining the corridor map.

92. A computer software product for displaying a map on a mobile client device, the product comprising a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to read map data and to determine a route from a starting point to a destination within an area covered by the map data, the route comprising a sequence of route segments, and to associate a prompt with at least one of the route segments, so as to cause the client device to request updated information with respect to the route as a user of the client device travels over the route at a location associated with the at least one of the route segments, and to download the route segments to the client device so as to enable the client device to render an image of a map indicative of the route, using the downloaded route segments, the instructions further causing the computer to receive, responsively to the prompt, a request from the client device for the updated information, and to provide the updated information with respect to the route in response to the request.

93. The product according to claim 92, wherein the request comprises a Hypertext Transfer Protocol (HTTP) request, and wherein the instructions cause the computer to provide the updated information in a HTTP response.

94. The product according to claim 92, wherein the updated information comprises a notice to the client device of a change in the route.