Wie bestimme ich, ob sich zwei Linien schneiden oder nicht, und wenn ja, an welchem ​​x, y-Punkt?

Es gibt einen guten Ansatz für dieses Problem, bei dem Vektorkreuzprodukte verwendet werden. Definieren Sie das zweidimensionale Vektorkreuzprodukt v  ×  w als v _x  w _y  -  v _y  w _x .

Angenommen, die beiden Liniensegmente verlaufen von p nach p  +  r und von q nach q  +  s . Dann ist jeder Punkt auf der ersten Linie als p  +  t  r (für einen Skalarparameter  t ) und jeder Punkt auf der zweiten Linie als q  +  u  s (für einen Skalarparameter  u ) darstellbar.

Die beiden Linien schneiden sich, wenn wir t und u so finden können, dass:

p + t  r = q + u  s

Kreuzen Sie beide Seiten mit s und bekommen Sie

( P + t  r ) × n = ( q + u  s ) × s

Und da s  ×  s = 0 ist, bedeutet dies

t  ( r × s ) = ( q - p ) × s

Und deshalb nach t lösen :

t = ( q - p ) × s / ( r × s )

Auf die gleiche Weise können wir für u lösen :

( P + t  r ) x r = ( q + u  s ) × R

u  ( s × r ) = ( p - q ) × r

u = ( p - q ) × r / ( s × r )

Um die Anzahl der Berechnungsschritte zu verringern, ist es zweckmäßig, dies wie folgt umzuschreiben (wobei zu beachten ist, dass s  ×  r = -  r  ×  s ):

u = ( q - p ) × r / ( r × s )

Jetzt gibt es vier Fälle:

1. Wenn r  ×  s  = 0 und ( q  -  p ) ×  r  = 0 ist, sind die beiden Linien kollinear.

   Drücken Sie in diesem Fall die Endpunkte des zweiten Segments ( q und q  +  s ) als Gleichung des ersten Liniensegments ( p + t r ) aus:

   t ₀ = ( q - p ) ·  r / ( r  ·  r )

   t ₁ = ( q + s - p ) ·  r / ( r  ·  r ) = t ₀ + s  ·  r / ( r  ·  r )

   Wenn das Intervall zwischen t ₀ und t ₁ das Intervall [0, 1] schneidet, sind die Liniensegmente kollinear und überlappen sich; ansonsten sind sie kollinear und disjunkt.

   Es ist zu beachten, dass wenn s und r in entgegengesetzte Richtungen zeigen, s  ·  r <0 ist und das zu prüfende Intervall daher [ t ₁ , t ₀ ] und nicht [ t ₀ , t ₁ ] ist.

2. Wenn r  ×  s  = 0 und ( q  -  p ) ×  r  ≠ 0 ist, sind die beiden Linien parallel und schneiden sich nicht.

3. Wenn r  ×  s  ≤ 0 und 0 ≤  t  ≤ 1 und 0 ≤  u  ≤ 1 ist, treffen sich die beiden Liniensegmente am Punkt p + t  r = q + u  s .

4. Andernfalls sind die beiden Liniensegmente nicht parallel, schneiden sich jedoch nicht.

Kredit: Diese Methode ist die zweidimensionale Spezialisierung des 3D-Linienschnittalgorithmus aus dem Artikel "Schnittmenge zweier Linien im Dreiraum" von Ronald Goldman, veröffentlicht in Graphics Gems , Seite 304. In drei Dimensionen ist dies der übliche Fall Die Linien sind schief (weder parallel noch schneidend). In diesem Fall gibt die Methode die Punkte an, an denen sich die beiden Linien am nächsten nähern.

FWIW erkennt die folgende Funktion (in C) sowohl Linienschnittpunkte als auch den Schnittpunkt. Es basiert auf einem Algorithmus in Andre LeMothes " Tricks of the Windows Game Programming Gurus ". Es ist nicht unähnlich zu einigen Algorithmen in anderen Antworten (z. B. Gareths). LeMothe verwendet dann Cramers Regel (frag mich nicht), um die Gleichungen selbst zu lösen.

Ich kann bestätigen, dass es in meinem schwachen Asteroiden-Klon funktioniert und mit den Randfällen, die in anderen Antworten von Elemental, Dan und Wodzu beschrieben wurden, korrekt umzugehen scheint. Es ist wahrscheinlich auch schneller als der von KingNestor veröffentlichte Code, da alles Multiplikation und Division ist, keine Quadratwurzeln!

Ich denke, es gibt ein gewisses Potenzial für eine Division durch Null, obwohl es in meinem Fall kein Problem war. Einfach zu modifizieren, um den Absturz trotzdem zu vermeiden.

// Returns 1 if the lines intersect, otherwise 0. In addition, if the lines 
// intersect the intersection point may be stored in the floats i_x and i_y.
char get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y, 
    float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
    float s1_x, s1_y, s2_x, s2_y;
    s1_x = p1_x - p0_x;     s1_y = p1_y - p0_y;
    s2_x = p3_x - p2_x;     s2_y = p3_y - p2_y;

    float s, t;
    s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
    {
        // Collision detected
        if (i_x != NULL)
            *i_x = p0_x + (t * s1_x);
        if (i_y != NULL)
            *i_y = p0_y + (t * s1_y);
        return 1;
    }

    return 0; // No collision
}

Übrigens muss ich sagen, dass in LeMothes Buch, obwohl er anscheinend den Algorithmus richtig macht, das konkrete Beispiel, dass er Stecker in den falschen Zahlen zeigt und Berechnungen falsch macht. Zum Beispiel:

(4 * (4 - 1) + 12 * (7 - 1)) / (17 * 4 + 12 * 10)

= 844 / 0,88

= 0,44

Das hat mich stundenlang verwirrt . :(

Das Problem reduziert sich auf diese Frage: Überschneiden sich zwei Linien von A nach B und von C nach D? Dann können Sie es viermal fragen (zwischen der Linie und jeder der vier Seiten des Rechtecks).

Hier ist die Vektormathematik dafür. Ich gehe davon aus, dass die Linie von A nach B die fragliche Linie ist und die Linie von C nach D eine der Rechtecklinien ist. Meine Notation ist, dass dies Axdie "x-Koordinate von A" und Cydie "y-Koordinate von C" ist. Und " *" bedeutet Punktprodukt, also z A*B = Ax*Bx + Ay*By.

E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy ) 
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )

Diese hNummer ist der Schlüssel. Wenn hzwischen 0und 1, schneiden sich die Linien, sonst nicht. Wenn F*PNull ist, können Sie die Berechnung natürlich nicht durchführen, aber in diesem Fall sind die Linien parallel und schneiden sich daher nur in den offensichtlichen Fällen.

Der genaue Schnittpunkt ist C + F*h.

Mehr Spaß:

Wenn hist genau 0 oder 1die Linien berühren an einem Endpunkt. Sie können dies als "Schnittpunkt" betrachten oder nicht, wie Sie es für richtig halten.

Insbesondere müssen hSie die Länge der Linie multiplizieren, um die andere Linie genau zu berühren.

Daher h<0bedeutet If , dass die Rechtecklinie "hinter" der angegebenen Linie liegt (wobei "Richtung" "von A nach B" ist) und wenn h>1die Rechtecklinie "vor" der angegebenen Linie liegt.

Ableitung:

A und C sind Vektoren, die auf den Beginn der Linie zeigen; E und F sind die Vektoren von den Enden von A und C, die die Linie bilden.

Für irgendwelche zwei nicht parallele Linien in der Ebene, muss es genau ein Paar von Skalar- gund hderart , daß diese Gleichung gilt:

A + E*g = C + F*h

