Solving “Mountainous Landscape,” a Fun Geometry Problem
I have a problem. Would you like to help me out?
The statement of Mountainous Landscape can be summarized as follows:
Given a polyline, for every segment \(S\), find the first (closest) segment \(R\) to the right, which you'd be able to see if you stand on \(S\). Your vision field can be modeled as the ray \(\overrightarrow{S}\).
Points in the polyline have strictly increasing \(x\) coordinates.
A picture is worth a thousand words:
Assume the polyline has \(n = 100,000\) points, so you need to come up with a fast algorithm. A complexity of \(O(n\ log\ n)\) or similar is desired for this problem.
I'm going to walk you through the solution I implemented for this problem. But first, let's analyze the problem a little bit.
Analysis
I'll go through some of the observations that have to be made in order to be able to solve this problem.
This problem can be solved in \(O(n^2)\) if, for every segment, we do a linear search to the right until we find the first visible segment. We can try to turn the linear search into something a bit more efficient.
The first thing is to realize that if the ray intersects the convex hull (upper only) of a part of the polyline, then the final answer will be somewhere inside that hull. This means we can decompose the polyline into several nested convex hulls and iteratively traverse from one hull to the next (which will be inside the previous one) until we get to the final answer.
Since each convex hull (except the largest one) is fully contained by another convex hull, we can model this as a tree of convex hulls.
We also need to come up with a way to query the tree in such a way that we find the closest visible segment and not any other segment. The query needs to consider the vision field, which is modeled as a ray.
Building a Tree of Convex Hulls
Let's say we have the following polyline. We need to transform this into a tree of upper convex hulls.
The first step is to build the upper hull for the entire polyline. Note that all convex hulls in this problem can be built in \(O(n)\) since the points are already sorted by ascending \(x\) coordinate. This node is the root of the tree.
We then build the two children by recursively applying the same process to both the left and right halves.
After one more step, it'd look like in the following picture. Continue doing this until it can't be divided anymore.
There are several ways to build this tree, but I implemented it in a similar fashion to how one would usually build a segment tree, that is, starting by building from the range \([0, n-1]\), then dividing the range into two halves, and recursively build the tree for both halves.
Note that this gives us a binary tree.
Querying the Tree
For every segment in the polyline, you must perform a query in order to find the final node, which gives us the position of the segment that can be seen from where you are currently standing.
Since each node has two children, but we need to find the closest one to the right, we can follow this rule:
- Try querying the left node.
- If querying the left node found an answer, stop.
- If not, then query the right node.
We can also do some simple pruning by checking if the node's convex hull can never intersect the ray. Since all rays point to the right, then for a convex hull to be intersected, at least part of it should be to the right of the corresponding polyline segment. Otherwise, it'd never intersect. We can skip querying a node if there's no way it intersects.
Ray v/s Upper Convex Hull Intersection Detection in Logarithmic Time
The remaining problem is that every time we query a node, we should check whether it intersects its corresponding convex hull. You could iterate all points and check if the ray intersects it, but this brings back the complexity to \(O(n)\), so we must find a better way. I got stuck for a rather long time trying to figure out how to do this efficiently since I had never implemented something like this before.
Turns out there's a nice technique using a binary search that helps here.
Let's start by considering the ray query and all the edges in the upper hull as vectors. Now we can do some vector arithmetic and use some useful properties to find whether there's a collision or not.
As you go from the first to the last edge in the upper hull, you can tell that the orientation of the polygon edge relative to the ray transitions from counterclockwise to clockwise.
At some point in between, there's an edge that's the closest to being parallel to the ray. In other words, it has the minimum angle and in some cases, could be parallel. It's possible to find this one using a binary search.
You only need that one edge to tell whether the ray intersects the upper hull. Simply do an orientation check using both the ray and that edge. Note that this is an ad-hoc algorithm and only works for this problem. It's not a general solution for the ray v/s convex polygon intersection problem.
Solution Source Code
Here's my solution in C++.
