How to find where two lines intersect using numpy.linalg.solve given points coordinates?

Question

So I'm trying to use numpy.linalg.solve() to find where two lines intersect with each other using only some endpoints coordinates. If the coordinates of one lines are: (x1, y1), (x2, y2). I tried:

import numpy as np
a = np.array([[y2-y1],[x1-x2]])
b = np.array([(x1*y2)-(y1*x2)])

np.linalg.solve(a,b)

However I don't think the equations are correct and it is returning the following error:

numpy.linalg.LinAlgError: Last 2 dimensions of the array must be square

so I'm not really sure what to do, can someone help me with this?

I am not sure that you use `np.linalg.solve` correctly. Reading the docs (https://numpy.org/doc/stable/reference/generated/numpy.linalg.solve.html), it says that it receives a matrix, and an output vector, and solves the linear equation. If I have a matrix `A`, and a vector `b`, and I look for the vector `x` which satisfies `A*x=b`, then the solution is `np.linalg.solve(A,b)`. I try to figure out from your explanation what `x1, y1, x2, y2` mean. Please explain this again, more accurately. — yonatansc97, Dec 04 '20 at 12:20

Yacola · Accepted Answer · 2020-12-04T15:43:07.940

Following these answers which gives clear explanations about the equations behind this problem and its well-known analytical resolution (based on Cramer's rule and determinants), it is possible to construct a simple linear system A x = b in order to use np.linalg.solve as requested:

import numpy as np

# Given these endpoints coordinates
# Line 1 passing through points p1 (x1,y1) and p2 (x2,y2)
p1 = [0, 0]
p2 = [1, 1]

# Line 2 passing through points p3 (x3,y3) and p4 (x4,y4)
p3 = [0, 1]
p4 = [1, 0]

# Line 1 dy, dx and determinant
a11 = (p1[1] - p2[1])
a12 = (p2[0] - p1[0])
b1 = (p1[0]*p2[1] - p2[0]*p1[1])

# Line 2 dy, dx and determinant
a21 = (p3[1] - p4[1])
a22 = (p4[0] - p3[0])
b2 = (p3[0]*p4[1] - p4[0]*p3[1])

# Construction of the linear system
# coefficient matrix
A = np.array([[a11, a12],
              [a21, a22]])

# right hand side vector
b = -np.array([b1,
               b2])
# solve
try:
    intersection_point = np.linalg.solve(A,b)
    print('Intersection point detected at:', intersection_point)
except np.linalg.LinAlgError:
    print('No single intersection point detected')

which gives the intended output for those given points:

>>> Intersection point detected at: [0.5 0.5]

How to find where two lines intersect using numpy.linalg.solve given points coordinates?

1 Answers1