Warum? Da sich zwei nicht parallele Linien schneiden müssen, können Sie beide Linien jeweils um einen bestimmten Betrag skalieren und berühren.

( Auf den ersten Blick sieht dies wie eine einzelne Gleichung mit zwei Unbekannten aus! Dies ist jedoch nicht der Fall, wenn man bedenkt, dass es sich um eine 2D-Vektorgleichung handelt, was bedeutet, dass dies wirklich ein Paar von Gleichungen in xund ist y.)

Wir müssen eine dieser Variablen eliminieren. Ein einfacher Weg ist es, den ETerm Null zu machen . Nehmen Sie dazu das Punktprodukt beider Seiten der Gleichung mit einem Vektor, der mit E auf Null punktiert. Dieser Vektor, den ich Poben aufgerufen habe , und ich haben die offensichtliche Transformation von E durchgeführt.

Sie haben jetzt:

A*P = C*P + F*P*h
(A-C)*P = (F*P)*h
( (A-C)*P ) / (F*P) = h

Ich habe versucht, den von Jason oben so elegant beschriebenen Algorithmus zu implementieren. Leider habe ich während der Arbeit mit der Mathematik beim Debuggen viele Fälle gefunden, für die es nicht funktioniert.

Betrachten Sie zum Beispiel die Punkte A (10,10) B (20,20) C (10,1) D (1,10) ergibt h = 0,5, und dennoch wird durch Untersuchung klar, dass diese Segmente nicht nahe beieinander liegen andere.

Die grafische Darstellung macht deutlich, dass 0 <h <1-Kriterien nur anzeigen, dass der Schnittpunkt auf CD liegen würde, wenn er vorhanden wäre, aber nichts darüber aussagen, ob dieser Punkt auf AB liegt. Um sicherzustellen, dass es einen Kreuzungspunkt gibt, müssen Sie die symmetrische Berechnung für die Variable g durchführen. Die Anforderung für das Abfangen lautet: 0 <g <1 UND 0 <h <1

Hier ist eine Verbesserung von Gavins Antwort. Die Lösung von marcp ist ebenfalls ähnlich, verschiebt jedoch weder die Teilung.

Dies stellt sich tatsächlich auch als praktische Anwendung der Antwort von Gareth Rees heraus, da das Kreuzproduktäquivalent in 2D das Perp-Punkt-Produkt ist, von dem dieser Code drei verwendet. Wenn Sie zu 3D wechseln und das Kreuzprodukt verwenden und am Ende sowohl s als auch t interpolieren, erhalten Sie die beiden nächstgelegenen Punkte zwischen den Linien in 3D. Wie auch immer, die 2D-Lösung:

int get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y, 
    float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
    float s02_x, s02_y, s10_x, s10_y, s32_x, s32_y, s_numer, t_numer, denom, t;
    s10_x = p1_x - p0_x;
    s10_y = p1_y - p0_y;
    s32_x = p3_x - p2_x;
    s32_y = p3_y - p2_y;

    denom = s10_x * s32_y - s32_x * s10_y;
    if (denom == 0)
        return 0; // Collinear
    bool denomPositive = denom > 0;

    s02_x = p0_x - p2_x;
    s02_y = p0_y - p2_y;
    s_numer = s10_x * s02_y - s10_y * s02_x;
    if ((s_numer < 0) == denomPositive)
        return 0; // No collision

    t_numer = s32_x * s02_y - s32_y * s02_x;
    if ((t_numer < 0) == denomPositive)
        return 0; // No collision

    if (((s_numer > denom) == denomPositive) || ((t_numer > denom) == denomPositive))
        return 0; // No collision
    // Collision detected
    t = t_numer / denom;
    if (i_x != NULL)
        *i_x = p0_x + (t * s10_x);
    if (i_y != NULL)
        *i_y = p0_y + (t * s10_y);

    return 1;
}

Grundsätzlich wird die Teilung auf den letzten Moment verschoben und die meisten Tests werden verschoben, bis bestimmte Berechnungen durchgeführt wurden, wodurch Early-Outs hinzugefügt werden. Schließlich wird auch die Division durch Null vermieden, die auftritt, wenn die Linien parallel sind.

Möglicherweise möchten Sie auch einen Epsilon-Test anstelle eines Vergleichs mit Null verwenden. Linien, die extrem nahe an der Parallele liegen, können zu leicht abweichenden Ergebnissen führen. Dies ist kein Fehler, sondern eine Einschränkung bei der Gleitkomma-Mathematik.

Frage C: Wie erkennen Sie, ob sich zwei Liniensegmente schneiden oder nicht?

Ich habe nach dem gleichen Thema gesucht und war mit den Antworten nicht zufrieden. Deshalb habe ich einen Artikel geschrieben, in dem sehr detailliert erklärt wird, wie überprüft wird, ob sich zwei Liniensegmente mit vielen Bildern schneiden . Es gibt vollständigen (und getesteten) Java-Code.

Hier ist der Artikel, der auf die wichtigsten Teile zugeschnitten ist:

Der Algorithmus, der prüft, ob das Liniensegment a das Liniensegment b schneidet, sieht folgendermaßen aus:

Was sind Begrenzungsrahmen? Hier sind zwei Begrenzungsrahmen aus zwei Liniensegmenten:

Wenn beide Begrenzungsrahmen einen Schnittpunkt haben, verschieben Sie das Liniensegment a so, dass ein Punkt bei (0 | 0) liegt. Jetzt haben Sie eine Linie durch den durch a definierten Ursprung. Verschieben Sie nun das Liniensegment b auf die gleiche Weise und prüfen Sie, ob sich die neuen Punkte des Liniensegments b auf verschiedenen Seiten der Linie a befinden. Wenn dies der Fall ist, überprüfen Sie es umgekehrt. Ist dies auch der Fall, schneiden sich die Liniensegmente. Wenn nicht, kreuzen sie sich nicht.

Frage A: Wo schneiden sich zwei Liniensegmente?

Sie wissen, dass sich zwei Liniensegmente a und b schneiden. Wenn Sie das nicht wissen, überprüfen Sie es mit den Tools, die ich Ihnen in "Frage C" gegeben habe.

Jetzt können Sie einige Fälle durchgehen und die Lösung mit Mathematik der 7. Klasse erhalten (siehe Code und interaktives Beispiel ).

Frage B: Wie erkennen Sie, ob sich zwei Linien schneiden oder nicht?

Angenommen, Ihr Punkt A = (x1, y1), Punkt B = (x2, y2), C = (x_3, y_3), D = (x_4, y_4). Ihre erste Zeile wird durch AB (mit A! = B) und Ihre zweite durch CD (mit C! = D) definiert.

function doLinesIntersect(AB, CD) {
    if (x1 == x2) {
        return !(x3 == x4 && x1 != x3);
    } else if (x3 == x4) {
        return true;
    } else {
        // Both lines are not parallel to the y-axis
        m1 = (y1-y2)/(x1-x2);
        m2 = (y3-y4)/(x3-x4);
        return m1 != m2;
    }
}

Frage D: Wo schneiden sich zwei Linien?

Überprüfen Sie mit Frage B, ob sie sich überhaupt schneiden.

Die Linien a und b werden durch zwei Punkte für jede Linie definiert. Sie können grundsätzlich dieselbe Logik anwenden, die in Frage A verwendet wurde.

Die Antwort, die hier einmal akzeptiert wurde, ist falsch (sie wurde seitdem nicht akzeptiert, also Hurra!). Es werden nicht alle Nicht-Schnittpunkte korrekt entfernt. Trivial scheint es zu funktionieren, aber es kann fehlschlagen, insbesondere in dem Fall, dass 0 und 1 für h als gültig angesehen werden.

Betrachten Sie den folgenden Fall:

Linien bei (4,1) - (5,1) und (0,0) - (0,2)

