Jak ustalić, czy dwie linie przecinają się, a jeśli tak, to w jakim punkcie x, y?

Jest ładne podejście do tego problemu, w którym wykorzystuje się krzyżowe produkty wektorowe. Zdefiniuj dwuwymiarowy wektorowy krzyżowy iloczyn v  ×  w na v _x  w _y  -  v _y  w _x .

Załóżmy, że dwa segmenty linii biegną od p do p  +  r i od q do q  +  s . Następnie każdy punkt na pierwszej linii się przedstawić jako p  +  t  r (dla skalarnych parametru  t ) oraz dowolny punkt na drugiej linii, q  +  u  s (o skalara parametru  U ).

Obie linie przecinają się, czy możemy znaleźć T i U takie, że:

p + t  r = q + u  s

Przejdź po obu stronach z s , coraz

( p + t  r ) × s = ( q + u  s ) × s

A ponieważ s  ×  s = 0, oznacza to

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

A zatem rozwiązanie dla t :

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

W ten sam sposób możemy rozwiązać dla ciebie :

( p + t  r ) × r = ( q + u  s ) × r

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

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

Aby zmniejszyć liczbę kroków obliczeniowych, wygodnie jest przepisać to w następujący sposób (pamiętając, że s  ×  r = -  r  ×  s ):

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

Teraz są cztery przypadki:

1. Jeśli r  ×  s  = 0 i ( q  -  p ) ×  r  = 0, wówczas dwie linie są współliniowe.

   W takim przypadku wyraż punkty końcowe drugiego segmentu ( q i q  +  s ) w kategoriach równania pierwszego segmentu linii ( p + t r ):

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

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

   Jeżeli odstęp między t ₀ i t ₁ krzyżuje się z przedziału [0, 1], po czym odcinki są współliniowe i nakładania; w przeciwnym razie są kolinearne i rozłączne.

   Należy zauważyć, że jeśli s i R punkt w przeciwnych kierunkach, a y  ·  R <0, a więc w odstępie być sprawdzony [ T ₁ , T ₀ ] zamiast [ t ₀ , T ₁ ].

2. Jeśli r  ×  s  = 0 i ( q  -  p ) ×  r  ≠ 0, wówczas dwie linie są równoległe i nie przecinają się.

3. Jeśli R  x  y  ≠ 0 i 0 ≤  t  ≤ 1 i 0 ≤  U  ≤ 1, dwa odcinki spotkać w punkcie p + t  r = q + u  s .

4. W przeciwnym razie dwa segmenty linii nie są równoległe, ale się nie przecinają.

Źródło: ta metoda to dwuwymiarowa specjalizacja algorytmu przecięcia linii 3D z artykułu Ronalda Goldmana „Przecięcie dwóch linii w trójprzestrzeni”, opublikowanego w Graphics Gems , strona 304. W trzech wymiarach zwykle występuje to, że linie są pochylone (ani równoległe, ani przecinające się), w którym to przypadku metoda podaje punkty najbliższego zbliżenia dwóch linii.

FWIW, następująca funkcja (w C) zarówno wykrywa przecięcia linii, jak i określa punkt przecięcia. Opiera się on na algorytmie z „Trików guru programowania gier systemu Andre” Leona LeMotheta . Nie różni się od niektórych algorytmów w innych odpowiedziach (np. Garetha). Następnie LeMothe używa reguły Cramera (nie pytaj mnie), aby rozwiązać same równania.

Mogę zaświadczyć, że działa w moim słabym klonie asteroid i wydaje się, że poprawnie radzi sobie z przypadkowymi przypadkami opisanymi w innych odpowiedziach przez Elementala, Dana i Wodzu. Prawdopodobnie jest także szybszy niż kod opublikowany przez KingNestor, ponieważ to wszystko mnożenie i dzielenie, bez pierwiastków kwadratowych!

Wydaje mi się, że istnieje potencjał podziału przez zero, choć w moim przypadku nie było to problemem. Łatwo je zmodyfikować, aby i tak uniknąć awarii.

// 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
}

BTW, muszę powiedzieć, że w książce LeMothe'a, chociaż najwyraźniej poprawia algorytm, konkretny przykład, w którym pokazuje błędne liczby i błędne obliczenia. Na przykład:

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

