Kürzester Abstand zwischen einem Punkt und einem Liniensegment

358

Ich brauche eine Grundfunktion, um den kürzesten Abstand zwischen einem Punkt und einem Liniensegment zu finden. Sie können die Lösung auch in einer beliebigen Sprache schreiben. Ich kann es in das übersetzen, was ich benutze (Javascript).

BEARBEITEN: Mein Liniensegment wird durch zwei Endpunkte definiert. Mein Liniensegment ABwird also durch die beiden Punkte A (x1,y1)und definiert B (x2,y2). Ich versuche, den Abstand zwischen diesem Liniensegment und einem Punkt zu ermitteln C (x3,y3). Meine Geometriekenntnisse sind verrostet, daher sind die Beispiele, die ich gesehen habe, verwirrend. Es tut mir leid, das zuzugeben.

Eli Courtwright
quelle
Ich weiß nicht, wie Sie Linien und Punkte darstellen, aber hier finden Sie die gesamte Mathematik, die Sie für den Einstieg benötigen. Sollte nicht zu schwer sein, um herauszufinden, was Sie tun müssen.
Mandaleeka
4
@ArthurKalliokoski: Dieser Link ist tot, aber ich habe eine Kopie gefunden: paulbourke.net/geometry/pointline
Gunther Struyf
11
@ GuntherStruyf: Dieser Link ist auch tot, aber dieser ähnliche Link funktioniert: paulbourke.net/geometry/pointlineplane
Michael
1
Wenn jemand nach einem Abstand zwischen einem Punkt und einer Linie sucht, nicht nach einem Punkt und einer Linie SEGMENT, überprüfen Sie diesen Link: gist.github.com/rhyolight/2846020
Nick Budden
1
Der obige Link ist tot. Hier ist Pseudo-Code und C ++ - Beispiel, erklärt und abgeleitet wie ein Lehrbuch, geomalgorithms.com/a02-_lines.html
Eric

Antworten:

447

Eli, der Code, auf den du dich festgelegt hast, ist falsch. Ein Punkt in der Nähe der Linie, auf der das Segment liegt, aber weit entfernt von einem Ende des Segments, würde in der Nähe des Segments falsch beurteilt. Update: Die angegebene falsche Antwort ist nicht mehr die akzeptierte.

Hier ist ein korrekter Code in C ++. Es class vec2 {float x,y;}wird im Wesentlichen ein Klasse-2D-Vektor mit Operatoren zum Addieren, Subtrahieren, Skalieren usw. sowie einer Distanz- und Punktproduktfunktion (dh x1 x2 + y1 y2) vorausgesetzt .

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: Ich brauchte eine Javascript-Implementierung, also hier ist es ohne Abhängigkeiten (oder Kommentare, aber es ist ein direkter Port der oben genannten). Punkte werden als Objekte mit xund yAttributen dargestellt.

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: Ich brauchte eine Java-Version, aber was noch wichtiger ist, ich brauchte sie in 3D statt in 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));
}
Grumdrig
quelle
1
Ich habe eine ausführliche Version davon als separate Antwort hinzugefügt.
M Katz
4
Vielen Dank an @Grumdrig, Ihre Javascript-Lösung war genau richtig und spart viel Zeit. Ich habe Ihre Lösung auf Objective-C portiert und unten hinzugefügt.
Awolf
1
Wir versuchen wirklich nur, eine Division durch Null zu vermeiden.
Grumdrig
9
Die Projektion eines Punktes pauf eine Linie ist der Punkt auf der Linie, der am nächsten liegt p. (Und ein senkrecht zu der Linie auf der Projektion wird durchlaufen p.) Die Anzahl tist , wie weit entlang des Liniensegmentes aus vzu , wdass die Projektion fällt. Wenn talso 0 ist, fällt die Projektion genau auf v; wenn es 1 ist, ist es an w; Wenn es zum Beispiel 0,5 ist, liegt es auf halbem Weg dazwischen. Wenn tes kleiner als 0 oder größer als 1 ist, fällt es auf die Linie hinter dem einen oder anderen Ende des Segments. In diesem Fall ist der Abstand zum Segment der Abstand zum näheren Ende.
Grumdrig
1
Hoppla - habe nicht bemerkt, dass jemand eine 3D-Version geliefert hat. @RogiSolorzano, Sie müssen zuerst die lat, langen Koordinaten in x-, y- und z-Koordinaten im 3-Raum konvertieren.
Grumdrig
110

