How do I compute the intersection point of two lines?

Viewed 186879

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]
10 Answers

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.

enter image description here

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

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

enter image description here

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]
Related