METHOD, APPARATUS AND COMPUTER PROGRAM PRODUCT FOR ROUTE GENERATION

• US 20160123756A1
• Filed: 10/30/2014
• Published: 05/05/2016
• Est. Priority Date: 10/30/2014
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Becker, Wolfgang, Kopp, Markus
• Granted Patent: US 10,260,900 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• 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/3476 using point of interest [POI] information, e.g. a route passing visible POIs
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds

Abstract

Provided herein is a method, apparatus and computer program product for the generation of a route. In particular, the method may include receiving a plurality of trace points, where each of the plurality of trace points includes location information, receiving a distance tolerance value for each trace point, generating a first portion of a route using a first subset of the plurality of trace points, generating a second portion of the route using a second subset of the plurality of trace points, and concatenating the first portion of the route with the second portion of the route to generate a route. Generating the first portion of the route or the second portion of the route may optionally include removing a trace point that is less than a proximity tolerance distance away from a trace point immediately preceding the removed trace point in sequence.

Claims

1. A method comprising:

receiving a plurality of trace points, wherein each of the plurality of trace points comprises location information;

receiving a distance tolerance value for each trace point;

generating a first portion of a route using a first subset of the plurality of trace points;

generating a second portion of the route using a second subset of the plurality of trace points; and

concatenating the first portion of the route with the second portion of the route to generate a route.

2. The method of claim 1, wherein generating the first portion or the second portion of a route comprises removing a trace point that is less than a predetermined distance away from a trace point immediately preceding the removed trace point in sequence.

3. The method of claim 1, wherein generating the first portion or the second portion of a route comprises removing a second trace point that is at least a predefined distance away from a first trace point immediately preceding the removed second trace point in sequence, wherein the amount of time between the first trace point and the second trace point is shorter than a predetermined amount of time.

4. The method of claim 1, wherein generating the first portion or the second portion of a route comprises removing one or more trace points in response to the one or more trace points resulting in discontinuity in the route.

5. The method of claim 1, wherein concatenating the first portion of the route with the second portion of the route comprises determining an established path that is within a respective distance tolerance value for each trace point.

6. The method of claim 5, wherein concatenating the first portion of the route with the second portion of the route comprises removing at least a part of the first portion or the second portion in response to determining that the part of the first portion or the second portion comprises a redundant part of the route.

7. The method of claim 5, wherein in response to determining that an established path is not within a respective distance tolerance value for one or more trace points, generating an updated distance tolerance value for each of the one or more trace points and determining an established path that is within a respective updated distance tolerance value for each of the one or more trace points.

8. An apparatus comprising at least one processor and at least one memory including computer program code, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to:

receive a plurality of trace points, wherein each of the plurality of trace points comprises location information;

receive a distance tolerance value for each trace point;

generate a first portion of a route using a first subset of the plurality of trace points;

generate a second portion of the route using a second subset of the plurality of trace points; and

concatenate the first portion of the route with the second portion of the route to generate a route.

9. The apparatus of claim 8, wherein causing the apparatus to generate a first portion of the route or the second portion of the route comprises causing the apparatus to remove a trace point that is less than a proximity tolerance distance away from a trace point immediately preceding the removed trace point in sequence.

10. The apparatus of claim 8, wherein causing the apparatus to generate a first portion of the route or the second portion of the route comprises causing the apparatus to remove a second trace point that is at least a predefined distance away from a first trace point immediately preceding the removed second trace point in sequence, wherein the amount of time between the first trace point and the second trace point is shorter than a predetermined amount of time.

11. The apparatus of claim 8, wherein causing the apparatus to generate a first portion of the route or the second portion of the route comprises causing the apparatus to remove one or more trace points in response to the one or more trace points resulting in discontinuity in the route.

12. The apparatus of claim 8, wherein causing the apparatus to concatenate the first portion of the route with the second portion of the route comprises causing the apparatus to determine an established path that is within a respective distance tolerance value for each trace point.

13. The apparatus of claim 12, wherein causing the apparatus to concatenate the first portion of the route with the second portion of the route comprises causing the apparatus to remove at least a part of the first portion or the second portion in response to determining that the part of the first portion or the second portion comprises a redundant part of the route.

14. The apparatus of claim 12, wherein in response to the apparatus being caused to determine that an established path is not within a respective distance tolerance value for one or more trace points, causing the apparatus to generate an updated distance tolerance value for each of the one or more trace points and causing the apparatus to generate an established path that is within a respective updated distance tolerance value for each of the one or more trace points.

15. A computer program product comprising at least one non-transitory computer-readable storage medium having computer executable program code instructions stored therein, the computer executable program code instructions comprising:

program code instructions to receive a plurality of trace points, wherein each of the plurality of trace points comprises location information;

program code instructions to receive a distance tolerance value for each trace point;

program code instructions to generate a first portion of a route using a first subset of the plurality of trace points;

program code instructions to generate a second portion of the route using a second subset of the plurality of trace points; and

program code instructions to concatenate the first portion of the route with the second portion of the route to generate a route.

16. The computer program product of claim 15, wherein the program code instructions to generate a first portion of the route or the program code instructions to generate the second portion of the route comprise program code instructions to remove a trace point that is less than a proximity tolerance distance away from a trace point immediately preceding the removed trace point in sequence.

17. The computer program product of claim 15, wherein the program code instructions to generate a first portion of the route or the program code instructions to generate the second portion of the route comprise program code instructions to remove a second trace point that is at least a predefined distance away from a first trace point immediately preceding the removed second trace point in sequence, wherein the amount of time between the first trace point and the second trace point is shorter than a predetermined amount of time.

18. The computer program product of claim 15, wherein the program code instructions to generate a first portion of the route or the program code instructions to generate the second portion of the route comprise program code instructions to remove one or more trace points in response to the one or more trace points resulting in discontinuity in the route.

19. The computer program product of claim 15, wherein the program code instructions to concatenate the first portion of the route with the second portion of the route comprises program code instructions to determine an established path that is within a respective distance tolerance value for each trace point.

20. The computer program product of claim 19, wherein the program code instructions to concatenate the first portion of the route with the second portion of the route comprises program code instructions to remove at least a part of the first portion or the second portion in response to determining that the part of the first portion or the second portion comprises a redundant part of the route.