Dies sind senkrechte Linien, die sich eindeutig nicht überlappen.

A = (4,1)
B = (5,1)
C = (0,0)
D = (0,2)
E = (5,1) - (4,1) = (- 1,0)
F = (0,2) - (0,0) = (0, -2)
P = (0,1)
h = ((4,1) - (0,0)) Punkt (0,1) / ((0) , -2) Punkt (0,1)) = 0

Gemäß der obigen Antwort treffen sich diese beiden Liniensegmente an einem Endpunkt (Werte von 0 und 1). Dieser Endpunkt wäre:

(0,0) + (0, -2) * 0 = (0,0)

Anscheinend treffen sich die beiden Liniensegmente bei (0,0), was sich auf Linie CD befindet, aber nicht auf Linie AB. Was läuft also falsch? Die Antwort ist, dass die Werte 0 und 1 nicht gültig sind und nur manchmal PASSIEREN, um den Endpunktschnitt korrekt vorherzusagen. Wenn die Verlängerung einer Linie (aber nicht der anderen) das Liniensegment treffen würde, sagt der Algorithmus einen Schnittpunkt von Liniensegmenten voraus, dies ist jedoch nicht korrekt. Ich stelle mir vor, dass durch Testen, beginnend mit AB gegen CD und dann auch mit CD gegen AB, dieses Problem beseitigt würde. Nur wenn beide einschließlich zwischen 0 und 1 liegen, kann gesagt werden, dass sie sich schneiden.

Ich empfehle die Verwendung der Vektorkreuzproduktmethode, wenn Sie Endpunkte vorhersagen müssen.

-Dan

Python-Version der Antwort von iMalc:

def find_intersection( p0, p1, p2, p3 ) :

    s10_x = p1[0] - p0[0]
    s10_y = p1[1] - p0[1]
    s32_x = p3[0] - p2[0]
    s32_y = p3[1] - p2[1]

    denom = s10_x * s32_y - s32_x * s10_y

    if denom == 0 : return None # collinear

    denom_is_positive = denom > 0

    s02_x = p0[0] - p2[0]
    s02_y = p0[1] - p2[1]

    s_numer = s10_x * s02_y - s10_y * s02_x

    if (s_numer < 0) == denom_is_positive : return None # no collision

    t_numer = s32_x * s02_y - s32_y * s02_x

    if (t_numer < 0) == denom_is_positive : return None # no collision

    if (s_numer > denom) == denom_is_positive or (t_numer > denom) == denom_is_positive : return None # no collision


    # collision detected

    t = t_numer / denom

    intersection_point = [ p0[0] + (t * s10_x), p0[1] + (t * s10_y) ]


    return intersection_point

Das Finden des richtigen Schnittpunkts zweier Liniensegmente ist eine nicht triviale Aufgabe mit vielen Randfällen. Hier ist eine gut dokumentierte, funktionierende und getestete Lösung in Java.

Im Wesentlichen können drei Dinge passieren, wenn der Schnittpunkt zweier Liniensegmente gefunden wird:

1. Die Segmente schneiden sich nicht

2. Es gibt einen eindeutigen Schnittpunkt

3. Die Kreuzung ist ein weiteres Segment

HINWEIS : Im Code gehe ich davon aus, dass ein Liniensegment (x1, y1), (x2, y2) mit x1 = x2 und y1 = y2 ein gültiges Liniensegment ist. Mathematisch gesehen besteht ein Liniensegment aus verschiedenen Punkten, aber ich erlaube der Vollständigkeit halber, dass Segmente Punkte in dieser Implementierung sind.

Der Code stammt aus meinem Github-Repo

/**
 * This snippet finds the intersection of two line segments.
 * The intersection may either be empty, a single point or the
 * intersection is a subsegment there's an overlap.
 */

import static java.lang.Math.abs;
import static java.lang.Math.max;
import static java.lang.Math.min;

import java.util.ArrayList;
import java.util.List;

public class LineSegmentLineSegmentIntersection {

  // Small epsilon used for double value comparison.
  private static final double EPS = 1e-5;

  // 2D Point class.
  public static class Pt {
    double x, y;
    public Pt(double x, double y) {
      this.x = x; 
      this.y = y;
    }
    public boolean equals(Pt pt) {
      return abs(x - pt.x) < EPS && abs(y - pt.y) < EPS;
    }
  }

  // Finds the orientation of point 'c' relative to the line segment (a, b)
  // Returns  0 if all three points are collinear.
  // Returns -1 if 'c' is clockwise to segment (a, b), i.e right of line formed by the segment.
  // Returns +1 if 'c' is counter clockwise to segment (a, b), i.e left of line
  // formed by the segment.
  public static int orientation(Pt a, Pt b, Pt c) {
    double value = (b.y - a.y) * (c.x - b.x) - 
                   (b.x - a.x) * (c.y - b.y);
    if (abs(value) < EPS) return 0;
    return (value > 0) ? -1 : +1;
  }

  // Tests whether point 'c' is on the line segment (a, b).
  // Ensure first that point c is collinear to segment (a, b) and
  // then check whether c is within the rectangle formed by (a, b)
  public static boolean pointOnLine(Pt a, Pt b, Pt c) {
    return orientation(a, b, c) == 0 && 
           min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x) && 
           min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
  }

  // Determines whether two segments intersect.
  public static boolean segmentsIntersect(Pt p1, Pt p2, Pt p3, Pt p4) {

    // Get the orientation of points p3 and p4 in relation
    // to the line segment (p1, p2)
    int o1 = orientation(p1, p2, p3);
    int o2 = orientation(p1, p2, p4);
    int o3 = orientation(p3, p4, p1);
    int o4 = orientation(p3, p4, p2);

    // If the points p1, p2 are on opposite sides of the infinite
    // line formed by (p3, p4) and conversly p3, p4 are on opposite
    // sides of the infinite line formed by (p1, p2) then there is
    // an intersection.
    if (o1 != o2 && o3 != o4) return true;

    // Collinear special cases (perhaps these if checks can be simplified?)
    if (o1 == 0 && pointOnLine(p1, p2, p3)) return true;
    if (o2 == 0 && pointOnLine(p1, p2, p4)) return true;
    if (o3 == 0 && pointOnLine(p3, p4, p1)) return true;
    if (o4 == 0 && pointOnLine(p3, p4, p2)) return true;

    return false;
  }

  public static List<Pt> getCommonEndpoints(Pt p1, Pt p2, Pt p3, Pt p4) {

    List<Pt> points = new ArrayList<>();

    if (p1.equals(p3)) {
      points.add(p1);
      if (p2.equals(p4)) points.add(p2);

    } else if (p1.equals(p4)) {
      points.add(p1);
      if (p2.equals(p3)) points.add(p2);

    } else if (p2.equals(p3)) {
      points.add(p2);
      if (p1.equals(p4)) points.add(p1);

    } else if (p2.equals(p4)) {
      points.add(p2);
      if (p1.equals(p3)) points.add(p1);
    }

    return points;
  }

  // Finds the intersection point(s) of two line segments. Unlike regular line 
  // segments, segments which are points (x1 = x2 and y1 = y2) are allowed.
  public static Pt[] lineSegmentLineSegmentIntersection(Pt p1, Pt p2, Pt p3, Pt p4) {

    // No intersection.
    if (!segmentsIntersect(p1, p2, p3, p4)) return new Pt[]{};

    // Both segments are a single point.
    if (p1.equals(p2) && p2.equals(p3) && p3.equals(p4))
      return new Pt[]{p1};

    List<Pt> endpoints = getCommonEndpoints(p1, p2, p3, p4);
    int n = endpoints.size();

    // One of the line segments is an intersecting single point.
    // NOTE: checking only n == 1 is insufficient to return early
    // because the solution might be a sub segment.
    boolean singleton = p1.equals(p2) || p3.equals(p4);
    if (n == 1 && singleton) return new Pt[]{endpoints.get(0)};

    // Segments are equal.
    if (n == 2) return new Pt[]{endpoints.get(0), endpoints.get(1)};

    boolean collinearSegments = (orientation(p1, p2, p3) == 0) && 
                                (orientation(p1, p2, p4) == 0);

    // The intersection will be a sub-segment of the two
    // segments since they overlap each other.
    if (collinearSegments) {

      // Segment #2 is enclosed in segment #1
      if (pointOnLine(p1, p2, p3) && pointOnLine(p1, p2, p4))
        return new Pt[]{p3, p4};

      // Segment #1 is enclosed in segment #2
      if (pointOnLine(p3, p4, p1) && pointOnLine(p3, p4, p2))
        return new Pt[]{p1, p2};

      // The subsegment is part of segment #1 and part of segment #2.
      // Find the middle points which correspond to this segment.
      Pt midPoint1 = pointOnLine(p1, p2, p3) ? p3 : p4;
      Pt midPoint2 = pointOnLine(p3, p4, p1) ? p1 : p2;

      // There is actually only one middle point!
      if (midPoint1.equals(midPoint2)) return new Pt[]{midPoint1};

      return new Pt[]{midPoint1, midPoint2};
    }

    /* Beyond this point there is a unique intersection point. */

    // Segment #1 is a vertical line.
    if (abs(p1.x - p2.x) < EPS) {
      double m = (p4.y - p3.y) / (p4.x - p3.x);
      double b = p3.y - m * p3.x;
      return new Pt[]{new Pt(p1.x, m * p1.x + b)};
    }

    // Segment #2 is a vertical line.
    if (abs(p3.x - p4.x) < EPS) {
      double m = (p2.y - p1.y) / (p2.x - p1.x);
      double b = p1.y - m * p1.x;
      return new Pt[]{new Pt(p3.x, m * p3.x + b)};
    }

    double m1 = (p2.y - p1.y) / (p2.x - p1.x);
    double m2 = (p4.y - p3.y) / (p4.x - p3.x);
    double b1 = p1.y - m1 * p1.x;
    double b2 = p3.y - m2 * p3.x;
    double x = (b2 - b1) / (m1 - m2);
    double y = (m1 * b2 - m2 * b1) / (m1 - m2);

    return new Pt[]{new Pt(x, y)};
  }

}

