1
$\begingroup$

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:

crappy handdrawn example

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! That answer the question as asked! What I didn't express very clearly is that I need the lines to be somehow "mapped" to each other. (these are actually gps tracks). i.e. when you say: > Let $Q_i$ be the point on the red polyline that is closest to $P_i$. that considers only the local mapping. I need it so that if Qi matched $P_i$, $P_{i+1}$ must match $Q_j$, where $j>=i$. This is why I used dynamic programming to find the mapping when working with discreet points. That's not actually what I asked though, so I'll accept this answer! $\endgroup$ – gromgull Oct 11 '16 at 8:49
  • $\begingroup$ @gromgull, thanks for your kind words. Feel free to ask another question if you didn't quite get what you needed from this one! $\endgroup$ – D.W. Oct 11 '16 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.