Zwei Liniensegmente verbinden

Question

Bei zwei 2D-Liniensegmenten, A und B, wie berechne ich die Länge des kürzesten 2D-Liniensegments C, das A und B verbindet?

Answer 1

Betrachten Sie Ihre zwei Liniensegmente A und B, die durch jeweils zwei Punkte dargestellt werden (in Fortran!):

Linie A von A1 (x, y), A2 (x, y) dargestellt werden

Linie B, dargestellt durch B1 (x, y) B2 (x, y)

Überprüfen Sie zuerst, ob sich die beiden Linien mit diesem Algorithmus schneiden.

Wenn sie schneiden, dann ist der Abstand zwischen den beiden Linien Null und das Liniensegment, das sie verbindet, ist der Schnittpunkt.

Wenn sie nicht schneiden, Verwenden Sie diese Methode:

B

1. Punkt A1 und Linie B
2. Punkt A2 und Linie
3. Punkt B1 und Leitung: http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/ den kürzesten Abstand zwischen berechnen Ein
4. Punkt B2 und die Linie A

Die kürzeste von diesen vier Liniensegmenten ist Ihre Antwort.

Answer 2

This page hat Informationen, nach denen Sie möglicherweise suchen.

Answer 3

Gernot Hoffmann Papier (Algorithmus und Pascal-Code):

http://www.fho-emden.de/~hoffmann/xsegdist03072004.pdf

Answer 4

Quick-Tipp: Wenn Sie Abstände vergleichen basiert auf Punkte wollen, ist es nicht notwendig, die Quadratwurzeln zu tun.

z. wenn P-to-Q zu sehen, ein kleinerer Abstand als Q-to-R ist, nur überprüfen (Pseudo-Code):

square(P.x-Q.x) + square(P.y-Q.y) < square(Q.x-R.x) + square(Q.y-R.y) 

Answer 5

This page hat eine schöne kurze Beschreibung für die kürzeste Entfernung zwischen zwei Linien zu finden, obwohl @ strager die Link enthält einen Code

Answer 6

Nach dem Leben sagte, "Überprüfen Sie zuerst, ob sich die beiden Linien mit diesem Algorithmus schneiden", aber er gab nicht an, welchen Algorithmus er meinte. Offensichtlich ist es der Schnittpunkt der Linie Segmente nicht die erweiterten Linien, was zählt; Alle nichtparallelen Liniensegmente (ausgenommen koinzidente Endpunkte, die keine Linie definieren) schneiden sich, aber der Abstand zwischen den Liniensegmenten ist nicht notwendigerweise Null. Ich nehme an, er meinte dort eher "Liniensegmente" als "Linien".

Der Link Afterlife gab einen sehr eleganten Ansatz, um den nächsten Punkt auf einer Linie (oder Liniensegment oder Strahl) zu einem anderen beliebigen Punkt zu finden. Dies funktioniert, um die Entfernung von jedem Endpunkt zu dem anderen Liniensegment zu finden (die Beschränkung des berechneten Parameters u auf nicht weniger als 0 für ein Liniensegment oder Strahl und nicht mehr als 1 für ein Liniensegment), tut dies jedoch nicht behandeln Sie die Möglichkeit, dass ein innerer Punkt auf einem Liniensegment näher als jeder Endpunkt ist, da sie sich tatsächlich schneiden, daher ist eine zusätzliche Überprüfung des Schnittpunkts erforderlich.Der Algorithmus für die Bestimmung des Liniensegmentschnittpunkts besteht darin, den Schnittpunkt der erweiterten Linien zu finden (falls parallel, dann ist dies der Fall) und dann zu bestimmen, ob dieser Punkt innerhalb beider Liniensegmente liegt, z B. indem das Skalarprodukt der Vektoren vom Schnittpunkt T zu den beiden Endpunkten genommen wird:

((Tx - A1x) * (Tx - A2x)) + ((Ty - A1y) ​​* (Ty - A2y))