Hier ist ein einfaches Anwendungsbeispiel:

  public static void main(String[] args) {

    // Segment #1 is (p1, p2), segment #2 is (p3, p4)
    Pt p1, p2, p3, p4;

    p1 = new Pt(-2, 4); p2 = new Pt(3, 3);
    p3 = new Pt(0, 0);  p4 = new Pt(2, 4);
    Pt[] points = lineSegmentLineSegmentIntersection(p1, p2, p3, p4);
    Pt point = points[0];

    // Prints: (1.636, 3.273)
    System.out.printf("(%.3f, %.3f)\n", point.x, point.y);

    p1 = new Pt(-10, 0); p2 = new Pt(+10, 0);
    p3 = new Pt(-5, 0);  p4 = new Pt(+5, 0);
    points = lineSegmentLineSegmentIntersection(p1, p2, p3, p4);
    Pt point1 = points[0], point2 = points[1];

    // Prints: (-5.000, 0.000) (5.000, 0.000)
    System.out.printf("(%.3f, %.3f) (%.3f, %.3f)\n", point1.x, point1.y, point2.x, point2.y);
  }

Ich wollte nur erwähnen, dass eine gute Erklärung und explizite Lösung in der Reihe Numeric Recipes zu finden ist. Ich habe die 3. Ausgabe und die Antwort finden Sie auf Seite 1117, Abschnitt 21.4. Eine andere Lösung mit einer anderen Nomenklatur findet sich in einem Artikel von Marina Gavrilova Reliable Line Section Intersection Testing . Ihre Lösung ist meiner Meinung nach etwas einfacher.

Meine Implementierung ist unten:

bool NuGeometry::IsBetween(const double& x0, const double& x, const double& x1){
   return (x >= x0) && (x <= x1);
}

bool NuGeometry::FindIntersection(const double& x0, const double& y0, 
     const double& x1, const double& y1,
     const double& a0, const double& b0, 
     const double& a1, const double& b1, 
     double& xy, double& ab) {
   // four endpoints are x0, y0 & x1,y1 & a0,b0 & a1,b1
   // returned values xy and ab are the fractional distance along xy and ab
   // and are only defined when the result is true

   bool partial = false;
   double denom = (b0 - b1) * (x0 - x1) - (y0 - y1) * (a0 - a1);
   if (denom == 0) {
      xy = -1;
      ab = -1;
   } else {
      xy = (a0 * (y1 - b1) + a1 * (b0 - y1) + x1 * (b1 - b0)) / denom;
      partial = NuGeometry::IsBetween(0, xy, 1);
      if (partial) {
         // no point calculating this unless xy is between 0 & 1
         ab = (y1 * (x0 - a1) + b1 * (x1 - x0) + y0 * (a1 - x1)) / denom; 
      }
   }
   if ( partial && NuGeometry::IsBetween(0, ab, 1)) {
      ab = 1-ab;
      xy = 1-xy;
      return true;
   }  else return false;
}

Oben sind viele Lösungen verfügbar, aber ich denke, die unten stehende Lösung ist ziemlich einfach und leicht zu verstehen.

Zwei Segmente Vector AB und Vector CD schneiden sich genau dann, wenn

1. Die Endpunkte a und b befinden sich auf gegenüberliegenden Seiten der Segment-CD.
2. Die Endpunkte c und d befinden sich auf der gegenüberliegenden Seite des Segments AB.

Insbesondere befinden sich a und b genau dann auf der gegenüberliegenden Seite des Segments CD, wenn genau eines der beiden Tripel a, c, d und b, c, d gegen den Uhrzeigersinn ist.

Intersect(a, b, c, d)
 if CCW(a, c, d) == CCW(b, c, d)
    return false;
 else if CCW(a, b, c) == CCW(a, b, d)
    return false;
 else
    return true;

Hier stellt CCW gegen den Uhrzeigersinn dar, was basierend auf der Ausrichtung der Punkte wahr / falsch zurückgibt.

Quelle: http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf Seite 2

C und Ziel-C

Basierend auf der Antwort von Gareth Rees

const AGKLine AGKLineZero = (AGKLine){(CGPoint){0.0, 0.0}, (CGPoint){0.0, 0.0}};

AGKLine AGKLineMake(CGPoint start, CGPoint end)
{
    return (AGKLine){start, end};
}

double AGKLineLength(AGKLine l)
{
    return CGPointLengthBetween_AGK(l.start, l.end);
}

BOOL AGKLineIntersection(AGKLine l1, AGKLine l2, CGPoint *out_pointOfIntersection)
{
    // http://stackoverflow.com/a/565282/202451

    CGPoint p = l1.start;
    CGPoint q = l2.start;
    CGPoint r = CGPointSubtract_AGK(l1.end, l1.start);
    CGPoint s = CGPointSubtract_AGK(l2.end, l2.start);

    double s_r_crossProduct = CGPointCrossProductZComponent_AGK(r, s);
    double t = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), s) / s_r_crossProduct;
    double u = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), r) / s_r_crossProduct;

    if(t < 0 || t > 1.0 || u < 0 || u > 1.0)
    {
        if(out_pointOfIntersection != NULL)
        {
            *out_pointOfIntersection = CGPointZero;
        }
        return NO;
    }
    else
    {
        if(out_pointOfIntersection != NULL)
        {
            CGPoint i = CGPointAdd_AGK(p, CGPointMultiply_AGK(r, t));
            *out_pointOfIntersection = i;
        }
        return YES;
    }
}

CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}

CGPoint CGPointSubtract_AGK(CGPoint p1, CGPoint p2)
{
    return (CGPoint){p1.x - p2.x, p1.y - p2.y};
}

CGPoint CGPointAdd_AGK(CGPoint p1, CGPoint p2)
{
    return (CGPoint){p1.x + p2.x, p1.y + p2.y};
}

CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}

CGPoint CGPointMultiply_AGK(CGPoint p1, CGFloat factor)
{
    return (CGPoint){p1.x * factor, p1.y * factor};
}

Viele der Funktionen und Strukturen sind privat, aber Sie sollten ziemlich einfach wissen können, was los ist. Dies ist in diesem Repo öffentlich https://github.com/hfossli/AGGeometryKit/

Das funktioniert gut für mich. Von hier genommen .

 // calculates intersection and checks for parallel lines.  
 // also checks that the intersection point is actually on  
 // the line segment p1-p2  
 Point findIntersection(Point p1,Point p2,  
   Point p3,Point p4) {  
   float xD1,yD1,xD2,yD2,xD3,yD3;  
   float dot,deg,len1,len2;  
   float segmentLen1,segmentLen2;  
   float ua,ub,div;  

   // calculate differences  
   xD1=p2.x-p1.x;  
   xD2=p4.x-p3.x;  
   yD1=p2.y-p1.y;  
   yD2=p4.y-p3.y;  
   xD3=p1.x-p3.x;  
   yD3=p1.y-p3.y;    

   // calculate the lengths of the two lines  
   len1=sqrt(xD1*xD1+yD1*yD1);  
   len2=sqrt(xD2*xD2+yD2*yD2);  

   // calculate angle between the two lines.  
   dot=(xD1*xD2+yD1*yD2); // dot product  
   deg=dot/(len1*len2);  

   // if abs(angle)==1 then the lines are parallell,  
   // so no intersection is possible  
   if(abs(deg)==1) return null;  

   // find intersection Pt between two lines  
   Point pt=new Point(0,0);  
   div=yD2*xD1-xD2*yD1;  
   ua=(xD2*yD3-yD2*xD3)/div;  
   ub=(xD1*yD3-yD1*xD3)/div;  
   pt.x=p1.x+ua*xD1;  
   pt.y=p1.y+ua*yD1;  

   // calculate the combined length of the two segments  
   // between Pt-p1 and Pt-p2  
   xD1=pt.x-p1.x;  
   xD2=pt.x-p2.x;  
   yD1=pt.y-p1.y;  
   yD2=pt.y-p2.y;  
   segmentLen1=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);  

   // calculate the combined length of the two segments  
   // between Pt-p3 and Pt-p4  
   xD1=pt.x-p3.x;  
   xD2=pt.x-p4.x;  
   yD1=pt.y-p3.y;  
   yD2=pt.y-p4.y;  
   segmentLen2=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);  

   // if the lengths of both sets of segments are the same as  
   // the lenghts of the two lines the point is actually  
   // on the line segment.  

   // if the point isn’t on the line, return null  
   if(abs(len1-segmentLen1)>0.01 || abs(len2-segmentLen2)>0.01)  
     return null;  

   // return the valid intersection  
   return pt;  
 }  

 class Point{  
   float x,y;  
   Point(float x, float y){  
     this.x = x;  
     this.y = y;  
   }  

   void set(float x, float y){  
     this.x = x;  
     this.y = y;  
   }  
 }  

Ich habe einige dieser Antworten ausprobiert, aber sie haben bei mir nicht funktioniert (sorry Leute); Nach einigem Suchen im Internet fand ich dies .

Mit einer kleinen Änderung an seinem Code habe ich jetzt diese Funktion, die den Schnittpunkt zurückgibt, oder wenn keine Kreuzung gefunden wird, gibt sie -1, -1 zurück.

    Public Function intercetion(ByVal ax As Integer, ByVal ay As Integer, ByVal bx As Integer, ByVal by As Integer, ByVal cx As Integer, ByVal cy As Integer, ByVal dx As Integer, ByVal dy As Integer) As Point
    '//  Determines the intersection point of the line segment defined by points A and B
    '//  with the line segment defined by points C and D.
    '//
    '//  Returns YES if the intersection point was found, and stores that point in X,Y.
    '//  Returns NO if there is no determinable intersection point, in which case X,Y will
    '//  be unmodified.

    Dim distAB, theCos, theSin, newX, ABpos As Double

    '//  Fail if either line segment is zero-length.
    If ax = bx And ay = by Or cx = dx And cy = dy Then Return New Point(-1, -1)

    '//  Fail if the segments share an end-point.
    If ax = cx And ay = cy Or bx = cx And by = cy Or ax = dx And ay = dy Or bx = dx And by = dy Then Return New Point(-1, -1)

    '//  (1) Translate the system so that point A is on the origin.
    bx -= ax
    by -= ay
    cx -= ax
    cy -= ay
    dx -= ax
    dy -= ay

    '//  Discover the length of segment A-B.
    distAB = Math.Sqrt(bx * bx + by * by)

    '//  (2) Rotate the system so that point B is on the positive X axis.
    theCos = bx / distAB
    theSin = by / distAB
    newX = cx * theCos + cy * theSin
    cy = cy * theCos - cx * theSin
    cx = newX
    newX = dx * theCos + dy * theSin
    dy = dy * theCos - dx * theSin
    dx = newX

    '//  Fail if segment C-D doesn't cross line A-B.
    If cy < 0 And dy < 0 Or cy >= 0 And dy >= 0 Then Return New Point(-1, -1)

    '//  (3) Discover the position of the intersection point along line A-B.
    ABpos = dx + (cx - dx) * dy / (dy - cy)

    '//  Fail if segment C-D crosses line A-B outside of segment A-B.
    If ABpos < 0 Or ABpos > distAB Then Return New Point(-1, -1)

    '//  (4) Apply the discovered position to line A-B in the original coordinate system.
    '*X=Ax+ABpos*theCos
    '*Y=Ay+ABpos*theSin

    '//  Success.
    Return New Point(ax + ABpos * theCos, ay + ABpos * theSin)
End Function

Es scheint ein gewisses Interesse an Gavins Antwort zu bestehen, für die Cortijon eine Javascript-Version in der Kommentaren und iMalc eine Version mit etwas weniger Berechnungen bereitstellte . Einige haben auf Mängel bei verschiedenen Codevorschlägen hingewiesen, andere haben die Effizienz einiger Codevorschläge kommentiert.

Der von iMalc über Gavins Antwort bereitgestellte Algorithmus ist der, den ich derzeit in einem Javascript-Projekt verwende, und ich wollte hier nur eine bereinigte Version bereitstellen, wenn er jemandem helfen kann.

// Some variables for reuse, others may do this differently
var p0x, p1x, p2x, p3x, ix,
    p0y, p1y, p2y, p3y, iy,
    collisionDetected;

// do stuff, call other functions, set endpoints...

// note: for my purpose I use |t| < |d| as opposed to
// |t| <= |d| which is equivalent to 0 <= t < 1 rather than
// 0 <= t <= 1 as in Gavin's answer - results may vary

