METHODS AND SYSTEMS FOR RECONSTRUCTING TRACKS USING ELECTRONIC MAP DATA

• US 20170082453A1
• Filed: 11/04/2015
• Published: 03/23/2017
• Est. Priority Date: 09/21/2015
• Status: Active Grant

• Current Assignee: TomTom Navigation B.V (TomTom NV)
• Original Assignee: TomTom Navigation B.V (TomTom NV)
• Inventors: Fischer, Johannes Robert, Sasse, Jan-Ole, Grothklags, Sven
• Granted Patent: US 9,816,831 B2
• Time in Patent Office: Days
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• 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/3667 Display of a road map G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635

Abstract

A method and system for generating a route reconstructing a track through a navigable network in an area covered by an electronic map is disclosed, wherein the track is represented by an ordered series of point locations. One or more of the point locations are selected and an area is defined and associated with each of the one or more selected point locations. The ordered series of point locations and the defined areas are used to determine a plurality of polylines, and, for each of the polylines, a first route is generated based on the respective polyline. A second route is generated through each of the defined areas connecting the respective first generated routes. The route reconstructing the track comprises the generated first routes and the one or more generated second routes.

Claims

1. A method of generating a route reconstructing a track through a navigable network in an area covered by an electronic map, the electronic map comprising a plurality of segments representing navigable elements of the navigable network, the method comprising using at least one processor arranged to:

obtain data indicative of a track through the navigable network to be reconstructed, wherein said data indicative of the track comprises an ordered series of point locations;

select one or more of the point locations, and defining an area associated with each of the one or more selected point locations;

use the ordered series of point locations and the defined areas associated with each of the selected one or more point locations to determine a plurality of polylines, each polyline being representative of a portion of the track to be reconstructed;

generate, for each of the polylines, a first route along segments of the electronic map using a first routing process based on the respective polyline, wherein the generated first route provides a reconstruction of the portion of the track represented by the polyline through the navigable network in relation to the electronic map;

generate, for the defined area associated with each of the selected one or more point locations, a second route along segments of the electronic map using a second routing process, wherein the second generated route provides a route through the defined area connecting the respective first generated routes, at least one of the segments of the second generated route being determined based in part on the relative distance between the segment and the point location to which the area is associated; and

output for provision to a user at least one of;

data indicative of the route reconstructing the track; and

a set of navigation instructions for guiding the user along at least a portion of the route reconstructing the track, wherein the route reconstructing the track comprises the generated first routes and the one or more generated second routes.

2. The method of claim 1, wherein the data indicative of the track comprises one of:

a recorded track;

an itinerary;

or a pre-planned route.

3. The method of claim 1, wherein said using the ordered series of point locations and the defined areas associated with each of the selected one or more point locations to determine a plurality of polylines comprises:

using the ordered series of point location to determine a first polyline representative of the track to be reconstructed; and

using the defined areas associated with each of the selected one or more point locations to cut the first polyline into a plurality of second polylines, each of the second polylines being representative of a portion of the track to be reconstructed.

4. The method of claim 1, comprising determining a distance between neighbouring point locations, wherein the one or more selected point locations comprise the point locations that are spaced from a neighbouring point location by more than a predetermined distance value.

5. The method of claim 1, comprising using the ordered series of point locations to determine at least one curved portion of the track to be reconstructed having a curvature above a predetermined curvature value, wherein the one or more selected point locations comprise at least one point location on the at least one curved portion of the track to be reconstructed.

6. The method of claim 1, further comprising:

defining an area associated with one or both of an origin and a destination location of the ordered series of point locations; and

generating, for the defined area associated with the origin and/or destination location, a third route along segments of the electronic map using a third routing process, wherein the third generated route provides a route from a segment within the defined area to the respective first generated route, the segment being determined based in part on the relative distance between the segment and the point location to which the area is associated,

wherein the route reconstructing the track further comprises the one or more generated third routes.

7. The method of claim 1, wherein the defined area associated with a point location is a circular area centred on the point location having a predetermined radius.

8. The method of claim 1, wherein the first routing process comprises favouring segments of the electronic map for inclusion in the generated route that are in greater proximity to the respective polyline.

9. The method of claim 8, wherein the first routing process comprises 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 respective polyline as represented on the electronic map, wherein those segments that are further from the respective polyline are penalised to a greater degree than those that are closer to the respective polyline.

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

18. A non-transitory computer readable medium comprising instructions which, when executed by at least one processor of a computing device, cause the computing device to operate according to the method of claim 1.

11. A method of generating a route reconstructing a track through a navigable network in an area covered by an electronic map, the electronic map comprising a plurality of segments representing navigable elements of the navigable network, the method comprising using at least one processor arranged to:

