Wie berechne ich den Schnittpunkt zweier Linien in Python?

Question

Ich habe zwei Linien, die sich an einem Punkt schneiden. Ich kenne die Endpunkte der beiden Linien. Wie berechne ich den Schnittpunkt in Python?

# 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] 

Answer 1

Im Gegensatz zu anderen Vorschlägen, das ist kurz und externe Bibliotheken nicht wie numpy verwenden. (Nicht, dass mit anderen Bibliotheken schlecht ist ... es ist schön, nicht müssen, vor allem für ein solches einfaches Problem.)

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

Und FYI, würde ich Tupel statt Listen für Ihre Punkte verwenden. Z.B.

A = (X, Y) 

Answer 2

kann ich nicht beiseite,

So haben wir lineares System:

A * x + B * y = C
A * x + B * y = C

wir tun es mit der Cramerschen Regel, so Lösung kann in Determinanten zu finden:

x = D _x/D
y = D _y/D

wo D Hauptdeterminante des Systems ist:

A B
A B

und D _x und D _y aus Matrizes gefunden werden:

C B
C B

und

A C
A _{C 2}

(Hinweis, wie C Spalte substitues folglich die COEF. Spalten von x und y)

So, jetzt dem Python, für uns aus Gründen der Klarheit Chaos Dinge nicht auf die Zuordnung zwischen Mathematik und Python tun lassen.Wir werden Array verwenden L für unsere coefs Speicherung A, B, C der Liniengleichungen und intestead von ziemlich x, y wir [0] haben werden, [1], aber trotzdem. So, was ich oben geschrieben wird das folgende Formular weiter im Code hat:

für D

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

für D _x

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

für D _y

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

Jetzt gehen zur Codierung:

line - produziert coefs A, B , C der Geradengleichung von zwei Punkten vorgesehen,
intersection - findet Schnittpunkt (falls vorhanden) aus zwei Zeilen von coefs vorgesehen.

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 

Anwendungsbeispiel:

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" 

Answer 3

Ich habe nicht eine intuitive Erklärung, die im Internet finden, so dass ich jetzt es hat geklappt, hier ist meine Lösung. Dies ist für unendliche Linien (was ich brauchte), nicht Segmente.

Einige Begriffe, die Sie erinnern sich vielleicht:

Eine Linie als y definiert ist = mx + b OR y = Steigung * x + y-Schnitt

Steigung = Anstieg über run = dy/dx = Höhe/Entfernung

Y-Schnittpunkt ist, wo die Linie, welche die Y-Achse kreuzt, wobei X = 0

diese Definitionen gegeben, hier sind einige Funktionen sind:

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 

Hier ist ein einfacher Test zwischen zwei (unendlich) Linien:

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

Ausgang:

(2.0, 2.0)