var lineSegmentIntersection = function(){
    var d, dx1, dx2, dx3, dy1, dy2, dy3, s, t;

    dx1 = p1x - p0x;      dy1 = p1y - p0y;
    dx2 = p3x - p2x;      dy2 = p3y - p2y;
    dx3 = p0x - p2x;      dy3 = p0y - p2y;

    collisionDetected = 0;

    d = dx1 * dy2 - dx2 * dy1;

    if(d !== 0){
        s = dx1 * dy3 - dx3 * dy1;
        if((s <= 0 && d < 0 && s >= d) || (s >= 0 && d > 0 && s <= d)){
            t = dx2 * dy3 - dx3 * dy2;
            if((t <= 0 && d < 0 && t > d) || (t >= 0 && d > 0 && t < d)){
                t = t / d;
                collisionDetected = 1;
                ix = p0x + t * dx1;
                iy = p0y + t * dy1;
            }
        }
    }
};

Ich denke, es gibt eine viel einfachere Lösung für dieses Problem. Ich habe mir heute eine andere Idee ausgedacht und sie scheint gut zu funktionieren (zumindest vorerst in 2D). Sie müssen lediglich den Schnittpunkt zwischen zwei Linien berechnen und dann prüfen, ob der berechnete Schnittpunkt innerhalb der Begrenzungsrahmen beider Liniensegmente liegt. Wenn dies der Fall ist, schneiden sich die Liniensegmente. Das ist es.

BEARBEITEN:

So berechne ich den Schnittpunkt (ich weiß nicht mehr, wo ich diesen Codeausschnitt gefunden habe)

Point3D

kommt von

System.Windows.Media.Media3D

public static Point3D? Intersection(Point3D start1, Point3D end1, Point3D start2, Point3D end2) {

        double a1 = end1.Y - start1.Y;
        double b1 = start1.X - end1.X;
        double c1 = a1 * start1.X + b1 * start1.Y;

        double a2 = end2.Y - start2.Y;
        double b2 = start2.X - end2.X;
        double c2 = a2 * start2.X + b2 * start2.Y;

        double det = a1 * b2 - a2 * b1;
        if (det == 0) { // lines are parallel
            return null;
        }

        double x = (b2 * c1 - b1 * c2) / det;
        double y = (a1 * c2 - a2 * c1) / det;

        return new Point3D(x, y, 0.0);
    }

und dies ist meine (zum Zweck der Antwort vereinfachte) BoundingBox-Klasse:

public class BoundingBox {
    private Point3D min = new Point3D();
    private Point3D max = new Point3D();

    public BoundingBox(Point3D point) {
        min = point;
        max = point;
    }

    public Point3D Min {
        get { return min; }
        set { min = value; }
    }

    public Point3D Max {
        get { return max; }
        set { max = value; }
    }

    public bool Contains(BoundingBox box) {
        bool contains =
            min.X <= box.min.X && max.X >= box.max.X &&
            min.Y <= box.min.Y && max.Y >= box.max.Y &&
            min.Z <= box.min.Z && max.Z >= box.max.Z;
        return contains;
    }

    public bool Contains(Point3D point) {
        return Contains(new BoundingBox(point));
    }

}

Diese Lösung kann helfen

public static float GetLineYIntesept(PointF p, float slope)
    {
        return p.Y - slope * p.X;
    }

    public static PointF FindIntersection(PointF line1Start, PointF line1End, PointF line2Start, PointF line2End)
    {

        float slope1 = (line1End.Y - line1Start.Y) / (line1End.X - line1Start.X);
        float slope2 = (line2End.Y - line2Start.Y) / (line2End.X - line2Start.X);

        float yinter1 = GetLineYIntesept(line1Start, slope1);
        float yinter2 = GetLineYIntesept(line2Start, slope2);

        if (slope1 == slope2 && yinter1 != yinter2)
            return PointF.Empty;

        float x = (yinter2 - yinter1) / (slope1 - slope2);

        float y = slope1 * x + yinter1;

        return new PointF(x, y);
    }

Ich habe Kris 'obige Antwort auf JavaScript portiert. Nachdem er zahlreiche verschiedene Antworten ausprobiert hatte, lieferte er die richtigen Punkte. Ich dachte, ich würde verrückt, dass ich nicht die Punkte bekam, die ich brauchte.

function getLineLineCollision(p0, p1, p2, p3) {
    var s1, s2;
    s1 = {x: p1.x - p0.x, y: p1.y - p0.y};
    s2 = {x: p3.x - p2.x, y: p3.y - p2.y};

    var s10_x = p1.x - p0.x;
    var s10_y = p1.y - p0.y;
    var s32_x = p3.x - p2.x;
    var s32_y = p3.y - p2.y;

    var denom = s10_x * s32_y - s32_x * s10_y;

    if(denom == 0) {
        return false;
    }

    var denom_positive = denom > 0;

    var s02_x = p0.x - p2.x;
    var s02_y = p0.y - p2.y;

    var s_numer = s10_x * s02_y - s10_y * s02_x;

    if((s_numer < 0) == denom_positive) {
        return false;
    }

    var t_numer = s32_x * s02_y - s32_y * s02_x;

    if((t_numer < 0) == denom_positive) {
        return false;
    }

    if((s_numer > denom) == denom_positive || (t_numer > denom) == denom_positive) {
        return false;
    }

    var t = t_numer / denom;

    var p = {x: p0.x + (t * s10_x), y: p0.y + (t * s10_y)};
    return p;
}

Ich habe viele Möglichkeiten ausprobiert und dann beschlossen, meine eigenen zu schreiben. Hier ist es also:

bool IsBetween (float x, float b1, float b2)
{
   return ( ((x >= (b1 - 0.1f)) && 
        (x <= (b2 + 0.1f))) || 
        ((x >= (b2 - 0.1f)) &&
        (x <= (b1 + 0.1f))));
}

bool IsSegmentsColliding(   POINTFLOAT lineA,
                POINTFLOAT lineB,
                POINTFLOAT line2A,
                POINTFLOAT line2B)
{
    float deltaX1 = lineB.x - lineA.x;
    float deltaX2 = line2B.x - line2A.x;
    float deltaY1 = lineB.y - lineA.y;
    float deltaY2 = line2B.y - line2A.y;

    if (abs(deltaX1) < 0.01f && 
        abs(deltaX2) < 0.01f) // Both are vertical lines
        return false;
    if (abs((deltaY1 / deltaX1) -
        (deltaY2 / deltaX2)) < 0.001f) // Two parallel line
        return false;

    float xCol = (  (   (deltaX1 * deltaX2) * 
                        (line2A.y - lineA.y)) - 
                    (line2A.x * deltaY2 * deltaX1) + 
                    (lineA.x * deltaY1 * deltaX2)) / 
                 ((deltaY1 * deltaX2) - (deltaY2 * deltaX1));
    float yCol = 0;
    if (deltaX1 < 0.01f) // L1 is a vertical line
        yCol = ((xCol * deltaY2) + 
                (line2A.y * deltaX2) - 
                (line2A.x * deltaY2)) / deltaX2;
    else // L1 is acceptable
        yCol = ((xCol * deltaY1) +
                (lineA.y * deltaX1) -
                (lineA.x * deltaY1)) / deltaX1;

    bool isCol =    IsBetween(xCol, lineA.x, lineB.x) &&
            IsBetween(yCol, lineA.y, lineB.y) &&
            IsBetween(xCol, line2A.x, line2B.x) &&
            IsBetween(yCol, line2A.y, line2B.y);
    return isCol;
}

Basierend auf diesen beiden Formeln: (Ich habe sie aus der Gleichung von Linien und anderen Formeln vereinfacht)

Dies basiert auf der Antwort von Gareth Ree. In diesem Fall wird auch die Überlappung der Liniensegmente zurückgegeben. In C ++ codiert, ist V eine einfache Vektorklasse. Wobei das Kreuzprodukt zweier Vektoren in 2D einen einzelnen Skalar zurückgibt. Es wurde von meinem automatischen Testsystem meiner Schule getestet und bestanden.

