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

Hier habe ich keine Java-Implementierung gesehen, also 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;
    }
}

Answer 2

Python Numpy Implementierung für ein 2D-Koordinatenarray:

import numpy as np

def dist2d(p1, p2, coords):
    ''' Entfernung von Punkten zu einer endlichen Linie zwischen p1 -> p2 '''
    assert coords.ndim == 2 and coords.shape[1] == 2, 'coords ist nicht 2-dimensional'
    dp = p2 - p1
    st = dp[0]**2 + dp[1]**2
    u = ((coords[:, 0] - p1[0]) * dp[0] + (coords[:, 1] - p1[1]) * dp[1]) / st

    u[u > 1.] = 1.
    u[u < 0.] = 0.

    dx = (p1[0] + u * dp[0]) - coords[:, 0]
    dy = (p1[1] + u * dp[1]) - coords[:, 1]

    return np.sqrt(dx**2 + dy**2)

# Verwendung:
p1 = np.array([0., 0.])
p2 = np.array([0., 10.])

# Liste von Koordinaten
coords = np.array(
    [[0., 0.],
     [5., 5.],
     [10., 10.],
     [20., 20.]
     ])

d = dist2d(p1, p2, coords)

# Einzelne Koordinate
coord = np.array([25., 25.])
d = dist2d(p1, p2, coord[np.newaxis, :])

Answer 3

Sehen Sie sich das Matlab GEOMETRY-Toolbox auf der folgenden Website an: http://people.sc.fsu.edu/~jburkardt/m_src/geometry/geometry.html

Strg + F und tippen Sie "segment", um Funktionen im Zusammenhang mit Liniensegmenten zu finden. Die Funktionen "segment_point_dist_2d.m" und "segment_point_dist_3d.m" sind das, was Sie benötigen.

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

Answer 4

Die akzeptierte Antwort funktioniert nicht (z. B. die Entfernung zwischen 0,0 und (-10,2,10,2) sollte 2 sein).

Hier ist der Code, der funktioniert:

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

Answer 5

AutoHotkeys-Version basierend auf Joshua's Javascript:

plDist(x, y, x1, y1, x2, y2) {
    A:= x - x1
    B:= y - y1
    C:= x2 - x1
    D:= y2 - y1

    dot:= A*C + B*D
    sqLen:= C*C + D*D
    param:= dot / sqLen

    if (param < 0 || ((x1 = x2) && (y1 = y2))) {
        xx:= x1
        yy:= y1
    } else if (param > 1) {
        xx:= x2
        yy:= y2
    } else {
        xx:= x1 + param*C
        yy:= y1 + param*D
    }

    dx:= x - xx
    dy:= y - yy

    return sqrt(dx*dx + dy*dy)
}