Hier ist der einfachste vollständige Code in Javascript.

x, y ist dein Zielpunkt und x1, y1 bis x2, y2 ist dein Liniensegment.

AKTUALISIERT: Behebung eines Zeilenproblems mit 0 Längen aus Kommentaren.

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

Bild zur Visualisierung der Lösung

Joshua
quelle
8
Von all dem Code, den ich gesehen habe, um dieses Problem zu lösen, gefällt mir dieser am besten. Es ist sehr klar und leicht zu lesen. Die Mathematik dahinter ist allerdings etwas mystisch. Was bedeutet zum Beispiel das Punktprodukt geteilt durch die quadratische Länge wirklich?
user1815201
2
Das Punktprodukt geteilt durch die Länge im Quadrat gibt den Projektionsabstand von (x1, y1) an. Dies ist der Bruchteil der Linie, dem der Punkt (x, y) am nächsten liegt. Beachten Sie die letzte else-Klausel, in der (xx, yy) berechnet wird - dies ist die Projektion des Punktes (x, y) auf das Segment (x1, y1) - (x2, y2).
Logan Pickup
4
Die Prüfung auf Liniensegmente der Länge 0 ist im Code zu weit unten. 'len_sq' ist Null und der Code wird durch 0 geteilt, bevor er zur Sicherheitsüberprüfung gelangt.
HostedMetrics.com
17
Meter. Es wird in Metern zurückgegeben.
Joshua
1
@nevermind, nennen wir unseren Punkt p0 und die Punkte, die die Linie als p1 und p2 definieren. Dann erhalten Sie die Vektoren A = p0 - p1 und B = p2 - p1. Param ist der Skalarwert, der bei Multiplikation mit B den Punkt auf der Linie ergibt, der p0 am nächsten liegt. Wenn param <= 0 ist, ist der nächste Punkt p1. Wenn param> = 1 ist, ist der nächste Punkt p1. Wenn es zwischen 0 und 1 liegt, liegt es irgendwo zwischen p1 und p2, also interpolieren wir. XX und YY ist dann der nächstgelegene Punkt auf dem Liniensegment, dx / dy ist der Vektor von p0 bis zu diesem Punkt, und schließlich geben wir die Länge dieses Vektors zurück.
Sean
70

Dies ist eine Implementierung, die für FINITE LINE SEGMENTS erstellt wurde, nicht für unendliche Zeilen, wie es die meisten anderen Funktionen hier zu sein scheinen (deshalb habe ich dies gemacht).

Umsetzung der Theorie von 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;

    }
Quano
quelle
2
Tut mir leid, aber ich habe es versucht und es gibt mir immer noch die Ergebnisse, als würde sich die Linie bis ins Unendliche erstrecken. Ich habe jedoch Grumdigs Antwort auf die Arbeit gefunden.
Frederik
1
In diesem Fall verwenden Sie es falsch oder meinen etwas anderes mit nicht unendlich. Ein Beispiel für diesen Code finden Sie hier: boomie.se/upload/Drawdebug.swf
quano
Sieht aus wie ein Fehler im Code oder so, ich bekomme das gleiche Ergebnis wie Frederik /
Kromster
30
Die Wahl der Variablennamen ist
alles
2
Ich habe die Python-Version der Funktion ausprobiert und festgestellt, dass sie falsche Ergebnisse anzeigt, wenn die Parameter Ganzzahlen sind. distAnother(0, 0, 4, 0, 2, 2)ergibt 2.8284271247461903 (falsch). distAnother(0., 0., 4., 0., 2., 2.)ergibt 2,0 (richtig). Bitte beachten Sie dies. Ich denke, der Code kann verbessert werden, um irgendwo eine Float-Konvertierung zu haben.
Vladimir Obrizan
22