Wenn dies negativ (oder "Null") ist, dann liegt T zwischen A1 und A2 (oder an einem Endpunkt). Überprüfen Sie ähnlich für das andere Liniensegment. Wenn beide größer als "Null" waren, schneiden sich die Liniensegmente nicht. Dies hängt natürlich davon ab, zuerst den Schnittpunkt der erweiterten Linien zu finden, was es erforderlich machen kann, jede Linie als eine Gleichung auszudrücken und das System durch Gaußsche Reduktion (etc.) zu lösen.

Aber es kann einen direkteren Weg geben, ohne für den Schnittpunkt zu lösen, indem man das Kreuzprodukt der Vektoren (B1-A1) und (B2-A1) und das Kreuzprodukt der Vektoren (B1 -A2) und (B2-A2). Wenn diese Kreuzprodukte in der gleichen Richtung verlaufen, befinden sich A1 und A2 auf derselben Seite der Linie B; wenn sie in entgegengesetzten Richtungen sind, dann sind sie auf gegenüberliegenden Seiten der Linie B (und wenn 0, dann sind eine oder beide auf Linie B). In ähnlicher Weise die Kreuzprodukte der Vektoren (A1-B1) und (A2-B1) und (A1-B2) und (A2-B2) überprüfen. Wenn eines dieser Kreuzprodukte "Null" ist oder wenn die Endpunkte von beide Liniensegmente auf gegenüberliegenden Seiten der anderen Linie liegen, müssen sich die Liniensegmente selbst schneiden, andernfalls schneiden sie sich nicht.

Natürlich benötigen Sie eine praktische Formel für die Berechnung eines Kreuzprodukts aus zwei Vektoren aus ihren Koordinaten. Oder, wenn Sie die Winkel (positiv oder negativ) bestimmen könnten, würden Sie das tatsächliche Kreuzprodukt nicht brauchen, da es die Richtung der Winkel zwischen den Vektoren ist, die wir tatsächlich interessieren (oder der Sinus des Winkels wirklich) . Aber ich denke, die Formel für Kreuzprodukt (in 2-D) ist einfach:

Kreuz (V1, V2) = (V1x * V2y) - (V2x * V1y)

Dies ist die z-Achse Komponente des 3D-Kreuzproduktvektors (wobei die x- und y-Komponenten Null sein müssen, da die Anfangsvektoren in der Ebene z = 0 liegen), so können Sie einfach auf das Zeichen (oder "Null") schauen.

Sie können also eine der beiden Methoden verwenden, um im Algorithmus, den Afterlife beschreibt (Verweis auf die Verknüpfung), nach einer Liniensegmentüberschneidung zu suchen.

Answer 7

Mit der allgemeinen Idee von Afterlife's und Rob Parker's Algorithmen oben, hier ist eine C++ - Version einer Reihe von Methoden, um den Mindestabstand zwischen 2 beliebigen 2D-Segmenten zu erhalten. Dies behandelt überlappende Segmente, parallele Segmente, sich überschneidende und nicht überschneidende Segmente. Darüber hinaus werden verschiedene Epsilon-Werte verwendet, um die Ungenauigkeit der Gleitkommazahl zu verhindern. Schließlich gibt Ihnen dieser Algorithmus zusätzlich zum Zurückgeben des Mindestabstandes den Punkt in Segment 1, der dem Segment 2 am nächsten liegt (der auch der Schnittpunkt ist, wenn sich die Segmente schneiden). Es wäre ziemlich trivial auch den Punkt zurück auf [p3, p4] am nächsten [p1, p2], wenn es so gewünscht wird, aber ich werde, dass für den Leser als Übung lassen :)

// minimum distance (squared) between vertices, i.e. minimum segment length (squared) 
#define EPSILON_MIN_VERTEX_DISTANCE_SQUARED 0.00000001 

// An arbitrary tiny epsilon. If you use float instead of double, you'll probably want to change this to something like 1E-7f 
#define EPSILON_TINY 1.0E-14 

