La plus courte distance entre un point et un segment de ligne

Eli, le code que vous avez installés sur est incorrect. Un point près de la ligne sur laquelle le segment se trouve, mais de loin l'une des extrémités du segment peut être mal jugé à proximité du segment. mise à Jour: La réponse incorrecte mentionné n'est plus accepté un.

Voici quelques bon code en C++. Il suppose une classe de 2D-vecteur class vec2 {float x,y;}, essentiellement, avec des opérateurs pour ajouter, subract, échelle, etc, et à une distance et point en fonction du produit (c'est à dire 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
  //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: j'avais besoin d'un Javascript de mise en œuvre, si elle est ici, sans dépendances (ou des commentaires, mais c'est un port direct de la ci-dessus). Les Points sont représentés comme des objets avec x et y attributs.

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

EDIT 2: j'ai besoin d'une version de Java, mais le plus important, j'ai besoin d'en 3d au lieu 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));
}

C'est une application faite pour les FINIS des SEGMENTS de LIGNE, pas à l'infini des lignes comme la plupart des autres fonctions semblent être (c'est pourquoi j'ai fait cela).

La mise en œuvre de la théorie de Paul Bourke.

Python:

def dist(x1, y1, x2, y2, x3, y3): # x3,y3 is the point
    px = x2-x1
    py = y2-y1

    norm = px*px + py*py

    u =  ((x3 - x1) * px + (y3 - y1) * py) / float(norm)

    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 = (dx*dx + dy*dy)**.5

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

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;

    }

En F#, la distance entre le point c pour le segment de ligne entre a et b est donnée par:

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

Le vecteur d points de a à b le long du segment de ligne. Le produit scalaire de d/s avec c-a donne le paramètre du point de plus grande approche entre l'infini de la ligne et le point c. Le min et max fonction sont utilisées pour la fixation de ce paramètre pour la gamme 0..s de sorte que le point se trouve entre a et b. Enfin, la longueur de a+p-c est la distance à partir de c de point le plus proche sur le segment de ligne.

Exemple d'utilisation:

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

Pour toute personne intéressée, voici une simple conversion de Josué du code Javascript à Objective-C:

- (double)distanceToPoint:(CGPoint)p fromLineSegmentBetween:(CGPoint)l1 and:(CGPoint)l2
{
double A = p.x - l1.x;
double B = p.y - 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 = p.x - xx;
double dy = p.y - yy;
return sqrtf(dx * dx + dy * dy);
}

J'avais besoin de cette solution fonctionne avec MKMapPoint donc je vais le partager au cas où quelqu'un d'autre en a besoin. Juste quelques changements mineurs et ce sera le retour de la distance en mètres :

- (double)distanceToPoint:(MKMapPoint)p fromLineSegmentBetween:(MKMapPoint)l1 and:(MKMapPoint)l2
{
double A = p.x - l1.x;
double B = p.y - 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));
}

Pour les paresseux, voici mon Objective-C port de @Grumdrig la solution ci-dessus:

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

Ici est une information plus complète sur l'orthographe de Grumdrig de la solution. Cette version renvoie également le point le plus proche de lui-même.

#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 ); //i.e. |w-v|^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 = [(p-v) . (w-v)] /|w-v|^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 );
}

Une solution en ligne à l'aide de arctangents:

L'idée est de déplacer Un à (0, 0) et faire pivoter le triangle des aiguilles d'une montre pour faire C laïcs sur l'axe X,
lorsque cela arrive, Par sera la distance.

1. un angle = Atan(Cy - Ay, le Cx - Ax);
2. angle b = Atan(Par - Ay, Bx - Ax);
3. Longueur AB = Sqrt( (Bx - Ax)^2 + (By - Ay)^2 )
4. Par un = Sin ( bracelet - aAngle) * ABLength

C#

public double Distance(Point a, Point b, Point c)
{
//normalize points
Point cn = new Point(c.X - a.X, c.Y - a.Y);
Point bn = new Point(b.X - a.X, b.Y - a.Y);
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;
}

Une ligne de C# (être converti en SQL)

double distance = Math.Sin(Math.Atan2(b.Y - a.Y, b.X - a.X) - Math.Atan2(c.Y - a.Y, c.X - a.X)) * Math.Sqrt((b.X - a.X) * (b.X - a.X) + (b.Y - a.Y) * (b.Y - a.Y))

Grumdrig du C++/JavaScript mise en œuvre a été très utile pour moi, j'ai donc fourni un Python direct port que j'utilise. Le code complet est ici.

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(v.x - w.x) + square(v.y - w.y)
def distance_point_segment_squared(p, v, w):
# Segment length squared, |w-v|^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 = [(p-v) . (w-v)] /|w-v|^2
t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) /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(v.x + t * (w.x - v.x), v.y + t * (w.y - v.y))
# print proj.x, proj.y
return distance_squared(p, proj)

