https://mht.wtf/post/navigate/

mht.wtf

Computer science, programming, and whatnot.

Navigate Gates

July 27, 2025 back to posts

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.

[ex] Sample input
[graph] Graph created from the rules above

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.

[fig1] Segmenting $g_1$ is trivial
[fig2] A new region is needed to cover $g_2$

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:

[fig3] $g_3$ gets a new region
[fig4] $g_4$ also gets a new region
[fig5] $g_5$ was already covered
[fig6] A new region for $p_1$

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$:

[repr1] $g_i$ with roots in order
[repr2] Straight lines connect the dots
[repr3] Regions are colored

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?

[repr4] We check which regions $g_i$ is in
[repr5] Roots are updated
[repr6] New regions visualized

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:

[fan1]

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

mht | contact