How do I compute the intersection point of two lines?

Question

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]

Answer 1

This is how I’ve gotten the intersection from two lines…

we can use y = mx + b
So we take two lines (x1,y1) for line1 and (x2,y2) for line2
y=m1*(x-x1) + y1
y=m2*(x-x2) + y2

We rearrange the right side to left
y-y1-m1(x-x1) (same for the second equation)

With this we can get the difference of both equations and simplify
y-y1-m1(x-x1) - y+y2+m2(x-x2)=0
-y1-m1x+m1x1 + y2+m2x-m2x2=0
Rearrange to isolate x
m2x-m1x=y1-m1x1-y2+m2x2
Factor
x(m2-m1)=y1-m1x1-y2+m2x2

Finally, divide and you get the intersection
Intersectx=(y1-m1x1-y2+m2x2)(m2-m1)
Intersecty=m1(Intersectx-x1)+y1

Answer 2

The Euclid library should also be mentioned.

See: https://pypi.org/project/euclid/ (october 2023)

The Euclid library, as its name suggests, provides classes to define points, lines, segments, circles, and spheres in 2D and 3D, as well as a set of basic operations and methods for working with them. I found the code of the package to be very readable, which allowed me to easily add my own methods.

The following code finds the intersection of two lines:

>>> from euclid import Line2, Point2
>>> l1  = Line2(Point2(1.0, 2.0), Point2(3.0, 4.0))
>>> l2  = Line2(Point2(3.0, 4.0), Point2(-5.0, 6.0))
>>> l1.intersect(l2)
Point2(3.00, 4.00)

Answer 3

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]

Answer 4

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

Answer 5

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) 

Answer 6

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

Answer 7

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)

Answer 8

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

Answer 9

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

Answer 10

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]

Answer 11

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)

Answer 12

Can't stand aside,

So we have linear system:

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

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

x = D_x/D
y = D_y/D

where D is main determinant of the system:

A₁ B₁
A₂ B₂

and D_x and D_y can be found from matricies:

C₁ B₁
C₂ B₂

and

A₁ C₁
A₂ C₂

(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 D_x

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

for D_y

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"