Menor distância entre um ponto e um segmento de linha

Eu preciso de uma function básica para encontrar a menor distância entre um ponto e um segmento de linha. Sinta-se à vontade para escrever a solução em qualquer idioma que desejar; Eu posso traduzi-lo para o que estou usando (Javascript).

EDIT: meu segmento de linha é definido por dois pontos finais. Então, meu segmento de linha AB é definido pelos dois pontos A (x1,y1) e B (x2,y2) . Eu estou tentando encontrar a distância entre este segmento de linha e um ponto C (x3,y3) . Minhas habilidades geométricas estão enferrujadas, então os exemplos que vi são confusos, desculpe admitir.

Eli, o código que você escolheu está incorreto. Um ponto perto da linha em que o segmento se encontra, mas longe de uma extremidade do segmento, seria julgado incorretamente perto do segmento. Atualização: A resposta incorreta mencionada não é mais a aceita.

Aqui está algum código correto, em C ++. Presume-se uma class class vec2 {float x,y;} vetor 2D class vec2 {float x,y;} , essencialmente, com operadores para adicionar, subtrair, dimensionar, etc, e uma function de produto de distância e ponto (ou seja, 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); } 

EDIT: Eu precisava de uma implementação de JavaScript, então aqui está, sem dependencies (ou comentários, mas é uma porta direta do acima). Pontos são representados como objects com os atributos x e 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)); } 

EDIT 2: Eu precisava de uma versão Java, mas mais importante, eu precisava em 3d em vez de 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)); } 

Aqui está o código completo mais simples em JavaScript.

x, y é o seu ponto alvo e x1, y1 para x2, y2 é o seu segmento de linha.

ATUALIZADO: corrija para 0 problema na linha de comprimento dos comentários.

 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); } 

Esta é uma implementação feita para FINITE LINE SEGMENTS, não linhas infinitas como a maioria das outras funções aqui parecem ser (é por isso que eu fiz isso).

Exemplo está aqui .

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; } 

Estes foram feitos a partir disso .

Em F #, a distância do ponto c ao segmento de linha entre a e b é dada por:

 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 

O vetor d aponta de a para b ao longo do segmento de linha. O produto escalar de d/s com ca fornece o parâmetro do ponto de maior aproximação entre a linha infinita e o ponto c . As funções min e max são usadas para fixar este parâmetro no intervalo 0..s modo que o ponto fique entre a e b . Finalmente, o comprimento de a+pc é a distância de c até o ponto mais próximo no segmento de linha.

Exemplo de uso:

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

Na minha pergunta, como calcular a distância 2D mais curta entre um ponto e um segmento de linha em todos os casos em C, C # / .NET 2.0 ou Java? Fui solicitado a colocar uma resposta C # aqui quando encontrei uma: então aqui está, modificada de http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static :

 //Compute the dot product AB . BC 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); } 

Eu estou @SO não para responder, mas fazer perguntas, então eu espero não conseguir milhões de votos por algumas razões, mas construindo críticas. Eu apenas queria (e fui encorajado) a compartilhar as idéias de outras pessoas, já que as soluções neste tópico são ou com alguma linguagem exótica (Fortran, Mathematica) ou marcadas como falhas por alguém. O único útil (por Grumdrig) para mim é escrito com C ++ e ninguém marcou com defeito. Mas está faltando os methods (ponto etc.) que são chamados.

Em Mathematica

Ele usa uma descrição paramétrica do segmento e projeta o ponto na linha definida pelo segmento. Como o parâmetro vai de 0 a 1 no segmento, se a projeção estiver fora desse limite, calculamos a distância até o enpoint correspondente, em vez da linha reta normal ao segmento.

 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*) ] ]; 

Resultado da plotagem:

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

texto alternativo

Plote os pontos mais próximos de uma distância de corte :

texto alternativo

Contour Plot:

insira a descrição da imagem aqui

Para qualquer pessoa interessada, aqui está uma conversão trivial do código Javascript de Joshua para 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); } 

Eu precisava dessa solução para trabalhar com o MKMapPoint então vou compartilhá-la no caso de alguém precisar dela. Apenas algumas pequenas alterações e isso irá retornar a distância em metros:

 - (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)); } 