Et maintenant ma solution......
(Javascript)

Il est très rapide, parce que j'essaie d'éviter toute Mathématiques.pow fonctions.

Comme vous pouvez le voir, à la fin de la fonction, j'ai la distance de la ligne.

code de la lib http://www.draw2d.org/graphiti/jsdoc/#!/exemple

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

Ressemble à peu près tous les autres sur StackOverflow a contribué d'une réponse (23 réponses), voici donc ma contribution pour C#. Cela est principalement basé sur la réponse de M. Katz, qui à son tour est basé sur la réponse par 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);
}
}

Et voici un petit programme de test.

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

Comme vous pouvez le voir, j'ai essayé de mesurer la différence entre l'utilisation de la version qui évite la Sqrt() la méthode et la version normale. Mes tests indiquent que vous pouvez peut-être économiser environ 2,5%, mais je ne suis même pas sûr de qui - les variations dans les différentes séries de tests ont été du même ordre de grandeur. J'ai aussi essayé de mesurer la version posté par Matti (en plus d'une optimisation évidente), et cette version semble être d'environ 4% plus lente que la version basée sur Katz/Grumdrig code.

Edit: d'ailleurs, j'ai aussi essayé de la mesure d'une méthode qui trouve la distance à une ligne infinie (pas un segment de ligne) à l'aide d'un produit croisé (et un Sqrt()), et il est d'environ 32% plus rapide.

Ici, c'est l'utilisation de Swift

    /* Distance from a point (p1) to line l1 l2 */
func distanceFromPoint(p: CGPoint, toLineSegment l1: CGPoint, and l2: CGPoint) -> CGFloat {
let A = p.x - l1.x
let B = p.y - l1.y
let C = l2.x - l1.x
let D = l2.y - l1.y
let dot = A * C + B * D
let len_sq = C * C + D * D
let param = dot /len_sq
var xx, yy: CGFloat
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
}
let dx = p.x - xx
let dy = p.y - yy
return sqrt(dx * dx + dy * dy)
}

AutoHotkeys version basée sur Joshua 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)
}

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

Voici le code que j'ai fini par écrire. Ce code suppose qu'un point est défini dans le formulaire de {x:5, y:7}. Notez que ce n'est pas l'absolu moyen le plus efficace, mais c'est le plus simple et le plus facile à comprendre le code que je pouvais venir.

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

Ici est la même chose que le C++ répondre, mais porté à pascal. L'ordre du point de paramètre a changé pour l'adapter à mon code, mais c'est la même chose.

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);  //i.e. |w-v|^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 = [(p-v) . (w-v)] /|w-v|^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 := v.x + t * (w.x - v.x);
tt.y := v.y + t * (w.y - v.y);
result := Distance(p, tt);
end;

Un peu plus propre solution en JavaScript basé sur ce formule:

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

Cet algorithme est basé sur la recherche de l'intersection entre la ligne spécifiée et la orthogonale de la ligne, qui contient le point spécifié, et le calcul de sa distance. Dans le cas d'un segment de ligne, nous devons vérifier si l'intersection est entre les points du segment de ligne, si ce n'est pas le cas, alors la distance minimale entre le point et l'un des points de fin de la ligne. C'est un C# de mise en œuvre.

Double Distance(Point a, Point b)
{
double xdiff = a.X - b.X, ydiff = a.Y - b.Y;
return Math.Sqrt((long)xdiff * xdiff + (long)ydiff * ydiff);
}
Boolean IsBetween(double x, double a, double b)
{
return ((a <= b && x >= a && x <= b) || (a > b && x <= a && x >= b));
}
Double GetDistance(Point pt, Point pt1, Point pt2, out Point intersection)
{
Double a, x, y, R;
if (pt1.X != pt2.X) {
a = (double)(pt2.Y - pt1.Y) /(pt2.X - pt1.X);
x = (a * (pt.Y - pt1.Y) + a * a * pt1.X + pt.X) /(a * a + 1);
y = a * x + pt1.Y - a * pt1.X; }
else { x = pt1.X;  y = pt.Y; }
if (IsBetween(x, pt1.X, pt2.X) && IsBetween(y, pt1.Y, pt2.Y)) {
intersection = new Point((int)x, (int)y);
R = Distance(intersection, pt); }
else {
double d1 = Distance(pt, pt1), d2 = Distance(pt, pt2);
if (d1 < d2) { intersection = pt1; R = d1; }
else { intersection = pt2; R = d2; }}
return R;
}

