Generating trail network maps

• US 10,429,192 B2
• Filed: 09/14/2016
• Issued: 10/01/2019
• Est. Priority Date: 09/16/2015
• Status: Active Grant

• Current Assignee: Strava, Incorporated
• Original Assignee: Strava, Incorporated
• Inventors: Kitchel, Davis
• Primary Examiner(s): Issing, Gregory C.
• Application Number:
  US15/265,403
• Publication Number:
  US 20170074988A1
• Time in Patent Office: 1,112 Days
• CPC Class Codes: A63B 2024/0025 Tracking the path or location of one or more users, e.g. players of a game
• CPC Class Codes: A63B 2024/0056 for statistical or strategic analysis
• CPC Class Codes: A63B 2024/0071 Distinction between different activities, movements, or kind of sports performed
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G01C 21/3844 Data obtained from position sensors only, e.g. from inertial navigation
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G01S 19/14 specially adapted for specific applications
• CPC Class Codes: G01S 19/19 Sporting applications
• CPC Class Codes: G01S 19/39 the satellite radio beacon positioning system transmitting time-stamped messages, e.g. GPS [Global Positioning System], GLONASS [Global Orbiting Navigation Satellite System] or GALILEO
• CPC Class Codes: G01S 19/396 Determining accuracy or reliability of position or pseudorange measurements
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

Generating trail network maps, including: receiving a plurality of GPS recorded activities; identifying a subset of the plurality of GPS recorded activities that is associated with a trail network region; and generating a trail network map corresponding to the trail network region based at least in part on the subset of the plurality of GPS recorded activities.

Claims

1. A system, comprising:

a processor; and

a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to;

receive a plurality of GPS recorded activities associated with a geographic area;

determine a plurality of tiles associated with the geographic area;

determine respective activity types and respective equipment types of one or more GPS recorded activities that intersect a tile of the plurality of tiles, wherein to determine the respective activity types and the equipment types for the one or more GPS recorded activities that intersect the tile of the plurality of tiles includes;

for each of at least a subset of the plurality of tiles, determining cycling activity data that intersects that tile;

for each tile of the at least subset of the plurality of tiles, determining a portion of the cycling activity data that intersects that tile that is associated with mountain bike frames; and

for each tile of the at least a subset of the plurality of tiles, determining whether that tile is associated with a trail network based in part on the portion of the cycling activity data that intersects that tile that is associated with mountain bike frames;

determine a trail network region within the geographic area based in part on the respective activity types and the respective equipment types of the one or more GPS recorded activities that intersect the tile of the plurality of tiles;

identify a subset of the plurality of GPS recorded activities that is associated with the trail network region; and

generate a trail network map corresponding to the trail network region based in part on the subset of the plurality of GPS recorded activities.

2. The system of claim 1, wherein to determine the trail network region within the geographic area based in part on the respective activity types and the respective equipment types of the one or more GPS recorded activities that intersect the tile of the plurality of tiles includes:

determining at least a subset of contiguous tiles that meets a predetermined set of contiguous tiles threshold from the plurality of tiles, wherein each tile of the at least a subset of contiguous tiles is associated with the trail network; and

generating the trail network region associated with the trail network based in part on the at least a subset of contiguous tiles.

3. The system of claim 1, wherein to determine the trail network region within the geographic area based in part on the respective activity types and the respective equipment types of the one or more GPS recorded activities that intersect the tile of the plurality of tiles includes:

determining at least a subset of contiguous tiles that meets a predetermined set of contiguous tiles threshold from the plurality of tiles, wherein each tile of the at least a subset of contiguous tiles is associated with the trail network; and

generating the trail network region associated with the trail network based in part on the at least a subset of contiguous tiles and a buffer of area surrounding the at least a subset of contiguous tiles.

4. The system of claim 1, wherein the memory is further configured to provide the processor with instructions which when executed cause the processor to:

determine activity data that intersects the trail network region; and

store with a GPS data point of at least a subset of GPS data points of the determined activity data a corresponding set of attributes in a data structure.

5. The system of claim 1, wherein the memory is further configured to provide the processor with instructions which when executed cause the processor to:

determine an initial network point associated with a trail network associated with the trail network region based in part on selecting a GPS data point from activity data that intersects the trail network region; and

use the initial network point and at least a subset of the activity data to recursively determine network points along one or more branches of the trail network, wherein the network points represent locations along the one or more branches of the trail network.

6. The system of claim 1, wherein the memory is further configured to provide the processor with instructions which when executed cause the processor to:

store data associated with a current network point, wherein the current network point comprises a location along a current branch of a trail network;

determine a circle around a respective location that is a predetermined distance away from the current network point at each degree relative to the current network point;

for each circle around the respective location that is the predetermined distance away from the current network point at each degree relative to the current network point, determine a set of qualifying recorded GPS data points from activity data that intersects the circle; and

determine a plurality of degrees associated with circles with respective sets of qualifying recorded GPS data points that each meets a set of predetermined criteria.

