点与线段之间的最短距离

我需要一个基本的函数来find点和线段之间的最短距离。 随意用任何你想要的语言写解决scheme; 我可以把它翻译成我正在使用的（Javascript）。

编辑：我的线段由两个端点定义。 所以我的线段AB由两个点A (x1,y1)和B (x2,y2) 。 我试图find这个线段和点C (x3,y3)之间的距离。 我的几何技能是生锈的，所以我看到的例子令人困惑，我很抱歉承认。

Answer 1

Eli，你已经解决的代码是不正确的。 线段靠近线段的一端靠近线段一端的点将在线段附近被错误判断。 更新：提到的不正确答案已不再被接受。

这里有一些正确的代码，在C ++中。 它假定了一个二维vectorclass vec2 {float x,y;} ，本质上是带有运算符的运算符，用于添加，删除，缩放等，以及距离和点乘积函数（即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); // ie |wv|^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 = [(pv) . (wv)] / |wv|^2 // We clamp t from [0,1] to handle points outside the segment vw. const float t = max(0, min(1, dot(p - v, w - v) / l2)); const vec2 projection = v + t * (w - v); // Projection falls on the segment return distance(p, projection); } 

编辑：我需要一个Javascript的实现，所以在这里，没有依赖（或评论，但它是以上的直接端口）。 点表示为具有x和y属性的对象。

 function sqr(x) { return x * x } function dist2(v, w) { return sqr(vx - wx) + sqr(vy - wy) } function distToSegmentSquared(p, v, w) { var l2 = dist2(v, w); if (l2 == 0) return dist2(p, v); var t = ((px - vx) * (wx - vx) + (py - vy) * (wy - vy)) / l2; t = Math.max(0, Math.min(1, t)); return dist2(p, { x: vx + t * (wx - vx), y: vy + t * (wy - vy) }); } function distToSegment(p, v, w) { return Math.sqrt(distToSegmentSquared(p, v, w)); } 

编辑2：我需要一个Java版本，但更重要的是，我需要它在3d而不是2d。

 float dist_to_segment_squared(float px, float py, float pz, float lx1, float ly1, float lz1, float lx2, float ly2, float lz2) { float line_dist = dist_sq(lx1, ly1, lz1, lx2, ly2, lz2); if (line_dist == 0) return dist_sq(px, py, pz, lx1, ly1, lz1); float t = ((px - lx1) * (lx2 - lx1) + (py - ly1) * (ly2 - ly1) + (pz - lz1) * (lz2 - lz1)) / line_dist; t = constrain(t, 0, 1); return dist_sq(px, py, pz, lx1 + t * (lx2 - lx1), ly1 + t * (ly2 - ly1), lz1 + t * (lz2 - lz1)); } 

Answer 2

这里是Javascript中最简单的完整代码。

x，y是你的目标点，x1，y1到x2，y2是你的线段。

