Twitter  Facebook  Google+  YouTube  E-Mail  RSS
The One Man MMO Project
The story of a lone developer's quest to build an online world :: MMO programming, design, and industry commentary
2D or 3D Distance from a Point to a Line
By Robert Basler on 2013-09-13 11:10:58
Homepage: www.onemanmmo.com email:one at onemanmmo dot com

I spent a couple hours reading pages of Google results trying to figure this out last night. There are a lot of people who seem to have problems with this. The pictures are all reasonably clear, but the implementations are quite variable for a non-math guy. Here's the resulting vector code which seems to be good. Maybe this'll help someone. Note that you can replace Vector3 with Vector2 and this will work for 2D lines.

p1 and p2 are points on a line. DistancePointLine returns the perpendicular distance p3 is from that line. It returns true if p3 is perpendicular to the line segment from p1 to p2, false if not. It also returns the distance from the infinite line going through p1 and p2 (because I found that more helpful.)

pointdistance.jpg


IntersectionPointLine returns the point on the infinite line that runs through p1 and p2 that is perpendicular to p3. Some variations of IntersectionPointLine return either p1 or p2 as the intersection point if p3 is not within p1 to p2 (u is out of range 0.0-1.0) which would give the distance to a point which is on the line segment, but in this case it is no longer the perpendicular distance. If this is what you want, in IntersectionPointLine return p1 if i < 0.0 and p2 if u > 1.0. That wasn't helpful in my case (I'm using this to decimate meshes) hence the code below finds the perpendicular distance from the infinite line.

Here is the C++ code:

    bool Geometry::DistancePointLine( const Vector3& p3, const Vector3& p1, const Vector3& p2, float32 *distance )
{
Vector3 intersection;
bool withinLine = IntersectionPointLine( p3, p1, p2, &intersection );
if ( distance != NULL )
{
*distance = ( p3 - intersection ).Magnitude();
}
return withinLine;
}

bool Geometry::IntersectionPointLine( const Vector3& p3, const Vector3& p1, const Vector3& p2, Vector3 *intersection )
{
Vector3 diff = p3 - p1;
Vector3 dir = p2 - p1;
float u = Vector3::DotProduct( diff, dir ) / Vector3::DotProduct( dir, dir );
if ( intersection != NULL )
{
*intersection = p1 + dir * u;
}
if ( ( u < 0.0f ) || ( u > 1.0f ) )
{
// closest point does not fall within the line segment
return false;
}
return true;
}

By Robert Basler on 2013-10-23 13:45:20
Homepage: www.onemanmmo.com email:one at onemanmmo dot com
Code as posted did not include the end points of the line as inside the line. That isn't useful to me, so I've revised the original line:

Old: if ( ( u <= 0.0f ) || ( u >= 1.0f ) )
New: if ( ( u < 0.0f ) || ( u > 1.0f ) )

New Comment

Cookie Warning

We were unable to retrieve our session cookie from your web browser. If pressing F5 once to reload this page does not get rid of this message, please read this to learn more.

You will not be able to post until you resolve this problem.

Comment (You can use HTML, but please double-check web link URLs and HTML tags!)
Your Name
Homepage (optional, don't include http://)
Email (optional, but automatically spam protected so please do)
What color is a lime? (What's this?)

  Admin Log In



[The Imperial Realm :: Miranda] [Blog] [Gallery] [About]
Terms Of Use & Privacy Policy