Find intersection of two lines with four points Python

The aim of this challenge is to write a script that allows the user to input the equation of two straight lines (Line 1: y=ax+b, Line 2: y=cx+d). The program will then calculate the coordinates of the intersection point if such a point exists!

Flowchart

Your Code

Complete your code here, using the steps described on the above flowchart.

Testing

Once your code is complete, you can check it works by completing the following tests:

Using Python Turtle to trace the lines!

The following code uses Python Turtle to trace both lines.

Extension Task

Can you write a computer program that takes the (x,y) coordinates of two different points and calculates the linear equation (y = ax + b) of the straight line joining these two dots.

To do so you will need to:

Retrieve four inputs: x1, y1, x2, y2 (The coordinates of the two points to join)
Calculate the slope of the straight line: a = (y2 – y1) / (x2 – x1)
Calculate b = y1 – ax1
Display the linear equation: y = ax + b

Note that in case of a vertical line (if x1 == x2), you will not be able to calculate the slope a. The equation of your straight line would then be x = x1.

The solution for this challenge is available to full members!Find out how to become a member:

Members Area

Homepage / Discuss / How do I compute the intersection point of two 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?

A = [X, Y] B = [X, Y] C = [X, Y] D = [X, Y] 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.)

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.

A = (X, Y) B = (X, Y) C = (X, Y) D = (X, Y) point_of_intersection = (X, Y) 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)

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, 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): return(P2[1] - P1[1]) / (P2[0] - P1[0]) def y_intercept(P1, slope): return P1[1] - slope * P1[0] def line_intersect(m1, b1, m2, b2): if m1 == m2: print ("These lines are parallel!!!") return None x = (b2 - b1) / (m1 - m2) 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)

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 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=x1+ua*(x2-x1) y=y1+ua*(y2-y1) print("DO?RULAR {},{} NOKTASINDA KES??T?".format(x,y))