更新：修复0评论长度线问题。

 function pDistance(x, y, x1, y1, x2, y2) { var A = x - x1; var B = y - y1; var C = x2 - x1; var D = y2 - y1; var dot = A * C + B * D; var len_sq = C * C + D * D; var param = -1; if (len_sq != 0) //in case of 0 length line param = dot / len_sq; var 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; } var dx = x - xx; var dy = y - yy; return Math.sqrt(dx * dx + dy * dy); } 

Answer 3

这是一个有限的线段的实现，而不是无限的线，像大多数其他function在这里似乎（这就是为什么我这样做）。

例子就在这里 。

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) / float(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 # (ie 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 = ((px - segA.x) * p2.x + (py - 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 - px; var dy:Number = y - py; var dist:Number = Math.sqrt(dx*dx + dy*dy); return dist; } 

JAVA

 private double shortestDistance(float x1,float y1,float x2,float y2,float x3,float y3) { float px=x2-x1; float py=y2-y1; float temp=(px*px)+(py*py); float u=((x3 - x1) * px + (y3 - y1) * py) / (temp); if(u>1){ u=1; } else if(u<0){ u=0; } float x = x1 + u * px; float y = y1 + u * py; float dx = x - x3; float dy = y - y3; double dist = Math.sqrt(dx*dx + dy*dy); return dist; } 

这些是由此而来的。

Answer 4

在F＃中，从点c到a和b之间a线段的距离由下式给出：

 let pointToLineSegmentDistance (a: Vector, b: Vector) (c: Vector) = let d = b - a let s = d.Length let lambda = (c - a) * d / s let p = (lambda |> max 0.0 |> min s) * d / s (a + p - c).Length 

向量d沿线段从a指向b 。 d/s与ca的点积给出了无限长线与点c之间最接近点的参数。 min和max函数用于将此参数限制在0..s的范围内，以便该点位于a和b之间。 最后， a+pc的长度是从c到线段上最近点的距离。

使用示例：

 pointToLineSegmentDistance (Vector(0.0, 0.0), Vector(1.0, 0.0)) (Vector(-1.0, 1.0)) 

Answer 5

在我自己的问题线程中， 如何在C，C＃/ .NET 2.0或Java中的所有情况下计算点和线段之间的最短二维距离？ 我被要求在这里find一个C＃的答案：所以在这里，从http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static修改：;

 //Compute the dot product AB . AC private double DotProduct(double[] pointA, double[] pointB, double[] pointC) { double[] AB = new double[2]; double[] BC = new double[2]; AB[0] = pointB[0] - pointA[0]; AB[1] = pointB[1] - pointA[1]; BC[0] = pointC[0] - pointB[0]; BC[1] = pointC[1] - pointB[1]; double dot = AB[0] * BC[0] + AB[1] * BC[1]; return dot; } //Compute the cross product AB x AC private double CrossProduct(double[] pointA, double[] pointB, double[] pointC) { double[] AB = new double[2]; double[] AC = new double[2]; AB[0] = pointB[0] - pointA[0]; AB[1] = pointB[1] - pointA[1]; AC[0] = pointC[0] - pointA[0]; AC[1] = pointC[1] - pointA[1]; double cross = AB[0] * AC[1] - AB[1] * AC[0]; return cross; } //Compute the distance from A to B double Distance(double[] pointA, double[] pointB) { double d1 = pointA[0] - pointB[0]; double d2 = pointA[1] - pointB[1]; return Math.Sqrt(d1 * d1 + d2 * d2); } //Compute the distance from AB to C //if isSegment is true, AB is a segment, not a line. double LineToPointDistance2D(double[] pointA, double[] pointB, double[] pointC, bool isSegment) { double dist = CrossProduct(pointA, pointB, pointC) / Distance(pointA, pointB); if (isSegment) { double dot1 = DotProduct(pointA, pointB, pointC); if (dot1 > 0) return Distance(pointB, pointC); double dot2 = DotProduct(pointB, pointA, pointC); if (dot2 > 0) return Distance(pointA, pointC); } return Math.Abs(dist); } 

我是@SO不回答，而是提出问题，所以我希望我不会因为某些原因而倒下投票，而是build立批评。 我只是想（并被鼓励）分享别人的想法，因为在这个线程的解决scheme是用一些外来的语言（Fortran，Mathematica）或被人标记为有缺陷的。 唯一有用的（由Grumdrig）对我来说是用C ++写的，没有人标记错误。 但它缺less被调用的方法（点等）。

Answer 6

在Mathematica中

它使用段的参数描述，并将点投影到段定义的行中。 由于参数从0到1，如果投影在这个边界之外，我们计算到对应的开始点的距离，而不是垂直于该段的直线。

 Clear["Global`*"]; distance[{start_, end_}, pt_] := Module[{param}, param = ((pt - start).(end - start))/Norm[end - start]^2; (*parameter. the "." here means vector product*) Which[ param < 0, EuclideanDistance[start, pt], (*If outside bounds*) param > 1, EuclideanDistance[end, pt], True, EuclideanDistance[pt, start + param (end - start)] (*Normal distance*) ] ]; 

绘图结果：

 Plot3D[distance[{{0, 0}, {1, 0}}, {xp, yp}], {xp, -1, 2}, {yp, -1, 2}] 

画出比临界距离更近的点：

等高线图：

Answer 7

对于任何有兴趣的人来说，这里是Joshua的Javascript代码到Objective-C的简单转换：

 - (double)distanceToPoint:(CGPoint)p fromLineSegmentBetween:(CGPoint)l1 and:(CGPoint)l2 { double A = px - l1.x; double B = py - l1.y; double C = l2.x - l1.x; double D = l2.y - l1.y; double dot = A * C + B * D; double len_sq = C * C + D * D; double param = dot / len_sq; double xx, yy; if (param < 0 || (l1.x == l2.x && l1.y == l2.y)) { xx = l1.x; yy = l1.y; } else if (param > 1) { xx = l2.x; yy = l2.y; } else { xx = l1.x + param * C; yy = l1.y + param * D; } double dx = px - xx; double dy = py - yy; return sqrtf(dx * dx + dy * dy); } 

我需要这个解决scheme来处理MKMapPoint所以我会分享它，以防别人需要它。 只是一些小的变化，这将返回以米为单位的距离：

 - (double)distanceToPoint:(MKMapPoint)p fromLineSegmentBetween:(MKMapPoint)l1 and:(MKMapPoint)l2 { double A = px - l1.x; double B = py - l1.y; double C = l2.x - l1.x; double D = l2.y - l1.y; double dot = A * C + B * D; double len_sq = C * C + D * D; double param = dot / len_sq; double xx, yy; if (param < 0 || (l1.x == l2.x && l1.y == l2.y)) { xx = l1.x; yy = l1.y; } else if (param > 1) { xx = l2.x; yy = l2.y; } else { xx = l1.x + param * C; yy = l1.y + param * D; } return MKMetersBetweenMapPoints(p, MKMapPointMake(xx, yy)); } 

Answer 8

我不知道你是如何expression线条和点，但这里是所有你需要开始的math。 不要太难以弄清楚你需要做什么。

Answer 9

嘿，我昨天写了这个。 它在ActionScript 3.0，基本上是Javascript，但你可能没有相同的Point类。

 //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( bx * keyDotToPctOfB, by * keyDotToPctOfB ); nearestPt = st.add(partOfB); } var dist:Number = (pt.subtract(nearestPt)).length; return dist; } 

此外，还有一个相当完整和可读的关于这个问题的讨论： notejot.com

Answer 10

无法拒绝在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) 

同样为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 

Answer 11

