1

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?

Yacola
  • 2,873
  • 1
  • 10
  • 27
soap and butter sandwhich
  • 29
  • 1
  • 7
  • 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

2 Answers2

3

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]
Yacola
  • 2,873
  • 1
  • 10
  • 27
0
import numpy as np

data = np.array([
    #  segment1               segment2
    # [[x1, y1], [x2, y2]],  [[x1, y1], [x2, y2]]
    [[0, 0], [1, 1], [0, 1], [1, 0]],
    [[0, 0], [1, 1], [1, 0], [1, 1]],
    [(0, 1), (0, 2), (1, 10), (2, 10)],
    [(0, 1), (1, 2), (0, 10), (1, 9)],
    [[0, 0], [0, 1], [0, 2], [1, 3]],
    [[0, 1], [2, 3], [4, 5], [6, 7]],  
    [[1, 2], [3, 4], [5, 6], [7, 8]],
])

def intersect(data):
    L = len(data)
    x1, y1, x2, y2 = data.reshape(L * 2, -1).T
    R = np.full([L, 2], np.nan)
    X = np.concatenate([
        (y2 - y1).reshape(L * 2, -1), 
        (x1 - x2).reshape(L * 2, -1)], 
        axis=1
    ).reshape(L, 2, 2)
    B = (x1 * y2 - x2 * y1).reshape(L, 2)
    I = np.isfinite(np.linalg.cond(X))
    R[I] = np.matmul(np.linalg.inv(X[I]), B[I][:,:,None]).squeeze(-1)
    return R

intersect(data)

array([[ 0.5,  0.5],
       [ 1. ,  1. ],
       [ 0. , 10. ],
       [ 4.5,  5.5],
       [ 0. ,  2. ],
       [ nan,  nan],
       [ nan,  nan]])
xmduhan
  • 965
  • 12
  • 14