//Required input point must be colinear with the line
bool on_segment(const V& p, const LineSegment& l)
{
    //If a point is on the line, the sum of the vectors formed by the point to the line endpoints must be equal
    V va = p - l.pa;
    V vb = p - l.pb;
    R ma = va.magnitude();
    R mb = vb.magnitude();
    R ml = (l.pb - l.pa).magnitude();
    R s = ma + mb;
    bool r = s <= ml + epsilon;
    return r;
}

//Compute using vector math
// Returns 0 points if the lines do not intersect or overlap
// Returns 1 point if the lines intersect
//  Returns 2 points if the lines overlap, contain the points where overlapping start starts and stop
std::vector<V> intersect(const LineSegment& la, const LineSegment& lb)
{
    std::vector<V> r;

    //http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
    V oa, ob, da, db; //Origin and direction vectors
    R sa, sb; //Scalar values
    oa = la.pa;
    da = la.pb - la.pa;
    ob = lb.pa;
    db = lb.pb - lb.pa;

    if (da.cross(db) == 0 && (ob - oa).cross(da) == 0) //If colinear
    {
        if (on_segment(lb.pa, la) && on_segment(lb.pb, la))
        {
            r.push_back(lb.pa);
            r.push_back(lb.pb);
            dprintf("colinear, overlapping\n");
            return r;
        }

        if (on_segment(la.pa, lb) && on_segment(la.pb, lb))
        {
            r.push_back(la.pa);
            r.push_back(la.pb);
            dprintf("colinear, overlapping\n");
            return r;
        }

        if (on_segment(la.pa, lb))
            r.push_back(la.pa);

        if (on_segment(la.pb, lb))
            r.push_back(la.pb);

        if (on_segment(lb.pa, la))
            r.push_back(lb.pa);

        if (on_segment(lb.pb, la))
            r.push_back(lb.pb);

        if (r.size() == 0)
            dprintf("colinear, non-overlapping\n");
        else
            dprintf("colinear, overlapping\n");

        return r;
    }

    if (da.cross(db) == 0 && (ob - oa).cross(da) != 0)
    {
        dprintf("parallel non-intersecting\n");
        return r;
    }

    //Math trick db cross db == 0, which is a single scalar in 2D.
    //Crossing both sides with vector db gives:
    sa = (ob - oa).cross(db) / da.cross(db);

    //Crossing both sides with vector da gives
    sb = (oa - ob).cross(da) / db.cross(da);

    if (0 <= sa && sa <= 1 && 0 <= sb && sb <= 1)
    {
        dprintf("intersecting\n");
        r.push_back(oa + da * sa);
        return r;
    }

    dprintf("non-intersecting, non-parallel, non-colinear, non-overlapping\n");
    return r;
}

Hier ist eine grundlegende Implementierung eines Liniensegments in C # mit dem entsprechenden Schnittpunkterkennungscode. Es ist eine 2D-Vektor- / Punktstruktur erforderlich, die aufgerufen werden Vector2fkann. Sie können diese jedoch durch einen anderen Typ mit X / Y-Eigenschaften ersetzen. Sie können auch ersetzen floatmitdouble , wenn das passt besser auf Ihre Bedürfnisse.

Dieser Code wird in meiner .NET-Physikbibliothek Boing verwendet .

public struct LineSegment2f
{
    public Vector2f From { get; }
    public Vector2f To { get; }

    public LineSegment2f(Vector2f @from, Vector2f to)
    {
        From = @from;
        To = to;
    }

    public Vector2f Delta => new Vector2f(To.X - From.X, To.Y - From.Y);

    /// <summary>
    /// Attempt to intersect two line segments.
    /// </summary>
    /// <remarks>
    /// Even if the line segments do not intersect, <paramref name="t"/> and <paramref name="u"/> will be set.
    /// If the lines are parallel, <paramref name="t"/> and <paramref name="u"/> are set to <see cref="float.NaN"/>.
    /// </remarks>
    /// <param name="other">The line to attempt intersection of this line with.</param>
    /// <param name="intersectionPoint">The point of intersection if within the line segments, or empty..</param>
    /// <param name="t">The distance along this line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
    /// <param name="u">The distance along the other line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
    /// <returns><c>true</c> if the line segments intersect, otherwise <c>false</c>.</returns>
    public bool TryIntersect(LineSegment2f other, out Vector2f intersectionPoint, out float t, out float u)
    {
        var p = From;
        var q = other.From;
        var r = Delta;
        var s = other.Delta;

        // t = (q − p) × s / (r × s)
        // u = (q − p) × r / (r × s)

        var denom = Fake2DCross(r, s);

        if (denom == 0)
        {
            // lines are collinear or parallel
            t = float.NaN;
            u = float.NaN;
            intersectionPoint = default(Vector2f);
            return false;
        }

        var tNumer = Fake2DCross(q - p, s);
        var uNumer = Fake2DCross(q - p, r);

        t = tNumer / denom;
        u = uNumer / denom;

        if (t < 0 || t > 1 || u < 0 || u > 1)
        {
            // line segments do not intersect within their ranges
            intersectionPoint = default(Vector2f);
            return false;
        }

        intersectionPoint = p + r * t;
        return true;
    }

    private static float Fake2DCross(Vector2f a, Vector2f b)
    {
        return a.X * b.Y - a.Y * b.X;
    }
}

Ein C ++ - Programm, um zu überprüfen, ob sich zwei bestimmte Liniensegmente schneiden

#include <iostream>
using namespace std;

struct Point
{
    int x;
    int y;
};

// Given three colinear points p, q, r, the function checks if
// point q lies on line segment 'pr'
bool onSegment(Point p, Point q, Point r)
{
    if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
        q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
       return true;

    return false;
}

// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r)
{
    // See 10th slides from following link for derivation of the formula
    // http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;  // colinear

    return (val > 0)? 1: 2; // clock or counterclock wise
}

// The main function that returns true if line segment 'p1q1'
// and 'p2q2' intersect.
bool doIntersect(Point p1, Point q1, Point p2, Point q2)
{
    // Find the four orientations needed for general and
    // special cases
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    // General case
    if (o1 != o2 && o3 != o4)
        return true;

    // Special Cases
    // p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;

    // p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;

    // p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;

     // p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

    return false; // Doesn't fall in any of the above cases
}

// Driver program to test above functions
int main()
{
    struct Point p1 = {1, 1}, q1 = {10, 1};
    struct Point p2 = {1, 2}, q2 = {10, 2};

    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    p1 = {10, 0}, q1 = {0, 10};
    p2 = {0, 0}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    p1 = {-5, -5}, q1 = {0, 0};
    p2 = {1, 1}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    return 0;
}

Basierend auf der Antwort von @Gareth Rees, Version für Python:

import numpy as np

def np_perp( a ) :
    b = np.empty_like(a)
    b[0] = a[1]
    b[1] = -a[0]
    return b

def np_cross_product(a, b):
    return np.dot(a, np_perp(b))

def np_seg_intersect(a, b, considerCollinearOverlapAsIntersect = False):
    # /programming/563198/how-do-you-detect-where-two-line-segments-intersect/565282#565282
    # http://www.codeproject.com/Tips/862988/Find-the-intersection-point-of-two-line-segments
    r = a[1] - a[0]
    s = b[1] - b[0]
    v = b[0] - a[0]
    num = np_cross_product(v, r)
    denom = np_cross_product(r, s)
    # If r x s = 0 and (q - p) x r = 0, then the two lines are collinear.
    if np.isclose(denom, 0) and np.isclose(num, 0):
        # 1. If either  0 <= (q - p) * r <= r * r or 0 <= (p - q) * s <= * s
        # then the two lines are overlapping,
        if(considerCollinearOverlapAsIntersect):
            vDotR = np.dot(v, r)
            aDotS = np.dot(-v, s)
            if (0 <= vDotR  and vDotR <= np.dot(r,r)) or (0 <= aDotS  and aDotS <= np.dot(s,s)):
                return True
        # 2. If neither 0 <= (q - p) * r = r * r nor 0 <= (p - q) * s <= s * s
        # then the two lines are collinear but disjoint.
        # No need to implement this expression, as it follows from the expression above.
        return None
    if np.isclose(denom, 0) and not np.isclose(num, 0):
        # Parallel and non intersecting
        return None
    u = num / denom
    t = np_cross_product(v, s) / denom
    if u >= 0 and u <= 1 and t >= 0 and t <= 1:
        res = b[0] + (s*u)
        return res
    # Otherwise, the two line segments are not parallel but do not intersect.
    return None

