Methods and systems for reconstructing tracks using electronic map data

• US 9,816,831 B2
• Filed: 11/04/2015
• Issued: 11/14/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
• Primary Examiner(s): Kan, Yuri
• Application Number:
  US14/931,972
• Publication Number:
  US 20170082453A1
• Time in Patent Office: 741 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 define a defined area associated with each of the selected one or more point locations;

use the ordered series of point locations and the defined area associated with each of the selected one or more point locations to determine a plurality of poly lines, each polyline being representative of a portion of the track to be reconstructed, so that an entirety of the track is represented by the plurality of poly lines in a series, interspersed with and separated by the defined area associated with each of the selected one or more point locations;

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

generate, for each defined area, a second route along segments of the electronic map using a second routing process, wherein the second route provides a route through the defined area to connect respective first routes, at least one segment of the second route being determined based in part on a relative distance between the at least one segment and a point location with which the defined 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 each first route and each second route.

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 area associated with each of the selected one or more point locations to determine a plurality of polylines comprises:

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

using the defined area 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 selected one or more point locations comprise 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 selected one or more 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 a defined 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 route provides a route through the defined area to a respective first route, at least one segment of the third route being determined based in part on a relative distance between the at least one segment and the one of the origin or destination location with which the defined area is associated,

wherein the route reconstructing the track further comprises each third route.

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 that are in greater proximity to a respective polyline.

9. The method of claim 8, wherein, when favouring segments, segments that are further from the respective polyline are penalised to a greater degree than segments 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 define a defined area associated with each of the one or both of the origin and destination locations;

use the ordered series of point locations to determine one or more poly lines, each of said one or more poly lines being representative of at least a portion of the track to be reconstructed, so that an entirety of the track is represented by the one or more polylines in a series coupled to the defined area associated with each of the one or both of the origin and destination locations;

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

generate, for the defined area associated with each of the one or both of the origin and destination locations, a second route along segments of the electronic map using a second routing process, wherein the second route provides a route through the defined area to a respective first route, at least one segment of the second route being determined based in part on a relative distance between the at least one segment and the one of the origin and destination locations with which the defined 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 each first route and each second route.

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 each defined area associated with the one or both of the origin and destination locations is a circular area centred on a corresponding 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 that are in greater proximity to a respective polyline.

15. The method of claim 14, wherein, when favouring segments, segments that are further from the respective polyline are penalised to a greater degree than segments 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 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 define a defined area associated with each of the selected one or more point locations;

use the ordered series of point locations and the defined area associated with each of the selected one or more point locations to determine a plurality of poly lines, each polyline being representative of a portion of the track to be reconstructed, so that an entirety of the track is represented by the plurality of poly lines in a series, interspersed with and separated by the defined area associated with each of the selected one or more point locations;

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

generate, for each defined area, a second route along segments of the electronic map using a second routing process, wherein the second route provides a route through the defined area to connect respective first routes, at least one segment of the second route being determined based in part on a relative distance between the at least one segment and a point location with which the defined 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 each first route and each second route.

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 define a defined area associated with each of the one or both of the origin and destination locations;

use the ordered series of point locations to determine one or more poly lines, each of said one or more poly lines being representative of at least a portion of the track to be reconstructed, so that an entirety of the track is represented by the one or more polylines in a series coupled to the defined area associated with each of the one or both of the origin and destination locations;

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

generate, for the defined area associated with each of the one or both of the origin and destination locations, a second route along segments of the electronic map using a second routing process, wherein the second route provides a route through the defined area to a respective first route, at least one segment of the second route being determined based in part on a relative distance between the at least one segment and the one of the origin and destination locations with which the defined 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 each first route and each second route.