Line-Line Schnittpunkt in Python mit numpy

Question

Ich habe eine relativ einfache Frage, ich kenne die Antwort, aber ich kann nicht scheinen, die richtige Implementierung mit Python und Numpy zu finden. Die Idee ist, ich habe zwei Zeilen und muss den virtuellen Schnittpunkt finden (ich habe das Beispiel aus https://www.youtube.com/watch?v=kCyoaidiXAU&t=313s verwendet).

Beide Linien haben die Form von r = r0 + t * V, mit r0 als Positionsvektor (ein Punkt, den die Linie durchläuft), t eine Variable und V, der Richtungsvektor. Der Richtungsvektor V kann einfach durch Auffinden des Vektors durch beide Punkte der Linie, z. V = A - B.

Damit ist es möglich, die Leitung zu formulieren:
L1 = r0 (bekannten Punkt) + t (unbekannte Variable) * V (Richtungsvektor)

Jetzt kann ich, leicht zu finden t manuell, aber ich habe keine Ahnung, wie ich Python sagen .. Ich versuchte numpy.linalg.solve, aber das gibt mir eine Matrix, während ich einen einzelnen Wert brauche.

Zum Beispiel:

# Line A and Line B that intersect somewhere 
A = LineString([(4., 0.), (4., -3.)]) 
B = LineString([(6., 2.), (10., 2.)]) 

# direction vectors for line A and B 
v1 = (A[0].x - A[1].x, A[0].y, A[1].y) # --> [0,3] 
v2 = (B[0].x - B[1].x, B[0].y, B[1].y) # --> [-4,0] 

L1 = A[1] + x * v1 
L2 = B[1] + y * v2 

Nun, ich dies manuell L1 lösen würde für x durch Lösung:

L1 = [4, 0] + x * [0, 3] = [4, 3x] 
L2 = [6, 2] + y * [-4, 0] = [6-4y, 2] 

# finding intersection point by solving L1 = L2 
4 = 6-4y & 3x = 2 
y = 1/2 & x = 2/3 

Aber ich habe keine Ahnung, wie numpy/Python zu sagen, wie für x zu lösen Andy.

Jede Hilfe oder Anleitung in die richtige Richtung würde sehr geschätzt werden.

Answer 1

Die Linie durch A0 und A1 hat parametrische Gleichung (1-t)*A0 + t*A1, wobei t der Parameter ist. Die Linie durch B0 und B1 hat die Parametergleichung (1-s)*A0 + s*A1, wobei s der Parameter ist. Wenn diese Werte gleich sind, erhalten wir das System (A1-A0)t + (B0-B1)s == B0-A0. Also ist die rechte Seite B0-A0 und die Matrix hat die Spalten A1-A0 und B0-B1. Das System kann mit np.linalg.solve gelöst werden. Komplettes Beispiel:

A = np.array([[4, 0], [4, -3]]) 
B = np.array([[6, 2], [10, 2]]) 
t, s = np.linalg.solve(np.array([A[1]-A[0], B[0]-B[1]]).T, B[0]-A[0]) 
print((1-t)*A[0] + t*A[1]) 
print((1-s)*B[0] + s*B[1]) 

Beiden Druckbefehle Ausgabe [4., 2.] zur Bestätigung der Richtigkeit. (Der zweite Druck es wirklich redundant.)