In meinem eigenen Fragenthread, wie man den kürzesten 2D-Abstand zwischen einem Punkt und einem Liniensegment in allen Fällen in C, C # / .NET 2.0 oder Java berechnet? Ich wurde gebeten, hier eine C # -Antwort einzugeben, wenn ich eine finde: Hier ist sie, geändert von 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);
} 

Ich bin @SO, um nicht zu antworten, sondern Fragen zu stellen, also hoffe ich, dass ich aus bestimmten Gründen keine Millionen Stimmen bekomme, sondern Kritiker konstruiere. Ich wollte (und wurde ermutigt) nur die Ideen eines anderen teilen, da die Lösungen in diesem Thread entweder in einer exotischen Sprache (Fortran, Mathematica) vorliegen oder von jemandem als fehlerhaft markiert wurden. Das einzig nützliche (von Grumdrig) für mich ist mit C ++ geschrieben und niemand hat es als fehlerhaft markiert. Es fehlen jedoch die aufgerufenen Methoden (Punkt usw.).

char m
quelle
1
Vielen Dank für die Veröffentlichung. Es sieht jedoch so aus, als ob bei der letzten Methode eine offensichtliche Optimierung möglich ist: Berechnen Sie dist erst, nachdem festgestellt wurde, dass es benötigt wird.
RenniePet
2
Der Kommentar zu DotProduct besagt, dass AB.AC berechnet wird, AB.BC jedoch.
Metal450
Das Kreuzprodukt gibt per Definition einen Vektor zurück, hier jedoch einen Skalar.
SteakOverflow
21

In F # ist der Abstand vom Punkt czum Liniensegment zwischen aund bgegeben durch:

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 dzeigt von abis bentlang des Liniensegments. Das Punktprodukt von d/smit c-agibt den Parameter des Punktes der nächsten Annäherung zwischen der unendlichen Linie und dem Punkt an c. Die minund max-Funktion wird verwendet, um diesen Parameter auf den Bereich zu klemmen, 0..ssodass der Punkt zwischen aund liegt b. Schließlich ist die Länge von a+p-cder Abstand vom cnächsten Punkt auf dem Liniensegment.

Anwendungsbeispiel:

pointToLineSegmentDistance (Vector(0.0, 0.0), Vector(1.0, 0.0)) (Vector(-1.0, 1.0))
Jon Harrop
quelle
1
Ich denke, die letzte Zeile ist falsch und sollte lauten:(a + p - c).Length
Blair Holloway
Damit ist das Problem immer noch nicht vollständig behoben. Eine Möglichkeit, die Funktion zu korrigieren, besteht darin, lambdabzw. pals let lambda = (c - a) * d / (s * s)und neu zu definieren let p = a + (lambda |> max 0.0 |> min 1.0) * d. Danach gibt die Funktion den korrekten Abstand zurück, z. B. für den Fall a = (0,1), in dem b = (1,0)und c = (1,1).
Mikkoma
20

Für alle Interessierten gibt es hier eine triviale Konvertierung von Joshuas Javascript-Code in 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);
}

Ich brauchte diese Lösung, um MKMapPointdamit arbeiten zu können, damit ich sie weitergeben kann, falls jemand anderes sie benötigt. Nur eine kleine Änderung und dies gibt die Entfernung in Metern zurück:

- (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));
}
Ben Gotow
quelle
Das scheint für mich gut zu funktionieren. Danke für die Konvertierung.
Gregir
Es ist erwähnenswert, dass (xx, yy) der Ort des nächsten Punktes ist. Ich habe Ihren Code ein wenig bearbeitet, sodass er sowohl den Punkt als auch die Entfernung zurückgibt . Die überarbeiteten Namen beschreiben, was was ist, und geben ein Beispiel unter: stackoverflow.com/a/28028023/849616 .
Vive
20

In Mathematica