7. The system of claim 1, wherein the memory is further configured to provide the processor with instructions which when executed cause the processor to:

store data associated with a current network point, wherein the current network point comprises a location along a current branch of a trail network;

determine a circle around a respective location that is a predetermined distance away from the current network point at each degree relative to the current network point;

for each circle around the respective location that is the predetermined distance away from the current network point at each degree relative to the current network point, determine a set of qualifying recorded GPS data points from activity data that intersects the circle;

determine a plurality of degrees associated with circles with respective sets of qualifying recorded GPS data points that each meets a set of predetermined criteria;

determine that a degree of the plurality of degrees is along a new path;

determine that a new branch of the trail network has been found; and

set a location along the degree along the new path as a new current network point of the new branch of the trail network.

8. The system of claim 1, wherein the memory is further configured to provide the processor with instructions which when executed cause the processor to:

store data associated with a current network point, wherein the current network point comprises a location along a current branch of a trail network;

determine a circle around a respective location that is a predetermined distance away from the current network point at each degree relative to the current network point;

for each circle around the respective location that is the predetermined distance away from the current network point at each degree relative to the current network point, determine a set of qualifying recorded GPS data points from activity data that intersects the circle;

determine a plurality of degrees associated with circles with respective sets of qualifying recorded GPS data points that each meets a predetermined criteria;

determine that a degree of the plurality of degrees is along the current branch of the trail network; and

set a location along the degree as a new current network point of the current branch of the trail network.

9. The system of claim 1, wherein to generate the trail network map corresponding to the trail network region comprises to:

determine a plurality of linestrings based in part on a plurality of network points corresponding to one or more branches of a trail network associated with the trail network region; and

split the plurality of linestrings at branch intersection points.

10. A method, comprising:

receiving a plurality of GPS recorded activities associated with a geographic area;

determining a plurality of tiles associated with the geographic area;

determining respective activity types and respective equipment types of one or more GPS recorded activities that intersect a tile of the plurality of tiles wherein determining the respective activity types and the equipment types for the one or more GPS recorded activities that intersect the tile of the plurality of tiles includes;

for each of at least a subset of the plurality of tiles determining cycling activity data that intersects that tile;

for each tile of the at least subset of the plurality of tiles, determining a portion of the cycling activity data that intersects that tile that is associated with mountain bike frames; and

for each tile of the at least a subset of the plurality of tiles, determining whether that tile is associated with a trail network based in part on the portion of the cycling activity data that intersects that tile that is associated with mountain bike frames;

determining a trail network region within the geographic area based in part on the respective activity types and the respective equipment types of the one or more GPS recorded activities that intersect the tile of the plurality of tiles;

identifying a subset of the plurality of GPS recorded activities that is associated with the trail network region; and

generating a trail network map corresponding to the trail network region based in part on the subset of the plurality of GPS recorded activities.

11. The method of claim 10,

wherein determining the trail network region within the geographic area based in part on the respective activity types and the respective equipment types of the one or more GPS recorded activities that intersect the tile of the plurality of tiles includes:

determining at least a subset of contiguous tiles that meets a predetermined set of contiguous tiles threshold from the plurality of tiles, wherein each tile of the at least a subset of contiguous tiles is associated with the trail network; and

generating the trail network region associated with the trail network based in part on the at least a subset of contiguous tiles.

12. The method of claim 10,

wherein determining the trail network region within the geographic area based in part on the respective activity types and the respective equipment types of the one or more GPS recorded activities that intersect the tile of the plurality of tiles includes:

determining at least a subset of contiguous tiles that meets a predetermined set of contiguous tiles threshold from the plurality of tiles, wherein each tile of the at least a subset of contiguous tiles is associated with the trail network; and

generating the trail network region associated with the trail network based in part on the at least a subset of contiguous tiles and a buffer of area surrounding the at least a subset of contiguous tiles.

13. The method of claim 10, further comprising:

determining activity data that intersects the trail network region; and

storing with a GPS data point of at least a subset of GPS data points of the determined activity data a corresponding set of attributes in a data structure.

14. The method of claim 10, further comprising:

determining an initial network point associated with a trail network associated with the trail network region based in part on selecting a GPS data point from activity data that intersects the trail network region; and

using the initial network point and at least a subset of the activity data to recursively determine network points along one or more branches of the trail network, wherein the network points represent locations along the one or more branches of the trail network.

15. The method of claim 10, further comprising:

storing data associated with a current network point, wherein the current network point comprises a location along a current branch of a trail network;

determining a circle around a respective location that is a predetermined distance away from the current network point at each degree relative to the current network point;

for each circle around the respective location that is the predetermined distance away from the current network point at each degree relative to the current network point, determining a set of qualifying recorded GPS data points from activity data that intersects the circle; and

determining a plurality of degrees associated with circles with respective sets of qualifying recorded GPS data points that each meets a set of predetermined criteria.

16. The method of claim 10, further comprising:

storing data associated with a current network point, wherein the current network point comprises a location along a current branch of a trail network;

