Find the first point along a heading that is a specified distance away from a line segment.

Question

Hi, Given a starting point, a heading, a distance, and a line segment, find the first point along this heading that is the specified distance away from this line segment.

I covered two cases, but I haven't been able to cover the last one. First case: heading away from the line. Ignore it even if the starting point is within the specified distance.

Second case: It intersects the line. I solved it using trig and triangles. Initially didn't consider the next case.

Third case: It is heading towards the line, but it does not intersect it. I think this will solve the second case as well if it's done correctly. Three sub cases: 3.1 The minimum line distance is greater than the specified distance. Ignore it. 3.2 The minimum line distance is equal to the specified distance. Found the points already. 3.3 The minimum line distance is less than the specified distance. This means there is a perpendicular line from the along the heading to an end point of the line segment that is less than the Distance needed. This also means on either side of this perpendicular line will be two lines of the Distance needed. One is perpendicular to the heading, while the other is closest to the same end point and not perpendicular to the heading. Just a matter of finding those points and seeing which one is closer to the start point.

This is where I am stuck today. Drawing it up was easy, but doing the vector calc or whatever turned out tricky. Thanks for any help.

Possible to rephrase as: At what time(s) is P(t) = P0 + t*v at a distance D from the line segment L((x1,y1), (x2,y2))? v=(sin(heading), -cos(heading)) in my case.

Answer 1

Find the initial distance betweenen P0 and L. Say that is D0.

D(t) is now given by

D(t) = D0 - v*t*sin(alpha)

Where alpha is angle between the heading (the P(t) line) and L.

You can compute alpha by writing both lines in the form y = mx + c and calculating the angles (using arctan) and taking the difference. Be careful to choose the right signs.

Hope that helps.

Answer 2

Thanks, that works. I found the alpha this way: heading = 45.0*pi/180. #heading 45 degrees. if x1 > x2: #line segment (x1,y1)<->(x2,y2) dx = x2 - x1 dy = y2 - y1 else: dx = x1 - x2 dy = y1 - y2

segmentHeading = atan2(dx, dy)

if heading > 0: alpha = segmentHeading + heading else: alpha = -segmentHeading + heading

t = abs( (dStart - D) / -cos(alpha) ) #-cos in python, sin in C.

Answer 3

Shoot mang your solution doesn't always work. I found a counter example:

Line Segment = (0,0) -> (0,14)

Start Point = (19, 6) @ heading -159.5 or 200.5 in west/counter-clockwise

It will intersect the line at (2.952, 0.0) so I ask, where does it it come within a distance of 0.0.

The result I get is incorrect.

http://img5.imageshack.us/i/failuref.png/

How I can tell which ones will work using your solution and which ones do not work depends whether the minimum starting distance between the point and the line segment creates a perpendicular line.

If I can post another picture in the next post, I will put the successful example.

I would have liked to post some code for Sage which produced those images, but the code tags are accepting python unfortunately.

Answer 4

A successful result where the minimum starting distance between the point and the line segment is perpendicular to the line segment:

http://img46.imageshack.us/i/success.png/

Answer 5

Hi the solution I eventually came up with.

1. Does the ray intersect line segments that are parallel and the specified distance D away from the line segment. Just drawing a rectangle and checking the sides parallel to the line segment.

2. Does the ray intersect circles of radius D at each end point of the line segment.

3. Minimize for total unit time to find the first point along the ray that is D away from the line segment.

Possible Border case: Is the start point within D and heads away from the line? Up to the user how to handle this case.