Es verwendet eine parametrische Beschreibung des Segments und projiziert den Punkt in die durch das Segment definierte Linie. Wenn der Parameter im Segment von 0 auf 1 geht und die Projektion außerhalb dieser Grenzen liegt, berechnen wir den Abstand zum entsprechenden Punkt anstelle der geraden Linie senkrecht zum Segment.

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

Darstellungsergebnis:

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

Alt-Text

Zeichnen Sie diese Punkte näher als einen Grenzabstand :

Alt-Text

Konturdiagramm:

Geben Sie hier die Bildbeschreibung ein

Dr. belisarius
quelle
11

Hey, das habe ich gestern gerade geschrieben. Es befindet sich in Actionscript 3.0, das im Grunde Javascript ist, obwohl Sie möglicherweise nicht dieselbe Point-Klasse haben.

//st = start of line segment
//b = the line segment (as in: st + b = end of line segment)
//pt = point to test
//Returns distance from point to line segment.  
//Note: nearest point on the segment to the test point is right there if we ever need it
public static function linePointDist( st:Point, b:Point, pt:Point ):Number
{
    var nearestPt:Point; //closest point on seqment to pt

    var keyDot:Number = dot( b, pt.subtract( st ) ); //key dot product
    var bLenSq:Number = dot( b, b ); //Segment length squared

    if( keyDot <= 0 )  //pt is "behind" st, use st
    {
        nearestPt = st  
    }
    else if( keyDot >= bLenSq ) //pt is "past" end of segment, use end (notice we are saving twin sqrts here cuz)
    {
        nearestPt = st.add(b);
    }
    else //pt is inside segment, reuse keyDot and bLenSq to get percent of seqment to move in to find closest point
    {
        var keyDotToPctOfB:Number = keyDot/bLenSq; //REM dot product comes squared
        var partOfB:Point = new Point( b.x * keyDotToPctOfB, b.y * keyDotToPctOfB );
        nearestPt = st.add(partOfB);
    }

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

    return dist;
}

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

Matt W.
quelle
Danke - das ist genau die Art von Code, nach der ich gesucht habe. Ich habe unten meine eigene Antwort gepostet, da ich es geschafft habe, etwas zusammenzustellen, das in Browser-Javascript der aktuellen Ära funktioniert, aber ich habe Ihre Antwort als akzeptiert markiert, weil sie einfach, gut geschrieben und leicht zu verstehen ist. und sehr geschätzt.
Eli Courtwright
Fehlt hier nicht die Punktmethode? In jedem Fall ist es einfach zu berechnen: vec1.x * vec2.x + vec1.y * vec2.y
Quano
11

Für die Faulen ist hier 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));
}
awolf
quelle
Ich bekomme 'nan' von dieser Linie zurück. Irgendeine Idee warum? (Danke übrigens, dass Sie dies in Obj-C return dist2(p, CGPointMake(v.x + t * (w.x - v.x), v.y + t * (w.y - v.y)))
eingegeben haben
sqrtf () quadriert x und bekommt seine Quadratwurzel nicht
Sinnvoll
@Senseful Nicht sicher, was du meinst. sqrtf ist Quadratwurzel. developer.apple.com/library/mac/documentation/Darwin/Reference/…
awolf
@awolf: Schauen Sie sich die erste Codezeile oben an. Es definiert die Methode sqrtf(x) = x*x.
Sinnvoll
@Senseful danke, es wurde falsch benannt, anstatt die falsche Operation durchzuführen.
Awolf
10

Konnte nicht widerstehen, es in Python zu codieren :)

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)


Das Gleiche gilt für 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
Cyberthanasis
quelle
10
Berechnet dies nicht die Entfernung eines Punktes zu einer Linie anstelle des Segments?
balint.miklos
6
Dies ist in der Tat der Abstand zu der Linie, auf der sich das Segment befindet, nicht zum Segment.
Grumdrig
12
Das scheint nicht zu funktionieren. Wenn Sie ein Segment von (0,0) und (5,0) haben und es gegen Punkt (7,0) versuchen, wird 0 zurückgegeben, was nicht stimmt. Die Entfernung sollte 2.
Quano
8
Er hat den Fall nicht berücksichtigt, in dem die Projektion des Punktes auf das Segment außerhalb des Intervalls von A nach B liegt. Das könnte der Fragesteller sein, aber nicht das, was er gefragt hat.
Phkahler
5
Dies wurde ursprünglich nicht gefragt.
Sambatyon
10

