Navigate Gates

Here's an interesting leetcode-style problem: we are given two points $p_0$ and $p_1$ and a list of $n$ line segments $G=\{g_i\}$ which we call gates. We want to find the shortest path from $p_0$ to $p_1$ that crosses every gate $g_i$ in order. Imagine a boat sailing from port to port through gates to avoid running aground in shallow waters.

A Simple Solution

A simple solution is to create a graph where the vertices are the two points and the endpoints of the lines (which we'll call $l_i$ and $r_i$). Then we connect up vertices that follow the rules:

• $\{v_0, l_i\}\in E $ if the line $(v_0, l_i)$ intersects all gates $g_k$ for $k=1\dots i-1$ (and same with $r$).
• $\{l_i ,r_j\} \in E, i<j$ if the line $(l_i, r_j)$ intersects all gates $g_k$ for $k=i+1\dots j-1$ (for all four pairs of left/right).
• $\{l_i, v_1\}\in E$ — same rules as with $v_0$ but the other way around.

Now we have the full graph of valid moves, and can run Dijkstra's (or A*, or whatever you want) to find the shortest path. You can also consider the two endpoints to be gates of zero width so that all three cases collapse to the middle case.

This works, but it's a lot of work to compute the graph, and without some smart shortcuts (e.g. checking that the trivial line $(v_0, v_1)$ is valid) you risk doing a lot of intersection testing where none was required, for instance if the gates are a bunch of horizontal short segments stacked upwards. It's probably possible to prune the set of gates, or accelerate with an spacial index, or other methods, but this introduces more complexity.

Can we do better?

A Nice Solution

Here's an observation: If we look at a shortest path through a gate, it is always one of two cases:

1. The path goes in a straight line through the gate, or
2. The path goes to either endpoint and then turns away from the gate.

We can use this to extend shortest paths going from $p_0$ to the gate $g_i$ to also go to gate $g_{i+1}$: straight lines continue, and the rest of $g_{i+1}$ is covered by going from an endpoint of $g$ (whichever is the closer one). If we segment each gate this way we can compute the segmentation of the next gate, and once all gates are handled we can backtrack to find the path.

Let's see how this works. The first step is easy because the shortest path from the any point on the first gate back to start is the straight line. $g_1$ is covered by one solid region.

When segmenting $g_2$ we get two regions. The region that covered $g_1$ is extended where it overlaps with $g_2$: all points on this part of $g_2$ has a trivial path back to the start (the straight line). This doesn't cover the entire gate since there's more on the right side, so we create a new region here that is rooted in the rightmost point of $g_1$, namely $r_1$. The shortest path from any point on this part of $g_2$ back to the start is first to $r_1$ (the root of the region), and then back to start.

This was the observation: going from $p_0$ to $g_2$ we can either go straight ahead (going through $g_1$ in the process) to $g_2$, or we can first go to $r_1$, turn to the right, and then go straight ahead to the remainder of $g_2$. This holds for all points in the region: the shortest path from $p_0$ to any point $q$ in the region is the shortest path to the root of that region, plus the straight line to $q$.

We continue with the remaining gates, and it looks like this:

In the very last step we need to check which region $p_1$ is in. If it's inside a region we're done, and otherwise we insert a new region on the appropriate endpoint of the gate. This is also the same as pretending it is a gate of width zero, so no special logic is needed.

Now that we have found the end we need to backtrack to find the path. To do this we follow the roots of the regions backwards: $p_1$ is contained in the tiny blue region rooted in $r_5$, so this is the first point. $r_5$ is covered by the orange region rooted in $l_2$. And $l_2$ is covered by the blue region rooted in $p_0$. The final path is $[p_0, l_2, r_5, p_1]$.

That's it! This method is really cool, because we've just computed the shortest path between two points without computing any lengths! Think about this for a second: we have found a path that minimizes the distance in between two points without every computing a single distance.

What we have done, is used the triangle inequality of metric spaces, which says it's never farther to go in a straight line than to go through an intermediate point. We used this every time we segmented a new gate, since we argued that if we can go in a straight line, we'll do so.

Details

This is a cool method, but what makes it even cooler is how little data you need to store to run it. Consider this: If you look at $g_i$ and you know the ordered roots of each region, that describes the segmentation of $g_i$:

We have three roots $1$, $2$, and $3$, and we draw a line from $1$ to $l_i$, lines in between adjacent roots, and $3$ to $r_i$. When we extend the regions from $g_{i-1}$ to $g_i$ we only need to find in which region (if any) the two endpoints $l_i$ and $r_i$ are. To do this we can find the first (last) line that has $l_i$ ($r_i$) on its left (right). This is the only operation we need: is a point on the left or right side of a line?

Extending the segmentation to a new gate goes like this: we look at the lines in order from left to right, and find that $l_i$ is to the left of our first line. This means that it is before our first region, so we create a new region for $l_i$ (green). Then we look at $r_i$ to find the first line for which $r_i$ is on the right, which turns out to be the third line. This means the point is in the region in between the second and third line (blue), and so we shrink this region to match $r_i$. All regions in between the inserted green region and the clipped blue region (only the orange) are kept as-is.

There's just one catch: since we're doing orientation queries we need to be mindful of the orientation of the lines. In this example we have lines $(1, l_i), (2,1), (2,3), (3,r_i)$; how can we know that we should use $(2,1)$ and not $(1,2)$? We can of course store the pairs explicitly, even if this is twice the number of points that we really need. But we don't need to.

It turns out that the segmentation always have the same V-like shape:

It's not so hard to imagine why this is: new regions are always added on the two ends and are set to cover the remaining part of the gate. Other regions might be shrunk or discarded completely, so their "orientation" doesn't ever change. We can store which root is the "bottom" root, and this gives us the ordering of all of the lines, since they all point away from the root and towards the edges of the gate.

To simplify backtracking when computing the final shortest path we can store back links on the endpoints of the gates. When we compute which region covers the endpoints of a new gate we can record the root of the region that covered it. Then the final path is computed by following the back links and reversing the path.

Lastly, checking whether a point is on the left or right side of a line is easy: you can take the dot product of the rotated line direction and the line-to-point vector and check its sign:

fn is_on_the_left(line: Line, p: Point) -> bool {
    let to_p = p - line.root;
    let rot = [-line.dir.y, line.dir.x].into(); // 90deg CCW
    0 < rot.dot(to_p)
}

Thanks for reading.

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License