# How do I compute the intersection point of two lines?

Each Answer to this Q is separated by one/two green lines.

I have two lines that intersect at a point. I know the endpoints of the two lines. How do I compute the intersection point 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]
``````

Unlike other suggestions, this is short and doesn’t use external libraries like `numpy`. (Not that using other libraries is bad…it’s nice not need to, especially for such a simple 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])

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

And FYI, I would use tuples instead of lists for your points. E.g.

``````A = (X, Y)
``````

EDIT: Initially there was a typo. That was fixed Sept 2014 thanks to @zidik.

This is simply the Python transliteration of the following formula, where the lines are (a1, a2) and (b1, b2) and the intersection is p. (If the denominator is zero, the lines have no unique intersection.)

$\mathbf{p} = \frac{ \begin{vmatrix} \begin{vmatrix}\mathbf{a_1} & \mathbf{a_2}\end{vmatrix} & \mathbf{a_1} - \mathbf{a_2} \\ \begin{vmatrix}\mathbf{b_1} & \mathbf{b_2}\end{vmatrix} & \mathbf{b_1} - \mathbf{b_2} \end{vmatrix} }{\begin{vmatrix}\mathbf{a_1} - \mathbf{a_2} & \mathbf{b_1} - \mathbf{b_2}\end{vmatrix}}$

Can’t stand aside,

So we have linear system:

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

let’s do it with Cramer’s rule, so solution can be found in determinants:

x = Dx/D
y = Dy/D

where D is main determinant of the system:

A1 B1
A2 B2

and Dx and Dy can be found from matricies:

C1 B1
C2 B2

and

A1 C1
A2 C2

(notice, as C column consequently substitues the coef. columns of x and y)

So now the python, for clarity for us, to not mess things up let’s do mapping between math and python. We will use array `L` for storing our coefs A, B, C of the line equations and intestead of pretty `x`, `y` we’ll have `[0]`, `[1]`, but anyway. Thus, what I wrote above will have the following form further in the code:

for D

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

for Dx

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

for Dy

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

Now go for coding:

`line` – produces coefs A, B, C of line equation by two points provided,
`intersection` – finds intersection point (if any) of two lines provided by 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
``````

Usage example:

``````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"
``````

Here is a solution using the Shapely library. Shapely is often used for GIS work, but is built to be useful for computational geometry. I changed your inputs from lists to tuples.

# Problem

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

# Solution

``````import shapely
from shapely.geometry import LineString, Point

line1 = LineString([A, B])
line2 = LineString([C, D])

int_pt = line1.intersection(line2)
point_of_intersection = int_pt.x, int_pt.y

print(point_of_intersection)
``````

Using formula from:
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]
``````

If your lines are multiple points instead, you can use this version.

``````import numpy as np
import matplotlib.pyplot as plt
"""
Sukhbinder
5 April 2017
Based on:
"""

def _rect_inter_inner(x1,x2):
n1=x1.shape[0]-1
n2=x2.shape[0]-1
X1=np.c_[x1[:-1],x1[1:]]
X2=np.c_[x2[:-1],x2[1:]]
S1=np.tile(X1.min(axis=1),(n2,1)).T
S2=np.tile(X2.max(axis=1),(n1,1))
S3=np.tile(X1.max(axis=1),(n2,1)).T
S4=np.tile(X2.min(axis=1),(n1,1))
return S1,S2,S3,S4

def _rectangle_intersection_(x1,y1,x2,y2):
S1,S2,S3,S4=_rect_inter_inner(x1,x2)
S5,S6,S7,S8=_rect_inter_inner(y1,y2)

C1=np.less_equal(S1,S2)
C2=np.greater_equal(S3,S4)
C3=np.less_equal(S5,S6)
C4=np.greater_equal(S7,S8)

ii,jj=np.nonzero(C1 & C2 & C3 & C4)
return ii,jj

def intersection(x1,y1,x2,y2):
"""
INTERSECTIONS Intersections of curves.
Computes the (x,y) locations where two curves intersect.  The curves
can be broken with NaNs or have vertical segments.
usage:
x,y=intersection(x1,y1,x2,y2)
Example:
a, b = 1, 2
phi = np.linspace(3, 10, 100)
x1 = a*phi - b*np.sin(phi)
y1 = a - b*np.cos(phi)
x2=phi
y2=np.sin(phi)+2
x,y=intersection(x1,y1,x2,y2)
plt.plot(x1,y1,c="r")
plt.plot(x2,y2,c="g")
plt.plot(x,y,'*k')
plt.show()
"""
ii,jj=_rectangle_intersection_(x1,y1,x2,y2)
n=len(ii)

dxy1=np.diff(np.c_[x1,y1],axis=0)
dxy2=np.diff(np.c_[x2,y2],axis=0)

T=np.zeros((4,n))
AA=np.zeros((4,4,n))
AA[0:2,2,:]=-1
AA[2:4,3,:]=-1
AA[0::2,0,:]=dxy1[ii,:].T
AA[1::2,1,:]=dxy2[jj,:].T