// Arbitrary general epsilon. Useful for places where you need more "slop" than EPSILON_TINY (which is most places). 
// If you use float instead of double, you'll likely want to change this to something like 1.192092896E-04 
#define EPSILON_GENERAL 1.192092896E-07 

bool AreValuesEqual(double val1, double val2, double tolerance) 
{ 
    if (val1 >= (val2 - tolerance) && val1 <= (val2 + tolerance)) 
    { 
     return true; 
    } 

    return false; 
} 


double PointToPointDistanceSquared(double p1x, double p1y, double p2x, double p2y) 
{ 
    double dx = p2x - p1x; 
    double dy = p2y - p1y; 
    return (dx * dx) + (dy * dy); 
} 


double PointSegmentDistanceSquared(double px, double py, 
            double p1x, double p1y, 
            double p2x, double p2y, 
            double& t, 
            double& qx, double& qy) 
{ 
    double dx = p2x - p1x; 
    double dy = p2y - p1y; 
    double dp1x = px - p1x; 
    double dp1y = py - p1y; 
    const double segLenSquared = (dx * dx) + (dy * dy); 
    if (AreValuesEqual(segLenSquared, 0.0, EPSILON_MIN_VERTEX_DISTANCE_SQUARED)) 
    { 
     // segment is a point. 
     qx = p1x; 
     qy = p1y; 
     t = 0.0; 
     return ((dp1x * dp1x) + (dp1y * dp1y)); 
    } 
    else 
    { 
     t = ((dp1x * dx) + (dp1y * dy))/segLenSquared; 
     if (t <= EPSILON_TINY) 
     { 
      // 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 >= -EPSILON_TINY) 
      { 
       // 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 - EPSILON_TINY)) 
     { 
      // 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 + EPSILON_TINY)) 
      { 
       // intersects at 2nd segment vertex 
       t = 1.0; 
      } 
      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 = ((1.0 - t) * p1x) + (t * p2x); 
      qy = ((1.0 - t) * p1y) + (t * p2y); 
      // for debugging 
      //ASSERT(AreValuesEqual(qx, p1x + (t * dx), EPSILON_TINY)); 
      //ASSERT(AreValuesEqual(qy, p1y + (t * dy), EPSILON_TINY)); 
     } 
     // return the squared distance from p to the intersection point. 
     double dpqx = px - qx; 
     double dpqy = py - qy; 
     return ((dpqx * dpqx) + (dpqy * dpqy)); 
    } 
} 


double SegmentSegmentDistanceSquared( double p1x, double p1y, 
             double p2x, double p2y, 
             double p3x, double p3y, 
             double p4x, double p4y, 
             double& qx, double& qy) 
{ 
    // check to make sure both segments are long enough (i.e. verts are farther apart than minimum allowed vert distance). 
    // If 1 or both segments are shorter than this min length, treat them as a single point. 
    double segLen12Squared = PointToPointDistanceSquared(p1x, p1y, p2x, p2y); 
    double segLen34Squared = PointToPointDistanceSquared(p3x, p3y, p4x, p4y); 
    double t = 0.0; 
    double minDist2 = 1E+38; 
    if (segLen12Squared <= EPSILON_MIN_VERTEX_DISTANCE_SQUARED) 
    { 
     qx = p1x; 
     qy = p1y; 
     if (segLen34Squared <= EPSILON_MIN_VERTEX_DISTANCE_SQUARED) 
     { 
      // point to point 
      minDist2 = PointToPointDistanceSquared(p1x, p1y, p3x, p3y); 
     } 
     else 
     { 
      // point - seg 
      minDist2 = PointSegmentDistanceSquared(p1x, p1y, p3x, p3y, p4x, p4y); 
     } 
     return minDist2; 
    } 
    else if (segLen34Squared <= EPSILON_MIN_VERTEX_DISTANCE_SQUARED) 
    { 
     // seg - point 
     minDist2 = PointSegmentDistanceSquared(p3x, p3y, p1x, p1y, p2x, p2y, t, qx, qy); 
     return minDist2; 
    } 

    // if you have a point class and/or methods to do cross products, you can use those here. 
    // This is what we're actually doing: 
    // Point2D delta43(p4x - p3x, p4y - p3y); // dir of p3 -> p4 
    // Point2D delta12(p1x - p2x, p1y - p2y); // dir of p2 -> p1 
    // double d = delta12.Cross2D(delta43); 
    double d = ((p4y - p3y) * (p1x - p2x)) - ((p1y - p2y) * (p4x - p3x)); 
    bool bParallel = AreValuesEqual(d, 0.0, EPSILON_GENERAL); 

    if (!bParallel) 
    { 
     // segments are not parallel. Check for intersection. 
     // Point2D delta42(p4x - p2x, p4y - p2y); // dir of p2 -> p4 
     // t = 1.0 - (delta42.Cross2D(delta43)/d); 
     t = 1.0 - ((((p4y - p3y) * (p4x - p2x)) - ((p4y - p2y) * (p4x - p3x)))/d); 
     double seg12TEps = sqrt(EPSILON_MIN_VERTEX_DISTANCE_SQUARED/segLen12Squared); 
     if (t >= -seg12TEps && t <= (1.0 + seg12TEps)) 
     { 
      // inside [p1,p2]. Segments may intersect. 
      // double s = 1.0 - (delta12.Cross2D(delta42)/d); 
      double s = 1.0 - ((((p4y - p2y) * (p1x - p2x)) - ((p1y - p2y) * (p4x - p2x)))/d); 
      double seg34TEps = sqrt(EPSILON_MIN_VERTEX_DISTANCE_SQUARED/segLen34Squared); 
      if (s >= -seg34TEps && s <= (1.0 + seg34TEps)) 
      { 
       // segments intersect! 
       minDist2 = 0.0; 
       qx = ((1.0 - t) * p1x) + (t * p2x); 
       qy = ((1.0 - t) * p1y) + (t * p2y); 
       // for debugging 
       //double qsx = ((1.0 - s) * p3x) + (s * p4x); 
       //double qsy = ((1.0 - s) * p3y) + (s * p4y); 
       //ASSERT(AreValuesEqual(qx, qsx, EPSILON_MIN_VERTEX_DISTANCE_SQUARED)); 
       //ASSERT(AreValuesEqual(qy, qsy, EPSILON_MIN_VERTEX_DISTANCE_SQUARED)); 
       return minDist2; 
      } 
     } 
    } 

    // Segments do not intersect. Find closest point and return dist. No other way at this 
    // point except to just brute-force check each segment end-point vs opposite segment. The 
    // minimum distance of those 4 tests is the closest point. 
    double tmpQx, tmpQy, tmpD2; 
    minDist2 = PointSegmentDistanceSquared(p3x, p3y, p1x, p1y, p2x, p2y, t, qx, qy); 
    tmpD2 = PointSegmentDistanceSquared(p4x, p4y, p1x, p1y, p2x, p2y, t, tmpQx, tmpQy); 
    if (tmpD2 < minDist2) 
    { 
     qx = tmpQx; 
     qy = tmpQy; 
     minDist2 = tmpD2; 
    } 
    tmpD2 = PointSegmentDistanceSquared(p1x, p1y, p3x, p3y, p4x, p4y, t, tmpQx, tmpQy); 
    if (tmpD2 < minDist2) 
    { 
     qx = p1x; 
     qy = p1y; 
     minDist2 = tmpD2; 
    } 
    tmpD2 = PointSegmentDistanceSquared(p2x, p2y, p3x, p3y, p4x, p4y, t, tmpQx, tmpQy); 
    if (tmpD2 < minDist2) 
    { 
     qx = p2x; 
     qy = p2y; 
     minDist2 = tmpD2; 
    } 

    return minDist2; 
}