Jump to content
  • Advertisement
Sign in to follow this  
OCcsdude

2d point-line distance

This topic is 4844 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

Here is the function I've written for finding the shortest distance between a point and a line (in 2d). If someone could evaluate it for me to make sure it's working right, that would be great. It's been a little frustrating for me to debug some subtle problems in a program I'm making. I would appreciate it very much if someone could evaluate this function real quick to see if it is working correctly. I've tried about three different methods but it's hard to be 100% sure if it is working all the time. And some advice on how to speed it up would be cool to if anyone wants to share some knowledge. Thanks a lot ;).
long double Vertice :: PointLineTwoDDistance
(
long double ldX1,      //the point's X
long double ldY1,      //the point's Y
long double ldLineX1,  //coordinates of line made up by two x and y pairs:
long double ldLineY1,  //(ldLineX1, ldLineY1), (ldLineX2, ldLineY2)
long double ldLineX2, 
long double ldLineY2
)
{
	long double ldRise = ( (ldLineY2) - (ldLineY1) );
	long double ldRun = ( (ldLineX2) - (ldLineX1) );

	if (ldRise == 0)
		return (ldY1 - ldLineY1);
	if (ldRun == 0)
		return (ldX1 - ldLineX1);

	if (ldRise != 0 && ldRun != 0)
	{
		long double ldA = ( (-1) * (ldRise / ldRun) );
		long double ldB = 1;
		long double ldC = ( (-1) * ( ldLineY1 - ( ( ldA * (-1) ) * (ldLineX1) ) ) );

		return ( fabs ( ( (ldX1 * ldA) + (ldY1 * ldB) + (ldC) ) / ( sqrt ( (ldA * ldA) + (ldB * ldB) ) ) ) );
	}
	return 0;
}

[Edited by - OCcsdude on August 8, 2005 9:43:54 PM]

Share this post


Link to post
Share on other sites
Advertisement
Wow I JUST worked on this problem for my project. Took me a lot longer than I thought, my linalg is getting pretty bad :(

Anyway, I'm not exactly sure if your algorithm actually works, but I can definitely tell you that this line:

Quote:

long double ldA = ( (-1) * (ldRise / ldRun) );


is bad. You will get weird results as ldRun approaches 0. The best way is to keep your line expressed as a vector (instead of finding the slope).

Here's the algorithm that I'm using, it's all tested and it works. I'm using floats but you can keep using long doubles.


float dx = ldLineX2 - ldLineX1;
float dy = ldLineY2 - ldLineY1;
if (dx == 0 && dy == 0)
return 0;
float length = (float) Math.sqrt(dx*dx + dy*dy);
float norm_dx = dx / length;
float norm_dy = dy / length;
float dist_from_line = Math.abs(norm_dx * (ldLineY1 - ldY1) - norm_dy *(ldLineX1 - ldX1));

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Hey, thanks a lot for the function. I think I understand what I did wrong now. I'll make another post in a bit explaining what I did wrong, and I'll post the new function. I appreciate it, hopefully the headache with the specifics of some of this linear algebra will start to go away now :).

Share this post


Link to post
Share on other sites
Point P line A, B



Vector2 closest_point_on_segment_AB_to_point_P(Vector2 A, Vector B, Vector P)
{
Vector U = B-A;

float t = dot(P-A,U) / dot(U,U);

if ( t < 0 ) t = 0; if ( t > 1 ) t = 1;

return A + U * t;
}

float PointDistanceFromLine(Vector2 A, Vector B, Vector P);
{
Vector2 Pt = closest_point_on_segment_AB_to_point_P(A, B, P);

return (P-Pt).Length();
}


this is mine using VECTOR_PROJECTION

Share this post


Link to post
Share on other sites
My advice is to forget rise/run and use raymond's method instead. That will avoid degenerate cases, and is just generally more useful.

Here's a slightly more efficient version of the function:
Vector2 ClosestPointOnSegment(const Vector2& A, const Vector2& B, const Vector2& P)
{
Vector2 D = B-A;
float numer = dot(P-A,D);
if (numer <= 0.0f)
return A;
float denom = dot(D,D);
if (numer >= denom)
return B;
return A + (numer/denom) * D;
}

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!