determining a circle around a respective location that is a predetermined distance away from the current network point at each degree relative to the current network point;

for each circle around the respective location that is the predetermined distance away from the current network point at each degree relative to the current network point, determining a set of qualifying recorded GPS data points from activity data that intersects the circle;

determining a plurality of degrees associated with circles with respective sets of qualifying recorded GPS data points that each meets a set of predetermined criteria;

determining that a degree of the plurality of degrees is along a new path;

determining that a new branch of the trail network has been found; and

setting a location along the degree along the new path as a new current network point of the new branch of the trail network.

17. The method of claim 10, further comprising:

storing data associated with a current network point, wherein the current network point comprises a location along a current branch of a trail network;

determining a circle around a respective location that is a predetermined distance away from the current network point at each degree relative to the current network point;

for each circle around the respective location that is the predetermined distance away from the current network point at each degree relative to the current network point, determining a set of qualifying recorded GPS data points from activity data that intersects the circle;

determining a plurality of degrees associated with circles with respective sets of qualifying recorded GPS data points that each meets a predetermined criteria;

determining that a degree of the plurality of degrees is along the current branch of the trail network; and

setting a location along the degree as a new current network point of the current branch of the trail network.

18. The method of claim 10, wherein generating the trail network map corresponding to the trail network region comprises:

determining a plurality of linestrings based in part on a plurality of network points corresponding to one or more branches of a trail network associated with the trail network region; and

splitting the plurality of linestrings at branch intersection points.

19. A computer program product, the computer program product being embodied in a non-transitory computer readable storage medium configured to store a plurality of programming instructions executable on a processor and comprising computer instructions for:

receiving a plurality of GPS recorded activities associated with a geographic area;

determining a plurality of tiles associated with the geographic area;

determining respective activity types and respective equipment types of one or more GPS recorded activities that intersect a tile of the plurality of tiles, wherein determining the respective activity types and the equipment types for the one or more GPS recorded activities that intersect the tile of the plurality of tiles includes;

for each of at least a subset of the plurality of tiles determining cycling activity data that intersects that tile;

for each tile of the at least subset of the plurality of tiles, determining a portion of the cycling activity data that intersects that tile that is associated with mountain bike frames; and

for each tile of the at least a subset of the plurality of tiles, determining whether that tile is associated with a trail network based in part on the portion of the cycling activity data that intersects that tile that is associated with mountain bike frames;

determining a trail network region within the geographic area based in part on the respective activity types and the respective equipment types of the one or more GPS recorded activities that intersect the tile of the plurality of tiles;

identifying a subset of the plurality of GPS recorded activities that is associated with the trail network region; and

generating a trail network map corresponding to the trail network region based in part on the subset of the plurality of GPS recorded activities.

20. A system, comprising:

a processor; and

a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to;

receive a plurality of GPS recorded activities associated with a geographic area;

determine a plurality of tiles associated with the geographic area;

determine respective activity types and respective equipment types of one or more GPS recorded activities that intersect a tile of the plurality of tiles;

determine a trail network region within the geographic area based in part on the respective activity types and the respective equipment types of the one or more GPS recorded activities that intersect the tile of the plurality of tiles;

identify a subset of the plurality of GPS recorded activities that is associated with the trail network region; and

generate a trail network map corresponding to the trail network region based in part on the subset of the plurality of GPS recorded activities, wherein to generate the trail network map includes;

storing data associated with a current network point, wherein the current network point comprises a location along a current branch of a trail network;

determining a circle around a respective location that is a predetermined distance away from the current network point at each degree relative to the current network point;

for each circle around the respective location that is the predetermined distance away from the current network point at each degree relative to the current network point, determining a set of qualifying recorded GPS data points from activity data that intersects the circle; and

determining a plurality of degrees associated with circles with respective sets of qualifying recorded GPS data points that each meets a set of predetermined criteria.

21. A method, comprising:

receiving a plurality of GPS recorded activities associated with a geographic area;

determining a plurality of tiles associated with the geographic area;

determining respective activity types and respective equipment types of one or more GPS recorded activities that intersect a tile of the plurality of tiles;

determining a trail network region within the geographic area based in part on the respective activity types and the respective equipment types of the one or more GPS recorded activities that intersect the tile of the plurality of tiles;

identifying a subset of the plurality of GPS recorded activities that is associated with the trail network region; and

generating a trail network map corresponding to the trail network region based in part on the subset of the plurality of GPS recorded activities, wherein generating the trail network map includes;

storing data associated with a current network point, wherein the current network point comprises a location along a current branch of a trail network;

determining a circle around a respective location that is a predetermined distance away from the current network point at each degree relative to the current network point;

for each circle around the respective location that is the predetermined distance away from the current network point at each degree relative to the current network point, determining a set of qualifying recorded GPS data points from activity data that intersects the circle; and

determining a plurality of degrees associated with circles with respective sets of qualifying recorded GPS data points that each meets a set of predetermined criteria.