Jump to content
  • Advertisement
Sign in to follow this  
MadsGustaf

[2D] Distance from a point to a line segment

This topic is 3760 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a point(x,y) and a line between two points (x1,y1) and (x2,y2) I am currently using the following code to compute the distance between the point and the line, however i am not getting the correct result ( i am getting a constant value every iteration):
[source langg = "cpp"]
float A = x - x1;
float B = y - y1;
float C = x2 - x1;
float D = y2 - y1;

float dot = A * C + B * D;
float len_sq = C * C + D * D;
float param = dot / len_sq;

float xx,yy;

if(param < 0)
{
    xx = x1;
    yy = y1;
}
else if(param > 1)
{
    xx = x2;
    yy = y2;
}
else
{
    xx = x1 + param * C;
    yy = y1 + param * D;
}

float dist =sqrt( ((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2)) ) ;


cout << dist << endl;

I am using a coordinate system increasing going from up to down(y) and from left to right(x).

Share this post


Link to post
Share on other sites
Advertisement
General algorithm for this:
- Find the point on the line closest to the point. In 2D that's quite easy; the distance along the line is
d = (p.v) - (A.v)
... where p is the point, A is a reference point on the line (probably one end), and v is the (normalised) direction of the line.

If d <= 0, your point is off the beginning, and the closest point is A.
If d > (distance from A to B), the point is off the end, and the closest point is B.
Otherwise, the point is on the line segment, at A+d(B-A).

- Find the distance from the point to the closest point on the line: trivial ;)

Share this post


Link to post
Share on other sites
Sorry, but could you elaborate on this

Quote:

....and v is the (normalised) direction of the line.

I may just be confused by the notation (aka my obviously weak math) p.v and A.v(/B.v)

Share this post


Link to post
Share on other sites
No problem. Imagine your line is between (2,3) and (7,4). The direction of the line is (B-A) = (7-2, 4-3) = (5,1), so the normalised direction vector v for this example would be (5, 1)/√26 = (0.981, 0.196) – the vector along the line with a magnitude of 1.

(Why 26? ... 5²+1².)

p.v and A.v uses the vector dot product (a.b = (axbx+ayby in 2D).

Let's say you want to find the distance from (3, 8) to the line. So for this example,
A = (2, 3)
B = (7, 4)
v = (0.981, 0.196)
p = (3, 8)

A.v = 2.54
p.v = 4.51
=> d = 1.96

Closest point is A+dv = (2,3) + 1.96(0.981, 0.196) = (3.92, 3.38)

Difference = (-0.92, 4.61). This should be perpendicular to the line, as the closest point is between A and B; indeed,
Quote:
+/dx×v // dot product
-3.33066907387547E-16 // might as well be zero

And obviously distance = mag(dx) = 4.7 units.

Hope that helps :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!