J'ai fait un interactive Desmos graphique pour montrer comment y parvenir:

https://www.desmos.com/calculator/kswrm8ddum

Le point rouge est Un, le point vert est B et le point C est le bleu.
Vous pouvez faire glisser les points dans le graphique pour voir les changements.
Sur la gauche, la valeur " s " est le paramètre de la ligne de segment (c'est à dire s = 0 signifie que le point A, et s = 1 signifie que le point B).
La valeur de " d " est la distance entre le troisième point de la droite passant par A et B.

EDIT:

Amusant petit aperçu: les coordonnées (s, d) est la coordonnée du troisième point C dans le système de coordonnées où AB est l'unité de l'axe des x, et l'unité de l'axe y est perpendiculaire à AB.

la accepté de répondre ne fonctionne pas
(par exemple, la distance entre 0,0 et (-10,2,10,2) doit être de 2).

voici le code qui fonctionne:

   def dist2line2(x,y,line):
x1,y1,x2,y2=line
vx = x1 - x
vy = y1 - y
ux = x2-x1
uy = y2-y1
length = ux * ux + uy * uy
det = (-vx * ux) + (-vy * uy) #//if this is < 0 or > length then its outside the line segment
if det < 0:
return (x1 - x)**2 + (y1 - y)**2
if det > length:
return (x2 - x)**2 + (y2 - y)**2
det = ux * vy - uy * vx
return det**2 /length
def dist2line(x,y,line): return math.sqrt(dist2line2(x,y,line))

Viens de tomber sur ce et j'ai pensé ajouter un Lua mise en œuvre. Il suppose que les points sont donnés sous forme de tableaux {x=xVal, y=yVal} et la ligne ou un segment est donnée par un tableau contenant deux points (voir exemple ci-dessous):

function distance( P1, P2 )
return math.sqrt((P1.x-P2.x)^2 + (P1.y-P2.y)^2)
end
-- Returns false if the point lies beyond the reaches of the segment
function distPointToSegment( line, P )
if line[1].x == line[2].x and line[1].y == line[2].y then
print("Error: Not a line!")
return false
end
local d = distance( line[1], line[2] )
local t = ((P.x - line[1].x)*(line[2].x - line[1].x) + (P.y - line[1].y)*(line[2].y - line[1].y))/(d^2)
local projection = {}
projection.x = line[1].x + t*(line[2].x-line[1].x)
projection.y = line[1].y + t*(line[2].y-line[1].y)
if t >= 0 and t <= 1 then   -- within line segment?
return distance( projection, {x=P.x, y=P.y} )
else
return false
end
end
-- Returns value even if point is further down the line (outside segment)
function distPointToLine( line, P )
if line[1].x == line[2].x and line[1].y == line[2].y then
print("Error: Not a line!")
return false
end
local d = distance( line[1], line[2] )
local t = ((P.x - line[1].x)*(line[2].x - line[1].x) + (P.y - line[1].y)*(line[2].y - line[1].y))/(d^2)
local projection = {}
projection.x = line[1].x + t*(line[2].x-line[1].x)
projection.y = line[1].y + t*(line[2].y-line[1].y)
return distance( projection, {x=P.x, y=P.y} )
end

Exemple d'utilisation:

local P1 = {x = 0, y = 0}
local P2 = {x = 10, y = 10}
local line = { P1, P2 }
local P3 = {x = 7, y = 15}
print(distPointToLine( line, P3 ))  -- prints 5.6568542494924
print(distPointToSegment( line, P3 )) -- prints false

Même que cette réponse, sauf dans Visual Basic. Le rend utilisable comme une Fonction Définie par l'Utilisateur dans Microsoft Excel et VBA/macros.

La fonction renvoie la plus petite distance à partir du point (x,y) pour le segment défini par (x1,y1) et (x2,y2)

Function DistanceToSegment(x As Double, y As Double, x1 As Double, y1 As Double, x2 As Double, y2 As Double)
Dim A As Double
A = x - x1
Dim B As Double
B = y - y1
Dim C  As Double
C = x2 - x1
Dim D As Double
D = y2 - y1
Dim dot As Double
dot = A * C + B * D
Dim len_sq As Double
len_sq = C * C + D * D
Dim param As Double
param = -1
If (len_sq <> 0) Then
param = dot /len_sq
End If
Dim xx As Double
Dim yy As Double
If (param < 0) Then
xx = x1
yy = y1
ElseIf (param > 1) Then
xx = x2
yy = y2
Else
xx = x1 + param * C
yy = y1 + param * D
End If
Dim dx As Double
dx = x - xx
Dim dy As Double
dy = y - yy
DistanceToSegment = Math.Sqr(dx * dx + dy * dy)
End Function

Cette réponse est fondée sur la accepté de répondre às'JavaScript solution.
Il est principalement formaté plus agréable, avec en plus des noms de fonction, et des cours plus courts syntaxe de la fonction parce que c'est dans l'ES6 + CoffeeScript.

Version JavaScript (ES6)

distanceSquared = (v, w)=> Math.pow(v.x - w.x, 2) + Math.pow(v.y - w.y, 2);
distance = (v, w)=> Math.sqrt(distanceSquared(v, w));
distanceToLineSegmentSquared = (p, v, w)=> {
l2 = distanceSquared(v, w);
if (l2 === 0) {
return distanceSquared(p, v);
}
t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) /l2;
t = Math.max(0, Math.min(1, t));
return distanceSquared(p, {
x: v.x + t * (w.x - v.x),
y: v.y + t * (w.y - v.y)
});
}
distanceToLineSegment = (p, v, w)=> {
return Math.sqrt(distanceToLineSegmentSquared(p, v));
}

