Kürzeste Entfernung zwischen einem Punkt und einem Linienabschnitt

Question

Ich benötige eine Grundfunktion, um die kürzeste Entfernung zwischen einem Punkt und einem Linienabschnitt zu finden. Fühlen Sie sich frei, die Lösung in jeder beliebigen Sprache zu schreiben; ich kann sie in das übersetzen, was ich benutze (Javascript).

BEARBEITEN: Mein Linienabschnitt wird durch zwei Endpunkte definiert. Also ist mein Linienabschnitt AB definiert durch die beiden Punkte A (x1, y1) und B (x2, y2). Ich versuche die Entfernung zwischen diesem Linienabschnitt und einem Punkt C (x3, y3) zu finden. Meine geometrischen Fähigkeiten sind eingerostet, daher sind die Beispiele, die ich gesehen habe, verwirrend, das muss ich zugeben.

Answer 1

In Mathematica

Es verwendet eine parametrische Beschreibung des Segments und projiziert den Punkt auf die von diesem definierte Linie. Wenn der Parameter von 0 bis 1 im Segment geht, wird, wenn die Projektion außerhalb dieser Grenzen liegt, anstelle der Geraden normal zum Segment der Abstand zum entsprechenden Endpunkt berechnet.

Clear["Global`*"];
 distance[{start_, end_}, pt_] := 
   Module[{param},
   param = ((pt - start).(end - start))/Norm[end - start]^2; (*Parameter. Das "."
                                                       hier bedeutet Vektorprodukt*)

   Which[
    param < 0, EuclideanDistance[start, pt],                 (*Wenn außerhalb der Grenzen*)
    param > 1, EuclideanDistance[end, pt],
    True, EuclideanDistance[pt, start + param (end - start)] (*Normaler Abstand*)
    ]
   ];  

Plotten des Ergebnisses:

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

Plotten Sie die Punkte näher als einen Abschneideabstand:

Konturplot:

Answer 2

In F#, die Entfernung von Punkt c zum Linienabschnitt zwischen a und b ist wie folgt:

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

Der Vektor d zeigt von a nach b entlang des Linienabschnitts. Das Skalarprodukt von d/s mit c-a gibt den Parameter des Punktes des nächsten Ansatzes zwischen der unendlichen Linie und dem Punkt c an. Die Funktionen min und max werden verwendet, um diesen Parameter auf den Bereich 0..s zu begrenzen, damit der Punkt zwischen a und b liegt. Schließlich ist die Länge von a+p-c die Entfernung von c zum nächsten Punkt auf dem Linienabschnitt.

Beispiel Verwendung:

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

Answer 3

Hey, ich habe das gestern geschrieben. Es ist in Actionscript 3.0, was im Grunde Javascript ist, obwohl du die gleiche Point-Klasse vielleicht nicht hast.

//st = Anfang des Linienabschnitts
//b = der Linienabschnitt (wie in: st + b = Ende des Linienabschnitts)
//pt = Testpunkt
//Gibt den Abstand vom Punkt zum Linienabschnitt zurück.  
//Hinweis: Der nächstgelegene Punkt auf dem Segment zum Testpunkt ist direkt da, falls wir ihn jemals benötigen
public static function linePointDist( st:Point, b:Point, pt:Point ):Number
{
    var nearestPt:Point; //nächster Punkt auf dem Segment zum Punkt

    var keyDot:Number = dot( b, pt.subtract( st ) ); //Schlüssel-Punktprodukt
    var bLenSq:Number = dot( b, b ); //Segmentlänge im Quadrat

    if( keyDot <= 0 )  //pt ist "hinter" st, verwende st
    {
        nearestPt = st  
    }
    else if( keyDot >= bLenSq ) //pt ist "vor" dem Ende des Segments, verwende Ende (beachte, dass wir hier zwei Quadratwurzeln sparen, weil)
    {
        nearestPt = st.add(b);
    }
    else //pt ist im Inneren des Segments, wiederverwenden keyDot und bLenSq, um Prozent des Segments zu erhalten, um den nächstgelegenen Punkt zu finden
    {
        var keyDotToPctOfB:Number = keyDot/bLenSq; //HINWEIS: Punktprodukt erfolgt quadriert
        var partOfB:Point = new Point( b.x * keyDotToPctOfB, b.y * keyDotToPctOfB );
        nearestPt = st.add(partOfB);
    }

    var dist:Number = (pt.subtract(nearestPt)).length;

    return dist;
}

Außerdem gibt es eine ziemlich vollständige und lesbare Diskussion des Problems hier: notejot.com

Answer 4

Für die Faulen, hier ist mein Objective-C-Port von @Grumdrigs Lösung oben:

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

Answer 5

Eine Lösung in einer Zeile unter Verwendung von Arkustangens:

Die Idee ist, A zu (0, 0) zu verschieben und das Dreieck im Uhrzeigersinn zu drehen, damit C auf der X-Achse liegt. Wenn dies geschieht, wird By der Abstand sein.

1. Winkel a = Atan(Cy - Ay, Cx - Ax);
2. Winkel b = Atan(By - Ay, Bx - Ax);
3. Länge AB = Wurzel( (Bx - Ax)^2 + (By - Ay)^2 )
4. By = Sin ( bWinkel - aWinkel) * ABLength

C#

public double Distanz(Point a, Point b, Point c)
{
    // Punkte normalisieren
    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 winkel = Math.Atan2(bn.Y, bn.X) - Math.Atan2(cn.Y, cn.X);
    double abLänge = Math.Sqrt(bn.X*bn.X + bn.Y*bn.Y);

    return Math.Sin(winkel)*abLänge;
}

Einzeiliges C# (umgewandelt in SQL)

double distanz = 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))