Ei, eu acabei de escrever isso ontem. Está no Actionscript 3.0, que é basicamente Javascript, embora você não tenha a mesma class 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; } 

Além disso, há uma discussão bastante completa e legível do problema aqui: notejot.com

Não pude resistir a codificá-lo em 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) 

Idem para 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 

Para os preguiçosos, aqui está minha porta Objective-C da solução @ Grumdrig acima:

 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)); } 

Aqui está uma ortografia mais completa da solução de Grumdrig. Esta versão também retorna o próprio ponto mais próximo.

 #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 ); } 

Eu estou supondo que você quer encontrar a menor distância entre o ponto e um segmento de linha; para fazer isso, você precisa encontrar a linha (linha A) que é perpendicular ao seu segmento de linha (linha B) que passa pelo seu ponto, determinar a interseção entre essa linha (linha A) e sua linha que passa pelo seu segmento de linha (linha B) ; se esse ponto estiver entre os dois pontos do seu segmento de linha, então a distância é a distância entre o seu ponto e o ponto que você acabou de encontrar, que é a interseção da linha A e linha B; se o ponto não estiver entre os dois pontos do seu segmento de linha, você precisará obter a distância entre o seu ponto e o mais próximo de duas extremidades do segmento de linha; isso pode ser feito facilmente tomando a distância quadrada (para evitar uma raiz quadrada) entre o ponto e os dois pontos do segmento de linha; o que estiver mais perto, pegue a raiz quadrada daquele.

Considere esta modificação para a resposta de Grumdrig acima. Muitas vezes você descobrirá que a imprecisão de ponto flutuante pode causar problemas. Eu estou usando duplas na versão abaixo, mas você pode facilmente mudar para carros alegóricos. A parte importante é que ele usa um epsilon para lidar com o “slop”. Além disso, muitas vezes você vai querer saber onde a interseção aconteceu, ou se aconteceu. Se o t retornado for <0,0 ou> 1,0, nenhuma colisão ocorreu. No entanto, mesmo se nenhuma colisão ocorreu, muitas vezes você vai querer saber onde é o ponto mais próximo do segmento para P e, portanto, eu uso qx e qy para retornar esse local.

 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)); } } 

Solução de uma linha usando arctangents:

A idéia é mover A para (0, 0) e girar o triângulo no sentido horário para fazer C no eixo X, quando isso acontecer, By será a distância.

  1. um ângulo = Atan (Cy – Ay, Cx – Ax);
  2. b ângulo = Atan (Por – Ay, Bx – Ax);
  3. AB length = Sqrt ((Bx – Ax) ^ 2 + (Por – Ay) ^ 2)
  4. Por = 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; } 

Uma linha C # (para ser convertido em 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)) 

A implementação de C ++ / JavaScript da Grumdrig foi muito útil para mim, por isso forneci uma porta direta do Python que estou usando. O código completo está aqui .

 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) 

Código Matlab, com “autoteste” embutido, se eles chamam a function sem argumentos:

 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 

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) 

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 

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.

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; } 

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.

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) } 

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; } } 

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; } } 

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); } 

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)); }; } 

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; } 

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; 
 %Matlab solution by Tim from Cody function ans=distP2S(x0,y0,x1,y1,x2,y2) % Point is x0,y0 z=complex(x0-x1,y0-y1); complex(x2-x1,y2-y1); abs(z-ans*min(1,max(0,real(z/ans)))); 

A little cleaner solution in JavaScript based on this formula : insira a descrição da imagem aqui

 distToSegment: function (point, linePointA, linePointB){ var x0 = point.X; var y0 = point.Y; var x1 = linePointA.X; var y1 = linePointA.Y; var x2 = linePointB.X; var y2 = linePointB.Y; var Dx = (x2 - x1); var Dy = (y2 - y1); var numerator = Math.abs(Dy*x0 - Dx*y0 - x1*y2 + x2*y1); var denominator = Math.sqrt(Dx*Dx + Dy*Dy); if (denominator == 0) { return this.dist2(point, linePointA); } return numerator/denominator; }