obtain data indicative of a track through the navigable network to be reconstructed, wherein said data indicative of the track comprises an ordered series of point locations from an origin location to a destination location;

select one or both of the origin and destination locations, and defining an area associated with each of the one or more selected point locations;

use the ordered series of point locations to determine one or more polylines, each of said one or more polylines being representative of at least a portion of the track to be reconstructed;

generate, for each of the one or more polylines, a first route along segments of the electronic map using a first routing process based on the respective polyline, wherein the generated first route provides a reconstruction of the at least a portion of the track represented by the polyline through the navigable network in relation to the electronic map;

generate, for the defined area associated with each of the selected one or more point locations, a second route along segments of the electronic map using a second routing process, wherein the second generated route provides a route from a segment within the defined area to the respective first generated route, the segment being determined based in part on the relative distance between the segment and the point location to which the area is associated; and

output for provision to a user at least one of;

data indicative of the route reconstructing the track; and

a set of navigation instructions for guiding the user along at least a portion of the route reconstructing the track, wherein the route reconstructing the track comprises the one or more generated first routes and the one or more generated second routes.

12. The method of claim 11, wherein the data indicative of the track comprises one of:

a recorded track;

an itinerary;

or a pre-planned route.

13. The method of claim 11, wherein the defined area associated with a point location is a circular area centred on the point location having a predetermined radius.

14. The method of claim 11, wherein the first routing process comprises favouring segments of the electronic map for inclusion in the generated route that are in greater proximity to the respective polyline.

15. The method of claim 14, wherein the first routing process comprises 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 respective polyline as represented on the electronic map, wherein those segments that are further from the respective polyline are penalised to a greater degree than those that are closer to the respective polyline.

19. A non-transitory computer readable medium comprising instructions which, when executed by at least one processor of a computing device, cause the computing device to operate according to the method of claim 11.

16. A computing device for generating a route reconstructing a track through a navigable network in an area covered by an electronic map, the electronic map comprising a plurality of segments representing navigable elements of the navigable network, the computing device comprising at least one processor and a memory, wherein the at least one processor is arranged to:

obtain data indicative of a track through the navigable network to be reconstructed, wherein said data indicative of the track comprises an ordered series of point locations;

select one or more of the point locations, and defining an area associated with each of the one or more selected point locations;

use the ordered series of point locations and the defined areas associated with each of the selected one or more point locations to determine a plurality of polylines, each polyline being representative of a portion of the track to be reconstructed;

generate, for each of the polylines, a first route along segments of the electronic map using a first routing process based on the respective polyline, wherein the generated first route provides a reconstruction of the portion of the track represented by the polyline through the navigable network in relation to the electronic map;

generate, for the defined area associated with each of the selected one or more point locations, a second route along segments of the electronic map using a second routing process, wherein the second generated route provides a route through the defined area connecting the respective first generated routes, at least one of the segments of the second generated route being determined based in part on the relative distance between the segment and the point location to which the area is associated; and

output for provision to a user at least one of;

data indicative of the route reconstructing the track; and

a set of navigation instructions for guiding the user along at least a portion of the route reconstructing the track, wherein the route reconstructing the track comprises the generated first routes and the one or more generated second routes.

17. A computing device for generating a route reconstructing a track through a navigable network in an area covered by an electronic map, the electronic map comprising a plurality of segments representing navigable elements of the navigable network, the computing device comprising at least one processor and a memory, wherein the at least one processor is arranged to:

obtain data indicative of a track through the navigable network to be reconstructed, wherein said data indicative of the track comprises an ordered series of point locations from an origin location to a destination location;

select one or both of the origin and destination locations, and defining an area associated with each of the one or more selected point locations;

use the ordered series of point locations to determine one or more polylines, each of said one or more polylines being representative of at least a portion of the track to be reconstructed;

generate, for each of the one or more polylines, a first route along segments of the electronic map using a first routing process based on the respective polyline, wherein the generated first route provides a reconstruction of the at least a portion of the track represented by the polyline through the navigable network in relation to the electronic map;

generate, for the defined area associated with each of the selected one or more point locations, a second route along segments of the electronic map using a second routing process, wherein the second generated route provides a route from a segment within the defined area to the respective first generated route, the segment being determined based in part on the relative distance between the segment and the point location to which the area is associated; and

output for provision to a user at least one of;

data indicative of the route reconstructing the track; and

a set of navigation instructions for guiding the user along at least a portion of the route reconstructing the track, wherein the route reconstructing the track comprises the one or more generated first routes and the one or more generated second routes.