CoffeeScript version

distanceSquared = (v, w)-> (v.x - w.x) ** 2 + (v.y - w.y) ** 2
distance = (v, w)-> Math.sqrt(distanceSquared(v, w))
distanceToLineSegmentSquared = (p, v, w)->
l2 = distanceSquared(v, w)
return distanceSquared(p, v) if l2 is 0
t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) /l2
t = Math.max(0, Math.min(1, t))
distanceSquared(p, {
x: v.x + t * (w.x - v.x)
y: v.y + t * (w.y - v.y)
})
distanceToLineSegment = (p, v, w)->
Math.sqrt(distanceToLineSegmentSquared(p, v, w))

En javascript à l'aide de la Géométrie:

var a = { x:20, y:20};//start segment    
var b = { x:40, y:30};//end segment   
var c = { x:37, y:14};//point   
//magnitude from a to c    
var ac = Math.sqrt( Math.pow( ( a.x - c.x ), 2 ) + Math.pow( ( a.y - c.y ), 2) );    
//magnitude from b to c   
var bc = Math.sqrt( Math.pow( ( b.x - c.x ), 2 ) + Math.pow( ( b.y - c.y ), 2 ) );    
//magnitude from a to b (base)     
var ab = Math.sqrt( Math.pow( ( a.x - b.x ), 2 ) + Math.pow( ( a.y - b.y ), 2 ) );    
//perimeter of triangle     
var p = ac + bc + ab;    
//area of the triangle    
var area = Math.sqrt( p/2 * ( p/2 - ac) * ( p/2 - bc ) * ( p/2 - ab ) );    
//height of the triangle = distance    
var h = ( area * 2 ) /ab;    
console.log ("height: " + h);

Eigen C++ Version 3D segment de ligne et de point

//Return minimum distance between line segment: head--->tail and point
double MinimumDistance(Eigen::Vector3d head, Eigen::Vector3d tail,Eigen::Vector3d point)
{
double l2 = std::pow((head - tail).norm(),2);
if(l2 ==0.0) return (head - point).norm();//head == tail case
//Consider the line extending the segment, parameterized as head + t (tail - point).
//We find projection of point onto the line.
//It falls where t = [(point-head) . (tail-head)] /|tail-head|^2
//We clamp t from [0,1] to handle points outside the segment head--->tail.
double t = max(0,min(1,(point-head).dot(tail-head)/l2));
Eigen::Vector3d projection = head + t*(tail-head);
return (point - projection).norm();
}

Ici est celui basé sur le vecteur de mathématiques; cette solution fonctionnera aussi pour les dimensions supérieures et également un rapport sur les interection point (sur le segment de ligne).

def dist(x1,y1,x2,y2,px,py):
a = np.array([[x1,y1]]).T
b = np.array([[x2,y2]]).T
x = np.array([[px,py]]).T
tp = (np.dot(x.T, b) - np.dot(a.T, b)) /np.dot(b.T, b)
tp = tp[0][0]
tmp = x - (a + tp*b)
d = np.sqrt(np.dot(tmp.T,tmp)[0][0])
return d, a+tp*b
x1,y1=2.,2.
x2,y2=5.,5.
px,py=4.,1.
d, inters = dist(x1,y1, x2,y2, px,py)
print (d)
print (inters)

Résultat est

2.1213203435596424
[[2.5]
[2.5]]

Le calcul est expliqué ici

https://brilliant.org/wiki/distance-between-point-and-line/