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

Eli, der von dir festgelegte Code ist falsch. Ein Punkt in der Nähe der Linie, auf der das Segment liegt, aber weit weg von einem Ende des Segments würde fälschlicherweise in der Nähe des Segments beurteilt werden. Aktualisierung: Die falsche Antwort, die erwähnt wurde, wird nicht mehr akzeptiert.

Hier ist etwas korrekter Code, in C++. Er setzt einen 2D-Vektor class vec2 {float x, y;} voraus, im Wesentlichen mit Operatoren zum Addieren, Subtrahieren, Skalieren usw. und einer Funktion zur Entfernung und zum Skalarprodukt (d.h. x1 x2 + y1 y2).

float minimum_distance(vec2 v, vec2 w, vec2 p) {
  // Gib den minimalen Abstand zwischen dem Linienabschnitt vw und dem Punkt p zurück
  const float l2 = length_squared(v, w);  // d.h. |w-v|^2 - ein Wurzel vermeiden
  if (l2 == 0.0) return distance(p, v);   // Fall v == w
  // Betrachte die Linie, die den Abschnitt erweitert, parametrisiert als v + t (w - v).
  // Wir finden die Projektion des Punktes p auf die Linie.
  // Sie fällt dort, wo t = [(p-v) . (w-v)] / |w-v|^2
  // Wir begrenzen t auf [0,1], um mit Punkten außerhalb des Abschnitts vw umzugehen.
  const float t = max(0, min(1, dot(p - v, w - v) / l2));
  const vec2 projection = v + t * (w - v);  // Die Projektion fällt auf den Abschnitt
  return distance(p, projection);
}

EDIT: Ich brauchte eine Javascript-Implementierung, also hier ist sie, ohne Abhängigkeiten (oder Kommentare, aber es ist eine direkte Umsetzung des oben Genannten). Punkte werden als Objekte mit den Attributen x und y 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 noch wichtiger, ich brauchte sie in 3D anstelle von 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));
}

Hier sind in den Funktionsparametern der betreffende Punkt und der Linienabschnitt hat die Endpunkte und . Die Funktion dist_sq (die angenommen wird) findet das Quadrat des Abstands zwischen zwei Punkten.

Answer 2

Hier ist der einfachste vollständige Code in Javascript.

x, y ist Ihr Zielpunkt und x1, y1 bis x2, y2 ist Ihr Linienabschnitt.

Aktualisiert: Fehlerbehebung für das Problem mit der Linie der Länge 0 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) //im Falle einer Linie der Länge 0
      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);
}

Aktualisiert: Kotlin Version

fun getDistance(x: Double, y: Double, x1: Double, y1: Double, x2: Double, y2: Double): Double {
    val a = x - x1
    val b = y - y1
    val c = x2 - x1
    val d = y2 - y1

    val lenSq = c * c + d * d
    val param = if (lenSq != .0) { //im Falle einer Linie der Länge 0
        val dot = a * c + b * d
        dot / lenSq
    } else {
        -1.0
    }

    val (xx, yy) = when {
        param < 0 -> x1 to y1
        param > 1 -> x2 to y2
        else -> x1 + param * c to y1 + param * d
    }

    val dx = x - xx
    val dy = y - yy
    return hypot(dx, dy)
}

Answer 3

Dies ist eine Implementierung für ENDLICHE LINIENSEGMENTE, nicht unendliche Linien wie die meisten anderen Funktionen hier (deshalb habe ich das gemacht).

Implementierung der Theorie von Paul Bourke.

Python:

def dist(x1, y1, x2, y2, x3, y3): # x3,y3 ist der Punkt
    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

    # Hinweis: Wenn der tatsächliche Abstand nicht wichtig ist,
    # wenn Sie nur das Ergebnis dieser Funktion mit anderen Ergebnissen vergleichen möchten,
    # können Sie einfach den quadratischen Abstand zurückgeben
    # (d. h. entfernen Sie die Wurzel), um etwas Leistung zu gewinnen

    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;

    }

Answer 4

In meinem eigenen Frage-Thread Wie berechnet man den kürzesten 2D-Abstand zwischen einem Punkt und einem Liniensegment in allen Fällen in C, C# / .NET 2.0 oder Java? wurde ich gebeten, hier eine C#-Antwort zu hinterlegen, wenn ich eine finde: Hier ist sie, modifiziert von http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static :

//Den Punktprodukt AB . BC berechnen
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;
}

//Das Kreuzprodukt AB x AC berechnen
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;
}

//Den Abstand von A zu B berechnen
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);
}

//Den Abstand von AB zu C berechnen
//Wenn isSegment wahr ist, ist AB ein Segment, keine Linie.
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 Fragen zu stellen und nicht zu beantworten, deshalb hoffe ich, dass ich nicht aus irgendeinem Grund Millionen von negativen Bewertungen bekomme, sondern konstruktive Kritik üben. Ich wollte nur (und wurde ermutigt), die Ideen von jemand anderem zu teilen, da die Lösungen in diesem Thread entweder in einer exotischen Sprache (Fortran, Mathematica) geschrieben sind oder von jemandem als fehlerhaft gekennzeichnet wurden. Die einzige nützliche (von Grumdrig) für mich ist mit C++ geschrieben und von niemandem als fehlerhaft gekennzeichnet. Aber es fehlen die verwendeten Methoden (dot usw.).

Answer 5

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: