Jak obliczyć punkt przecięcia dwóch linii w Pythonie?

Mam dwie linie, które przecinają się w punkcie. Znam punkty końcowe obu linii. Jak obliczyć punkt przecięcia w Pythonie?

# Given these endpoints
#line 1
A = [X, Y]
B = [X, Y]

#line 2
C = [X, Y]
D = [X, Y]

# Compute this:
point_of_intersection = [X, Y]
Author: Jeffrey Bosboom, 2013-12-19
Source

4 answers

W przeciwieństwie do innych sugestii, jest krótki i nie używa zewnętrznych bibliotek, takich jak numpy. (Nie to, że korzystanie z innych bibliotek jest bad...it miło, że nie trzeba, szczególnie w przypadku tak prostego problemu.)

def line_intersection(line1, line2):
    xdiff = (line1[0][0] - line1[1][0], line2[0][0] - line2[1][0])
    ydiff = (line1[0][1] - line1[1][1], line2[0][1] - line2[1][1]) #Typo was here

    def det(a, b):
        return a[0] * b[1] - a[1] * b[0]

    div = det(xdiff, ydiff)
    if div == 0:
       raise Exception('lines do not intersect')

    d = (det(*line1), det(*line2))
    x = det(d, xdiff) / div
    y = det(d, ydiff) / div
    return x, y

print line_intersection((A, B), (C, D))

I dla twojej informacji, użyłbym krotek zamiast list dla Twoich punktów. Np. 

A = (X, Y)
 28
Author: Paul Draper,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-09-12 21:45:16

Can ' t stand away,

Mamy więc układ liniowy:

A1 * x + B1 * y = C1
A2 * x + B2 * y = C2

Zróbmy to z regułą Cramera, więc rozwiązanie można znaleźć w wyznacznikach:

X = Dx / D
y = dy / D

Gdzie D jest głównym wyznacznikiem układu:

A 1 B1
A2 B2

I D x i D y można znaleźć na stronach maturalnych:

C1 B1
C2 B2

I

A1 C1
A2 C2

(Uwaga, jako C kolumna w konsekwencji zastępuje coef. kolumny x oraz y )

Więc teraz python, dla jasności dla nas, aby nie zepsuć rzeczy, zróbmy mapowanie między math i python. Będziemy używać tablicy L do przechowywania naszych coefów A, B, C równań liniowych i x, y będziemy mieli [0], [1], ale w każdym razie. Tak więc to, co napisałem powyżej, będzie miało następującą postać dalej w kodzie:

DlaD

L1 [0] L1 [1]
L2[0] L2[1]

Dla D x

L1 [2] L1[1]
L2 [2] L2[1]

Dla D y

L1 [0] L1 [2]
L2[0] L2[2]

Teraz przejdź do kodowania:

line - produkuje coefs A, B, C równania liniowego o dwa punkty podane,
intersection - znajduje punkt przecięcia (jeśli występuje) dwóch linii dostarczonych przez coefs.

from __future__ import division 

def line(p1, p2):
    A = (p1[1] - p2[1])
    B = (p2[0] - p1[0])
    C = (p1[0]*p2[1] - p2[0]*p1[1])
    return A, B, -C

def intersection(L1, L2):
    D  = L1[0] * L2[1] - L1[1] * L2[0]
    Dx = L1[2] * L2[1] - L1[1] * L2[2]
    Dy = L1[0] * L2[2] - L1[2] * L2[0]
    if D != 0:
        x = Dx / D
        y = Dy / D
        return x,y
    else:
        return False

Przykład użycia: 

L1 = line([0,1], [2,3])
L2 = line([2,3], [0,4])

R = intersection(L1, L2)
if R:
    print "Intersection detected:", R
else:
    print "No single intersection point detected"
 43
Author: rook,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-12-19 10:46:47

Nie znalazłem intuicyjnego wyjaśnienia w Internecie, więc teraz, gdy to rozgryzłem, oto moje rozwiązanie. To jest dla nieskończonych linii (czego potrzebowałem), a nie segmentów.

Niektóre terminy, które możesz zapamiętać:

Linia jest zdefiniowana jako y = mx + b lub y = slope * x + y-intercept

Nachylenie = wzrost nad biegiem = dy / dx = wysokość / odległość

Y-intercept to miejsce, w którym linia przecina oś Y, gdzie X = 0

Biorąc pod uwagę te definicje, oto kilka funkcje: 

def slope(P1, P2):
    # dy/dx
    # (y2 - y1) / (x2 - x1)
    return(P2[1] - P1[1]) / (P2[0] - P1[0])

def y_intercept(P1, slope):
    # y = mx + b
    # b = y - mx
    # b = P1[1] - slope * P1[0]
    return P1[1] - slope * P1[0]

def line_intersect(m1, b1, m2, b2):
    if m1 == m2:
        print ("These lines are parallel!!!")
        return None
    # y = mx + b
    # Set both lines equal to find the intersection point in the x direction
    # m1 * x + b1 = m2 * x + b2
    # m1 * x - m2 * x = b2 - b1
    # x * (m1 - m2) = b2 - b1
    # x = (b2 - b1) / (m1 - m2)
    x = (b2 - b1) / (m1 - m2)
    # Now solve for y -- use either line, because they are equal here
    # y = mx + b
    y = m1 * x + b1
    return x,y

Oto prosty test między dwoma (nieskończonymi) liniami: 

A1 = [1,1]
A2 = [3,3]
B1 = [1,3]
B2 = [3,1]
slope_A = slope(A1, A2)
slope_B = slope(B1, B2)
y_int_A = y_intercept(A1, slope_A)
y_int_B = y_intercept(B1, slope_B)
print(line_intersect(slope_A, y_int_A, slope_B, y_int_B))

Wyjście: 

(2.0, 2.0)
 1
Author: Kiki Jewell,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-09-18 21:50:17

Używając formuły z: https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection 

 def findIntersection(x1,y1,x2,y2,x3,y3,x4,y4):
        px= ( (x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4) ) / ( (x1-x2)*(y3-y4)-(y1-y2)*(x3-x4) ) 
        py= ( (x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4) ) / ( (x1-x2)*(y3-y4)-(y1-y2)*(x3-x4) )
        return [px, py]
 1
Author: Gabriel Eng,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-07-01 23:31:52