How can I find spans where the distance between two poly-lines is more or less than some threshold?

Question

I have two poly-lines. I would like to find segments of these lines where the minimum distance between them is higher (or lower) than some threshold.

I.e. I want to find the parts of the lines highlighted in squiggly pink here:

My best attempt is to split each line into some equally sized segments, and then use dynamic programming to find the closest corresponding points on each line. This is efficient, and works, but will of course be off by some amount from the real points where the minimum distance is reached. Making the segments smaller will make the solution better (but slower), but I have a feeling a continuous and exact solution is possible?

Answer 1

Given a point $P$ and a polyline $L$, you can compute the distance from $P$ to $L$ (i.e., the distance from $P$ to the nearest point on $L$).

Now take the union of all of the following points:

• The endpoints of the line segments in the blue polyline

• For each endpoint of each line segment in the red polyline, the closest point on the blue polyline

• All intersection points where the blue polyline intersects the red polyline

This set can be computed efficiently, and its size is linear in the size of the input. Let $P_1,P_2,\dots,P_n$ denote these points, in the order they appear on the blue polyline. Let $Q_i$ be the point on the red polyline that is closest to $P_i$.

Now consider any pair of consecutive points $P_i,P_{i+1}$. As we move along the blue polyline from $P_i$ to $P_{i+1}$, the distance to the red polyline will either increase monotonically or decrease monotonically. Thus, if it crosses the threshold (e.g., starts below the threshold and increases to something larger than the threshold), you can use binary search to find the point where it crosses the threshold.

In fact, we can say more. Consider a point $P = \alpha P_1 + (1-\alpha) P_{i+1}$, as $\alpha$ increases from $0$ to $1$, and let $Q$ be the nearest point on the red polyline to $P$. As $\alpha$ increases from $0$ to $1$, $P$ be moving along a straight-line path, i.e., along a single line segment of the blue polyline. Similarly, $Q$ will also e moving along a straight-line path, i.e., along a single line segment of the red polyline. Consequently, there's a simple formula for the distance between the two as a function of $\alpha$, and we can solve for the $\alpha$ that makes this distance equal to the threshold. Thus, this will let us precisely identify the point where the minimum distance between the two polylines is exactly equal to the threshold.

Now doing a linear scan over all consecutive pairs $P_i,P_{i+1}$ will enable you to find all places where the minimum distance is higher than some threshold, exactly.