NOTE: This is a pretty old post, I wrote it but didn't publish it. Decided to publish it in the end.
I stumbled on this thing: The Reaktor Orbital Challenge and decided to give it a try (might not be online any longer by now).
If you haven't seen it before, or if you don't feel like heading over there to read it, then here's a recap.
Reaktor had a programming competition: you get a set of data representing satellites in orbit around Earth plus two sets of coordinates on the surface. The task is to route a fictional call from
finish, through the satellites in orbit. You can win an Oculus Rift (pretty cool).
My first impression was that it looks a lot like a shortest-path-first problem, with one important caveat: you can only route between two satellites that have a clear line of sight. In other words, the Earth might get in between two potential hops and ruin it.
They also simplify things a bit by defining the Earth as a perfect sphere with the radius 6 371 km.
So, breaking it down I get a couple of partial problems:
start,find the first satellite to route through.
- From one satellite, find the next viable hop that will take me towards the
- Repeat until the next hop is the
- Repeat until the next hop is the
Breaking it down a little further, I get some more partial problems:
- When looking for a potential next hop from any satellite, make sure there is a clear line of sight:
- Drawing a line from one satellite to another, will it touch or intersect with the Earth?
- Is there a maximum angle
down(in the direction of the Earth) I can calculate to help limiting my choices?
- All coordinates are given in latitude, longitude and altitude.
- Would it be easier to switch to cartesian coordinates?
- I think so. That would make things nice and clear (in my head).
TL;DR I've concocted a general solution based on some basic geometry and algebra
Breaking it down, this is my solution:
- Convert all
satellitesand their terrestrial coordinates into points in 3D space with cartesian coordinates.
- Use known math problems for finding out if a line intersects with a circle in 2D space to figure out if a vertex between two of the points have a clear line of sight.
- Use known math problems for finding out if a point is above or below a plane in 3D space together with known math for finding the tangent plane of a sphere at a given point to figure out if a point in space is visible from a point on the surface of the sphere (Earth).
- Use Dijkstra's algorithm for finding the shortest path to find the route from one terrestrial point, through a connected graph of nodes, ending at a final terrestrial point.
1.1. Switching coordinate space
Translating from latitude and longitude into simple () coordinates in 3D space can be done like this:
Where is the radius of the Earth. Note that those will calculate points on the Earth, so we'll have to add the altitude we've got to move it out from the sphere.
Not to hard! In Ruby then:
We'll keep that for later to use when importing the data snapshot.
1.2. Figuring out intersects with the Earth
I'm basing this on the same type of problem in 2D space, since that will translate straight up into 3D space by simply adding a third spatial coordinate. Formulated in 2D space, this would be the problem of finding the intersection of a line between two points (satellites) and a circle (the Earth).
Here's a crappy drawing to illustrate the problem in 2D space:
We want to find the line from one point to another that doesn't intersect the sphere (or circle in the drawing above).
Given the Earth as a perfect sphere, we can use the cartesian equation to describe the sphere in 3D space.
Then, we can define our vector from to with all points along the line as
with being a real number .
Substituting for , and in the equation of the sphere we get the quadratic equation
which can be collected into
and then we can figure out the root(s) by calculating
I actually1 had to dig up my old TI-89 calculator for this, hadn't used that one in a looooong while.
In the final equation for calculating the root(s) , we can isolate the discriminant and since we have a quadratic equation that discriminant is in our case .
Then we can look at this discriminant to figure out if there are any intersect points between our line and sphere, or in someone else's words, replace with and ray with line to make it more applicable:
Depending on the values of , , and , the quadratic equation may have 0, 1, or 2 real solutions for . These three special cases correspond to three different scenarios where a ray may miss the sphere entirely (0 solutions), may graze the sphere tangentially at one point (1 solution), or may pierce the sphere, entering at one point and exiting at another (2 solutions). The value of the expression inside the quadratic solution's square root (called the radicand) determines which of the three special cases we counter:
- : no solutions
- : one solution
- : two solutions
Our function will regard the first case as
two nodes having a clear line of sight or
true and the other as
there is a sphere in the way or
Now, if we translate all this into code, we'll get a function that returns a point of intersection. This can be used to make a function that simple replies truthy or falsey to the question
can this point see this other point, or is there a planet in the way?
Ok, code then:
1.3. Finding nodes visible from the surface
The start and end points are a bit special since they are on the surface of the sphere so the algorithm above won't work that well. Instead, I'm going to look at it as finding the distance from a point on a plane to another point above that plane. The plane being the tangent plane of the sphere at the given point of its surface (the start or end point).
We can use the known position of the point on the surface of the sphere and the fact that our sphere is centered at to find the normal vector of the tangent plane as which gives us the tangent plane as .
From that, we can derive the distance from our given point to some other point as:
If that distance is then the point is above the plane (in the direction of the normal vector), and if it's then it's below the plane (in the opposite direction of the normal vector).
If we convert this to Ruby code, we get something like this:
1.4. Finding a path
Now that we have a basic set of nodes in some space, each with coordinates, we can start thinking about this as a proper shortest-path-first problem. A good algorithm here would be something like Dijkstra's algorithm which pretty much does exactly what we want, if we add a constraint to stop the search once the target node is reached (the goal coordinates on the Earth). We can use the line of sight-thing to define the
distance used in Dijkstra's algorithm to make the algorithm not pick those paths but that would probably result in those paths being picked anyway if no other exist (the case where a route does not actually exist), or we can use it when defining the graph of nodes (the satellites in orbit) so that certain nodes simply aren't connected to some other node (probably the best use of that data) and define all distances as the actual distances between two nodes (simple algebra when we have the cartesian coordinates to work with).
The distance between two points in 3D space is simply defined as:
or in Ruby:
1.4.2. Building a graph
Since I'm using Ruby, I'm going to set up some objects to represent the satellites/nodes in the graph. This way, I can let each node in the graph hold a list of reachable neighbours together with the distance to them. You could probably do this in any number of ways but this works for me.
So the satellites will look something like this:
Where the vertices looks something like this:
Then the graph as something like:
1.4.3. Traversing the graph
Going through the graph, we can use Dijkstra's algorithm with something like this in the Graph class (I'm not going to go through the details of Dijkstra's algorithm, there's a perfectly good Wikipedia page for that):
2. Wrapping up
Ok so I think we have everything we need to make this work, I'm thinking that the algorithm will go something like this:
So, this seems to be working just fine! Downloading a couple of data snapshots and verifying the calculated route tells me it's working as supposed:
Fun challenge all in all! Guess all that's left now is hoping to win that Rift headset 😊 (Hint: I didn't, still fun though.)
Converting latitude and longitude to x y z coordinates in Partiview.From COSMUS, University of Chicago Department of Astronomy and Astrophysics. http://astro.uchicago.edu/cosmus/tech/latlong.html
- Weisstein, Eric W.
Circle-Line Intersection.From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Circle-LineIntersection.html
- Hinson, Anthony
General AlgorithmsSection 2.1.4: Intersection of Parametric Line and Sphere. http://www.ahinson.com/algorithms_general/Sections/Geometry/IntersectionOfParametricLineAndSphere.pdf
- Cross, Don
Fundamentals of Ray TracingChapter 6: Sphere Intersections. http://cosinekitty.com/raytrace/chapter06_sphere.html
- Nikunj (http://math.stackexchange.com/users/287774/nikunj), Tangent plane to sphere, URL (version: 2016-04-23): http://math.stackexchange.com/q/1517146
- Weisstein, Eric W.
Point-Plane Distance.From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Point-PlaneDistance.html
I can barely type the word
actuallywithout thinking about this one: https://www.facebook.com/buzzfeedadam/posts/1151999248184613 by the generally awesome Adam Ellis ↩