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

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

Answer 2

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(['Ungültige Argumente, distPointToLineSegment führt den (rekursiven) Selbsttest aus...']);

        ptA = [1;1]; ptB = [-1;-1];
        ptC = [1/2;1/2];  % auf der Linie
        ptD = [-2;-1.5];  % zu weit entfernt vom Linienabschnitt
        ptE = [1/2;0];    % sollte gleich dem senkrechten Abstand zur Linie sein
        ptF = [1.5;1.5];      % entlang von A-B, aber außerhalb des Segments

        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

Answer 3

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

Es ist sehr schnell, weil ich versuche, jegliche 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 Lib http://www.draw2d.org/graphiti/jsdoc/#!/example

/**
 * Statische Hilfsfunktion zur Bestimmung, ob ein Punkt(px,py) auf der Linie(x1,y1,x2,y2) liegt
 * Ein einfacher Treffertest.
 * 
 * @return {boolean}
 * @static
 * @private
 * @param {Number} coronaWidth die akzeptierte Größe des Treffertests
 * @param {Number} X1 x-Koordinate des Startpunkts der Linie
 * @param {Number} Y1 y-Koordinate des Startpunkts der Linie
 * @param {Number} X2 x-Koordinate des Endpunkts der Linie
 * @param {Number} Y2 y-Koordinate des Endpunkts der Linie
 * @param {Number} px x-Koordinate des zu testenden Punkts
 * @param {Number} py y-Koordinate des zu testenden Punkts
 **/
graphiti.shape.basic.Line.hit= function( coronaWidth, X1, Y1,  X2,  Y2, px, py)
{
  // Vektoren relativ zu X1,Y1 anpassen
  // X2,Y2 wird zum relativen Vektor von X1,Y1 zum Ende des Segments
  X2 -= X1;
  Y2 -= Y1;
  // px,py wird zum relativen Vektor von X1,Y1 zum Testpunkt
  px -= X1;
  py -= Y1;
  var dotprod = px * X2 + py * Y2;
  var projlenSq;
  if (dotprod <= 0.0) {
      // px,py liegt auf der Seite von X1,Y1 weg von X2,Y2
      // Entfernung zum Segment ist die Länge des px,py Vektors
      // "Länge seiner (beschnittenen) Projektion" ist jetzt 0.0
      projlenSq = 0.0;
  } else {
      // zu rückwärtsgerichteten Vektoren relativ zu X2,Y2 wechseln
      // X2,Y2 sind bereits das Negative von X1,Y1=>X2,Y2
      // um px,py das Negative von px,py=>X2,Y2 zu machen
      // ist das Skalarprodukt zweier negierter Vektoren dasselbe
      // wie das Skalarprodukt der beiden normalen Vektoren
      px = X2 - px;
      py = Y2 - py;
      dotprod = px * X2 + py * Y2;
      if (dotprod <= 0.0) {
          // px,py liegt auf der Seite von X2,Y2 weg von X1,Y1
          // Entfernung zum Segment ist die Länge des (rückwärts gerichteten) px,py Vektors
          // "Länge seiner (beschnittenen) Projektion" ist jetzt 0.0
          projlenSq = 0.0;
      } else {
          // px,py liegt zwischen X1,Y1 und X2,Y2
          // dotprod ist die Länge des px,py Vektors
          // projiziert auf den X2,Y2=>X1,Y1 Vektor multipliziert mit der
          // Länge des X2,Y2=>X1,Y1 Vektors
          projlenSq = dotprod * dotprod / (X2 * X2 + Y2 * Y2);
      }
  }
    // Die Entfernung zur Linie ist nun die Länge des relativen Punkt-
    // Vektors minus die Länge seiner Projektion auf die Linie
    // (was 0 ist, wenn die Projektion außerhalb des Bereichs
    //  des Liniensegments fällt).
    var lenSq = px * px + py * py - projlenSq;
    if (lenSq < 0) {
        lenSq = 0;
    }
    return Math.sqrt(lenSq)

Answer 4

C#

Adaptiert von @Grumdrig

public static double MindestabstandZuLinienabschnitt(this Point p,
    Line line)
{
    var v = line.StartPoint;
    var w = line.EndPoint;

    double lengthSquared = AbstandQuadrat(v, w);

    if (lengthSquared == 0.0)
        return Abstand(p, v);

    double t = Math.Max(0, Math.Min(1, Skalarprodukt(p - v, w - v) / lengthSquared));
    var projektion = v + t * (w - v);

    return Abstand(p, projektion);
}

public static double Abstand(Point a, Point b)
{
    return Math.Sqrt(AbstandQuadrat(a, b));
}

public static double AbstandQuadrat(Point a, Point b)
{
    var d = a - b;
    return Skalarprodukt(d, d);
}

public static double Skalarprodukt(Point a, Point b)
{
    return (a.X * b.X) + (a.Y * b.Y);
}

Answer 5

In T-SQL codiert

Der Punkt ist (@px, @py) und das Linienstück 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

--Beispiel für die Entfernung von einem Punkt bei (6,1) zu einem Linienstück, das von (4,2) nach (2,1) verläuft
select dbo.fn_DistanceToSegment(6, 1, 4, 2, 2, 1) 
--Ergebnis = 2.2360679775

--Beispiel für die Entfernung von einem Punkt bei (-3,-2) zu einem Linienstück, das von (0,-2) nach (-2,1) verläuft
select dbo.fn_DistanceToSegment(-3, -2, 0, -2, -2, 1) 
--Ergebnis = 2.4961508830

--Beispiel für die Entfernung von einem Punkt bei (0,-2) zu einem Linienstück, das von (0,-2) nach (-2,1) verläuft
select dbo.fn_DistanceToSegment(0,-2, 0, -2, -2, 1) 
--Ergebnis = 0.0000000000