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 ist eine ausführlichere Erläuterung von Grumdrigs Lösung. Diese Version gibt auch den nähesten 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 );
}

Answer 2

Konnte nicht widerstehen, es in Python zu coden :)

from math import sqrt, fabs
def pdis(a, b, c):
    t = b[0]-a[0], b[1]-a[1]           # Vektor ab
    dd = sqrt(t[0]**2+t[1]**2)         # Länge von ab
    t = t[0]/dd, t[1]/dd               # Einheitsvektor von ab
    n = -t[1], t[0]                    # Normaler Einheitsvektor zu ab
    ac = c[0]-a[0], c[1]-a[1]          # Vektor ac
    return fabs(ac[0]*n[0]+ac[1]*n[1]) # Projektion von ac auf n (der minimale Abstand)

print pdis((1,1), (2,2), (2,0))        # Beispiel (Antwort ist 1,414)

Dito 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                          ! Vektor ab
    dd = sqrt(t(0)**2+t(1)**2)         ! Länge von ab
    t = t/dd                           ! Einheitsvektor von ab
    n = (/-t(1), t(0)/)                ! Normaler Einheitsvektor zu ab
    ac = c - a                         ! Vektor ac
    pdis = abs(ac(0)*n(0)+ac(1)*n(1))  ! Projektion von ac auf n (der minimale Abstand)
end function pdis

program test
    print *, pdis((/1.0,1.0/), (/2.0,2.0/), (/2.0,0.0/))   ! Beispiel (Antwort ist 1,414)
end program test

Answer 3

Hier ist es mit Swift

    /* Entfernung von einem Punkt (p1) zu einer Linie l1 l2 */
func entfernungVonPunkt(p: CGPoint, zurLinieSegment l1: CGPoint, und 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
    var param : CGFloat = -1
    if len_sq != 0 {
        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)
}

Answer 4

Ich gehe davon aus, dass du den kürzesten Abstand zwischen dem Punkt und einem Linienabschnitt finden möchtest; um dies zu tun, musst du die Linie (LinieA) finden, die senkrecht zu deinem Linienabschnitt (LinieB) verläuft und durch deinen Punkt verläuft, den Schnittpunkt zwischen dieser Linie (LinieA) und deiner Linie, die durch deinen Linienabschnitt verläuft (LinieB) bestimmen; wenn dieser Punkt zwischen den beiden Punkten deines Linienabschnitts liegt, dann ist der Abstand der Abstand zwischen deinem Punkt und dem Punkt, den du gerade gefunden hast, der Schnittpunkt von LinieA und LinieB; wenn der Punkt nicht zwischen den beiden Punkten deines Linienabschnitts liegt, musst du den Abstand zwischen deinem Punkt und dem näheren der beiden Enden des Linienabschnitts ermitteln; dies kann leicht durch Bestimmung des quadratischen Abstands (um eine Quadratwurzel zu vermeiden) zwischen dem Punkt und den beiden Punkten des Linienabschnitts erfolgen; welcher Punkt näher ist, nehme die Quadratwurzel davon.

Answer 5

Erwägen Sie diese Änderung an Grumdrigs Antwort oben. Oftmals stellt man fest, dass Ungenauigkeiten bei Gleitkomma-Zahlen Probleme verursachen können. In der unten stehenden Version verwende ich Doubles, aber Sie können problemlos zu Floats wechseln. Der wichtige Teil ist, dass ein Epsilon verwendet wird, um den "Spielraum" zu behandeln. Darüber hinaus möchten Sie oft wissen, WO der Schnittpunkt stattgefunden hat oder ob er überhaupt stattgefunden hat. 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 nächstgelegene Punkt auf dem Segment zu P ist, und deshalb 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;  // anpassen. Wenn Sie Float verwenden, möchten Sie wahrscheinlich etwas wie 0.000001f
    static const double kEpsilon = 1.0E-14;  // anpassen. Wenn Sie Floats verwenden, möchten Sie wahrscheinlich etwas wie 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 ist ein Punkt.
        qx = p1x;
        qy = p1y;
        t = 0.0;
        return ((dp1x * dp1x) + (dp1y * dp1y));
    }
    else
    {
        // Projizieren einer Linie von p zum Segment [p1,p2]. Durch Betrachten der Linie,
        // die das Segment erweitert, parametrisiert als p1 + (t * (p2 - p1)),
        // finden wir die Projektion des Punktes P auf die Linie.
        // Es fällt dorthin, wo t = [(p - p1) . (p2 - p1)] / |p2 - p1|^2
        t = ((dp1x * dx) + (dp1y * dy)) / segLenSquared;
        if (t < kEpsilon)
        {
            // Schneidet am oder links vom ersten Segmentpunkt (p1x, p1y). Wenn t ungefähr 0,0 ist, dann
            // Schnittpunkt ist bei p1. Wenn t kleiner ist als das, dann gibt es keinen Schnittpunkt (d.h. p ist nicht innerhalb
            // der 'Grenzen' des Segments)
            if (t > -kEpsilon)
            {
                // Schneidet am 1. Segmentpunkt.
                t = 0.0;
            }
            // setzen unseren "Schnittpunkt" auf p1.
            qx = p1x;
            qy = p1y;
            // Hinweis: Wenn Sie den TATSÄCHLICHEN Schnittpunkt wissen wollten, an dem die projizierten Linien sich schneiden würden, wenn
            // wir PointLineDistanceSquared durchführen würden, dann wäre qx (p1x + (t * dx)) und qy (p1y + (t * dy)).
        }
        else if (t > (1.0 - kEpsilon))
        {
            // Schneidet am oder rechts vom zweiten Segmentpunkt (p2x, p2y). Wenn t ungefähr 1,0 ist, dann
            // Schnittpunkt ist bei p2. Wenn t größer ist als das, dann gibt es keinen Schnittpunkt (d.h. p ist nicht innerhalb
            // der 'Grenzen' des Segments)
            if (t < (1.0 + kEpsilon))
            {
                // Schneidet am 2. Segmentpunkt.
                t = 1.0;
            }
            // setzen unseren "Schnittpunkt" auf p2.
            qx = p2x;
            qy = p2y;
            // Hinweis: Wenn Sie den TATSÄCHLICHEN Schnittpunkt wissen wollten, an dem die projizierten Linien sich schneiden würden, wenn
            // wir PointLineDistanceSquared durchführen würden, dann wäre qx (p1x + (t * dx)) und qy (p1y + (t * dy)).
        }
        else
        {
            // Die Projektion des Punktes auf den Punkt auf dem Segment, der lotrecht steht, war erfolgreich und der Punkt
            // ist innerhalb der 'Grenzen' des Segments. Setzen Sie den Schnittpunkt als diesen projizierten Punkt.
            qx = p1x + (t * dx);
            qy = p1y + (t * dy);
        }
        // geben Sie die quadrierte Entfernung von p zum Schnittpunkt zurück. Beachten Sie, dass wir die quadrierte Entfernung
        // als Optimierung zurückgeben, da Sie oft nur relative Entfernungen vergleichen müssen und die quadrierten Werte
        // dafür gut funktionieren. Wenn Sie die TATSÄCHLICHE Entfernung möchten, nehmen Sie einfach die Quadratwurzel dieses Wertes.
        double dpqx = px - qx;
        double dpqy = py - qy;
        return ((dpqx * dpqx) + (dpqy * dpqy));
    }
}