对于懒惰，这是我的@ Grumdrig解决scheme的Objective-C端口：

 CGFloat sqr(CGFloat x) { return x*x; } CGFloat dist2(CGPoint v, CGPoint w) { return sqr(vx - wx) + sqr(vy - wy); } CGFloat distanceToSegmentSquared(CGPoint p, CGPoint v, CGPoint w) { CGFloat l2 = dist2(v, w); if (l2 == 0.0f) return dist2(p, v); CGFloat t = ((px - vx) * (wx - vx) + (py - vy) * (wy - vy)) / l2; if (t < 0.0f) return dist2(p, v); if (t > 1.0f) return dist2(p, w); return dist2(p, CGPointMake(vx + t * (wx - vx), vy + t * (wy - vy))); } CGFloat distanceToSegment(CGPoint point, CGPoint segmentPointV, CGPoint segmentPointW) { return sqrtf(distanceToSegmentSquared(point, segmentPointV, segmentPointW)); } 

Answer 12

我假设你想find点和线段之间的最短距离; 要做到这一点，你需要find垂直于你的线段（lineB）的线（lineA），通过你的点，确定该线（lineA）和你的线（它通过你的线段）（lineB） ; 如果该点位于线段的两点之间，那么距离就是您的点与您刚才find的点（即线A和线B的交点）之间的距离; 如果该点不在线段的两点之间，则需要获得点与线段两端较近的距离; 这可以通过取点与线段的两点之间的平方距离（以避开平方根）来容易地完成; 取其近者，取其中一个的平方根。

Answer 13

这里是Grumdrig的解决scheme的更完整的拼写。 这个版本也返回最近的点。

 #include "stdio.h" #include "math.h" class Vec2 { public: float _x; float _y; Vec2() { _x = 0; _y = 0; } Vec2( const float x, const float y ) { _x = x; _y = y; } Vec2 operator+( const Vec2 &v ) const { return Vec2( this->_x + v._x, this->_y + v._y ); } Vec2 operator-( const Vec2 &v ) const { return Vec2( this->_x - v._x, this->_y - v._y ); } Vec2 operator*( const float f ) const { return Vec2( this->_x * f, this->_y * f ); } float DistanceToSquared( const Vec2 p ) const { const float dX = p._x - this->_x; const float dY = p._y - this->_y; return dX * dX + dY * dY; } float DistanceTo( const Vec2 p ) const { return sqrt( this->DistanceToSquared( p ) ); } float DotProduct( const Vec2 p ) const { return this->_x * p._x + this->_y * p._y; } }; // return minimum distance between line segment vw and point p, and the closest point on the line segment, q float DistanceFromLineSegmentToPoint( const Vec2 v, const Vec2 w, const Vec2 p, Vec2 * const q ) { const float distSq = v.DistanceToSquared( w ); // ie |wv|^2 ... avoid a sqrt if ( distSq == 0.0 ) { // v == w case (*q) = v; return v.DistanceTo( p ); } // 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 = [(pv) . (wv)] / |wv|^2 const float t = ( p - v ).DotProduct( w - v ) / distSq; if ( t < 0.0 ) { // beyond the v end of the segment (*q) = v; return v.DistanceTo( p ); } else if ( t > 1.0 ) { // beyond the w end of the segment (*q) = w; return w.DistanceTo( p ); } // projection falls on the segment const Vec2 projection = v + ( ( w - v ) * t ); (*q) = projection; return p.DistanceTo( projection ); } float DistanceFromLineSegmentToPoint( float segmentX1, float segmentY1, float segmentX2, float segmentY2, float pX, float pY, float *qX, float *qY ) { Vec2 q; float distance = DistanceFromLineSegmentToPoint( Vec2( segmentX1, segmentY1 ), Vec2( segmentX2, segmentY2 ), Vec2( pX, pY ), &q ); (*qX) = q._x; (*qY) = q._y; return distance; } void TestDistanceFromLineSegmentToPoint( float segmentX1, float segmentY1, float segmentX2, float segmentY2, float pX, float pY ) { float qX; float qY; float d = DistanceFromLineSegmentToPoint( segmentX1, segmentY1, segmentX2, segmentY2, pX, pY, &qX, &qY ); printf( "line segment = ( ( %f, %f ), ( %f, %f ) ), p = ( %f, %f ), distance = %f, q = ( %f, %f )\n", segmentX1, segmentY1, segmentX2, segmentY2, pX, pY, d, qX, qY ); } void TestDistanceFromLineSegmentToPoint() { TestDistanceFromLineSegmentToPoint( 0, 0, 1, 1, 1, 0 ); TestDistanceFromLineSegmentToPoint( 0, 0, 20, 10, 5, 4 ); TestDistanceFromLineSegmentToPoint( 0, 0, 20, 10, 30, 15 ); TestDistanceFromLineSegmentToPoint( 0, 0, 20, 10, -30, 15 ); TestDistanceFromLineSegmentToPoint( 0, 0, 10, 0, 5, 1 ); TestDistanceFromLineSegmentToPoint( 0, 0, 0, 10, 1, 5 ); } 

Answer 14