Hier ist eine vollständigere Schreibweise aus Grumdrigs Lösung. Diese Version gibt auch den nächstgelegenen Punkt selbst zurück.

#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 );
}
M Katz
quelle
Vielen Dank für die Veröffentlichung. Sehr gut strukturiert und kommentiert und formatiert - hätte mich fast vergessen lassen, wie sehr ich C ++ nicht mag. Ich habe dies verwendet, um eine entsprechende C # -Version zu erstellen, die ich jetzt hier gepostet habe.
RenniePet
10

Einzeilige Lösung mit Arkustangens:

Die Idee ist, A nach (0, 0) zu bewegen und das Dreieck im Uhrzeigersinn zu drehen, damit C auf der X-Achse liegt. In diesem Fall ist By der Abstand.

  1. ein Winkel = Atan (Cy - Ay, Cx - Axe);
  2. b Winkel = Atan (By - Ay, Bx - Ax);
  3. AB Länge = 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(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;
}

Eine Zeile C # (zur Konvertierung in 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))
ADOConnection
quelle
7

Betrachten Sie diese Änderung der obigen Antwort von Grumdrig. Oft werden Sie feststellen, dass Gleitkomma-Ungenauigkeiten Probleme verursachen können. Ich verwende in der folgenden Version Doppel, aber Sie können leicht zu Floats wechseln. Der wichtige Teil ist, dass es ein Epsilon verwendet, um den "Slop" zu handhaben. Außerdem möchten Sie oft wissen, wo die Kreuzung passiert ist oder ob sie überhaupt passiert ist. Wenn das zurückgegebene t <0,0 oder> 1,0 ist, ist keine Kollision aufgetreten. Selbst wenn keine Kollision aufgetreten ist, möchten Sie oft wissen, wo der Punkt auf dem Segment am nächsten zu P liegt, und daher verwende ich qx und qy, um diesen Ort zurückzugeben.

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 (i.e. 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 (i.e. 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));
    }
}
devnullicus
quelle
6

Ich gehe davon aus, dass Sie den kürzesten finden möchtenAbstand zwischen dem Punkt und einem Liniensegment; Dazu müssen Sie die Linie (Linie A) finden, die senkrecht zu Ihrem Liniensegment (Linie B) verläuft, das durch Ihren Punkt verläuft. Bestimmen Sie den Schnittpunkt zwischen dieser Linie (Linie A) und Ihrer Linie, die durch Ihr Liniensegment verläuft (Linie B). ;; Wenn dieser Punkt zwischen den beiden Punkten Ihres Liniensegments liegt, ist der Abstand der Abstand zwischen Ihrem Punkt und dem Punkt, den Sie gerade gefunden haben und der Schnittpunkt von Linie A und Linie B ist. Wenn der Punkt nicht zwischen den beiden Punkten Ihres Liniensegments liegt, müssen Sie den Abstand zwischen Ihrem Punkt und dem näheren von zwei Enden des Liniensegments ermitteln. Dies kann leicht erreicht werden, indem der Quadratabstand (um eine Quadratwurzel zu vermeiden) zwischen dem Punkt und den beiden Punkten des Liniensegments genommen wird. was auch immer näher ist, nimm die Quadratwurzel von diesem.

Paul Sonier
quelle
6

Die C ++ / JavaScript-Implementierung von Grumdrig war für mich sehr nützlich, daher habe ich einen Python-Direktport bereitgestellt, den ich verwende. Der vollständige Code ist hier .

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)
Woolie
quelle
5

