RECONSTRUCTING ROUTES USING ELECTRONIC MAP DATA

• US 20170016730A1
• Filed: 03/06/2015
• Published: 01/19/2017
• Est. Priority Date: 03/07/2014
• Status: Active Grant

• Current Assignee: TomTom International BV (TomTom NV)
• Original Assignee: TomTom Navigation B.V (TomTom NV)
• Inventors: GAWRILOW, Ewgenij
• Granted Patent: US 10,731,990 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G01C 21/36 Input/output arrangements for on-board computers

Abstract

A navigation device (300) transmits data indicative of an origin and destination of a desired route through a navigable network to a server. The server (310) generates a recommended route and provides data indicative of the route to a system (320) which provides a polyline representative of the route. The polyline is provided to the navigation device (300), which uses the polyline data to reconstruct the route. The navigation device (300) determines a least cost route through the network using the polyline data in order to reconstruct the route in respect to its own electronic map data. This is done by penalising segments depending upon their distance from the polyline, such that segments further from the polyline are less likely to be included in the route.

Claims

1. A method of reconstructing a route through a navigable network in an area covered by an electronic map, the electronic map comprising a plurality of segments representing navigable segments of the navigable network, the method comprising:

obtaining data indicative of a polyline representative of a route through the navigable network, which route is to be reconstructed in relation to the electronic map; and

using the obtained data indicative of the polyline in generating a route through the navigable network as represented by the electronic map, wherein the generated route provides a reconstruction of the route represented by the polyline through the navigable network in relation to the electronic map, and wherein the generating of the route comprises favouring segments of the electronic map for inclusion in the generated route that are in greater proximity to the polyline as represented on the electronic map.

2. The method of claim 1, comprising defining an area based on the polyline as represented on the electronic map, and favouring those segments of the electronic map which are considered to be within the area for the purposes of route generation.

3. The method of claim 1 further comprising penalising segments of the electronic map for the purposes of route generation to a degree which depends upon the proximity of the respective segments to the polyline as represented on the electronic map, wherein those segments that are further from the polyline are penalised to a greater degree than those that are closer to the polyline.

4. The method of claim 3, wherein segments are penalised by applying a variable penalty factor thereto depending upon distance of the segment from the polyline.

5. The method of claim 4, wherein the penalty factor applied to segments varies in proportion to a square of the distance between a segment and the polyline.

6. The method of claim 3, wherein segments are penalised by applying a penalty factor thereto, the penalty factor being used to provide a cost factor associated with traversing the segment that is taken into account in route generation.

7. The method of claim 1, wherein generating the route to provide a reconstruction of the route represented by the polyline comprises generating a least cost route through the navigable network.

8. The method of claim 1, wherein obtaining the data indicative of the polyline and using the obtained data in generating the route through the navigable network as represented by the electronic map are performed by a navigation device, the navigation device storing data indicative of the electronic map.

9. The method of claim 8, wherein the route to be reconstructed is an pre-planned route generated off-board from the navigation device, wherein the route is planned by a server in response to a request by the navigation device.

10. The method of claim 1, further comprising using data indicative of the route through the navigable network to be reconstructed to generate the data indicative of the polyline representative thereof.

11. The method of claim 1, wherein the route to be reconstructed is a pre-planned route between a first location and a second location.

12. The method of claim 8, wherein the route to be reconstructed is a previously travelled route through the network.

13. The method of claim 12, further comprising obtaining positional data and associated timing data indicative of the travelled route, and using the data to generate the data indicative of the polyline representative of the route.

14. The method of claim 13, wherein the navigation device obtains the positional data and associated timing data, and using the data to generate the polyline data, wherein the previously travelled route is a route travelled by the navigation device.

15. The method of claim 14, comprising the navigation device storing data indicative of a plurality of routes previously travelled by the device through the navigable network in the area covered by the electronic map of the device, and, for each route, using the previously travelled route data to generate data indicative of a polyline representative of the route, using the obtained data indicative of a polyline to generate a route through the navigable network as represented by the electronic map, the generated route providing a reconstruction of the route represented by the polyline, and storing data indicative of the reconstructed route.

16. The method of claim 1, wherein obtaining the data indicative of the polyline comprises receiving the data over a wireless communications link.

17. The method of claim 1, wherein the received polyline data is associated with the electronic map data for use in reconstruction, or data which may be used to retrieve the electronic map data, the method further comprising receiving and storing the electronic map data for use in route reconstruction.

18. The method of claim 1, further comprising outputting the generated route to a user and/or providing a set of navigation instructions for guiding a user along the route.

19. A routing system for reconstructing a route through a navigable network in an area covered by an electronic map, the electronic map comprising a plurality of segments representing navigable segments of the navigable network, the system comprising:

a processor;

a memory, wherein the memory stores the electronic map;

wherein the processor is operable to;

obtain data indicative of a polyline representative of a route through the navigable network, which route is to be reconstructed in relation to the electronic map; and

use the obtained data indicative of the polyline in generating a route through the navigable network as represented by the electronic map, wherein the generated route provides a reconstruction of the route represented by the polyline in relation to the electronic map, and wherein the generating of the route comprises favouring segments of the electronic map for inclusion in the generated route that are in greater proximity to the polyline as represented on the electronic map.

20. (canceled)

21. (canceled)

22. (canceled)

23. A non-transitory computer readable medium which stores a set of instructions which when executed performs a method for reconstructing a route through a navigable network in an area covered by an electronic map, the electronic map comprising a plurality of segments representing navigable segments of the navigable network, comprising:

obtaining data indicative of a polyline representative of a route through the navigable network, which route is to be reconstructed in relation to the electronic map; and

using the obtained data indicative of the polyline in generating a route through the navigable network as represented by the electronic map, wherein the generated route provides a reconstruction of the route represented by the polyline through the navigable network in relation to the electronic map, and wherein the generating of the route comprises favouring segments of the electronic map for inclusion in the generated route that are in greater proximity to the polyline as represented on the electronic map.