考虑一下上面对Grumdrig的回答的修改。 很多时候你会发现浮点不精确会导致问题。 我在下面的版本中使用双打，但你可以很容易地更改为浮动。 重要的是它使用一个epsilon来处理“污点”。 另外，你会多次想知道交叉点发生在哪里，或者如果它发生的话。 如果返回的t <0.0或> 1.0，则不发生冲突。 但是，即使没有发生碰撞，很多时候你也想知道段P上最近点的位置，因此我使用qx和qy来返回这个位置。

 double PointSegmentDistanceSquared( double px, double py, double p1x, double p1y, double p2x, double p2y, double& t, double& qx, double& qy) { static const double kMinSegmentLenSquared = 0.00000001; // adjust to suit. If you use float, you'll probably want something like 0.000001f static const double kEpsilon = 1.0E-14; // adjust to suit. If you use floats, you'll probably want something like 1E-7f double dx = p2x - p1x; double dy = p2y - p1y; double dp1x = px - p1x; double dp1y = py - p1y; const double segLenSquared = (dx * dx) + (dy * dy); if (segLenSquared >= -kMinSegmentLenSquared && segLenSquared <= kMinSegmentLenSquared) { // segment is a point. qx = p1x; qy = p1y; t = 0.0; return ((dp1x * dp1x) + (dp1y * dp1y)); } else { // Project a line from p to the segment [p1,p2]. By considering the line // extending the segment, parameterized as p1 + (t * (p2 - p1)), // we find projection of point p onto the line. // It falls where t = [(p - p1) . (p2 - p1)] / |p2 - p1|^2 t = ((dp1x * dx) + (dp1y * dy)) / segLenSquared; if (t < kEpsilon) { // intersects at or to the "left" of first segment vertex (p1x, p1y). If t is approximately 0.0, then // intersection is at p1. If t is less than that, then there is no intersection (ie p is not within // the 'bounds' of the segment) if (t > -kEpsilon) { // intersects at 1st segment vertex t = 0.0; } // set our 'intersection' point to p1. qx = p1x; qy = p1y; // Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if // we were doing PointLineDistanceSquared, then qx would be (p1x + (t * dx)) and qy would be (p1y + (t * dy)). } else if (t > (1.0 - kEpsilon)) { // intersects at or to the "right" of second segment vertex (p2x, p2y). If t is approximately 1.0, then // intersection is at p2. If t is greater than that, then there is no intersection (ie p is not within // the 'bounds' of the segment) if (t < (1.0 + kEpsilon)) { // intersects at 2nd segment vertex t = 1.0; } // set our 'intersection' point to p2. qx = p2x; qy = p2y; // Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if // we were doing PointLineDistanceSquared, then qx would be (p1x + (t * dx)) and qy would be (p1y + (t * dy)). } else { // The projection of the point to the point on the segment that is perpendicular succeeded and the point // is 'within' the bounds of the segment. Set the intersection point as that projected point. qx = p1x + (t * dx); qy = p1y + (t * dy); } // return the squared distance from p to the intersection point. Note that we return the squared distance // as an optimization because many times you just need to compare relative distances and the squared values // works fine for that. If you want the ACTUAL distance, just take the square root of this value. double dpqx = px - qx; double dpqy = py - qy; return ((dpqx * dpqx) + (dpqy * dpqy)); } } 

Answer 15

单线解决scheme使用arctangents：

这个想法是将A移动到（0,0）并顺时针旋转三angular形使C在X轴上，当发生这种情况时， By将是距离。

1. angular度= Atan（Cy-Ay，Cx-Ax）;
2. bangular度= Atan（By-Ay，Bx-Ax）;
3. AB长度= Sqrt（（Bx-Ax）^ 2 +（By-Ay）^ 2）
4. By = Sin（bAngle – aAngle）* ABLength

C＃

 public double Distance(Point a, Point b, Point c) { // normalize points Point cn = new Point(cX - aX, cY - aY); Point bn = new Point(bX - aX, bY - aY); double angle = Math.Atan2(bn.Y, bn.X) - Math.Atan2(cn.Y, cn.X); double abLength = Math.Sqrt(bn.X*bn.X + bn.Y*bn.Y); return Math.Sin(angle)*abLength; } 

一行C＃（将被转换为SQL）

 double distance = Math.Sin(Math.Atan2(bY - aY, bX - aX) - Math.Atan2(cY - aY, cX - aX)) * Math.Sqrt((bX - aX) * (bX - aX) + (bY - aY) * (bY - aY)) 

Answer 16

Grumdrig的C ++ / JavaScript实现对我非常有用，所以我提供了一个我正在使用的Python直接端口。 完整的代码在这里 。

 class Point(object): def __init__(self, x, y): self.x = float(x) self.y = float(y) def square(x): return x * x def distance_squared(v, w): return square(vx - wx) + square(vy - wy) def distance_point_segment_squared(p, v, w): # Segment length squared, |wv|^2 d2 = distance_squared(v, w) if d2 == 0: # v == w, return distance to v return distance_squared(p, v) # 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 = [(pv) . (wv)] / |wv|^2 t = ((px - vx) * (wx - vx) + (py - vy) * (wy - vy)) / d2; if t < 0: # Beyond v end of the segment return distance_squared(p, v) elif t > 1.0: # Beyond w end of the segment return distance_squared(p, w) else: # Projection falls on the segment. proj = Point(vx + t * (wx - vx), vy + t * (wy - vy)) # print proj.x, proj.y return distance_squared(p, proj) 

Answer 17

Matlab代码，如果他们调用没有参数的函数，则内置“自测”

 function r = distPointToLineSegment( xy0, xy1, xyP ) % r = distPointToLineSegment( xy0, xy1, xyP ) if( nargin < 3 ) selfTest(); r=0; else vx = xy0(1)-xyP(1); vy = xy0(2)-xyP(2); ux = xy1(1)-xy0(1); uy = xy1(2)-xy0(2); lenSqr= (ux*ux+uy*uy); detP= -vx*ux + -vy*uy; if( detP < 0 ) r = norm(xy0-xyP,2); elseif( detP > lenSqr ) r = norm(xy1-xyP,2); else r = abs(ux*vy-uy*vx)/sqrt(lenSqr); end end function selfTest() %#ok<*NASGU> disp(['invalid args, distPointToLineSegment running (recursive) self-test...']); ptA = [1;1]; ptB = [-1;-1]; ptC = [1/2;1/2]; % on the line ptD = [-2;-1.5]; % too far from line segment ptE = [1/2;0]; % should be same as perpendicular distance to line ptF = [1.5;1.5]; % along the AB but outside of the segment distCtoAB = distPointToLineSegment(ptA,ptB,ptC) distDtoAB = distPointToLineSegment(ptA,ptB,ptD) distEtoAB = distPointToLineSegment(ptA,ptB,ptE) distFtoAB = distPointToLineSegment(ptA,ptB,ptF) figure(1); clf; circle = @(x, y, r, c) rectangle('Position', [xr, yr, 2*r, 2*r], ... 'Curvature', [1 1], 'EdgeColor', c); plot([ptA(1) ptB(1)],[ptA(2) ptB(2)],'r-x'); hold on; plot(ptC(1),ptC(2),'b+'); circle(ptC(1),ptC(2), 0.5e-1, 'b'); plot(ptD(1),ptD(2),'g+'); circle(ptD(1),ptD(2), distDtoAB, 'g'); plot(ptE(1),ptE(2),'k+'); circle(ptE(1),ptE(2), distEtoAB, 'k'); plot(ptF(1),ptF(2),'m+'); circle(ptF(1),ptF(2), distFtoAB, 'm'); hold off; axis([-3 3 -3 3]); axis equal; end end 

Answer 18

And now my solution as well…… (Javascript)

It is very fast because I try to avoid any Math.pow functions.

As you can see, at the end of the function I have the distance of the line.

code is from the lib http://www.draw2d.org/graphiti/jsdoc/#!/example

 /** * Static util function to determine is a point(px,py) on the line(x1,y1,x2,y2) * A simple hit test. * * @return {boolean} * @static * @private * @param {Number} coronaWidth the accepted corona for the hit test * @param {Number} X1 x coordinate of the start point of the line * @param {Number} Y1 y coordinate of the start point of the line * @param {Number} X2 x coordinate of the end point of the line * @param {Number} Y2 y coordinate of the end point of the line * @param {Number} px x coordinate of the point to test * @param {Number} py y coordinate of the point to test **/ graphiti.shape.basic.Line.hit= function( coronaWidth, X1, Y1, X2, Y2, px, py) { // Adjust vectors relative to X1,Y1 // X2,Y2 becomes relative vector from X1,Y1 to end of segment X2 -= X1; Y2 -= Y1; // px,py becomes relative vector from X1,Y1 to test point px -= X1; py -= Y1; var dotprod = px * X2 + py * Y2; var projlenSq; if (dotprod <= 0.0) { // px,py is on the side of X1,Y1 away from X2,Y2 // distance to segment is length of px,py vector // "length of its (clipped) projection" is now 0.0 projlenSq = 0.0; } else { // switch to backwards vectors relative to X2,Y2 // X2,Y2 are already the negative of X1,Y1=>X2,Y2 // to get px,py to be the negative of px,py=>X2,Y2 // the dot product of two negated vectors is the same // as the dot product of the two normal vectors px = X2 - px; py = Y2 - py; dotprod = px * X2 + py * Y2; if (dotprod <= 0.0) { // px,py is on the side of X2,Y2 away from X1,Y1 // distance to segment is length of (backwards) px,py vector // "length of its (clipped) projection" is now 0.0 projlenSq = 0.0; } else { // px,py is between X1,Y1 and X2,Y2 // dotprod is the length of the px,py vector // projected on the X2,Y2=>X1,Y1 vector times the // length of the X2,Y2=>X1,Y1 vector projlenSq = dotprod * dotprod / (X2 * X2 + Y2 * Y2); } } // Distance to line is now the length of the relative point // vector minus the length of its projection onto the line // (which is zero if the projection falls outside the range // of the line segment). var lenSq = px * px + py * py - projlenSq; if (lenSq < 0) { lenSq = 0; } return Math.sqrt(lenSq)<coronaWidth; }; 

Answer 19

coded in t-sql

the point is (@px, @py) and the line segment runs from (@ax, @ay) to (@bx, @by)

 create function fn_sqr (@NumberToSquare decimal(18,10)) returns decimal(18,10) as begin declare @Result decimal(18,10) set @Result = @NumberToSquare * @NumberToSquare return @Result end go create function fn_Distance(@ax decimal (18,10) , @ay decimal (18,10), @bx decimal(18,10), @by decimal(18,10)) returns decimal(18,10) as begin declare @Result decimal(18,10) set @Result = (select dbo.fn_sqr(@ax - @bx) + dbo.fn_sqr(@ay - @by) ) return @Result end go create function fn_DistanceToSegmentSquared(@px decimal(18,10), @py decimal(18,10), @ax decimal(18,10), @ay decimal(18,10), @bx decimal(18,10), @by decimal(18,10)) returns decimal(18,10) as begin declare @l2 decimal(18,10) set @l2 = (select dbo.fn_Distance(@ax, @ay, @bx, @by)) if @l2 = 0 return dbo.fn_Distance(@px, @py, @ax, @ay) declare @t decimal(18,10) set @t = ((@px - @ax) * (@bx - @ax) + (@py - @ay) * (@by - @ay)) / @l2 if (@t < 0) return dbo.fn_Distance(@px, @py, @ax, @ay); if (@t > 1) return dbo.fn_Distance(@px, @py, @bx, @by); return dbo.fn_Distance(@px, @py, @ax + @t * (@bx - @ax), @ay + @t * (@by - @ay)) end go create function fn_DistanceToSegment(@px decimal(18,10), @py decimal(18,10), @ax decimal(18,10), @ay decimal(18,10), @bx decimal(18,10), @by decimal(18,10)) returns decimal(18,10) as begin return sqrt(dbo.fn_DistanceToSegmentSquared(@px, @py , @ax , @ay , @bx , @by )) end go --example execution for distance from a point at (6,1) to line segment that runs from (4,2) to (2,1) select dbo.fn_DistanceToSegment(6, 1, 4, 2, 2, 1) --result = 2.2360679775 --example execution for distance from a point at (-3,-2) to line segment that runs from (0,-2) to (-2,1) select dbo.fn_DistanceToSegment(-3, -2, 0, -2, -2, 1) --result = 2.4961508830 --example execution for distance from a point at (0,-2) to line segment that runs from (0,-2) to (-2,1) select dbo.fn_DistanceToSegment(0,-2, 0, -2, -2, 1) --result = 0.0000000000 

Answer 20

Looks like just about everyone else on StackOverflow has contributed an answer (23 answers so far), so here's my contribution for C#. This is mostly based on the answer by M. Katz, which in turn is based on the answer by Grumdrig.

  public struct MyVector { private readonly double _x, _y; // Constructor public MyVector(double x, double y) { _x = x; _y = y; } // Distance from this point to another point, squared private double DistanceSquared(MyVector otherPoint) { double dx = otherPoint._x - this._x; double dy = otherPoint._y - this._y; return dx * dx + dy * dy; } // Find the distance from this point to a line segment (which is not the same as from this // point to anywhere on an infinite line). Also returns the closest point. public double DistanceToLineSegment(MyVector lineSegmentPoint1, MyVector lineSegmentPoint2, out MyVector closestPoint) { return Math.Sqrt(DistanceToLineSegmentSquared(lineSegmentPoint1, lineSegmentPoint2, out closestPoint)); } // Same as above, but avoid using Sqrt(), saves a new nanoseconds in cases where you only want // to compare several distances to find the smallest or largest, but don't need the distance public double DistanceToLineSegmentSquared(MyVector lineSegmentPoint1, MyVector lineSegmentPoint2, out MyVector closestPoint) { // Compute length of line segment (squared) and handle special case of coincident points double segmentLengthSquared = lineSegmentPoint1.DistanceSquared(lineSegmentPoint2); if (segmentLengthSquared < 1E-7f) // Arbitrary "close enough for government work" value { closestPoint = lineSegmentPoint1; return this.DistanceSquared(closestPoint); } // Use the magic formula to compute the "projection" of this point on the infinite line MyVector lineSegment = lineSegmentPoint2 - lineSegmentPoint1; double t = (this - lineSegmentPoint1).DotProduct(lineSegment) / segmentLengthSquared; // Handle the two cases where the projection is not on the line segment, and the case where // the projection is on the segment if (t <= 0) closestPoint = lineSegmentPoint1; else if (t >= 1) closestPoint = lineSegmentPoint2; else closestPoint = lineSegmentPoint1 + (lineSegment * t); return this.DistanceSquared(closestPoint); } public double DotProduct(MyVector otherVector) { return this._x * otherVector._x + this._y * otherVector._y; } public static MyVector operator +(MyVector leftVector, MyVector rightVector) { return new MyVector(leftVector._x + rightVector._x, leftVector._y + rightVector._y); } public static MyVector operator -(MyVector leftVector, MyVector rightVector) { return new MyVector(leftVector._x - rightVector._x, leftVector._y - rightVector._y); } public static MyVector operator *(MyVector aVector, double aScalar) { return new MyVector(aVector._x * aScalar, aVector._y * aScalar); } // Added using ReSharper due to CodeAnalysis nagging public bool Equals(MyVector other) { return _x.Equals(other._x) && _y.Equals(other._y); } public override bool Equals(object obj) { if (ReferenceEquals(null, obj)) return false; return obj is MyVector && Equals((MyVector) obj); } public override int GetHashCode() { unchecked { return (_x.GetHashCode()*397) ^ _y.GetHashCode(); } } public static bool operator ==(MyVector left, MyVector right) { return left.Equals(right); } public static bool operator !=(MyVector left, MyVector right) { return !left.Equals(right); } } 

And here's a little test program.

  public static class JustTesting { public static void Main() { Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); for (int i = 0; i < 10000000; i++) { TestIt(1, 0, 0, 0, 1, 1, 0.70710678118654757); TestIt(5, 4, 0, 0, 20, 10, 1.3416407864998738); TestIt(30, 15, 0, 0, 20, 10, 11.180339887498949); TestIt(-30, 15, 0, 0, 20, 10, 33.541019662496844); TestIt(5, 1, 0, 0, 10, 0, 1.0); TestIt(1, 5, 0, 0, 0, 10, 1.0); } stopwatch.Stop(); TimeSpan timeSpan = stopwatch.Elapsed; } private static void TestIt(float aPointX, float aPointY, float lineSegmentPoint1X, float lineSegmentPoint1Y, float lineSegmentPoint2X, float lineSegmentPoint2Y, double expectedAnswer) { // Katz double d1 = DistanceFromPointToLineSegment(new MyVector(aPointX, aPointY), new MyVector(lineSegmentPoint1X, lineSegmentPoint1Y), new MyVector(lineSegmentPoint2X, lineSegmentPoint2Y)); Debug.Assert(d1 == expectedAnswer); /* // Katz using squared distance double d2 = DistanceFromPointToLineSegmentSquared(new MyVector(aPointX, aPointY), new MyVector(lineSegmentPoint1X, lineSegmentPoint1Y), new MyVector(lineSegmentPoint2X, lineSegmentPoint2Y)); Debug.Assert(Math.Abs(d2 - expectedAnswer * expectedAnswer) < 1E-7f); */ /* // Matti (optimized) double d3 = FloatVector.DistanceToLineSegment(new PointF(aPointX, aPointY), new PointF(lineSegmentPoint1X, lineSegmentPoint1Y), new PointF(lineSegmentPoint2X, lineSegmentPoint2Y)); Debug.Assert(Math.Abs(d3 - expectedAnswer) < 1E-7f); */ } private static double DistanceFromPointToLineSegment(MyVector aPoint, MyVector lineSegmentPoint1, MyVector lineSegmentPoint2) { MyVector closestPoint; // Not used return aPoint.DistanceToLineSegment(lineSegmentPoint1, lineSegmentPoint2, out closestPoint); } private static double DistanceFromPointToLineSegmentSquared(MyVector aPoint, MyVector lineSegmentPoint1, MyVector lineSegmentPoint2) { MyVector closestPoint; // Not used return aPoint.DistanceToLineSegmentSquared(lineSegmentPoint1, lineSegmentPoint2, out closestPoint); } } 

As you can see, I tried to measure the difference between using the version that avoids the Sqrt() method and the normal version. My tests indicate you can maybe save about 2.5%, but I'm not even sure of that – the variations within the various test runs were of the same order of magnitude. I also tried measuring the version posted by Matti (plus an obvious optimization), and that version seems to be about 4% slower than the version based on Katz/Grumdrig code.

Edit: Incidentally, I've also tried measuring a method that finds the distance to an infinite line (not a line segment) using a cross product (and a Sqrt()), and it's about 32% faster.

Answer 21

Here is devnullicus's C++ version converted to C#. For my implementation I needed to know the point of intersection and found his solution to work well.

 public static bool PointSegmentDistanceSquared(PointF point, PointF lineStart, PointF lineEnd, out double distance, out PointF intersectPoint) { const double kMinSegmentLenSquared = 0.00000001; // adjust to suit. If you use float, you'll probably want something like 0.000001f const double kEpsilon = 1.0E-14; // adjust to suit. If you use floats, you'll probably want something like 1E-7f double dX = lineEnd.X - lineStart.X; double dY = lineEnd.Y - lineStart.Y; double dp1X = point.X - lineStart.X; double dp1Y = point.Y - lineStart.Y; double segLenSquared = (dX * dX) + (dY * dY); double t = 0.0; if (segLenSquared >= -kMinSegmentLenSquared && segLenSquared <= kMinSegmentLenSquared) { // segment is a point. intersectPoint = lineStart; t = 0.0; distance = ((dp1X * dp1X) + (dp1Y * dp1Y)); } else { // Project a line from p to the segment [p1,p2]. By considering the line // extending the segment, parameterized as p1 + (t * (p2 - p1)), // we find projection of point p onto the line. // It falls where t = [(p - p1) . (p2 - p1)] / |p2 - p1|^2 t = ((dp1X * dX) + (dp1Y * dY)) / segLenSquared; if (t < kEpsilon) { // intersects at or to the "left" of first segment vertex (lineStart.X, lineStart.Y). If t is approximately 0.0, then // intersection is at p1. If t is less than that, then there is no intersection (ie p is not within // the 'bounds' of the segment) if (t > -kEpsilon) { // intersects at 1st segment vertex t = 0.0; } // set our 'intersection' point to p1. intersectPoint = lineStart; // Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if // we were doing PointLineDistanceSquared, then intersectPoint.X would be (lineStart.X + (t * dx)) and intersectPoint.Y would be (lineStart.Y + (t * dy)). } else if (t > (1.0 - kEpsilon)) { // intersects at or to the "right" of second segment vertex (lineEnd.X, lineEnd.Y). If t is approximately 1.0, then // intersection is at p2. If t is greater than that, then there is no intersection (ie p is not within // the 'bounds' of the segment) if (t < (1.0 + kEpsilon)) { // intersects at 2nd segment vertex t = 1.0; } // set our 'intersection' point to p2. intersectPoint = lineEnd; // Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if // we were doing PointLineDistanceSquared, then intersectPoint.X would be (lineStart.X + (t * dx)) and intersectPoint.Y would be (lineStart.Y + (t * dy)). } else { // The projection of the point to the point on the segment that is perpendicular succeeded and the point // is 'within' the bounds of the segment. Set the intersection point as that projected point. intersectPoint = new PointF((float)(lineStart.X + (t * dX)), (float)(lineStart.Y + (t * dY))); } // return the squared distance from p to the intersection point. Note that we return the squared distance // as an optimization because many times you just need to compare relative distances and the squared values // works fine for that. If you want the ACTUAL distance, just take the square root of this value. double dpqX = point.X - intersectPoint.X; double dpqY = point.Y - intersectPoint.Y; distance = ((dpqX * dpqX) + (dpqY * dpqY)); } return true; } 

Answer 22

see the Matlab GEOMETRY toolbox in the following website: http://people.sc.fsu.edu/~jburkardt/m_src/geometry/geometry.html

ctrl+f and type "segment" to find line segment related functions. the functions "segment_point_dist_2d.m" and "segment_point_dist_3d.m" are what you need.

The GEOMETRY codes are available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Answer 23

Here is same thing as the C++ answer but ported to pascal. The order of the point parameter has changed to suit my code but is the same thing.

 function Dot(const p1, p2: PointF): double; begin Result := p1.x * p2.x + p1.y * p2.y; end; function SubPoint(const p1, p2: PointF): PointF; begin result.x := p1.x - p2.x; result.y := p1.y - p2.y; end; function ShortestDistance2(const p,v,w : PointF) : double; var l2,t : double; projection,tt: PointF; begin // Return minimum distance between line segment vw and point p //l2 := length_squared(v, w); // ie |wv|^2 - avoid a sqrt l2 := Distance(v,w); l2 := MPower(l2,2); if (l2 = 0.0) then begin result:= Distance(p, v); // v == w case exit; end; // 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 = [(pv) . (wv)] / |wv|^2 t := Dot(SubPoint(p,v),SubPoint(w,v)) / l2; if (t < 0.0) then begin result := Distance(p, v); // Beyond the 'v' end of the segment exit; end else if (t > 1.0) then begin result := Distance(p, w); // Beyond the 'w' end of the segment exit; end; //projection := v + t * (w - v); // Projection falls on the segment tt.x := vx + t * (wx - vx); tt.y := vy + t * (wy - vy); result := Distance(p, tt); end; 

Answer 24

AutoHotkeys version based on Joshua's Javascript:

 plDist(x, y, x1, y1, x2, y2) { A:= x - x1 B:= y - y1 C:= x2 - x1 D:= y2 - y1 dot:= A*C + B*D sqLen:= C*C + D*D param:= dot / sqLen if (param < 0 || ((x1 = x2) && (y1 = y2))) { xx:= x1 yy:= y1 } else if (param > 1) { xx:= x2 yy:= y2 } else { xx:= x1 + param*C yy:= y1 + param*D } dx:= x - xx dy:= y - yy return sqrt(dx*dx + dy*dy) } 

Answer 25

Didn't see a Java implementation here, so I translated the Javascript function from the accepted answer to Java code:

 static double sqr(double x) { return x * x; } static double dist2(DoublePoint v, DoublePoint w) { return sqr(vx - wx) + sqr(vy - wy); } static double distToSegmentSquared(DoublePoint p, DoublePoint v, DoublePoint w) { double l2 = dist2(v, w); if (l2 == 0) return dist2(p, v); double t = ((px - vx) * (wx - vx) + (py - vy) * (wy - vy)) / l2; if (t < 0) return dist2(p, v); if (t > 1) return dist2(p, w); return dist2(p, new DoublePoint( vx + t * (wx - vx), vy + t * (wy - vy) )); } static double distToSegment(DoublePoint p, DoublePoint v, DoublePoint w) { return Math.sqrt(distToSegmentSquared(p, v, w)); } static class DoublePoint { public double x; public double y; public DoublePoint(double x, double y) { this.x = x; this.y = y; } } 

Answer 26

WPF version:

 public class LineSegment { private readonly Vector _offset; private readonly Vector _vector; public LineSegment(Point start, Point end) { _offset = (Vector)start; _vector = (Vector)(end - _offset); } public double DistanceTo(Point pt) { var v = (Vector)pt - _offset; // first, find a projection point on the segment in parametric form (0..1) var p = (v * _vector) / _vector.LengthSquared; // and limit it so it lays inside the segment p = Math.Min(Math.Max(p, 0), 1); // now, find the distance from that point to our point return (_vector * p - v).Length; } } 

Answer 27

C＃

Adapted from @Grumdrig

 public static double MinimumDistanceToLineSegment(this Point p, Line line) { var v = line.StartPoint; var w = line.EndPoint; double lengthSquared = DistanceSquared(v, w); if (lengthSquared == 0.0) return Distance(p, v); double t = Math.Max(0, Math.Min(1, DotProduct(p - v, w - v) / lengthSquared)); var projection = v + t * (w - v); return Distance(p, projection); } public static double Distance(Point a, Point b) { return Math.Sqrt(DistanceSquared(a, b)); } public static double DistanceSquared(Point a, Point b) { var d = a - b; return DotProduct(d, d); } public static double DotProduct(Point a, Point b) { return (aX * bX) + (aY * bY); } 

Answer 28

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.

Answer 29

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 = ax - bx; var dy = ay - by; return Math.sqrt(dx*dx + dy*dy); } function Segment(a, b) { var ab = { x: bx - ax, y: by - ay }; var length = distance(a, b); function cross(c) { return ab.x * (cy-ay) - ab.y * (cx-ax); }; this.distanceFrom = function(c) { return Math.min(distance(a,c), distance(b,c), Math.abs(cross(c) / length)); }; } 

Answer 30

The above function is not working on vertical lines. Here is a function that is working fine! Line with points p1, p2. and CheckPoint is p;

 public float DistanceOfPointToLine2(PointF p1, PointF p2, PointF p) { // (y1-y2)x + (x2-x1)y + (x1y2-x2y1) //d(P,L) = -------------------------------- // sqrt( (x2-x1)pow2 + (y2-y1)pow2 ) double ch = (p1.Y - p2.Y) * pX + (p2.X - p1.X) * pY + (p1.X * p2.Y - p2.X * p1.Y); double del = Math.Sqrt(Math.Pow(p2.X - p1.X, 2) + Math.Pow(p2.Y - p1.Y, 2)); double d = ch / del; return (float)d; }