Matlab-Code mit integriertem "Selbsttest", wenn die Funktion ohne Argumente aufgerufen wird:

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 A-B 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', [x-r, y-r, 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
Peter Karasev
quelle
Dank dieses Matlab-Codes wird tatsächlich der kürzeste Abstand zur Linie SEGMENT berechnet und nicht der Abstand zur unendlichen Linie, auf der das Segment liegt.
Rudolf Meijering
4

Und jetzt auch meine Lösung ...... (Javascript)

Es ist sehr schnell, weil ich versuche, Math.pow-Funktionen zu vermeiden.

Wie Sie sehen können, habe ich am Ende der Funktion den Abstand der Linie.

Der Code stammt aus der Bibliothek 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;
};
user1397870
quelle
4

codiert in t-sql

Der Punkt ist (@px, @py) und das Liniensegment verläuft von (@ax, @ay) nach (@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
rob mcnicol
quelle
4

Es sieht so aus, als hätten fast alle anderen auf StackOverflow eine Antwort beigesteuert (bisher 23 Antworten). Hier ist mein Beitrag für C #. Dies basiert hauptsächlich auf der Antwort von M. Katz, die wiederum auf der Antwort von Grumdrig basiert.

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

Und hier ist ein kleines Testprogramm.

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

Wie Sie sehen können, habe ich versucht, den Unterschied zwischen der Verwendung der Version, die die Sqrt () -Methode vermeidet, und der normalen Version zu messen. Meine Tests zeigen, dass Sie vielleicht etwa 2,5% sparen können, aber ich bin mir nicht einmal sicher - die Abweichungen innerhalb der verschiedenen Testläufe waren in der gleichen Größenordnung. Ich habe auch versucht, die von Matti veröffentlichte Version zu messen (plus eine offensichtliche Optimierung), und diese Version scheint etwa 4% langsamer zu sein als die auf Katz / Grumdrig-Code basierende Version.

Bearbeiten: Übrigens habe ich auch versucht, eine Methode zu messen, die den Abstand zu einer unendlichen Linie (kein Liniensegment) mit einem Kreuzprodukt (und einem Sqrt ()) ermittelt, und sie ist ungefähr 32% schneller.

RenniePet
quelle
3

Hier ist die C ++ - Version von devnullicus, die in C # konvertiert wurde. Für meine Implementierung musste ich den Schnittpunkt kennen und fand, dass seine Lösung gut funktioniert.

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 (i.e. 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 (i.e. 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;
}
headkaze
quelle
Klappt wunderbar!! Hat mir unzählige Stunden gerettet. Vielen Dank!!
Steve Johnson
3

Hier wird Swift verwendet

    /* 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)
}
OzRunways
quelle
3

C #

Adaptiert von @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 (a.X * b.X) + (a.Y * b.Y);
}
Mateen Ulhaq
quelle
Versuchte diesen Code, scheint nicht ganz richtig zu funktionieren. Scheint manchmal die falsche Distanz zu bekommen.
WDUK
3

Eine 2D- und 3D-Lösung

Betrachten Sie eine Änderung der Basis, so dass das Liniensegment (0, 0, 0)-(d, 0, 0)und der Punkt wird (u, v, 0). Die kürzeste Entfernung tritt in dieser Ebene auf und ist gegeben durch

    u ≤ 0 -> d(A, C)
0 ≤ u ≤ d -> |v|
d ≤ u     -> d(B, C)

(Der Abstand zu einem der Endpunkte oder zur Stützlinie hängt von der Projektion auf die Linie ab. Der Iso-Distanz-Ort besteht aus zwei Halbkreisen und zwei Liniensegmenten.)

Geben Sie hier die Bildbeschreibung ein

In dem obigen Ausdruck ist d die Länge des Segments AB und u, v sind jeweils das Skalarprodukt und (Modul des) Kreuzprodukts von AB / d (Einheitsvektor in Richtung AB) und AC. Daher vektoriell

AB.AC ≤ 0             -> |AC|
    0 ≤ AB.AC ≤ AB²   -> |ABxAC|/|AB|
          AB² ≤ AB.AC -> |BC|
Yves Daoust
quelle
2

Weitere Informationen finden Sie in der Matlab GEOMETRY-Toolbox auf der folgenden Website: http://people.sc.fsu.edu/~jburkardt/m_src/geometry/geometry.html

Strg + f und geben Sie "segment" ein, um liniensegmentbezogene Funktionen zu finden. Die Funktionen "segment_point_dist_2d.m" und "segment_point_dist_3d.m" sind genau das, was Sie brauchen.

Die GEOMETRY-Codes sind in einer C-Version und einer C ++ - Version sowie einer FORTRAN77-Version und einer FORTRAN90-Version und einer MATLAB-Version verfügbar.

Lilie
quelle
2

AutoHotkeys-Version basierend auf Joshuas 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)
}
Chronozid
quelle
2

Da hier keine Java-Implementierung angezeigt wurde, habe ich die Javascript-Funktion aus der akzeptierten Antwort in Java-Code übersetzt:

static double sqr(double x) {
    return x * x;
}
static double dist2(DoublePoint v, DoublePoint w) {
    return sqr(v.x - w.x) + sqr(v.y - w.y);
}
static double distToSegmentSquared(DoublePoint p, DoublePoint v, DoublePoint w) {
    double l2 = dist2(v, w);
    if (l2 == 0) return dist2(p, v);
    double t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
    if (t < 0) return dist2(p, v);
    if (t > 1) return dist2(p, w);
    return dist2(p, new DoublePoint(
            v.x + t * (w.x - v.x),
            v.y + t * (w.y - v.y)
    ));
}
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;
    }
}
Yury Fedorov
quelle
2

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;
    }
}
Torvin
quelle
1

Hier ist der Code, den ich am Ende geschrieben habe. Dieser Code setzt voraus, dass ein Punkt in Form von definiert ist {x:5, y:7}. Beachten Sie, dass dies nicht der absolut effizienteste Weg ist, aber es ist der einfachste und am einfachsten zu verstehende Code, den ich finden könnte.

// 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));
    };
}
Eli Courtwright
quelle
1
Dieser Code hat einen Fehler. Ein Punkt in der Nähe der Linie, auf der das Segment liegt, aber weit entfernt von einem Ende des Segments, wird fälschlicherweise als nahe dem Segment beurteilt.
Grumdrig
Interessant, ich werde dies das nächste Mal untersuchen, wenn ich an dieser Codebasis arbeite, um Ihre Behauptung zu bestätigen. Danke für den Tipp.
Eli Courtwright
1

Die obige Funktion funktioniert nicht bei vertikalen Linien. Hier ist eine Funktion, die gut funktioniert! Linie mit den Punkten p1, p2. und CheckPoint ist 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) * p.X + (p2.X - p1.X) * p.Y + (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;
}
Dmitry
quelle
Beantwortet die Frage nicht. Dies funktioniert nur für Linien (die sich unendlich im Raum erstrecken), nicht für Liniensegmente (die eine endliche Länge haben).
Trinidad
"obige Funktion" ist eine mehrdeutige Referenz. (Irritiert mich, weil manchmal diese Antwort unter meiner Antwort angezeigt wird.)
RenniePet
1

Hier ist das Gleiche wie bei der C ++ - Antwort, jedoch auf Pascal portiert. Die Reihenfolge des Punktparameters hat sich geändert, um meinem Code zu entsprechen, ist aber dasselbe.

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;
user1401452
quelle
Bei dieser Antwort gibt es mehrere Probleme: Der Typ PointF ist nicht deklariert (möglicherweise ist dies in einigen Pascal-Implementierungen ein Standardtyp). Es ist wahrscheinlich ein Datensatz x, y: double; Ende; 2. Die Funktionen Distance und MPower sind nicht deklariert und es gibt keine Erklärung dafür, was sie tun (wir können raten, ja). 3. Die variable Projektion wird deklariert, aber nie verwendet. Insgesamt ist das eine eher schlechte Antwort.
Dummzeuch