2

This question is more conceptual as I do not have any code to show for it as of right now. However, I was wondering if I could get some help on how I could go about coding something like this without having the program take years to compute.

Basically, imagine that a wingsuit base jumper needs at least a 30 degree slope to fly a safe line to his landing. How can we go about finding the longest flight line he could take on earth?

        |----
        |     ----
        |         ----               A slope with a 3-1 glide angle
 100m   |             ----
        |                 ----
        |_________________________
                     300m

Our planet has ~510 million km² of surface area. Let's assume we want to take a data point every 200m, which comes out as 25 data points in a square kilometer. The n^2 solution here clearly is not good enough.

Here are my thoughts on a potential solution: loop through all (510*25) million possible start points. Connect those points to their adjacent point neighbours in the form of a graph. Since we now have a grid of interconnected points as a graph we can remove all edges that do not fit the 30 degree slope requirement. Next up we use an algorithm to find the longest path in a directed acyclic graph.

https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

Will my solution work? Is it feasable to compute? Thoughts on other solutions?

0

1 Answer 1

2

Sort the points by elevation.

Make an array for the longest path to each point, and initialize it with zeros -- that's the path the starts that point.

Process the points in order of descending elevation. For each point, look up the length of the longest path to it, and use that to adjust the longest paths to its lower neighbors.

The longest path to each point will be correct when you process it, since it can only depend on the higher-elevation points, which will have been processed already.

Remember the highest number you see, and that will be the length of the longest path. If you remember where it is then you can reconstruct the path by working backwards, repeatedly finding the higher neighbor with the longest path to it.

Total time is O(N log N), dominated by the initial sort.

7
  • Still trying to understand your solution. Will these paths follow the restriction of having at least a 3-1 glide angle between points? Where does that check come into play? Feb 5, 2019 at 5:32
  • Yes. "adjust the longest paths to its lower neighbors" means you look at the neighboring points, find the ones that are low enough (3-1 glide angle), and then see if the path to them through the current point is longer than the longest path to those points already recorded. Feb 5, 2019 at 5:36
  • Ok, so I have my almost 2 billion points sorted by elevation. What does "make an array for the longest path to each point" mean? Does that mean each point object has it's own array that stores the distance it is from other points? Seems like an n^2 solution? Feb 5, 2019 at 5:43
  • No, it must means that you're going to associate a number with each point that will end up being the length of the longest path to that point. One array of 2 billion numbers. That may be too big for your memory, so you may have to divide the world into regions... but that's an orthogonal consideration. Feb 5, 2019 at 5:46
  • How do we know if points are neighbouring? Are you using a graph like I suggested? Honestly think I'm confusing my self here haha sorry. Basically I understand that the array will represent the longest path we could find on the map. So that might look like [100,104,109,110] where those numbers are point ids. Feb 5, 2019 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.