= 844 / 0,88

= 0,44

Zdezorientowało mnie to godzinami . :(

Problem sprowadza się do pytania: czy przecinają się dwie linie od A do B i od C do D? Następnie możesz go zadać cztery razy (między linią a każdym z czterech boków prostokąta).

Oto matematyka wektorowa do tego. Zakładam, że linia od A do B jest linią, o której mowa, a linia od C do D jest jedną z linii prostokątnych. Mam na Axmyśli, że jest to „współrzędna x A” i Cy„współrzędna y C.” A „ *” oznacza iloczyn skalarny, więc np 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 )

Ten hnumer jest kluczem. Jeśli hjest pomiędzy 0i 1, linie przecinają się, w przeciwnym razie nie. Jeśli F*Pwynosi zero, oczywiście nie można wykonać obliczeń, ale w tym przypadku linie są równoległe i dlatego przecinają się tylko w oczywistych przypadkach.

Dokładny punkt przecięcia to C + F*h.

Więcej zabawy:

Jeśli hjest dokładnie 0 lub 1linie stykają się w punkcie końcowym. Możesz uznać to za „skrzyżowanie” lub nie, jak uważasz za stosowne.

W szczególności hjest to, ile trzeba pomnożyć długość linii, aby dokładnie dotknąć drugiej linii.

Dlatego „If” h<0oznacza, że ​​linia prostokąta znajduje się „za” daną linią („kierunek” jest „od A do B”), a h>1linia prostokąta znajduje się „przed” daną linią.

Pochodzenie:

A i C to wektory, które wskazują początek linii; E i F to wektory z końców A i C, które tworzą linię.

Dla dwóch dowolnych nierównoległych linii w płaszczyźnie musi istnieć dokładnie jedna para skalarna gi htakie równanie zawiera:

A + E*g = C + F*h

Dlaczego? Ponieważ dwie nierównoległe linie muszą się przecinać, co oznacza, że ​​można przeskalować obie linie o określoną wartość i dotknąć się nawzajem.

( Początkowo to wygląda pojedynczego równania z dwoma niewiadomymi! Ale to nie jest jeśli wziąć pod uwagę, że jest to równanie wektorowe 2D, co oznacza, że jest to naprawdę parę równań xa y).

Musimy wyeliminować jedną z tych zmiennych. Prostym sposobem jest uczynienie Eterminu zerowym. Aby to zrobić, weź iloczyn iloczynu po obu stronach równania, używając wektora, który będzie kropkował zero do E. Ten wektor, który wezwałem Ppowyżej, i wykonałem oczywistą transformację E.

Teraz masz:

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

Próbowałem zaimplementować algorytm tak elegancko opisany przez Jasona powyżej; niestety podczas pracy z matematyką podczas debugowania znalazłem wiele przypadków, dla których to nie działa.

Rozważmy na przykład punkty A (10,10) B (20,20) C (10,1) D (1,10), które dają h = .5, a jednak z badania wynika, że ​​segmenty te nie znajdują się blisko siebie inny.

Wykreślenie tego pokazuje, że kryteria 0 <h <1 wskazują tylko, że punkt przecięcia leżałby na CD, gdyby istniał, ale nie mówi nic o tym, czy ten punkt leży na AB. Aby upewnić się, że istnieje punkt przecięcia, należy wykonać obliczenia symetryczne dla zmiennej g, a warunkiem przechwytywania jest: 0 <g <1 AND 0 <h <1

Oto poprawka do odpowiedzi Gavina. Rozwiązanie marcp jest również podobne, ale żadne nie opóźnia podziału.

W rzeczywistości okazuje się to również praktycznym zastosowaniem odpowiedzi Garetha Reesa, ponieważ ekwiwalentem wielu produktów w 2D jest iloczyn perp-kropka, z czego ten kod wykorzystuje trzy. Przełączenie na 3D i użycie produktu krzyżowego, interpolacja zarówno s, jak i t na końcu, daje w wyniku dwa najbliższe punkty między liniami w 3D. W każdym razie rozwiązanie 2D:

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

Zasadniczo odkłada podział na ostatnią chwilę i przenosi większość testów, aż do wykonania pewnych obliczeń, dodając w ten sposób wczesne wyjścia. Wreszcie, unika się również dzielenia przez przypadek zerowy, który występuje, gdy linie są równoległe.

Możesz również rozważyć użycie testu epsilon zamiast porównania z zerem. Linie, które są bardzo zbliżone do równoległych, mogą dawać nieznacznie niejednoznaczne wyniki. To nie jest błąd, to ograniczenie matematyki zmiennoprzecinkowej.

Pytanie C: Jak wykryć, czy przecinają się dwa segmenty linii?

Szukałem tego samego tematu i nie byłem zadowolony z odpowiedzi. Napisałem więc artykuł, który wyjaśnia bardzo szczegółowo, jak sprawdzić, czy dwa segmenty linii przecinają się z wieloma obrazami. Istnieje kompletny (i przetestowany) kod Java.

Oto artykuł, przycięty do najważniejszych części:

Algorytm, który sprawdza, czy odcinek linii a przecina się z odcinkiem linii b, wygląda następująco:

Co to są obwiednie? Oto dwie ramki ograniczające dwóch segmentów linii:

Jeśli obie ramki ograniczające mają przecięcie, przesuwasz segment linii a, tak aby jeden punkt znajdował się na (0 | 0). Teraz masz linię przechodzącą przez początek zdefiniowany przez. Teraz przesuń segment linii b w ten sam sposób i sprawdź, czy nowe punkty segmentu linii b znajdują się po różnych stronach linii a. W takim przypadku sprawdź to na odwrót. W takim przypadku odcinki linii przecinają się. Jeśli nie, nie przecinają się.

Pytanie A: Gdzie przecinają się dwa segmenty linii?

Wiesz, że dwa odcinki linii aib przecinają się. Jeśli nie wiesz, sprawdź to za pomocą narzędzi, które ci dałem w „Pytaniu C”.

Teraz możesz przejrzeć niektóre przypadki i uzyskać rozwiązanie z matematyki 7 klasy (patrz kod i interaktywny przykład ).

Pytanie B: Jak rozpoznać, czy przecinają się dwie linie?

Załóżmy, że punkt A = (x1, y1), punkt B = (x2, y2), C = (x_3, y_3), D = (x_4, y_4). Twój pierwszy wiersz jest zdefiniowany przez AB (z A! = B), a twój drugi przez CD (z C! = D).

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

Pytanie D: Gdzie przecinają się dwie linie?

Sprawdź pytanie B, czy w ogóle się przecinają.

Linie aib są zdefiniowane przez dwa punkty dla każdej linii. Możesz w zasadzie zastosować tę samą logikę, której użyto w pytaniu A.

Odpowiedź raz zaakceptowana tutaj jest niepoprawna (od tego czasu nie została zaakceptowana, więc brawo!). Nie eliminuje poprawnie wszystkich nieprzecięć. Trywialnie może się wydawać, że działa, ale może się nie powieść, szczególnie w przypadku, gdy 0 i 1 są uważane za prawidłowe dla h.

Rozważ następujący przypadek:

Linie w (4,1) - (5,1) i (0,0) - (0,2)

Są to linie prostopadłe, które wyraźnie się nie nakładają.

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)) kropka (0,1) / ((0 , -2) kropka (0,1)) = 0

Zgodnie z powyższą odpowiedzią te dwa segmenty linii spotykają się w punkcie końcowym (wartości 0 i 1). Ten punkt końcowy to:

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

Zatem najwyraźniej dwa segmenty linii spotykają się w punkcie (0,0), który znajduje się na linii CD, ale nie na linii AB. Co się dzieje nie tak? Odpowiedź jest taka, że ​​wartości 0 i 1 są niepoprawne i tylko czasami SZCZĘŚLIWY, aby poprawnie przewidzieć przecięcie punktu końcowego. Gdy przedłużenie jednej linii (ale nie drugiej) byłoby zgodne z segmentem linii, algorytm przewiduje przecięcie segmentów linii, ale nie jest to poprawne. Wyobrażam sobie, że poprzez testowanie zaczynając od AB kontra CD, a następnie także testując CD z AB, problem ten zostałby wyeliminowany. Tylko jeśli oba mieszczą się w przedziale od 0 do 1 włącznie, można powiedzieć, że się przecinają.

Polecam użycie wektorowej metody krzyżowej, jeśli musisz przewidzieć punkty końcowe.

-Dan

Wersja odpowiedzi iMalc w języku Python:

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

Znalezienie prawidłowego przecięcia dwóch segmentów linii jest niełatwym zadaniem z dużą liczbą przypadków krawędzi. Oto dobrze udokumentowane, działające i przetestowane rozwiązanie w Javie.

Zasadniczo istnieją trzy rzeczy, które mogą się zdarzyć po znalezieniu przecięcia dwóch segmentów linii:

1. Segmenty się nie przecinają

2. Istnieje unikalny punkt przecięcia

3. Skrzyżowanie to kolejny segment

UWAGA : W kodzie zakładam, że segment linii (x1, y1), (x2, y2) z x1 = x2 i y1 = y2 jest prawidłowym segmentem linii. Z matematycznego punktu widzenia segment linii składa się z odrębnych punktów, ale pozwalam, aby segmenty były punktami w tej implementacji dla kompletności.

Kod pochodzi z mojego repozytorium github

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

}

Oto prosty przykład użycia:

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

Chciałem tylko wspomnieć, że dobre wyjaśnienie i jednoznaczne rozwiązanie można znaleźć w serii Przepisy numeryczne. Mam wydanie trzecie, a odpowiedź znajduje się na stronie 1117, sekcja 21.4. Inne rozwiązanie z inną nomenklaturą można znaleźć w artykule Marina Gavrilova Reliable Line Intersection Testing . Moim zdaniem jej rozwiązanie jest nieco prostsze.

Moja implementacja jest poniżej:

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

Wiele rozwiązań jest dostępnych powyżej, ale myślę, że poniższe rozwiązanie jest dość proste i łatwe do zrozumienia.

Dwa segmenty Vector AB i Vector CD przecinają się wtedy i tylko wtedy, gdy

1. Punkty końcowe aib znajdują się po przeciwnych stronach segmentu CD.
2. Punkty końcowe cid znajdują się po przeciwnej stronie odcinka AB.

Mówiąc dokładniej, aib znajdują się po przeciwnej stronie segmentu CD wtedy i tylko wtedy, gdy dokładnie jedna z dwóch trójek a, c, d i b, c, d jest w kolejności przeciwnej do ruchu wskazówek zegara.

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;

W tym przypadku CCW reprezentuje przeciwnie do ruchu wskazówek zegara, co zwraca wartość prawda / fałsz na podstawie orientacji punktów.

Źródło: http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf Strona 2

C i Cel-C

Na podstawie odpowiedzi Garetha Reesa

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

Wiele funkcji i struktur jest prywatnych, ale powinieneś dość łatwo wiedzieć, co się dzieje. To jest publiczne w tym repozytorium https://github.com/hfossli/AGGeometryKit/

To działa dobrze dla mnie. Zabrano stąd .

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

Próbowałem niektórych z tych odpowiedzi, ale one nie działały dla mnie (przepraszam chłopaki); po kilku kolejnych poszukiwaniach w sieci znalazłem to .

Z niewielką modyfikacją jego kodu mam teraz funkcję, która zwróci punkt przecięcia lub jeśli nie zostanie znalezione żadne przecięcie, zwróci -1, -1.

    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

Wydaje się, że istnieje pewne zainteresowanie odpowiedzią Gavina, dla której cortijon zaproponował wersję javascript w komentarzach, a iMalc dostarczył wersję z nieco mniejszą liczbą obliczeń . Niektórzy zwracali uwagę na wady różnych propozycji kodu, a inni komentowali efektywność niektórych propozycji kodu.

Algorytm dostarczony przez iMalc za pośrednictwem odpowiedzi Gavina jest tym, którego obecnie używam w projekcie javascript i chciałem tylko tutaj dostarczyć oczyszczoną wersję, jeśli może to komukolwiek pomóc.

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

Myślę, że istnieje znacznie prostsze rozwiązanie tego problemu. Wpadłem dziś na inny pomysł i wydaje się, że działa dobrze (przynajmniej na razie w 2D). Wszystko, co musisz zrobić, to obliczyć przecięcie między dwiema liniami, a następnie sprawdzić, czy obliczony punkt przecięcia znajduje się w polach ograniczających obu segmentów linii. Jeśli tak, odcinki linii przecinają się. Otóż ​​to.

EDYTOWAĆ:

W ten sposób obliczam przecięcie (już nie wiem, gdzie znalazłem ten fragment kodu)

Point3D

pochodzi z

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

i to jest moja (uproszczona dla celów odpowiedzi) klasa BoundingBox:

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

}

To rozwiązanie może pomóc

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

Przesłałem powyższą odpowiedź Krisa do JavaScript. Po wypróbowaniu wielu różnych odpowiedzi podał poprawne punkty. Myślałem, że wariuję, że nie dostaję potrzebnych punktów.

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

Próbowałem na wiele sposobów, a potem postanowiłem napisać własny. Oto on:

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

Na podstawie tych dwóch formuł: (uprościłem je z równania linii i innych formuł)

Opiera się to na odpowiedzi Garetha Ree. Zwraca również nakładanie się segmentów linii, jeśli tak się dzieje. Kodowany w C ++, V jest prostą klasą wektorową. Gdzie iloczyn krzyżowy dwóch wektorów w 2D zwraca pojedynczy skalar. Został przetestowany i zdany przez mój system automatycznych testów.

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

Oto podstawowa implementacja segmentu linii w języku C # z odpowiednim kodem wykrywania skrzyżowań. Wymaga wywołania struktury wektorowej / punktowej 2D Vector2f, choć można ją zastąpić dowolnym innym typem, który ma właściwości X / Y. Można również wymienić floatze doublejeśli który odpowiada Twoim potrzebom lepiej.

Ten kod jest używany w mojej bibliotece fizyki .NET, Boing .

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

Program C ++ do sprawdzania, czy przecinają się dwa podane segmenty linii

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

Na podstawie odpowiedzi @Gareth Rees, wersja dla 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

Jeśli każda strona prostokąta jest segmentem linii, a część narysowana przez użytkownika jest segmentem linii, musisz po prostu sprawdzić segment narysowany przez użytkownika pod kątem przecięcia z czterema segmentami linii bocznej. Powinno to być dość proste ćwiczenie, biorąc pod uwagę punkty początkowe i końcowe każdego segmentu.

Na podstawie odpowiedzi 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);
}

Algorytm czytam z książki „geometria wielu widoków”

następujący tekst za pomocą

„jako znak transpozycji

* jako produkt kropkowy

x jako produkt krzyżowy, gdy jest używany jako operator

1. definicja linii

punkt x_vec = (x, y) 'leży na linii ax + o + c = 0

oznaczamy L = (a, b, c) ', punkt jako (x, y, 1)' jako współrzędne jednorodne

równanie liniowe można zapisać jako

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

2. przecięcie linii

mamy dwie linie L1 = (a1, b1, c1) ', L2 = (a2, b2, c2)'

załóżmy, że x jest punktem, wektorem, a x = L1 x L2 (iloczyn L1 L2).

bądź ostrożny, x jest zawsze punktem 2D, przeczytaj jednorodne współrzędne, jeśli się mylisz (L1xL2) to wektor trzech elementów, a x to współrzędne 2D.

według potrójnego produktu wiemy o tym

L1 * (L1 x L2) = 0, a L2 * (L1 x L2) = 0, ze względu na współpłaszczyznę L1, L2

podstawiamy (L1xL2) wektorem x, a następnie mamy L1 * x = 0, L2 * x = 0, co oznacza, że ​​x leży zarówno na L1, jak i L2, x jest punktem przecięcia.

uważaj, tutaj x jest jednorodnymi współrzędnymi, jeśli ostatni element x wynosi zero, oznacza to, że L1 i L2 są równoległe.

Wiele odpowiedzi zawarło wszystkie obliczenia w jednej funkcji. Jeśli musisz obliczyć nachylenie linii, przecięcia y lub przecięcia x do użycia w innym miejscu w kodzie, będziesz wykonywać te obliczenia nadmiarowo. Wyodrębniłem odpowiednie funkcje, użyłem oczywistych nazw zmiennych i skomentowałem mój kod, aby ułatwić śledzenie. Musiałem wiedzieć, czy linie przecinają się nieskończenie poza ich punktami końcowymi, więc w 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
  };
}