Wenn jede Seite des Rechtecks ​​ein Liniensegment ist und der vom Benutzer gezeichnete Teil ein Liniensegment ist, müssen Sie nur das vom Benutzer gezeichnete Segment auf Schnittpunkte mit den vier Seitenliniensegmenten überprüfen. Dies sollte angesichts der Start- und Endpunkte jedes Segments eine ziemlich einfache Übung sein.

Basierend auf der Antwort von t3chb0t:

int intersezione_linee(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
   //L1: estremi (x1,y1)(x2,y2) L2: estremi (x3,y3)(x3,y3)
   int d;
   d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
   if(!d)
       return 0;
   p_x = ((x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4))/d;
   p_y = ((x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4))/d;
   return 1;
}

int in_bounding_box(int x1, int y1, int x2, int y2, int p_x, int p_y)
{
    return p_x>=x1 && p_x<=x2 && p_y>=y1 && p_y<=y2;

}

int intersezione_segmenti(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
    if (!intersezione_linee(x1,y1,x2,y2,x3,y3,x4,y4,p_x,p_y))
        return 0;

    return in_bounding_box(x1,y1,x2,y2,p_x,p_y) && in_bounding_box(x3,y3,x4,y4,p_x,p_y);
}

Ich habe diesen Algorithmus aus dem Buch "Multiple View Geometry" gelesen.

folgenden Text mit

'als Transponierungszeichen

* als Punktprodukt

x als Kreuzprodukt bei Verwendung als Operator

1. Liniendefinition

Ein Punkt x_vec = (x, y) 'liegt auf der Linie ax + by + c = 0

wir bezeichnen L = (a, b, c) ', den Punkt als (x, y, 1)' als homogene Koordinaten

Die Liniengleichung kann wie folgt geschrieben werden

(x, y, 1) (a, b, c) '= 0 oder x' * L = 0

2. Schnittpunkt von Linien

wir haben zwei Linien L1 = (a1, b1, c1) ', L2 = (a2, b2, c2)'

Angenommen, x ist ein Punkt, ein Vektor und x = L1 x L2 (L1 Kreuzprodukt L2).

Seien Sie vorsichtig, x ist immer ein 2D-Punkt. Bitte lesen Sie homogene Koordinaten, wenn Sie sich nicht sicher sind, ob (L1xL2) ein Vektor mit drei Elementen und x ein 2D-Koordinaten ist.

Laut Triple Product wissen wir das

L1 * (L1 x L2) = 0 und L2 * (L1 x L2) = 0 aufgrund der Co-Ebene von L1, L2

wir ersetzen (L1xL2) durch den Vektor x, dann haben wir L1 * x = 0, L2 * x = 0, was bedeutet, dass x sowohl auf L1 als auch auf L2 liegt, x ist der Schnittpunkt.

Seien Sie vorsichtig, hier ist x homogene Koordinaten. Wenn das letzte Element von x Null ist, bedeutet dies, dass L1 und L2 parallel sind.

Viele Antworten haben alle Berechnungen in einer einzigen Funktion zusammengefasst. Wenn Sie die Liniensteigungen, y-Abschnitte oder x-Abschnitte für die Verwendung an anderer Stelle in Ihrem Code berechnen müssen, führen Sie diese Berechnungen redundant durch. Ich habe die jeweiligen Funktionen getrennt, offensichtliche Variablennamen verwendet und meinen Code kommentiert, um das Verfolgen zu erleichtern. Ich musste wissen, ob sich Linien unendlich über ihre Endpunkte hinaus schneiden, also in JavaScript:

http://jsfiddle.net/skibulk/evmqq00u/

var point_a = {x:0, y:10},
    point_b = {x:12, y:12},
    point_c = {x:10, y:0},
    point_d = {x:0, y:0},
    slope_ab = slope(point_a, point_b),
    slope_bc = slope(point_b, point_c),
    slope_cd = slope(point_c, point_d),
    slope_da = slope(point_d, point_a),
    yint_ab = y_intercept(point_a, slope_ab),
    yint_bc = y_intercept(point_b, slope_bc),
    yint_cd = y_intercept(point_c, slope_cd),
    yint_da = y_intercept(point_d, slope_da),
    xint_ab = x_intercept(point_a, slope_ab, yint_ab),
    xint_bc = x_intercept(point_b, slope_bc, yint_bc),
    xint_cd = x_intercept(point_c, slope_cd, yint_cd),
    xint_da = x_intercept(point_d, slope_da, yint_da),
    point_aa = intersect(slope_da, yint_da, xint_da, slope_ab, yint_ab, xint_ab),
    point_bb = intersect(slope_ab, yint_ab, xint_ab, slope_bc, yint_bc, xint_bc),
    point_cc = intersect(slope_bc, yint_bc, xint_bc, slope_cd, yint_cd, xint_cd),
    point_dd = intersect(slope_cd, yint_cd, xint_cd, slope_da, yint_da, xint_da);

console.log(point_a, point_b, point_c, point_d);
console.log(slope_ab, slope_bc, slope_cd, slope_da);
console.log(yint_ab, yint_bc, yint_cd, yint_da);
console.log(xint_ab, xint_bc, xint_cd, xint_da);
console.log(point_aa, point_bb, point_cc, point_dd);

function slope(point_a, point_b) {
  var i = (point_b.y - point_a.y) / (point_b.x - point_a.x);
  if (i === -Infinity) return Infinity;
  if (i === -0) return 0;
  return i;
}

function y_intercept(point, slope) {
    // Horizontal Line
    if (slope == 0) return point.y;
  // Vertical Line
    if (slope == Infinity)
  {
    // THE Y-Axis
    if (point.x == 0) return Infinity;
    // No Intercept
    return null;
  }
  // Angled Line
  return point.y - (slope * point.x);
}

function x_intercept(point, slope, yint) {
    // Vertical Line
    if (slope == Infinity) return point.x;
  // Horizontal Line
    if (slope == 0)
  {
    // THE X-Axis
    if (point.y == 0) return Infinity;
    // No Intercept
    return null;
  }
  // Angled Line
  return -yint / slope;
}

// Intersection of two infinite lines
function intersect(slope_a, yint_a, xint_a, slope_b, yint_b, xint_b) {
  if (slope_a == slope_b)
  {
    // Equal Lines
    if (yint_a == yint_b && xint_a == xint_b) return Infinity;
    // Parallel Lines
    return null;
  }
  // First Line Vertical
    if (slope_a == Infinity)
  {
    return {
        x: xint_a,
      y: (slope_b * xint_a) + yint_b
    };
  }
  // Second Line Vertical
    if (slope_b == Infinity)
  {
    return {
        x: xint_b,
      y: (slope_a * xint_b) + yint_a
    };
  }
  // Not Equal, Not Parallel, Not Vertical
  var i = (yint_b - yint_a) / (slope_a - slope_b);
  return {
    x: i,
    y: (slope_a * i) + yint_a
  };
}