Terrain analysis for automatic route determination

• US 10,429,197 B1
• Filed: 06/14/2018
• Issued: 10/01/2019
• Est. Priority Date: 05/29/2018
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Carrino, John, Kruse, Joseph, Peterson, Jasmine, Anderson, Leah, Ryan, Paul, Glidden, Reese, Elder, Andrew, Ng, Kevin
• Primary Examiner(s): Elchanti, Hussein
• Application Number:
  US16/008,937
• Time in Patent Office: 474 Days
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• CPC Class Codes: H04W 4/02 Services making use of location information

Abstract

Systems, methods, and non-transitory computer readable media are provided for determining routes within a location. Location information for a location may be obtained. The location information may include terrain information for the location. A set of restricted regions within the location may be determined based on the location information. A set of paths within the location may be determined based on the set of restricted regions. An interface through which information describing the set of paths within the location is accessible may be provided.

Claims

1. A system comprising:

one or more processors; and

memory storing instructions that, when executed by the one or more processors, cause the system to perform;

obtaining location information for a location, the location information including terrain information for the location;

determining a set of restricted regions within the location based on the location information, the set of restricted regions comprising respective boundaries of the restricted regions;

determining one or more distances between the respective boundaries of at least two restricted regions of the set of restricted regions;

comparing the one or more distances with a distance threshold;

determining a topological skeleton of the location based on a straight skeleton analysis of the set of restricted regions within the location;

determining a set of paths within the location based on the topological skeleton of the location and the comparison of the one or more distances with the distance threshold; and

providing an interface through which information describing the set of paths within the location is accessible.

2. The system of claim 1, wherein the terrain information defines elevations of a terrain within the location and the set of restricted regions within the location is determined based on changes in the elevations of the terrain within the location.

3. The system of claim 2, wherein a boundary of a restricted region within the set of restricted regions traces a line of a given slope within the terrain.

4. The system of claim 3, wherein the given slope is defined by a single value or a range of values meeting a threshold.

5. The system of claim 3, wherein the given slope is determined based on a type of an entity that is expected to traverse one or more paths of the set of paths.

6. The system of claim 1, wherein the location information further includes restriction information for the location, the restriction information defining one or more restricted regions within the location.

7. The system of claim 1, wherein the set of paths is determined based on a straight skeleton analysis of the set of restricted regions within the location.

8. The system of claim 1, wherein the set of paths is determined based on distances between one or more boundaries of the set of restricted regions meeting a distance threshold.

9. The system of claim 8, wherein the distance threshold is determined based on a type of an entity that is expected to traverse one or more paths of the set of paths.

10. A method implemented by a computing system including one or more processors and storage media storing machine-readable instructions, wherein the method is performed using the one or more processors, the method comprising:

obtaining location information for a location, the location information including terrain information for the location;

determining a set of restricted regions within the location based on the location information, the set of restricted regions comprising respective boundaries of the restricted regions;

determining one or more distances between the respective boundaries of at least two restricted regions of the set of restricted regions;

comparing the one or more distances with a distance threshold;

determining a topological skeleton of the location based on a straight skeleton analysis of the set of restricted regions within the location;

determining a set of paths within the location based on the topological skeleton of the location and the comparison of the one or more distances with the distance threshold; and

providing an interface through which information describing the set of paths within the location is accessible.

11. The method of claim 10, wherein the terrain information defines elevations of a terrain within the location and the set of restricted regions within the location is determined based on changes in the elevations of the terrain within the location.

12. The method of claim 11, wherein a boundary of a restricted region within the set of restricted regions traces a line of a given slope within the terrain.

13. The method of claim 12, wherein the given slope is defined by a single value or a range of values meeting a threshold.

14. The method of claim 12, wherein the given slope is determined based on a type of an entity that is expected to traverse one or more paths of the set of paths.

15. The method of claim 10, wherein the location information further includes restriction information for the location, the restriction information defining one or more restricted regions within the location.

16. The method of claim 10, wherein the set of paths is determined based on a straight skeleton analysis of the set of restricted regions within the location.

17. The method of claim 10, wherein the set of paths is determined based on distances between one or more boundaries of the set of restricted regions meeting a distance threshold.

18. The method of claim 17, wherein the distance threshold is determined based on a type of an entity that is expected to traverse one or more paths of the set of paths.

19. A non-transitory computer readable medium comprising instructions that, when executed, cause one or more processors to perform:

obtaining location information for a location, the location information including terrain information for the location;

determining a set of restricted regions within the location based on the location information, the set of restricted regions comprising respective boundaries of the restricted regions;

determining one or more distances between the respective boundaries of at least two restricted regions of the set of restricted regions;

comparing the one or more distances with a distance threshold;

determining a topological skeleton of the location based on a straight skeleton analysis of the set of restricted regions within the location;

determining a set of paths within the location based on the topological skeleton of the location and the comparison of the one or more distances with the distance threshold; and

providing an interface through which information describing the set of paths within the location is accessible.

20. The non-transitory computer readable medium of claim 19, wherein the terrain information defines elevations of a terrain within the location and the set of restricted regions within the location is determined based on changes in the elevations of the terrain within the location.