BB=np.zeros((4,n))
BB[0,:]=-x1[ii].ravel()
BB[1,:]=-x2[jj].ravel()
BB[2,:]=-y1[ii].ravel()
BB[3,:]=-y2[jj].ravel()

for i in range(n):
try:
T[:,i]=np.linalg.solve(AA[:,:,i],BB[:,i])
except:
T[:,i]=np.NaN

in_range= (T[0,:] >=0) & (T[1,:] >=0) & (T[0,:] <=1) & (T[1,:] <=1)

xy0=T[2:,in_range]
xy0=xy0.T
return xy0[:,0],xy0[:,1]

if __name__ == '__main__':

# a piece of a prolate cycloid, and am going to find
a, b = 1, 2
phi = np.linspace(3, 10, 100)
x1 = a*phi - b*np.sin(phi)
y1 = a - b*np.cos(phi)

x2=phi
y2=np.sin(phi)+2
x,y=intersection(x1,y1,x2,y2)
plt.plot(x1,y1,c="r")
plt.plot(x2,y2,c="g")
plt.plot(x,y,'*k')
plt.show()
``````

I didn’t find an intuitive explanation on the web, so now that I worked it out, here’s my solution. This is for infinite lines (what I needed), not segments.

Some terms you might remember:

A line is defined as y = mx + b OR y = slope * x + y-intercept

Slope = rise over run = dy / dx = height / distance

Y-intercept is where the line crosses the Y axis, where X = 0

Given those definitions, here are some functions:

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

Here’s a simple test between two (infinite) lines:

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

Output:

``````(2.0, 2.0)
``````

The most concise solution I have found uses Sympy: https://www.geeksforgeeks.org/python-sympy-line-intersection-method/

``````# import sympy and Point, Line
from sympy import Point, Line

p1, p2, p3 = Point(0, 0), Point(1, 1), Point(7, 7)
l1 = Line(p1, p2)

# using intersection() method
showIntersection = l1.intersection(p3)

print(showIntersection)
``````

img And You can use this kode

``````class Nokta:
def __init__(self,x,y):
self.x=x
self.y=y
class Dogru:
def __init__(self,a,b):
self.a=a
self.b=b

def Kesisim(self,Dogru_b):
x1= self.a.x
x2=self.b.x
x3=Dogru_b.a.x
x4=Dogru_b.b.x
y1= self.a.y
y2=self.b.y
y3=Dogru_b.a.y
y4=Dogru_b.b.y
#Notlardaki denklemleri kulland?m
pay1=((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3))
pay2=((x2-x1) * (y1 - y3) - (y2 - y1) * (x1 - x3))
payda=((y4 - y3) *(x2-x1)-(x4 - x3)*(y2 - y1))

if pay1==0 and pay2==0 and payda==0:
print("DO?RULAR B?RB?R?NE ÇAKI?IKTIR")

elif payda==0:
print("DO?RULAR B?RB?RNE PARALELD?R")
else:
ua=pay1/payda if payda else 0
ub=pay2/payda  if payda else 0
#x ve y buldum
x=x1+ua*(x2-x1)
y=y1+ua*(y2-y1)
print("DO?RULAR {},{} NOKTASINDA KES??T?".format(x,y))
``````

With the scikit-spatial library you can easily do it in the following way:

``````import matplotlib.pyplot as plt

from skspatial.objects import Line

# Define the two lines.
line_1 = Line.from_points([3, -2], [5, 4])
line_2 = Line.from_points([-1, 0], [3, 2])

# Compute the intersection point
intersection_point = line_1.intersect_line(line_2)

# Plot
_, ax = plt.subplots()
line_1.plot_2d(ax, t_1=-2, t_2=3, c="k")
line_2.plot_2d(ax, t_1=-2, t_2=3, c="k")
intersection_point.plot_2d(ax, c="r", s=100)
grid = ax.grid()
``````

there is already an answer that uses formula from Wikipedia but that doesn’t have any check point to check if line segments actually intersect so here you go

``````def line_intersection(a, b, c, d):
t = ((a[0] - c[0]) * (c[1] - d[1]) - (a[1] - c[1]) * (c[0] - d[0])) / ((a[0] - b[0]) * (c[1] - d[1]) - (a[1] - b[1]) * (c[0] - d[0]))
u = ((a[0] - c[0]) * (a[1] - b[1]) - (a[1] - c[1]) * (a[0] - b[0])) / ((a[0] - b[0]) * (c[1] - d[1]) - (a[1] - b[1]) * (c[0] - d[0]))

# check if line actually intersect
if (0 <= t and t <= 1 and 0 <= u and u <= 1):
return [a[0] + t * (b[0] - a[0]), a[1] + t * (b[1] - a[1])]
else:
return False

#usage
print(line_intersection([0,0], [10, 10], [0, 10], [10,0]))

#result [5.0, 5.0]
``````

The answers/resolutions are collected from stackoverflow, are licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0 .