If you want to make money online : Register now

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

, , No Comments
Problem Detail: 

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?

Asked By : gromgull
Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/64339

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback