Jak mogę sprawdzić, czy dwa segmenty się przecinają?

Jak mogę sprawdzić, czy przecinają się 2 segmenty?

Mam następujące dane:

Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ] 

Muszę napisać mały algorytm w Pythonie, aby wykryć, czy te 2 linie się przecinają.

Równanie prostej to:

f(x) = A*x + b = y

W przypadku odcinka jest dokładnie to samo, z wyjątkiem tego, że x jest zawarte w przedziale I.

Jeśli masz dwa segmenty, zdefiniowane w następujący sposób:

Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}

Abcisse Xa potencjalnego punktu przecięcia (Xa, Ya) musi znajdować się zarówno w przedziale I1, jak i I2, zdefiniowanym następująco:

I1 = [min(X1,X2), max(X1,X2)]
I2 = [min(X3,X4), max(X3,X4)]

I możemy powiedzieć, że Xa jest zawarty w:

Ia = [max( min(X1,X2), min(X3,X4) ),
      min( max(X1,X2), max(X3,X4) )]

Teraz musimy sprawdzić, czy istnieje ten przedział Ia:

if (max(X1,X2) < min(X3,X4)):
    return False  # There is no mutual abcisses

Mamy więc formułę dwuwierszową i wzajemny interwał. Twoje formuły linii to:

f1(x) = A1*x + b1 = y
f2(x) = A2*x + b2 = y

Ponieważ mamy dwa punkty po segmencie, jesteśmy w stanie określić A1, A2, b1 i b2:

A1 = (Y1-Y2)/(X1-X2)  # Pay attention to not dividing by zero
A2 = (Y3-Y4)/(X3-X4)  # Pay attention to not dividing by zero
b1 = Y1-A1*X1 = Y2-A1*X2
b2 = Y3-A2*X3 = Y4-A2*X4

Jeśli segmenty są równoległe, to A1 == A2:

if (A1 == A2):
    return False  # Parallel segments

Punkt (Xa, Ya) stojący na obu liniach musi weryfikować oba wzory f1 i f2:

Ya = A1 * Xa + b1
Ya = A2 * Xa + b2
A1 * Xa + b1 = A2 * Xa + b2
Xa = (b2 - b1) / (A1 - A2)   # Once again, pay attention to not dividing by zero

Ostatnią rzeczą do zrobienia jest sprawdzenie, czy Xa jest uwzględniony w Ia:

if ( (Xa < max( min(X1,X2), min(X3,X4) )) or
     (Xa > min( max(X1,X2), max(X3,X4) )) ):
    return False  # intersection is out of bound
else:
    return True

Oprócz tego możesz sprawdzić podczas uruchamiania, czy dwa z czterech podanych punktów nie są równe, aby uniknąć wszystkich testów.

User @ i_4_got wskazuje na tę stronę z bardzo wydajnym rozwiązaniem w Pythonie. Powielam go tutaj dla wygody (ponieważ byłbym szczęśliwy, gdyby go tutaj miałem):

def ccw(A,B,C):
    return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)

# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

Nie musisz dokładnie obliczać, gdzie przecinają się segmenty, ale tylko zrozumieć, czy w ogóle się przecinają. Uprości to rozwiązanie.

Pomysł polega na potraktowaniu jednego segmentu jako „kotwicy” i podzieleniu drugiego segmentu na 2 punkty.
Teraz będziesz musiał znaleźć względne położenie każdego punktu względem „zakotwiczonego” segmentu (OnLeft, OnRight lub Collinear).
Po wykonaniu tej czynności dla obu punktów sprawdź, czy jeden z punktów jest Po lewej stronie, a drugi po prawej (lub może uwzględnij położenie współliniowe, jeśli chcesz uwzględnić również niewłaściwe skrzyżowania).

Następnie musisz powtórzyć ten proces z rolami kotwicy i oddzielnych segmentów.

Przecięcie istnieje wtedy i tylko wtedy, gdy jeden z punktów to OnLeft, a drugi to OnRight. Zobacz ten link, aby uzyskać bardziej szczegółowe wyjaśnienie z przykładowymi obrazami dla każdego możliwego przypadku.

Wdrożenie takiej metody będzie znacznie łatwiejsze niż faktyczne wdrożenie metody znajdującej punkt przecięcia (biorąc pod uwagę wiele przypadków narożnych, z którymi również będziesz musiał sobie poradzić).

Aktualizacja

Poniższe funkcje powinny zilustrować ten pomysł (źródło: Computational Geometry in C ).
Uwaga: ten przykład zakłada użycie liczb całkowitych. Jeśli zamiast tego używasz jakiejś reprezentacji zmiennoprzecinkowej (co oczywiście może skomplikować sprawę), powinieneś określić jakąś wartość epsilon, aby wskazać „równość” (głównie do IsCollinearoceny).

// points "a" and "b" forms the anchored segment.
// point "c" is the evaluated point
bool IsOnLeft(Point a, Point b, Point c)
{
     return Area2(a, b, c) > 0;
}

bool IsOnRight(Point a, Point b, Point c)
{
     return Area2(a, b, c) < 0;
}

bool IsCollinear(Point a, Point b, Point c)
{
     return Area2(a, b, c) == 0;
}

// calculates the triangle's size (formed by the "anchor" segment and additional point)
int Area2(Point a, Point b, Point c)
{
     return (b.X - a.X) * (c.Y - a.Y) -
            (c.X - a.X) * (b.Y - a.Y);
}

Oczywiście podczas korzystania z tych funkcji należy pamiętać o sprawdzeniu, czy każdy segment leży „pomiędzy” innym segmentem (ponieważ są to segmenty skończone, a nie nieskończone linie).

Ponadto, korzystając z tych funkcji, możesz zrozumieć, czy masz właściwe, czy niewłaściwe skrzyżowanie.

• Poprawnie : nie ma punktów współliniowych. Segmenty przecinają się „z boku na bok”.
• Niewłaściwe : jeden segment tylko „styka się” z drugim (co najmniej jeden z punktów jest współliniowy z zakotwiczonym segmentem).

Załóżmy, że te dwa segmenty mają punkty końcowe A, B i C, D. Niezawodnym numerycznie sposobem określenia przecięcia jest sprawdzenie znaku czterech wyznaczników:

| Ax-Cx  Bx-Cx |    | Ax-Dx  Bx-Dx |
| Ay-Cy  By-Cy |    | Ay-Dy  By-Dy |

| Cx-Ax  Dx-Ax |    | Cx-Bx  Dx-Bx |
| Cy-Ay  Dy-Ay |    | Cy-By  Dy-By |

W przypadku przecięcia każdy wyznacznik po lewej stronie musi mieć znak przeciwny do znaku znajdującego się po prawej stronie, ale między dwiema liniami nie musi istnieć żadna relacja. Zasadniczo sprawdzasz każdy punkt segmentu z innym segmentem, aby upewnić się, że leżą po przeciwnych stronach linii zdefiniowanej przez inny segment.

Zobacz tutaj: http://www.cs.cmu.edu/~quake/robust.html

Sprawdzenie, czy odcinki linii przecinają się jest bardzo łatwe dzięki bibliotece Shapely przy użyciu intersectsmetody:

from shapely.geometry import LineString

line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 0)])
print(line.intersects(other))
# True

line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 2)])
print(line.intersects(other))
# False

Na podstawie Liran za and Grumdrig za doskonałe odpowiedzi tutaj jest kompletny kod Pythona, aby sprawdzić, czy zamknięte odcinki przecinają. Działa dla segmentów współliniowych, segmentów równoległych do osi Y, segmentów zdegenerowanych (diabeł jest w szczegółach). Zakłada współrzędne całkowite. Współrzędne zmiennoprzecinkowe wymagają modyfikacji testu równości punktów.

def side(a,b,c):
    """ Returns a position of the point c relative to the line going through a and b
        Points a, b are expected to be different
    """
    d = (c[1]-a[1])*(b[0]-a[0]) - (b[1]-a[1])*(c[0]-a[0])
    return 1 if d > 0 else (-1 if d < 0 else 0)

def is_point_in_closed_segment(a, b, c):
    """ Returns True if c is inside closed segment, False otherwise.
        a, b, c are expected to be collinear
    """
    if a[0] < b[0]:
        return a[0] <= c[0] and c[0] <= b[0]
    if b[0] < a[0]:
        return b[0] <= c[0] and c[0] <= a[0]

    if a[1] < b[1]:
        return a[1] <= c[1] and c[1] <= b[1]
    if b[1] < a[1]:
        return b[1] <= c[1] and c[1] <= a[1]

    return a[0] == c[0] and a[1] == c[1]

#
def closed_segment_intersect(a,b,c,d):
    """ Verifies if closed segments a, b, c, d do intersect.
    """
    if a == b:
        return a == c or a == d
    if c == d:
        return c == a or c == b

    s1 = side(a,b,c)
    s2 = side(a,b,d)

    # All points are collinear
    if s1 == 0 and s2 == 0:
        return \
            is_point_in_closed_segment(a, b, c) or is_point_in_closed_segment(a, b, d) or \
            is_point_in_closed_segment(c, d, a) or is_point_in_closed_segment(c, d, b)

    # No touching and on the same side
    if s1 and s1 == s2:
        return False

    s1 = side(c,d,a)
    s2 = side(c,d,b)

    # No touching and on the same side
    if s1 and s1 == s2:
        return False

    return True

Oto rozwiązanie wykorzystujące iloczyn skalarny:

# assumes line segments are stored in the format [(x0,y0),(x1,y1)]
def intersects(s0,s1):
    dx0 = s0[1][0]-s0[0][0]
    dx1 = s1[1][0]-s1[0][0]
    dy0 = s0[1][1]-s0[0][1]
    dy1 = s1[1][1]-s1[0][1]
    p0 = dy1*(s1[1][0]-s0[0][0]) - dx1*(s1[1][1]-s0[0][1])
    p1 = dy1*(s1[1][0]-s0[1][0]) - dx1*(s1[1][1]-s0[1][1])
    p2 = dy0*(s0[1][0]-s1[0][0]) - dx0*(s0[1][1]-s1[0][1])
    p3 = dy0*(s0[1][0]-s1[1][0]) - dx0*(s0[1][1]-s1[1][1])
    return (p0*p1<=0) & (p2*p3<=0)

Oto wizualizacja w Desmos: Przecięcie odcinka linii

Masz dwa odcinki linii. Zdefiniuj jeden segment za pomocą punktów końcowych A i B, a drugi segment za pomocą punktów końcowych C i D. Jest niezła sztuczka, aby pokazać, że muszą się one przecinać W RAMACH granic segmentów. (Zwróć uwagę, że same linie mogą przecinać się poza granicami segmentów, więc musisz być ostrożny. Dobry kod będzie również zwracał uwagę na linie równoległe).

Sztuczka polega na sprawdzeniu, czy punkty A i B muszą leżeć po przeciwnych stronach linii CD ORAZ że punkty C i D muszą leżeć po przeciwnych stronach linii AB.

Ponieważ jest to praca domowa, nie dam ci jednoznacznego rozwiązania. Ale prostym testem, aby zobaczyć, po której stronie linii znajduje się punkt, jest użycie iloczynu skalarnego. Tak więc, dla danej linii CD, oblicz wektor normalny do tej linii (będę go nazywać N_C). Teraz po prostu przetestuj znaki tych dwóch wyników:

dot(A-C,N_C)

i

dot(B-C,N_C)

Jeśli te wyniki mają przeciwne znaki, to A i B są przeciwnymi stronami linii CD. Teraz wykonaj ten sam test dla drugiej linii AB. Ma wektor normalny N_A. Porównaj znaki

dot(C-A,N_A)

i

dot(D-A,N_A)

Zostawię ci, jak obliczyć wektor normalny. (W przypadku 2-d jest to trywialne, ale czy twój kod będzie się martwić o to, czy A i B są odrębnymi punktami? Podobnie, czy C i D są różne?)

Nadal musisz się martwić o segmenty linii, które leżą wzdłuż tej samej nieskończonej linii lub jeśli jeden punkt faktycznie leży na innym odcinku linii. Dobry kod rozwiąże każdy możliwy problem.

Oto kod C do sprawdzenia, czy dwa punkty znajdują się po przeciwnych stronach segmentu linii. Za pomocą tego kodu możesz sprawdzić, czy dwa segmenty również się przecinają.

// true if points p1, p2 lie on the opposite sides of segment s1--s2
bool oppositeSide (Point2f s1, Point2f s2, Point2f p1, Point2f p2) {

//calculate normal to the segment
Point2f vec = s1-s2;
Point2f normal(vec.y, -vec.x); // no need to normalize

// vectors to the points
Point2f v1 = p1-s1;
Point2f v2 = p2-s1;

// compare signs of the projections of v1, v2 onto the normal
float proj1 = v1.dot(normal);
float proj2 = v2.dot(normal);
if (proj1==0 || proj2==0)
        cout<<"collinear points"<<endl;

return(SIGN(proj1) != SIGN(proj2));

}

Oto kolejny kod Pythona, który sprawdza, czy zamknięte segmenty przecinają się. Jest to przepisana wersja kodu C ++ w http://www.cdn.geeksforgeeks.org/check-if-two-given-line-segments-intersect/ . Ta implementacja obejmuje wszystkie szczególne przypadki (np. Wszystkie punkty współliniowe).

def on_segment(p, q, r):
    '''Given three colinear points p, q, r, the function checks if 
    point q lies on line segment "pr"
    '''
    if (q[0] <= max(p[0], r[0]) and q[0] >= min(p[0], r[0]) and
        q[1] <= max(p[1], r[1]) and q[1] >= min(p[1], r[1])):
        return True
    return False

def orientation(p, q, r):
    '''Find orientation of ordered triplet (p, q, r).
    The function returns following values
    0 --> p, q and r are colinear
    1 --> Clockwise
    2 --> Counterclockwise
    '''

    val = ((q[1] - p[1]) * (r[0] - q[0]) - 
            (q[0] - p[0]) * (r[1] - q[1]))
    if val == 0:
        return 0  # colinear
    elif val > 0:
        return 1   # clockwise
    else:
        return 2  # counter-clockwise

def do_intersect(p1, q1, p2, q2):
    '''Main function to check whether the closed line segments p1 - q1 and p2 
       - q2 intersect'''
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)

    # General case
    if (o1 != o2 and o3 != o4):
        return True

    # Special Cases
    # p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if (o1 == 0 and on_segment(p1, p2, q1)):
        return True

    # p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 and on_segment(p1, q2, q1)):
        return True

    # p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 and on_segment(p2, p1, q2)):
        return True

    # p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if (o4 == 0 and on_segment(p2, q1, q2)):
        return True

    return False # Doesn't fall in any of the above cases

Poniżej znajduje się funkcja testowa, która sprawdza, czy działa.

import matplotlib.pyplot as plt

def test_intersect_func():
    p1 = (1, 1)
    q1 = (10, 1)
    p2 = (1, 2)
    q2 = (10, 2)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

    p1 = (10, 0)
    q1 = (0, 10)
    p2 = (0, 0)
    q2 = (10, 10)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

    p1 = (-5, -5)
    q1 = (0, 0)
    p2 = (1, 1)
    q2 = (10, 10)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

    p1 = (0, 0)
    q1 = (1, 1)
    p2 = (1, 1)
    q2 = (10, 10)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

w przypadku segmentów AB i CD znajdź nachylenie CD

slope=(Dy-Cy)/(Dx-Cx)

rozciągnij CD na A i B i zmierz odległość do CD idąc prosto w górę

dist1=slope*(Cx-Ax)+Ay-Cy
dist2=slope*(Dx-Ax)+Ay-Dy

sprawdź, czy są po przeciwnych stronach

return dist1*dist2<0

Ponieważ nie wspominasz, że chcesz znaleźć punkt przecięcia prostej, problem staje się prostszy do rozwiązania. Jeśli potrzebujesz punktu przecięcia, odpowiedź OMG_peanuts jest szybszym podejściem. Jeśli jednak chcesz tylko sprawdzić, czy linie się przecinają, czy nie, możesz to zrobić, używając równania linii (ax + by + c = 0). Podejście jest następujące:

1. Zacznijmy od dwóch odcinków linii: odcinka 1 i odcinka 2.

   segment1 = [[x1,y1], [x2,y2]]
   segment2 = [[x3,y3], [x4,y4]]
   

2. Sprawdź, czy dwa segmenty linii są liniami o niezerowej długości i odrębnymi segmentami.

3. Odtąd zakładam, że te dwa segmenty mają niezerową długość i są różne. Dla każdego odcinka prostej obliczyć nachylenie prostej, a następnie uzyskać równanie prostej w postaci ax + by + c = 0. Teraz oblicz wartość f = ax + by + c dla dwóch punktów inny odcinek linii (powtórz to również dla drugiego odcinka linii).

   a2 = (y3-y4)/(x3-x4);
   b1 = -1;
   b2 = -1;
   c1 = y1 - a1*x1;
   c2 = y3 - a2*x3;
   // using the sign function from numpy
   f1_1 = sign(a1*x3 + b1*y3 + c1);
   f1_2 = sign(a1*x4 + b1*y4 + c1);
   f2_1 = sign(a2*x1 + b2*y1 + c2);
   f2_2 = sign(a2*x2 + b2*y2 + c2);
   

4. Teraz pozostały tylko różne przypadki. Jeśli f = 0 dla dowolnego punktu, to dwie linie stykają się w punkcie. Jeśli f1_1 i f1_2 są równe lub f2_1 i f2_2 są równe, to proste nie przecinają się. Jeśli f1_1 i f1_2 są nierówne, a f2_1 i f2_2 są nierówne, to odcinki linii się przecinają. W zależności od tego, czy chcesz traktować stykające się linie jako „przecinające się”, czy nie, możesz dostosować swoje warunki.

Możemy również rozwiązać ten problem za pomocą wektorów.

Zdefiniujmy segmenty jako [start, end]. Biorąc pod uwagę dwa takie segmenty [A, B]i [C, D]oba mają niezerową długość, możemy wybrać jeden z punktów końcowych, który zostanie użyty jako punkt odniesienia, aby otrzymać trzy wektory:

x = 0
y = 1
p = A-C = [C[x]-A[x], C[y]-A[y]]
q = B-A = [B[x]-A[x], B[y]-A[y]]
r = D-C = [D[x]-C[x], D[y]-C[y]]

Stamtąd możemy szukać przecięcia, obliczając t i u in p + t*r = u*q. Po odrobinie zabawy z równaniem otrzymujemy:

t = (q[y]*p[x] - q[x]*p[y])/(q[x]*r[y] - q[y]*r[x])
u = (p[x] + t*r[x])/q[x]

Zatem funkcja jest taka:

def intersects(a, b):
    p = [b[0][0]-a[0][0], b[0][1]-a[0][1]]
    q = [a[1][0]-a[0][0], a[1][1]-a[0][1]]
    r = [b[1][0]-b[0][0], b[1][1]-b[0][1]]

    t = (q[1]*p[0] - q[0]*p[1])/(q[0]*r[1] - q[1]*r[0]) \
        if (q[0]*r[1] - q[1]*r[0]) != 0 \
        else (q[1]*p[0] - q[0]*p[1])
    u = (p[0] + t*r[0])/q[0] \
        if q[0] != 0 \
        else (p[1] + t*r[1])/q[1]

    return t >= 0 and t <= 1 and u >= 0 and u <= 1

To jest mój sposób na sprawdzenie, czy nie przecinają się linie i gdzie następuje przecięcie. Użyjmy od x1 do x4 i od y1 do y4

Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}

Następnie potrzebujemy wektorów do ich reprezentacji

dx1 = X2 - X1
dx2 = X4 - X4
dy1 = Y2 - Y1
dy2 = Y4 - Y3

Teraz spójrzmy na wyznacznik

det = dx1 * dy2 - dx2 * dy1

Jeśli wyznacznik wynosi 0,0, to odcinki linii są równoległe. Może to oznaczać, że się pokrywają. Jeśli nakładają się tylko w punktach końcowych, istnieje jedno rozwiązanie skrzyżowania. W przeciwnym razie będą nieskończone rozwiązania. Przy nieskończenie wielu rozwiązaniach, jaki jest twój punkt przecięcia? Jest to więc interesujący przypadek specjalny. Jeśli wiesz z wyprzedzeniem, że linie nie mogą się pokrywać, możesz po prostu sprawdzić, det == 0.0czy tak jest, a jeśli tak, po prostu powiedz, że się nie przecinają i gotowe. W przeciwnym razie kontynuujmy

dx3 = X3 - X1
dy3 = Y3 - Y1

det1 = dx1 * dy3 - dx3 * dy1
det2 = dx2 * dy3 - dx3 * dy2

Teraz, jeśli det, det1 i det2 są równe zero, to twoje linie są współliniowe i mogą się pokrywać. Jeśli det wynosi zero, ale det1 lub det2 nie są, to nie są one współliniowe, ale są równoległe, więc nie ma przecięcia. Więc to, co teraz pozostaje, jeśli det jest równe zero, to problem 1D zamiast 2D. Będziemy musieli sprawdzić jeden z dwóch sposobów, w zależności od tego, czy dx1 wynosi zero, czy nie (abyśmy mogli uniknąć dzielenia przez zero). Jeśli dx1 wynosi zero, po prostu wykonaj tę samą logikę z wartościami y zamiast x poniżej.

s = X3 / dx1
t = X4 / dx1

To oblicza dwa skalery, takie, że jeśli przeskalujemy wektor (dx1, dy1) o s, otrzymamy punkt (x3, y3), a po t otrzymamy (x4, y4). Więc jeśli s lub t jest między 0,0 a 1,0, to punkt 3 lub 4 leży na naszej pierwszej linii. Wartość ujemna oznaczałaby, że punkt znajduje się za początkiem naszego wektora, podczas gdy> 1,0 oznacza, że ​​znajduje się dalej przed końcem naszego wektora. 0,0 oznacza, że ​​jest w (x1, y1), a 1,0 oznacza, że ​​jest w (x2, y2). Jeśli oba s i t są <0,0 lub oba są> 1,0, to nie przecinają się. I to obsługuje specjalny przypadek równoległych linii.

Teraz, jeśli det != 0.0wtedy

s = det1 / det
t = det2 / det
if (s < 0.0 || s > 1.0 || t < 0.0 || t > 1.0)
    return false  // no intersect

Jest to podobne do tego, co robiliśmy powyżej. Teraz, jeśli przejdziemy powyższy test, nasze odcinki linii przecinają się i możemy dość łatwo obliczyć przecięcie w następujący sposób:

Ix = X1 + t * dx1
Iy = Y1 + t * dy1

Jeśli chcesz dokładniej przyjrzeć się temu, co robi matematyka, zapoznaj się z regułą Cramera.

Odpowiedź Georgy jest zdecydowanie najczystsza do wdrożenia. Musiałem to ścigać, ponieważ przykład brycboe, choć również prosty, miał problemy z kolinearnością.

Kod do testowania:

#!/usr/bin/python
#
# Notes on intersection:
#
# https://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/
#
# /programming/3838329/how-can-i-check-if-two-segments-intersect

from shapely.geometry import LineString

class Point:
    def __init__(self,x,y):
        self.x = x
        self.y = y

def ccw(A,B,C):
    return (C.y-A.y)*(B.x-A.x) > (B.y-A.y)*(C.x-A.x)

def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)


def ShapelyIntersect(A,B,C,D):
    return LineString([(A.x,A.y),(B.x,B.y)]).intersects(LineString([(C.x,C.y),(D.x,D.y)]))


a = Point(0,0)
b = Point(0,1)
c = Point(1,1)
d = Point(1,0)

'''
Test points:

b(0,1)   c(1,1)




a(0,0)   d(1,0)
'''

# F
print(intersect(a,b,c,d))

# T
print(intersect(a,c,b,d))
print(intersect(b,d,a,c))
print(intersect(d,b,a,c))

# F
print(intersect(a,d,b,c))

# same end point cases:
print("same end points")
# F - not intersected
print(intersect(a,b,a,d))
# T - This shows as intersected
print(intersect(b,a,a,d))
# F - this does not
print(intersect(b,a,d,a))
# F - this does not
print(intersect(a,b,d,a))

print("same end points, using shapely")
# T
print(ShapelyIntersect(a,b,a,d))
# T
print(ShapelyIntersect(b,a,a,d))
# T
print(ShapelyIntersect(b,a,d,a))
# T
print(ShapelyIntersect(a,b,d,a))

jeśli dane definiują linię, wystarczy udowodnić, że nie są równoległe. Aby to zrobić, możesz obliczyć

alpha = float(y2 - y1) / (x2 - x1).

Jeśli ten współczynnik jest równy dla Linii1 i Linii2, oznacza to, że linie są równoległe. Jeśli nie, oznacza to, że będą się przecinać.

Jeśli są równoległe, musisz udowodnić, że nie są takie same. W tym celu obliczasz

beta = y1 - alpha*x1

Jeśli beta jest taka sama dla Linii1 i Linii2, oznacza to, że przecinają się linie, ponieważ są równe

Jeśli są segmentami, nadal musisz obliczyć alfa i beta, jak opisano powyżej dla każdej linii. Następnie musisz sprawdzić, czy (beta1 - beta2) / (alpha1 - alpha2) jest większe niż Min (x1_line1, x2_line1) i mniejsze niż Max (x1_line1, x2_line1)

Oblicz punkt przecięcia linii leżących na twoich segmentach (oznacza to po prostu rozwiązanie układu równań liniowych), a następnie sprawdź, czy znajduje się między punktem początkowym i końcowym twoich segmentów.

Oto, co mam dla AS3, nie wiem zbyt wiele o Pythonie, ale koncepcja jest

    public function getIntersectingPointF($A:Point, $B:Point, $C:Point, $D:Point):Number {
        var A:Point = $A.clone();
        var B:Point = $B.clone();
        var C:Point = $C.clone();
        var D:Point = $D.clone();
        var f_ab:Number = (D.x - C.x) * (A.y - C.y) - (D.y - C.y) * (A.x - C.x);

        // are lines parallel
        if (f_ab == 0) { return Infinity };

        var f_cd:Number = (B.x - A.x) * (A.y - C.y) - (B.y - A.y) * (A.x - C.x);
        var f_d:Number = (D.y - C.y) * (B.x - A.x) - (D.x - C.x) * (B.y - A.y);
        var f1:Number = f_ab/f_d
        var f2:Number = f_cd / f_d
        if (f1 == Infinity || f1 <= 0 || f1 >= 1) { return Infinity };
        if (f2 == Infinity || f2 <= 0 || f2 >= 1) { return Infinity };
        return f1;
    }

    public function getIntersectingPoint($A:Point, $B:Point, $C:Point, $D:Point):Point
    {
        var f:Number = getIntersectingPointF($A, $B, $C, $D);
        if (f == Infinity || f <= 0 || f >= 1) { return null };

        var retPoint:Point = Point.interpolate($A, $B, 1 - f);
        return retPoint.clone();
    }

Zaimplementowany w JAVA. Jednak wydaje się, że nie działa dla linii współliniowych (czyli odcinków linii, które istnieją wewnątrz siebie L1 (0,0) (10,10) L2 (1,1) (2,2)

public class TestCode
{

  public class Point
  {
    public double x = 0;
    public double y = 0;
    public Point(){}
  }

  public class Line
  {
    public Point p1, p2;
    public Line( double x1, double y1, double x2, double y2) 
    {
      p1 = new Point();
      p2 = new Point();
      p1.x = x1;
      p1.y = y1;
      p2.x = x2;
      p2.y = y2;
    }
  }

  //line segments
  private static Line s1;
  private static Line s2;

  public TestCode()
  {
    s1 = new Line(0,0,0,10);
    s2 = new Line(-1,0,0,10);
  }

  public TestCode(double x1, double y1, 
    double x2, double y2,
    double x3, double y3,
    double x4, double y4)
  {
    s1 = new Line(x1,y1, x2,y2);
    s2 = new Line(x3,y3, x4,y4);
  }

  public static void main(String args[])
  {
     TestCode code  = null;
////////////////////////////
     code = new TestCode(0,0,0,10,
                         0,1,0,5);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,0,10,
                         0,1,0,10);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,10,0,
                         5,0,15,0);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,10,0,
                         0,0,15,0);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }

////////////////////////////
     code = new TestCode(0,0,10,10,
                         1,1,5,5);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,0,10,
                         -1,-1,0,10);
     if( intersect(code) )
     { System.out.println( "OK SLOPE END: INTERSECTS" ); }
     else
     { System.out.println( "ERROR SLOPE END: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(-10,-10,10,10,
                         -10,10,10,-10);
     if( intersect(code) )
     { System.out.println( "OK SLOPE Intersect(0,0): INTERSECTS" ); }
     else
     { System.out.println( "ERROR SLOPE Intersect(0,0): DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(-10,-10,10,10,
                         -3,-2,50,-2);
     if( intersect(code) )
     { System.out.println( "OK SLOPE Line2 VERTIAL: INTERSECTS" ); }
     else
     { System.out.println( "ERROR SLOPE Line2 VERTICAL: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(-10,-10,10,10,
                         50,-2,-3,-2);
     if( intersect(code) )
     { System.out.println( "OK SLOPE Line2 (reversed) VERTIAL: INTERSECTS" ); }
     else
     { System.out.println( "ERROR SLOPE Line2 (reversed) VERTICAL: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,0,10,
                         1,0,1,10);
     if( intersect(code) )
     { System.out.println( "ERROR PARALLEL VERTICAL: INTERSECTS" ); }
     else
     { System.out.println( "OK PARALLEL VERTICAL: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,2,10,2,
                         0,10,10,10);
     if( intersect(code) )
     { System.out.println( "ERROR PARALLEL HORIZONTAL: INTERSECTS" ); }
     else
     { System.out.println( "OK PARALLEL HORIZONTAL: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,10,5,13.75,
                         0,18.75,10,15);
     if( intersect(code) )
     { System.out.println( "ERROR PARALLEL SLOPE=.75: INTERSECTS" ); }
     else
     { System.out.println( "OK PARALLEL SLOPE=.75: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,1,1,
                         2,-1,2,10);
     if( intersect(code) )
     { System.out.println( "ERROR SEPERATE SEGMENTS: INTERSECTS" ); }
     else
     { System.out.println( "OK SEPERATE SEGMENTS: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,1,1,
                         -1,-10,-5,10);
     if( intersect(code) )
     { System.out.println( "ERROR SEPERATE SEGMENTS 2: INTERSECTS" ); }
     else
     { System.out.println( "OK SEPERATE SEGMENTS 2: DO NOT INTERSECT" ); }
  }

  public static boolean intersect( TestCode code )
  {
    return intersect( code.s1, code.s2);
  }

  public static boolean intersect( Line line1, Line line2 )
  {
    double i1min = Math.min(line1.p1.x, line1.p2.x);
    double i1max = Math.max(line1.p1.x, line1.p2.x);
    double i2min = Math.min(line2.p1.x, line2.p2.x);
    double i2max = Math.max(line2.p1.x, line2.p2.x);

    double iamax = Math.max(i1min, i2min);
    double iamin = Math.min(i1max, i2max);

    if( Math.max(line1.p1.x, line1.p2.x) < Math.min(line2.p1.x, line2.p2.x) )
      return false;

    double m1 = (line1.p2.y - line1.p1.y) / (line1.p2.x - line1.p1.x );
    double m2 = (line2.p2.y - line2.p1.y) / (line2.p2.x - line2.p1.x );

    if( m1 == m2 )
        return false;

    //b1 = line1[0][1] - m1 * line1[0][0]
    //b2 = line2[0][1] - m2 * line2[0][0]
    double b1 = line1.p1.y - m1 * line1.p1.x;
    double b2 = line2.p1.y - m2 * line2.p1.x;
    double x1 = (b2 - b1) / (m1 - m2);
    if( (x1 < Math.max(i1min, i2min)) || (x1 > Math.min(i1max, i2max)) )
        return false;
    return true;
  }
}

Jak dotąd wynik jest

ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
OK SLOPE END: INTERSECTS
OK SLOPE Intersect(0,0): INTERSECTS
OK SLOPE Line2 VERTIAL: INTERSECTS
OK SLOPE Line2 (reversed) VERTIAL: INTERSECTS
OK PARALLEL VERTICAL: DO NOT INTERSECT
OK PARALLEL HORIZONTAL: DO NOT INTERSECT
OK PARALLEL SLOPE=.75: DO NOT INTERSECT
OK SEPERATE SEGMENTS: DO NOT INTERSECT
OK SEPERATE SEGMENTS 2: DO NOT INTERSECT

Pomyślałem, że wrzucę fajne rozwiązanie Swift:

struct Pt {
    var x: Double
    var y: Double
}

struct LineSegment {
    var p1: Pt
    var p2: Pt
}

func doLineSegmentsIntersect(ls1: LineSegment, ls2: LineSegment) -> Bool {

    if (ls1.p2.x-ls1.p1.x == 0) { //handle vertical segment1
        if (ls2.p2.x-ls2.p1.x == 0) {
            //both lines are vertical and parallel
            return false
        }

        let x = ls1.p1.x

        let slope2 = (ls2.p2.y-ls2.p1.y)/(ls2.p2.x-ls2.p1.x)
        let c2 = ls2.p1.y-slope2*ls2.p1.x

        let y = x*slope2+c2 // y intersection point

        return (y > ls1.p1.y && x < ls1.p2.y) || (y > ls1.p2.y && y < ls1.p1.y) // check if y is between y1,y2 in segment1
    }

    if (ls2.p2.x-ls2.p1.x == 0) { //handle vertical segment2

        let x = ls2.p1.x

        let slope1 = (ls1.p2.y-ls1.p1.y)/(ls1.p2.x-ls1.p1.x)
        let c1 = ls1.p1.y-slope1*ls1.p1.x

        let y = x*slope1+c1 // y intersection point

        return (y > ls2.p1.y && x < ls2.p2.y) || (y > ls2.p2.y && y < ls2.p1.y) // validate that y is between y1,y2 in segment2

    }

    let slope1 = (ls1.p2.y-ls1.p1.y)/(ls1.p2.x-ls1.p1.x)
    let slope2 = (ls2.p2.y-ls2.p1.y)/(ls2.p2.x-ls2.p1.x)

    if (slope1 == slope2) { //segments are parallel
        return false
    }

    let c1 = ls1.p1.y-slope1*ls1.p1.x
    let c2 = ls2.p1.y-slope2*ls2.p1.x

    let x = (c2-c1)/(slope1-slope2)

    return (((x > ls1.p1.x && x < ls1.p2.x) || (x > ls1.p2.x && x < ls1.p1.x)) &&
        ((x > ls2.p1.x && x < ls2.p2.x) || (x > ls2.p2.x && x < ls2.p1.x)))
    //validate that x is between x1,x2 in both segments

}

Jedno z powyższych rozwiązań zadziałało tak dobrze, że postanowiłem napisać kompletny program demonstracyjny przy użyciu wxPython. Powinieneś móc uruchomić ten program w ten sposób: python " nazwa twojego pliku "

# Click on the window to draw a line.
# The program will tell you if this and the other line intersect.

import wx

class Point:
    def __init__(self, newX, newY):
        self.x = newX
        self.y = newY

app = wx.App()
frame = wx.Frame(None, wx.ID_ANY, "Main")
p1 = Point(90,200)
p2 = Point(150,80)
mp = Point(0,0) # mouse point
highestX = 0


def ccw(A,B,C):
    return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)

# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

def is_intersection(p1, p2, p3, p4):
    return intersect(p1, p2, p3, p4)

def drawIntersection(pc):
    mp2 = Point(highestX, mp.y)
    if is_intersection(p1, p2, mp, mp2):
        pc.DrawText("intersection", 10, 10)
    else:
        pc.DrawText("no intersection", 10, 10)

def do_paint(evt):
    pc = wx.PaintDC(frame)
    pc.DrawLine(p1.x, p1.y, p2.x, p2.y)
    pc.DrawLine(mp.x, mp.y, highestX, mp.y)
    drawIntersection(pc)

def do_left_mouse(evt):
    global mp, highestX
    point = evt.GetPosition()
    mp = Point(point[0], point[1])
    highestX = frame.Size[0]
    frame.Refresh()

frame.Bind(wx.EVT_PAINT, do_paint)
frame.Bind(wx.EVT_LEFT_DOWN, do_left_mouse)
frame.Show()
app.MainLoop()

Korzystając z rozwiązania OMG_Peanuts przetłumaczyłem na SQL. (Funkcja skalarna HANA)

Dzięki OMG_Peanuts, działa świetnie. Używam okrągłej ziemi, ale odległości są małe, więc myślę, że to w porządku.

FUNCTION GA_INTERSECT" ( IN LAT_A1 DOUBLE,
         IN LONG_A1 DOUBLE,
         IN LAT_A2 DOUBLE,
         IN LONG_A2 DOUBLE,
         IN LAT_B1 DOUBLE,
         IN LONG_B1 DOUBLE,
         IN LAT_B2 DOUBLE,
         IN LONG_B2 DOUBLE) 
    
RETURNS RET_DOESINTERSECT DOUBLE
    LANGUAGE SQLSCRIPT
    SQL SECURITY INVOKER AS
BEGIN

    DECLARE MA DOUBLE;
    DECLARE MB DOUBLE;
    DECLARE BA DOUBLE;
    DECLARE BB DOUBLE;
    DECLARE XA DOUBLE;
    DECLARE MAX_MIN_X DOUBLE;
    DECLARE MIN_MAX_X DOUBLE;
    DECLARE DOESINTERSECT INTEGER;
    
    SELECT 1 INTO DOESINTERSECT FROM DUMMY;
    
    IF LAT_A2-LAT_A1 != 0 AND LAT_B2-LAT_B1 != 0 THEN
        SELECT (LONG_A2 - LONG_A1)/(LAT_A2 - LAT_A1) INTO MA FROM DUMMY; 
        SELECT (LONG_B2 - LONG_B1)/(LAT_B2 - LAT_B1) INTO MB FROM DUMMY;
        IF MA = MB THEN
            SELECT 0 INTO DOESINTERSECT FROM DUMMY;
        END IF;
    END IF;
    
    SELECT LONG_A1-MA*LAT_A1 INTO BA FROM DUMMY;
    SELECT LONG_B1-MB*LAT_B1 INTO BB FROM DUMMY;
    SELECT (BB - BA) / (MA - MB) INTO XA FROM DUMMY;
    
    -- Max of Mins
    IF LAT_A1 < LAT_A2 THEN         -- MIN(LAT_A1, LAT_A2) = LAT_A1
        IF LAT_B1 < LAT_B2 THEN        -- MIN(LAT_B1, LAT_B2) = LAT_B1
            IF LAT_A1 > LAT_B1 THEN       -- MAX(LAT_A1, LAT_B1) = LAT_A1
                SELECT LAT_A1 INTO MAX_MIN_X FROM DUMMY;
            ELSE                          -- MAX(LAT_A1, LAT_B1) = LAT_B1
                SELECT LAT_B1 INTO MAX_MIN_X FROM DUMMY;
            END IF;
        ELSEIF LAT_B2 < LAT_B1 THEN   -- MIN(LAT_B1, LAT_B2) = LAT_B2
            IF LAT_A1 > LAT_B2 THEN       -- MAX(LAT_A1, LAT_B2) = LAT_A1
                SELECT LAT_A1 INTO MAX_MIN_X FROM DUMMY;
            ELSE                          -- MAX(LAT_A1, LAT_B2) = LAT_B2
                SELECT LAT_B2 INTO MAX_MIN_X FROM DUMMY;
            END IF;
        END IF;
    ELSEIF LAT_A2 < LAT_A1 THEN     -- MIN(LAT_A1, LAT_A2) = LAT_A2
        IF LAT_B1 < LAT_B2 THEN        -- MIN(LAT_B1, LAT_B2) = LAT_B1
            IF LAT_A2 > LAT_B1 THEN       -- MAX(LAT_A2, LAT_B1) = LAT_A2
                SELECT LAT_A2 INTO MAX_MIN_X FROM DUMMY;
            ELSE                          -- MAX(LAT_A2, LAT_B1) = LAT_B1
                SELECT LAT_B1 INTO MAX_MIN_X FROM DUMMY;
            END IF;
        ELSEIF LAT_B2 < LAT_B1 THEN   -- MIN(LAT_B1, LAT_B2) = LAT_B2
            IF LAT_A2 > LAT_B2 THEN       -- MAX(LAT_A2, LAT_B2) = LAT_A2
                SELECT LAT_A2 INTO MAX_MIN_X FROM DUMMY;
            ELSE                          -- MAX(LAT_A2, LAT_B2) = LAT_B2
                SELECT LAT_B2 INTO MAX_MIN_X FROM DUMMY;
            END IF;
        END IF;
    END IF;
    
    -- Min of Max
    IF LAT_A1 > LAT_A2 THEN         -- MAX(LAT_A1, LAT_A2) = LAT_A1
        IF LAT_B1 > LAT_B2 THEN        -- MAX(LAT_B1, LAT_B2) = LAT_B1
            IF LAT_A1 < LAT_B1 THEN       -- MIN(LAT_A1, LAT_B1) = LAT_A1
                SELECT LAT_A1 INTO MIN_MAX_X FROM DUMMY;
            ELSE                          -- MIN(LAT_A1, LAT_B1) = LAT_B1
                SELECT LAT_B1 INTO MIN_MAX_X FROM DUMMY;
            END IF;
        ELSEIF LAT_B2 > LAT_B1 THEN   -- MAX(LAT_B1, LAT_B2) = LAT_B2
            IF LAT_A1 < LAT_B2 THEN       -- MIN(LAT_A1, LAT_B2) = LAT_A1
                SELECT LAT_A1 INTO MIN_MAX_X FROM DUMMY;
            ELSE                          -- MIN(LAT_A1, LAT_B2) = LAT_B2
                SELECT LAT_B2 INTO MIN_MAX_X FROM DUMMY;
            END IF;
        END IF;
    ELSEIF LAT_A2 > LAT_A1 THEN     -- MAX(LAT_A1, LAT_A2) = LAT_A2
        IF LAT_B1 > LAT_B2 THEN        -- MAX(LAT_B1, LAT_B2) = LAT_B1
            IF LAT_A2 < LAT_B1 THEN       -- MIN(LAT_A2, LAT_B1) = LAT_A2
                SELECT LAT_A2 INTO MIN_MAX_X FROM DUMMY;
            ELSE                          -- MIN(LAT_A2, LAT_B1) = LAT_B1
                SELECT LAT_B1 INTO MIN_MAX_X FROM DUMMY;
            END IF;
        ELSEIF LAT_B2 > LAT_B1 THEN   -- MAX(LAT_B1, LAT_B2) = LAT_B2
            IF LAT_A2 < LAT_B2 THEN       -- MIN(LAT_A2, LAT_B2) = LAT_A2
                SELECT LAT_A2 INTO MIN_MAX_X FROM DUMMY;
            ELSE                          -- MIN(LAT_A2, LAT_B2) = LAT_B2
                SELECT LAT_B2 INTO MIN_MAX_X FROM DUMMY;
            END IF;
        END IF;
    END IF;
        
    
    IF XA < MAX_MIN_X OR
       XA > MIN_MAX_X THEN  
       SELECT 0 INTO DOESINTERSECT FROM DUMMY;
    END IF;
    
    RET_DOESINTERSECT := :DOESINTERSECT;
END;

Rozwiązane, ale nadal dlaczego nie w Pythonie ... :)

def islineintersect(line1, line2):
    i1 = [min(line1[0][0], line1[1][0]), max(line1[0][0], line1[1][0])]
    i2 = [min(line2[0][0], line2[1][0]), max(line2[0][0], line2[1][0])]
    ia = [max(i1[0], i2[0]), min(i1[1], i2[1])]
    if max(line1[0][0], line1[1][0]) < min(line2[0][0], line2[1][0]):
        return False
    m1 = (line1[1][1] - line1[0][1]) * 1. / (line1[1][0] - line1[0][0]) * 1.
    m2 = (line2[1][1] - line2[0][1]) * 1. / (line2[1][0] - line2[0][0]) * 1.
    if m1 == m2:
        return False
    b1 = line1[0][1] - m1 * line1[0][0]
    b2 = line2[0][1] - m2 * line2[0][0]
    x1 = (b2 - b1) / (m1 - m2)
    if (x1 < max(i1[0], i2[0])) or (x1 > min(i1[1], i2[1])):
        return False
    return True

To:

print islineintersect([(15, 20), (100, 200)], [(210, 5), (23, 119)])

Wynik:

True

I to:

print islineintersect([(15, 20), (100, 200)], [(-1, -5), (-5, -5)])

Wynik:

False