I need a basic function to find the shortest distance between a point and a line segment. Feel free to write the solution in any language you want; I can translate it into what I'm using (Javascript).
EDIT: My line segment is defined by two endpoints. So my line segment AB is defined by the two points A (x1,y1) and B (x2,y2). I'm trying to find the distance between this line segment and a point C (x3,y3). My geometry skills are rusty, so the examples I've seen are confusing, I'm sorry to admit.
I don't know how you're representing lines and points, but here's all the mathematics you need to get started. Shouldn't be too hard to figure out what you need to do
http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html
I'm assuming you want to find the shortest distance between the point and a line segment; to do this, you need to find the line (lineA) which is perpendicular to your line segment (lineB) which goes through your point, determine the intersection between that line (lineA) and your line which goes through your line segment (lineB); if that point is between the two points of your line segment, then the distance is the distance between your point and the point you just found which is the intersection of lineA and lineB; if the point is not between the two points of your line segment, you need to get the distance between your point and the closer of two ends of the line segment; this can be done easily by taking the square distance (to avoid a square root) between the point and the two points of the line segment; whichever is closer, take the square root of that one.
Here is a page that goes over a construction for the distance between two lines. Along the way he works out the distance between a point and a line.
See this
//========================================================================================
//
// DistancePointLine Unit Test
// Copyright (c) 2002, All rights reserved
//
// Damian Coventry
// Tuesday, 16 July 2002
//
// Implementation of theory by Paul Bourke
//
//========================================================================================
#include <stdio.h>
#include <math.h>
typedef struct tagXYZ
{
float X, Y, Z;
}
XYZ;
float Magnitude( XYZ *Point1, XYZ *Point2 )
{
XYZ Vector;
Vector.X = Point2->X - Point1->X;
Vector.Y = Point2->Y - Point1->Y;
Vector.Z = Point2->Z - Point1->Z;
return (float)sqrt( Vector.X * Vector.X + Vector.Y * Vector.Y + Vector.Z * Vector.Z );
}
int DistancePointLine( XYZ *Point, XYZ *LineStart, XYZ *LineEnd, float *Distance )
{
float LineMag;
float U;
XYZ Intersection;
LineMag = Magnitude( LineEnd, LineStart );
U = ( ( ( Point->X - LineStart->X ) * ( LineEnd->X - LineStart->X ) ) +
( ( Point->Y - LineStart->Y ) * ( LineEnd->Y - LineStart->Y ) ) +
( ( Point->Z - LineStart->Z ) * ( LineEnd->Z - LineStart->Z ) ) ) /
( LineMag * LineMag );
if( U < 0.0f || U > 1.0f )
return 0; // closest point does not fall within the line segment
Intersection.X = LineStart->X + U * ( LineEnd->X - LineStart->X );
Intersection.Y = LineStart->Y + U * ( LineEnd->Y - LineStart->Y );
Intersection.Z = LineStart->Z + U * ( LineEnd->Z - LineStart->Z );
*Distance = Magnitude( Point, &Intersection );
return 1;
}
void main( void )
{
XYZ LineStart, LineEnd, Point;
float Distance;
LineStart.X = 50.0f; LineStart.Y = 80.0f; LineStart.Z = 300.0f;
LineEnd.X = 50.0f; LineEnd.Y = -800.0f; LineEnd.Z = 1000.0f;
Point.X = 20.0f; Point.Y = 1000.0f; Point.Z = 400.0f;
if( DistancePointLine( &Point, &LineStart, &LineEnd, &Distance ) )
printf( "closest point falls within line segment, distance = %f\n", Distance );
else
printf( "closest point does not fall within line segment\n" );
LineStart.X = 0.0f; LineStart.Y = 0.0f; LineStart.Z = 50.0f;
LineEnd.X = 0.0f; LineEnd.Y = 0.0f; LineEnd.Z = -50.0f;
Point.X = 10.0f; Point.Y = 50.0f; Point.Z = 10.0f;
if( DistancePointLine( &Point, &LineStart, &LineEnd, &Distance ) )
printf( "closest point falls within line segment, distance = %f\n", Distance );
else
printf( "closest point does not fall within line segment\n" );
}
Hey, I just wrote this yesterday. It's in Actionscript 3.0, which is basically Javascript, though you might not have the same Point class.
//st = start of line segment
//b = the line segment (as in: st + b = end of line segment)
//pt = point to test
//Returns distance from point to line segment.
//Note: nearest point on the segment to the test point is right there if we ever need it
public static function linePointDist( st:Point, b:Point, pt:Point ):Number
{
var nearestPt:Point; //closest point on seqment to pt
var keyDot:Number = dot( b, pt.subtract( st ) ); //key dot product
var bLenSq:Number = dot( b, b ); //Segment length squared
if( keyDot <= 0 ) //pt is "behind" st, use st
{
nearestPt = st
}
else if( keyDot >= bLenSq ) //pt is "past" end of segment, use end (notice we are saving twin sqrts here cuz)
{
nearestPt = st.add(b);
}
else //pt is inside segment, reuse keyDot and bLenSq to get percent of seqment to move in to find closest point
{
var keyDotToPctOfB:Number = keyDot/bLenSq; //REM dot product comes squared
var partOfB:Point = new Point( b.x * keyDotToPctOfB, b.y * keyDotToPctOfB );
nearestPt = st.add(partOfB);
}
var dist:Number = (pt.subtract(nearestPt)).length;
return dist;
}
Also, there's a pretty complete and readable discussion of the problem here: notejot.com
Here's the code I ended up writing. This code assumes that a point is defined in the form of {x:5, y:7}. Note that this is not the absolute most efficient way, but it's the simplest and easiest-to-understand code that I could come up with.
// a, b, and c in the code below are all points
function distance(a, b)
{
var dx = a.x - b.x;
var dy = a.y - b.y;
return Math.sqrt(dx*dx + dy*dy);
}
function Segment(a, b)
{
var ab = {
x: b.x - a.x,
y: b.y - a.y
};
var length = distance(a, b);
function cross(c) {
return ab.x * (c.y-a.y) - ab.y * (c.x-a.x);
};
this.distanceFrom = function(c) {
return Math.min(distance(a,c),
distance(b,c),
Math.abs(cross(c) / length));
};
}
Couldn't resist coding it in python :)
from math import sqrt, fabs
def pdis(a, b, c):
t = b[0]-a[0], b[1]-a[1] # Vector ab
dd = sqrt(t[0]**2+t[1]**2) # Length of ab
t = t[0]/dd, t[1]/dd # unit vector of ab
n = -t[1], t[0] # normal unit vector to ab
ac = c[0]-a[0], c[1]-a[1] # vector ac
return fabs(ac[0]*n[0]+ac[1]*n[1]) # Projection of ac to n (the minimum distance)
print pdis((1,1), (2,2), (2,0)) # Example (answer is 1.414)
Ditto for fortran :)
real function pdis(a, b, c)
real, dimension(0:1), intent(in) :: a, b, c
real, dimension(0:1) :: t, n, ac
real :: dd
t = b - a ! Vector ab
dd = sqrt(t(0)**2+t(1)**2) ! Length of ab
t = t/dd ! unit vector of ab
n = (/-t(1), t(0)/) ! normal unit vector to ab
ac = c - a ! vector ac
pdis = abs(ac(0)*n(0)+ac(1)*n(1)) ! Projection of ac to n (the minimum distance)
end function pdis
program test
print *, pdis((/1.0,1.0/), (/2.0,2.0/), (/2.0,0.0/)) ! Example (answer is 1.414)
end program test
For future reference, this link has five source code examples for this problem.
Eli, the code you've settled on is incorrect. A point near the line on which the segment lies but far off one end of the segment would be incorrectly judged near the segment. Here's some correct code, in C++. It presumes a class 2D-vector class vec2 {float x,y;}, essentially, with operators to add, subract, scale, etc, and a distance and dot product function (i.e. x1 x2 + y1 y2).
float minimum_distance(vec2 v, vec2 w, vec2 p) {
// Return minimum distance between line segment vw and point p
const float l2 = length_squared(v, w); // i.e. |w-v|^2 - avoid a sqrt
if (l2 == 0.0) return distance(p, v); // v == w case
// Consider the line extending the segment, parameterized as v + t (w - v).
// We find projection of point p onto the line.
// It falls where t = [(p-v) . (w-v)] / |w-v|^2
const float t = dot(p - v, w - v) / l2;
if (t < 0.0) return distance(p, v); // Beyond the 'v' end of the segment
else if (t > 1.0) return distance(p, w); // Beyond the 'w' end of the segment
const vec2 projection = v + t * (w - v); // Projection falls on the segment
return distance(p, projection);
}
This is an implementation made for FINITE LINE SEGMENTS, not infinite lines like most other functions here seem to be (that's why I made this).
Example: http://boomie.se/upload/Drawdebug.swf
Python:
import math
def dist(x1,y1, x2,y2, x3,y3): # x3,y3 is the point
px = x2-x1
py = y2-y1
something = px*px + py*py
u = ((x3 - x1) * px + (y3 - y1) * py) / something
if u > 1:
u = 1
elif u < 0:
u = 0
x = x1 + u * px
y = y1 + u * py
dx = x - x3
dy = y - y3
# Note: If the actual distance does not matter,
# if you only want to compare what this function
# returns to other results of this function, you
# can just return the squared distance instead
# (i.e. remove the sqrt) to gain a little performance
dist = math.sqrt(dx*dx + dy*dy)
return dist
AS3:
public static function segmentDistToPoint(segA:Point, segB:Point, p:Point):Number
{
var p2:Point = new Point(segB.x - segA.x, segB.y - segA.y);
var something:Number = p2.x*p2.x + p2.y*p2.y;
var u:Number = ((p.x - segA.x) * p2.x + (p.y - segA.y) * p2.y) / something;
if (u > 1)
u = 1;
else if (u < 0)
u = 0;
var x:Number = segA.x + u * p2.x;
var y:Number = segA.y + u * p2.y;
var dx:Number = x - p.x;
var dy:Number = y - p.y;
var dist:Number = Math.sqrt(dx*dx + dy*dy);
return dist;
}
These were made from this: http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/