How do I compute the intersection point of two lines in Python?

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]

Are these line segments, or lines?
– user2357112
Dec 19 '13 at 9:31

This problem mostly boils down to "do the math". You can use algebraic manipulation to find an expression for the coordinates of the intersection, then insert that expression into your program. Remember to check for parallel lines first, though.
– user2357112
Dec 19 '13 at 9:33

Search stackoverflow before ask a question : [the answer][1] [1]: stackoverflow.com/questions/3252194/…
– Cao Manh Dat
Dec 19 '13 at 9:33

“I know how to do this on paper” — Then what exactly is your problem? It’s pure math which you need to apply here. And Python is your calculator. What have you tried?
– poke
Dec 19 '13 at 9:34

possible duplicate of How can I check if two segments intersect?
– Jerry Coffin
Dec 19 '13 at 9:43

4 Answers
4

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

numpy

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]) #Typo was here 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)

This solution yields (1.0, 2.0) for intersecting line_intersection(((0.5, 0.5), (1.5, 0.5)), ((1, 0), (1, 2))), which should be (1, 0.5).
– xtofl
Aug 11 '14 at 1:14

line_intersection(((0.5, 0.5), (1.5, 0.5)), ((1, 0), (1, 2)))

This works, thanks :)
– Mehdi
Aug 28 '15 at 12:19

I have to agree with @xtofl - this doesn't work. I get false positives and negatives.
– rbaleksandar
Sep 8 '16 at 12:57

Î would also avoid using exceptions here. A simple False would do and it's not as expensive as handling an exception.
– rbaleksandar
Sep 8 '16 at 13:12

False

This solution doesn't work for points that intersect at (0.,0.)
– Lee
Feb 23 '17 at 15:58

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:

L

x

y

[0]

[1]

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.

line

intersection

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"

Works well, very fast
– Alex Black
Jun 20 '16 at 0:00

This solution reports intersection where the lines COULD intersect given they have eternal lengths.
– firelynx
Sep 26 '16 at 14:18

@firelynx I think you are confusing the term line with line segment. The OP asks for a line intersection (on purpose or due to not understanding the difference). When checking lines for intersections on has to take into account the fact that lines are infinite that is the rays that start from its midpoint (defined by the given coordinates of the two points that define it) in both directions. In a case of line segment intersection only the part of the line between the given points is checked for intersection and its infinite continuation is ignored.
– rbaleksandar
Oct 16 '16 at 13:29

Btw how about coinciding lines? Using the algorithm above it returns true for two coinciding lines which can obviously not return a single point of intersection (since mathematically speaking there are infinite number of intersection points for this case). I think that the algorithms needs to handle this in a separate case since simply intersecting and coinciding lines are two very different cases.
– rbaleksandar
Nov 8 '16 at 15:19

true

Yes @rbaleksandar, with this method - when R is true (D != 0) we can say only about intersecting lines. All other cases for R (when D == 0) can mean anything except intersecting (coinciding or parallel) lines.
– rook
Nov 10 '16 at 16:30

R

true

D != 0

R

D == 0

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]

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)

You may want to try this with these points: A1 = [1,1] A2 = [1,3] B1 = [1,3] B2 = [3,1]
– Charlie Burns
Nov 21 '17 at 22:19

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

搜尋此網誌

Gtjkyu