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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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 kullandim     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  DOGRULAR BIRBIRINE   AKISIKTIR        elif payda  0                         print  DOGRULAR BIRBIRNE PARALELDIR               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  DOGRULAR       NOKTASINDA KESISTI  format x y

User · Answer

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

User · Answer

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  amp  C2  amp  C3  amp  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     gt  0   amp   T 1     gt  0   amp   T 0     lt  1   amp   T 1     lt  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

User · Answer

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

[python] How do I compute the intersection point of two lines?

Examples related to python

Examples related to geometry

Examples related to line

Examples related to intersect