How do you detect where two line segments intersect

Question

How do I determine whether or not two lines intersect  and if they do  at what x y point

User · Answer

Based on t3chb0t s answer   int intersezione linee int x1  int y1  int x2  int y2  int x3  int y3  int x4  int y4  int amp  p x  int amp  p y         L1  estremi  x1 y1  x2 y2  L2  estremi  x3 y3  x3 y3     int d     d    x1-x2   y3-y4  -  y1-y2   x3-x4      if  d         return 0     p x     x1 y2-y1 x2   x3-x4  -  x1-x2   x3 y4-y3 x4   d     p y     x1 y2-y1 x2   y3-y4  -  y1-y2   x3 y4-y3 x4   d     return 1     int in bounding box int x1  int y1  int x2  int y2  int p x  int p y        return p x gt  x1  amp  amp  p x lt  x2  amp  amp  p y gt  y1  amp  amp  p y lt  y2      int intersezione segmenti int x1  int y1  int x2  int y2  int x3  int y3  int x4  int y4  int amp  p x  int amp  p y        if   intersezione linee x1 y1 x2 y2 x3 y3 x4 y4 p x p y           return 0       return in bounding box x1 y1 x2 y2 p x p y   amp  amp  in bounding box x3 y3 x4 y4 p x p y

User · Answer

A C   program to check if two given line segments intersect   include  lt iostream gt  using namespace std   struct Point       int x      int y         Given three colinear points p  q  r  the function checks if    point q lies on line segment  pr  bool onSegment Point p  Point q  Point r        if  q x  lt   max p x  r x   amp  amp  q x  gt   min p x  r x   amp  amp          q y  lt   max p y  r y   amp  amp  q y  gt   min p y  r y          return true       return false        To find orientation of ordered triplet  p  q  r      The function returns following values    0 -- gt  p  q and r are colinear    1 -- gt  Clockwise    2 -- gt  Counterclockwise int orientation Point p  Point q  Point r           See 10th slides from following link for derivation of the formula        http   www dcs gla ac uk  pat 52233 slides Geometry1x1 pdf     int val    q y - p y     r x - q x  -                q x - p x     r y - q y        if  val    0  return 0      colinear      return  val  gt  0   1  2     clock or counterclock wise       The main function that returns true if line segment  p1q1     and  p2q2  intersect  bool doIntersect Point p1  Point q1  Point p2  Point q2           Find the four orientations needed for general and        special cases     int o1   orientation p1  q1  p2       int o2   orientation p1  q1  q2       int o3   orientation p2  q2  p1       int o4   orientation p2  q2  q1           General case     if  o1    o2  amp  amp  o3    o4          return true          Special Cases        p1  q1 and p2 are colinear and p2 lies on segment p1q1     if  o1    0  amp  amp  onSegment p1  p2  q1   return true          p1  q1 and p2 are colinear and q2 lies on segment p1q1     if  o2    0  amp  amp  onSegment p1  q2  q1   return true          p2  q2 and p1 are colinear and p1 lies on segment p2q2     if  o3    0  amp  amp  onSegment p2  p1  q2   return true           p2  q2 and q1 are colinear and q1 lies on segment p2q2     if  o4    0  amp  amp  onSegment p2  q1  q2   return true       return false     Doesn t fall in any of the above cases       Driver program to test above functions int main         struct Point p1    1  1   q1    10  1       struct Point p2    1  2   q2    10  2        doIntersect p1  q1  p2  q2   cout  lt  lt   Yes n   cout  lt  lt   No n        p1    10  0   q1    0  10       p2    0  0   q2    10  10       doIntersect p1  q1  p2  q2   cout  lt  lt   Yes n   cout  lt  lt   No n        p1    -5  -5   q1    0  0       p2    1  1   q2    10  10       doIntersect p1  q1  p2  q2   cout  lt  lt   Yes n   cout  lt  lt   No n        return 0

User · Answer

I tried some of these answers  but they didnt work for me  sorry guys   after some more net searching I found this   With a little modification to his code I now have this function that will return the point of intersection or if no intersection is found it will return -1 -1       Public Function intercetion ByVal ax As Integer  ByVal ay As Integer  ByVal bx As Integer  ByVal by As Integer  ByVal cx As Integer  ByVal cy As Integer  ByVal dx As Integer  ByVal dy As Integer  As Point          Determines the intersection point of the line segment defined by points A and B          with the line segment defined by points C and D                   Returns YES if the intersection point was found  and stores that point in X Y           Returns NO if there is no determinable intersection point  in which case X Y will          be unmodified       Dim distAB  theCos  theSin  newX  ABpos As Double           Fail if either line segment is zero-length      If ax   bx And ay   by Or cx   dx And cy   dy Then Return New Point -1  -1            Fail if the segments share an end-point      If ax   cx And ay   cy Or bx   cx And by   cy Or ax   dx And ay   dy Or bx   dx And by   dy Then Return New Point -1  -1             1  Translate the system so that point A is on the origin      bx -  ax     by -  ay     cx -  ax     cy -  ay     dx -  ax     dy -  ay           Discover the length of segment A-B      distAB   Math Sqrt bx   bx   by   by             2  Rotate the system so that point B is on the positive X axis      theCos   bx   distAB     theSin   by   distAB     newX   cx   theCos   cy   theSin     cy   cy   theCos - cx   theSin     cx   newX     newX   dx   theCos   dy   theSin     dy   dy   theCos - dx   theSin     dx   newX           Fail if segment C-D doesn t cross line A-B      If cy  lt  0 And dy  lt  0 Or cy  gt   0 And dy  gt   0 Then Return New Point -1  -1             3  Discover the position of the intersection point along line A-B      ABpos   dx    cx - dx    dy    dy - cy            Fail if segment C-D crosses line A-B outside of segment A-B      If ABpos  lt  0 Or ABpos  gt  distAB Then Return New Point -1  -1             4  Apply the discovered position to line A-B in the original coordinate system        X Ax ABpos theCos       Y Ay ABpos theSin           Success      Return New Point ax   ABpos   theCos  ay   ABpos   theSin  End Function

User · Answer

Finding the correct intersection of two line segments is a non-trivial task with lots of edge cases  Here s a well documented  working and tested solution in Java    In essence  there are three things that can happen when finding the intersection of two line segments    The segments do not intersect There is a unique intersection point The intersection is another segment   NOTE  In the code  I assume that a line segment  x1  y1    x2  y2  with x1   x2 and y1   y2 is a valid line segment  Mathematically speaking  a line segment consists of distinct points  but I am allowing segments to be points in this implementation for completeness   Code is taken from my github repo         This snippet finds the intersection of two line segments     The intersection may either be empty  a single point or the    intersection is a subsegment there s an overlap       import static java lang Math abs  import static java lang Math max  import static java lang Math min   import java util ArrayList  import java util List   public class LineSegmentLineSegmentIntersection         Small epsilon used for double value comparison    private static final double EPS   1e-5        2D Point class    public static class Pt       double x  y      public Pt double x  double y          this x   x         this y   y            public boolean equals Pt pt          return abs x - pt x   lt  EPS  amp  amp  abs y - pt y   lt  EPS                  Finds the orientation of point  c  relative to the line segment  a  b       Returns  0 if all three points are collinear       Returns -1 if  c  is clockwise to segment  a  b   i e right of line formed by the segment       Returns  1 if  c  is counter clockwise to segment  a  b   i e left of line      formed by the segment    public static int orientation Pt a  Pt b  Pt c        double value    b y - a y     c x - b x  -                      b x - a x     c y - b y       if  abs value   lt  EPS  return 0      return  value  gt  0    -1    1            Tests whether point  c  is on the line segment  a  b        Ensure first that point c is collinear to segment  a  b  and      then check whether c is within the rectangle formed by  a  b    public static boolean pointOnLine Pt a  Pt b  Pt c        return orientation a  b  c     0  amp  amp              min a x  b x   lt   c x  amp  amp  c x  lt   max a x  b x   amp  amp              min a y  b y   lt   c y  amp  amp  c y  lt   max a y  b y             Determines whether two segments intersect    public static boolean segmentsIntersect Pt p1  Pt p2  Pt p3  Pt p4            Get the orientation of points p3 and p4 in relation        to the line segment  p1  p2      int o1   orientation p1  p2  p3       int o2   orientation p1  p2  p4       int o3   orientation p3  p4  p1       int o4   orientation p3  p4  p2           If the points p1  p2 are on opposite sides of the infinite        line formed by  p3  p4  and conversly p3  p4 are on opposite        sides of the infinite line formed by  p1  p2  then there is        an intersection      if  o1    o2  amp  amp  o3    o4  return true          Collinear special cases  perhaps these if checks can be simplified       if  o1    0  amp  amp  pointOnLine p1  p2  p3   return true      if  o2    0  amp  amp  pointOnLine p1  p2  p4   return true      if  o3    0  amp  amp  pointOnLine p3  p4  p1   return true      if  o4    0  amp  amp  pointOnLine p3  p4  p2   return true       return false         public static List lt Pt gt  getCommonEndpoints Pt p1  Pt p2  Pt p3  Pt p4         List lt Pt gt  points   new ArrayList lt  gt          if  p1 equals p3           points add p1         if  p2 equals p4   points add p2          else if  p1 equals p4           points add p1         if  p2 equals p3   points add p2          else if  p2 equals p3           points add p2         if  p1 equals p4   points add p1          else if  p2 equals p4           points add p2         if  p1 equals p3   points add p1              return points            Finds the intersection point s  of two line segments  Unlike regular line       segments  segments which are points  x1   x2 and y1   y2  are allowed    public static Pt   lineSegmentLineSegmentIntersection Pt p1  Pt p2  Pt p3  Pt p4            No intersection      if   segmentsIntersect p1  p2  p3  p4   return new Pt              Both segments are a single point      if  p1 equals p2   amp  amp  p2 equals p3   amp  amp  p3 equals p4         return new Pt   p1        List lt Pt gt  endpoints   getCommonEndpoints p1  p2  p3  p4       int n   endpoints size            One of the line segments is an intersecting single point         NOTE  checking only n    1 is insufficient to return early        because the solution might be a sub segment      boolean singleton   p1 equals p2     p3 equals p4       if  n    1  amp  amp  singleton  return new Pt   endpoints get 0            Segments are equal      if  n    2  return new Pt   endpoints get 0   endpoints get 1         boolean collinearSegments    orientation p1  p2  p3     0   amp  amp                                    orientation p1  p2  p4     0           The intersection will be a sub-segment of the two        segments since they overlap each other      if  collinearSegments              Segment  2 is enclosed in segment  1       if  pointOnLine p1  p2  p3   amp  amp  pointOnLine p1  p2  p4           return new Pt   p3  p4             Segment  1 is enclosed in segment  2       if  pointOnLine p3  p4  p1   amp  amp  pointOnLine p3  p4  p2           return new Pt   p1  p2             The subsegment is part of segment  1 and part of segment  2           Find the middle points which correspond to this segment        Pt midPoint1   pointOnLine p1  p2  p3    p3   p4        Pt midPoint2   pointOnLine p3  p4  p1    p1   p2            There is actually only one middle point        if  midPoint1 equals midPoint2   return new Pt   midPoint1          return new Pt   midPoint1  midPoint2                 Beyond this point there is a unique intersection point             Segment  1 is a vertical line      if  abs p1 x - p2 x   lt  EPS          double m    p4 y - p3 y     p4 x - p3 x         double b   p3 y - m   p3 x        return new Pt   new Pt p1 x  m   p1 x   b                  Segment  2 is a vertical line      if  abs p3 x - p4 x   lt  EPS          double m    p2 y - p1 y     p2 x - p1 x         double b   p1 y - m   p1 x        return new Pt   new Pt p3 x  m   p3 x   b               double m1    p2 y - p1 y     p2 x - p1 x       double m2    p4 y - p3 y     p4 x - p3 x       double b1   p1 y - m1   p1 x      double b2   p3 y - m2   p3 x      double x    b2 - b1     m1 - m2       double y    m1   b2 - m2   b1     m1 - m2        return new Pt   new Pt x  y             Here is a simple usage example     public static void main String   args            Segment  1 is  p1  p2   segment  2 is  p3  p4      Pt p1  p2  p3  p4       p1   new Pt -2  4   p2   new Pt 3  3       p3   new Pt 0  0    p4   new Pt 2  4       Pt   points   lineSegmentLineSegmentIntersection p1  p2  p3  p4       Pt point   points 0           Prints   1 636  3 273      System out printf     3f    3f  n   point x  point y        p1   new Pt -10  0   p2   new Pt  10  0       p3   new Pt -5  0    p4   new Pt  5  0       points   lineSegmentLineSegmentIntersection p1  p2  p3  p4       Pt point1   points 0   point2   points 1           Prints   -5 000  0 000   5 000  0 000      System out printf     3f    3f     3f    3f  n   point1 x  point1 y  point2 x  point2 y

User · Answer

If each side of the rectangle is a line segment  and the user drawn portion is a line segment  then you need to just check the user drawn segment for intersection with the four side line segments  This should be a fairly simple exercise given the start and end points of each segment

User · Answer

Python version of iMalc s answer   def find intersection  p0  p1  p2  p3          s10 x   p1 0  - p0 0      s10 y   p1 1  - p0 1      s32 x   p3 0  - p2 0      s32 y   p3 1  - p2 1       denom   s10 x   s32 y - s32 x   s10 y      if denom    0   return None   collinear      denom is positive   denom  gt  0      s02 x   p0 0  - p2 0      s02 y   p0 1  - p2 1       s numer   s10 x   s02 y - s10 y   s02 x      if  s numer  lt  0     denom is positive   return None   no collision      t numer   s32 x   s02 y - s32 y   s02 x      if  t numer  lt  0     denom is positive   return None   no collision      if  s numer  gt  denom     denom is positive or  t numer  gt  denom     denom is positive   return None   no collision         collision detected      t   t numer   denom      intersection point     p0 0     t   s10 x   p0 1     t   s10 y          return intersection point

User · Answer

This based on Gareth Ree s answer  It also returns the overlap of the line segments if they do  Coded in C    V is a simple vector class  Where the cross product of two vectors in 2D returns a single scalar  It was tested and passed by my schools automatic testing system     Required input point must be colinear with the line bool on segment const V amp  p  const LineSegment amp  l          If a point is on the line  the sum of the vectors formed by the point to the line endpoints must be equal     V va   p - l pa      V vb   p - l pb      R ma   va magnitude        R mb   vb magnitude        R ml    l pb - l pa  magnitude        R s   ma   mb      bool r   s  lt   ml   epsilon      return r       Compute using vector math    Returns 0 points if the lines do not intersect or overlap    Returns 1 point if the lines intersect     Returns 2 points if the lines overlap  contain the points where overlapping start starts and stop std  vector lt V gt  intersect const LineSegment amp  la  const LineSegment amp  lb        std  vector lt V gt  r         http   stackoverflow com questions 563198 how-do-you-detect-where-two-line-segments-intersect     V oa  ob  da  db    Origin and direction vectors     R sa  sb    Scalar values     oa   la pa      da   la pb - la pa      ob   lb pa      db   lb pb - lb pa       if  da cross db     0  amp  amp   ob - oa  cross da     0    If colinear               if  on segment lb pa  la   amp  amp  on segment lb pb  la                         r push back lb pa               r push back lb pb               dprintf  colinear  overlapping n                return r                     if  on segment la pa  lb   amp  amp  on segment la pb  lb                         r push back la pa               r push back la pb               dprintf  colinear  overlapping n                return r                     if  on segment la pa  lb               r push back la pa            if  on segment la pb  lb               r push back la pb            if  on segment lb pa  la               r push back lb pa            if  on segment lb pb  la               r push back lb pb            if  r size      0              dprintf  colinear  non-overlapping n            else             dprintf  colinear  overlapping n             return r             if  da cross db     0  amp  amp   ob - oa  cross da     0                dprintf  parallel non-intersecting n            return r               Math trick db cross db    0  which is a single scalar in 2D        Crossing both sides with vector db gives      sa    ob - oa  cross db    da cross db          Crossing both sides with vector da gives     sb    oa - ob  cross da    db cross da        if  0  lt   sa  amp  amp  sa  lt   1  amp  amp  0  lt   sb  amp  amp  sb  lt   1                dprintf  intersecting n            r push back oa   da   sa           return r             dprintf  non-intersecting  non-parallel  non-colinear  non-overlapping n        return r

User · Answer

Plenty of solutions are available above  but I think below solution is pretty simple and easy to understand   Two segments Vector AB and Vector CD intersect if and only if   The endpoints a and b are on opposite sides of the segment CD  The endpoints c and d are on opposite side of the segment AB    More specifically a and b are on opposite side of segment CD if and only if exactly one of the two triples a c d and b c d is in counterclockwise order   Intersect a  b  c  d   if CCW a  c  d     CCW b  c  d      return false   else if CCW a  b  c     CCW a  b  d      return false   else     return true    Here CCW represent counterclockwise which returns true false based on the orientation of the points   Source   http   compgeom cs uiuc edu  jeffe teaching 373 notes x06-sweepline pdf Page 2

User · Answer

The problem reduces to this question  Do two lines from A to B and from C to D intersect   Then you can ask it four times  between the line and each of the four sides of the rectangle    Here s the vector math for doing it   I m assuming the line from A to B is the line in question and the line from C to D is one of the rectangle lines   My notation is that Ax is the  x-coordinate of A  and Cy is the  y-coordinate of C    And     means dot-product  so e g  A B   Ax Bx   Ay By   E   B-A     Bx-Ax  By-Ay   F   D-C     Dx-Cx  Dy-Cy    P     -Ey  Ex   h      A-C    P       F   P     This h number is the key   If h is between 0 and 1  the lines intersect  otherwise they don t   If F P is zero  of course you cannot make the calculation  but in this case the lines are parallel and therefore only intersect in the obvious cases   The exact point of intersection is C   F h   More Fun   If h is exactly 0 or 1 the lines touch at an end-point   You can consider this an  intersection  or not as you see fit   Specifically  h is how much you have to multiply the length of the line in order to exactly touch the other line   Therefore  If h lt 0  it means the rectangle line is  behind  the given line  with  direction  being  from A to B    and if h gt 1 the rectangle line is  in front  of the given line   Derivation   A and C are vectors that point to the start of the line  E and F are the vectors from the ends of A and C that form the line   For any two non-parallel lines in the plane  there must be exactly one pair of scalar g and h such that this equation holds   A   E g   C   F h   Why   Because two non-parallel lines must intersect  which means you can scale both lines by some amount each and touch each other    At first this looks like a single equation with two unknowns   But it isn t when you consider that this is a 2D vector equation  which means this is really a pair of equations in x and y    We have to eliminate one of these variables   An easy way is to make the E term zero   To do that  take the dot-product of both sides of the equation using a vector that will dot to zero with E   That vector I called P above  and I did the obvious transformation of E   You now have   A P   C P   F P h  A-C  P    F P  h    A-C  P      F P    h

User · Answer

Here s a basic implementation of a line segment in C   with corresponding intersection detection code   It requires a 2D vector point struct called Vector2f  though you can replace this with any other type that has X Y properties  You could also replace float with double if that suits your needs better   This code is used in my  NET physics library  Boing   public struct LineSegment2f       public Vector2f From   get        public Vector2f To   get         public LineSegment2f Vector2f  from  Vector2f to                From    from          To   to             public Vector2f Delta   gt  new Vector2f To X - From X  To Y - From Y             lt summary gt          Attempt to intersect two line segments           lt  summary gt           lt remarks gt          Even if the line segments do not intersect   lt paramref name  t   gt  and  lt paramref name  u   gt  will be set          If the lines are parallel   lt paramref name  t   gt  and  lt paramref name  u   gt  are set to  lt see cref  float NaN   gt            lt  remarks gt           lt param name  other  gt The line to attempt intersection of this line with  lt  param gt           lt param name  intersectionPoint  gt The point of intersection if within the line segments  or empty   lt  param gt           lt param name  t  gt The distance along this line at which intersection would occur  or NaN if lines are collinear parallel  lt  param gt           lt param name  u  gt The distance along the other line at which intersection would occur  or NaN if lines are collinear parallel  lt  param gt           lt returns gt  lt c gt true lt  c gt  if the line segments intersect  otherwise  lt c gt false lt  c gt   lt  returns gt      public bool TryIntersect LineSegment2f other  out Vector2f intersectionPoint  out float t  out float u                var p   From          var q   other From          var r   Delta          var s   other Delta              t    q - p     s    r    s             u    q - p     r    r    s           var denom   Fake2DCross r  s            if  denom    0                           lines are collinear or parallel             t   float NaN              u   float NaN              intersectionPoint   default Vector2f               return false                     var tNumer   Fake2DCross q - p  s           var uNumer   Fake2DCross q - p  r            t   tNumer   denom          u   uNumer   denom           if  t  lt  0    t  gt  1    u  lt  0    u  gt  1                           line segments do not intersect within their ranges             intersectionPoint   default Vector2f               return false                     intersectionPoint   p   r   t          return true             private static float Fake2DCross Vector2f a  Vector2f b                return a X   b Y - a Y   b X

User · Answer

There seems to be some interest in Gavin s answer for which cortijon proposed a javascript version in the comments and iMalc provided a version with slightly fewer computations   Some have pointed out shortcomings with various code proposals and others have commented on the efficiency of some code proposals   The algorithm provided by iMalc via Gavin s answer is the one that I am currently using in a javascript project and I just wanted to provide a cleaned up version here if it may help anyone      Some variables for reuse  others may do this differently var p0x  p1x  p2x  p3x  ix      p0y  p1y  p2y  p3y  iy      collisionDetected      do stuff  call other functions  set endpoints        note  for my purpose I use  t   lt   d  as opposed to     t   lt    d  which is equivalent to 0  lt   t  lt  1 rather than    0  lt   t  lt   1 as in Gavin s answer - results may vary  var lineSegmentIntersection   function        var d  dx1  dx2  dx3  dy1  dy2  dy3  s  t       dx1   p1x - p0x       dy1   p1y - p0y      dx2   p3x - p2x       dy2   p3y - p2y      dx3   p0x - p2x       dy3   p0y - p2y       collisionDetected   0       d   dx1   dy2 - dx2   dy1       if d     0           s   dx1   dy3 - dx3   dy1          if  s  lt   0  amp  amp  d  lt  0  amp  amp  s  gt   d      s  gt   0  amp  amp  d  gt  0  amp  amp  s  lt   d                t   dx2   dy3 - dx3   dy2              if  t  lt   0  amp  amp  d  lt  0  amp  amp  t  gt  d      t  gt   0  amp  amp  d  gt  0  amp  amp  t  lt  d                    t   t   d                  collisionDetected   1                  ix   p0x   t   dx1                  iy   p0y   t   dy1

User · Answer

Based on  Gareth Rees answer  version for Python   import numpy as np  def np perp  a         b   np empty like a      b 0    a 1      b 1    -a 0      return b  def np cross product a  b       return np dot a  np perp b    def np seg intersect a  b  considerCollinearOverlapAsIntersect   False         https   stackoverflow com questions 563198 how-do-you-detect-where-two-line-segments-intersect 565282 565282       http   www codeproject com Tips 862988 Find-the-intersection-point-of-two-line-segments     r   a 1  - a 0      s   b 1  - b 0      v   b 0  - a 0      num   np cross product v  r      denom   np cross product r  s        If r x s   0 and  q - p  x r   0  then the two lines are collinear      if np isclose denom  0  and np isclose num  0             1  If either  0  lt    q - p    r  lt   r   r or 0  lt    p - q    s  lt     s           then the two lines are overlapping          if considerCollinearOverlapAsIntersect               vDotR   np dot v  r              aDotS   np dot -v  s              if  0  lt   vDotR  and vDotR  lt   np dot r r   or  0  lt   aDotS  and aDotS  lt   np dot s s                    return True           2  If neither 0  lt    q - p    r   r   r nor 0  lt    p - q    s  lt   s   s           then the two lines are collinear but disjoint            No need to implement this expression  as it follows from the expression above          return None     if np isclose denom  0  and not np isclose num  0             Parallel and non intersecting         return None     u   num   denom     t   np cross product v  s    denom     if u  gt   0 and u  lt   1 and t  gt   0 and t  lt   1          res   b 0     s u          return res       Otherwise  the two line segments are not parallel but do not intersect      return None

User · Answer

Question C  How do you detect whether or not two line segments intersect   I have searched for the same topic  and I wasn t happy with the answers  So I have written an article that explains very detailed how to check if two line segments intersect with a lot of images  There is complete  and tested  Java-code   Here is the article  cropped to the most important parts   The algorithm  that checks if line segment a intersects with line segment b  looks like this     What are bounding boxes  Here are two bounding boxes of two line segments     If both bounding boxes have an intersection  you move line segment a so that one point is at  0 0   Now you have a line through the origin defined by a  Now move line segment b the same way and check if the new points of line segment b are on different sides of line a  If this is the case  check it the other way around  If this is also the case  the line segments intersect  If not  they don t intersect   Question A  Where do two line segments intersect   You know that two line segments a and b intersect  If you don t know that  check it with the tools I gave you in  Question C    Now you can go through some cases and get the solution with 7th grade math  see code and interactive example    Question B  How do you detect whether or not two lines intersect   Let s say your point A    x1  y1   point B    x2  y2   C    x 3  y 3   D    x 4  y 4   Your first line is defined by AB  with A    B   and your second one by CD  with C    D    function doLinesIntersect AB  CD        if  x1    x2            return   x3    x4  amp  amp  x1    x3         else if  x3    x4            return true        else              Both lines are not parallel to the y-axis         m1    y1-y2   x1-x2           m2    y3-y4   x3-x4           return m1    m2            Question D  Where do two lines intersect   Check with Question B if they intersect at all   The lines a and b are defined by two points for each line  You can basically apply the same logic was used in Question A

User · Answer

Many answers have wrapped up all the calculations into a single function  If you need to calculate the line slopes  y-intercepts  or x-intercepts for use elsewhere in your code  you ll be making those calculations redundantly  I have separated out the respective functions  used obvious variable names  and commented my code to make it easier to follow  I needed to know if lines intersect infinitely beyond their endpoints  so in JavaScript   http   jsfiddle net skibulk evmqq00u   var point a    x 0  y 10       point b    x 12  y 12       point c    x 10  y 0       point d    x 0  y 0       slope ab   slope point a  point b       slope bc   slope point b  point c       slope cd   slope point c  point d       slope da   slope point d  point a       yint ab   y intercept point a  slope ab       yint bc   y intercept point b  slope bc       yint cd   y intercept point c  slope cd       yint da   y intercept point d  slope da       xint ab   x intercept point a  slope ab  yint ab       xint bc   x intercept point b  slope bc  yint bc       xint cd   x intercept point c  slope cd  yint cd       xint da   x intercept point d  slope da  yint da       point aa   intersect slope da  yint da  xint da  slope ab  yint ab  xint ab       point bb   intersect slope ab  yint ab  xint ab  slope bc  yint bc  xint bc       point cc   intersect slope bc  yint bc  xint bc  slope cd  yint cd  xint cd       point dd   intersect slope cd  yint cd  xint cd  slope da  yint da  xint da    console log point a  point b  point c  point d   console log slope ab  slope bc  slope cd  slope da   console log yint ab  yint bc  yint cd  yint da   console log xint ab  xint bc  xint cd  xint da   console log point aa  point bb  point cc  point dd    function slope point a  point b      var i    point b y - point a y     point b x - point a x     if  i     -Infinity  return Infinity    if  i     -0  return 0    return i     function y intercept point  slope           Horizontal Line     if  slope    0  return point y       Vertical Line     if  slope    Infinity             THE Y-Axis     if  point x    0  return Infinity         No Intercept     return null           Angled Line   return point y -  slope   point x      function x intercept point  slope  yint           Vertical Line     if  slope    Infinity  return point x       Horizontal Line     if  slope    0             THE X-Axis     if  point y    0  return Infinity         No Intercept     return null           Angled Line   return -yint   slope        Intersection of two infinite lines function intersect slope a  yint a  xint a  slope b  yint b  xint b      if  slope a    slope b             Equal Lines     if  yint a    yint b  amp  amp  xint a    xint b  return Infinity         Parallel Lines     return null           First Line Vertical     if  slope a    Infinity          return           x  xint a        y   slope b   xint a    yint b                 Second Line Vertical     if  slope b    Infinity          return           x  xint b        y   slope a   xint b    yint a                 Not Equal  Not Parallel  Not Vertical   var i    yint b - yint a     slope a - slope b     return       x  i      y   slope a   i    yint a

User · Answer

I tried lot of ways and then I decided to write my own  So here it is   bool IsBetween  float x  float b1  float b2       return     x  gt    b1 - 0 1f    amp  amp            x  lt    b2   0 1f                  x  gt    b2 - 0 1f    amp  amp           x  lt    b1   0 1f         bool IsSegmentsColliding    POINTFLOAT lineA                  POINTFLOAT lineB                  POINTFLOAT line2A                  POINTFLOAT line2B        float deltaX1   lineB x - lineA x      float deltaX2   line2B x - line2A x      float deltaY1   lineB y - lineA y      float deltaY2   line2B y - line2A y       if  abs deltaX1   lt  0 01f  amp  amp           abs deltaX2   lt  0 01f     Both are vertical lines         return false      if  abs  deltaY1   deltaX1  -          deltaY2   deltaX2    lt  0 001f     Two parallel line         return false       float xCol           deltaX1   deltaX2                              line2A y - lineA y   -                       line2A x   deltaY2   deltaX1                          lineA x   deltaY1   deltaX2                         deltaY1   deltaX2  -  deltaY2   deltaX1        float yCol   0      if  deltaX1  lt  0 01f     L1 is a vertical line         yCol     xCol   deltaY2                      line2A y   deltaX2  -                   line2A x   deltaY2     deltaX2      else    L1 is acceptable         yCol     xCol   deltaY1                     lineA y   deltaX1  -                  lineA x   deltaY1     deltaX1       bool isCol      IsBetween xCol  lineA x  lineB x   amp  amp              IsBetween yCol  lineA y  lineB y   amp  amp              IsBetween xCol  line2A x  line2B x   amp  amp              IsBetween yCol  line2A y  line2B y       return isCol      Based on these two formulas   I simplified them from equation of lines and other formulas

User · Answer

Just wanted to mention that a good explanation and explicit solution can be found in the Numeric Recipes series  I ve got the 3rd edition and the answer is on page 1117  section 21 4  Another solution with a different nomenclature can be found in a paper by Marina Gavrilova Reliable Line Section Intersection Testing  Her solution is  to my mind  a little simpler   My implementation is below   bool NuGeometry  IsBetween const double amp  x0  const double amp  x  const double amp  x1      return  x  gt   x0   amp  amp   x  lt   x1      bool NuGeometry  FindIntersection const double amp  x0  const double amp  y0        const double amp  x1  const double amp  y1       const double amp  a0  const double amp  b0        const double amp  a1  const double amp  b1        double amp  xy  double amp  ab          four endpoints are x0  y0  amp  x1 y1  amp  a0 b0  amp  a1 b1       returned values xy and ab are the fractional distance along xy and ab       and are only defined when the result is true     bool partial   false     double denom    b0 - b1     x0 - x1  -  y0 - y1     a0 - a1      if  denom    0          xy   -1        ab   -1       else         xy    a0    y1 - b1    a1    b0 - y1    x1    b1 - b0     denom        partial   NuGeometry  IsBetween 0  xy  1         if  partial                no point calculating this unless xy is between 0  amp  1          ab    y1    x0 - a1    b1    x1 - x0    y0    a1 - x1     denom                   if   partial  amp  amp  NuGeometry  IsBetween 0  ab  1           ab   1-ab        xy   1-xy        return true        else return false

User · Answer

I read these algorithm from the book  multiple view geometry   following text using    as transpose sign    as dot product  x as cross product  when using as operator  1  line definition  a point x vec    x  y   lies on the line ax   by   c   0  we denote L    a  b  c    the point as  x  y  1   as homogeneous coordinates  the line equation can be written as   x  y  1  a  b  c     0 or x    L   0  2  intersection of lines  we have two lines L1  a1  b1  c1    L2  a2  b2  c2    assume x is a point  a vector  and x   L1 x L2  L1 cross product L2     be careful  x is always a 2D point  please read homogeneous coordinates if you are confused about  L1xL2  is a three elements vector  and x is a 2D coordinates   according to triple product  we know that  L1     L1 x L2     0  and L2    L1 x L2    0  because of L1 L2 co-plane  we substitute  L1xL2  with vector x  then we have L1 x 0  L2 x 0  which means x lie on both L1 and L2  x is the intersection point   be careful  here x is homogeneous coordinates  if the last element of x is zero  it means L1 and L2 are parallel

User · Answer

I think there is a much much simpler solution for this problem  I came up with another idea today and it seems to work just fine  at least in 2D for now   All you have to do  is to calculate the intersection between two lines  then check if the calculated intersection point is within the boundig boxes of both line segments  If it is  the line segments intersect  That s it   EDIT   This is how I calculate the intersection  I don t know anymore where I found this code snippet   Point3D   comes from  System Windows Media Media3D  public static Point3D  Intersection Point3D start1  Point3D end1  Point3D start2  Point3D end2             double a1   end1 Y - start1 Y          double b1   start1 X - end1 X          double c1   a1   start1 X   b1   start1 Y           double a2   end2 Y - start2 Y          double b2   start2 X - end2 X          double c2   a2   start2 X   b2   start2 Y           double det   a1   b2 - a2   b1          if  det    0       lines are parallel             return null                     double x    b2   c1 - b1   c2    det          double y    a1   c2 - a2   c1    det           return new Point3D x  y  0 0           and this is my  simplified for the purpose of the answer  BoundingBox class   public class BoundingBox       private Point3D min   new Point3D        private Point3D max   new Point3D         public BoundingBox Point3D point            min   point          max   point             public Point3D Min           get   return min            set   min   value               public Point3D Max           get   return max            set   max   value               public bool Contains BoundingBox box            bool contains               min X  lt   box min X  amp  amp  max X  gt   box max X  amp  amp              min Y  lt   box min Y  amp  amp  max Y  gt   box max Y  amp  amp              min Z  lt   box min Z  amp  amp  max Z  gt   box max Z          return contains             public bool Contains Point3D point            return Contains new BoundingBox point

User · Answer

I ported Kris s above answer to JavaScript  After trying numerous different answers  his provided the correct points  I thought I was going crazy that I wasn t getting the points I needed   function getLineLineCollision p0  p1  p2  p3        var s1  s2      s1    x  p1 x - p0 x  y  p1 y - p0 y       s2    x  p3 x - p2 x  y  p3 y - p2 y        var s10 x   p1 x - p0 x      var s10 y   p1 y - p0 y      var s32 x   p3 x - p2 x      var s32 y   p3 y - p2 y       var denom   s10 x   s32 y - s32 x   s10 y       if denom    0            return false             var denom positive   denom  gt  0       var s02 x   p0 x - p2 x      var s02 y   p0 y - p2 y       var s numer   s10 x   s02 y - s10 y   s02 x       if  s numer  lt  0     denom positive            return false             var t numer   s32 x   s02 y - s32 y   s02 x       if  t numer  lt  0     denom positive            return false             if  s numer  gt  denom     denom positive     t numer  gt  denom     denom positive            return false             var t   t numer   denom       var p    x  p0 x    t   s10 x   y  p0 y    t   s10 y        return p

User · Answer

This solution may help  public static float GetLineYIntesept PointF p  float slope                return p Y - slope   p X             public static PointF FindIntersection PointF line1Start  PointF line1End  PointF line2Start  PointF line2End                 float slope1    line1End Y - line1Start Y     line1End X - line1Start X           float slope2    line2End Y - line2Start Y     line2End X - line2Start X            float yinter1   GetLineYIntesept line1Start  slope1           float yinter2   GetLineYIntesept line2Start  slope2            if  slope1    slope2  amp  amp  yinter1    yinter2              return PointF Empty           float x    yinter2 - yinter1     slope1 - slope2            float y   slope1   x   yinter1           return new PointF x  y

User · Answer

Here s an improvement to Gavin s answer  marcp s solution is similar also  but neither postpone the division   This actually turns out to be a practical application of Gareth Rees  answer as well  because the cross-product s equivalent in 2D is the perp-dot-product  which is what this code uses three of  Switching to 3D and using the cross-product  interpolating both s and t at the end  results in the two closest points between the lines in 3D  Anyway  the 2D solution   int get line intersection float p0 x  float p0 y  float p1 x  float p1 y       float p2 x  float p2 y  float p3 x  float p3 y  float  i x  float  i y        float s02 x  s02 y  s10 x  s10 y  s32 x  s32 y  s numer  t numer  denom  t      s10 x   p1 x - p0 x      s10 y   p1 y - p0 y      s32 x   p3 x - p2 x      s32 y   p3 y - p2 y       denom   s10 x   s32 y - s32 x   s10 y      if  denom    0          return 0     Collinear     bool denomPositive   denom  gt  0       s02 x   p0 x - p2 x      s02 y   p0 y - p2 y      s numer   s10 x   s02 y - s10 y   s02 x      if   s numer  lt  0     denomPositive          return 0     No collision      t numer   s32 x   s02 y - s32 y   s02 x      if   t numer  lt  0     denomPositive          return 0     No collision      if    s numer  gt  denom     denomPositive       t numer  gt  denom     denomPositive           return 0     No collision        Collision detected     t   t numer   denom      if  i x    NULL           i x   p0 x    t   s10 x       if  i y    NULL           i y   p0 y    t   s10 y        return 1      Basically it postpones the division until the last moment  and moves most of the tests until before certain calculations are done  thereby adding early-outs  Finally  it also avoids the division by zero case which occurs when the lines are parallel   You also might want to consider using an epsilon test rather than comparison against zero  Lines that are extremely close to parallel can produce results that are slightly off  This is not a bug  it is a limitation with floating point math

User · Answer

This is working well for me   Taken from here       calculates intersection and checks for parallel lines        also checks that the intersection point is actually on       the line segment p1-p2    Point findIntersection Point p1 Point p2       Point p3 Point p4         float xD1 yD1 xD2 yD2 xD3 yD3       float dot deg len1 len2       float segmentLen1 segmentLen2       float ua ub div           calculate differences      xD1 p2 x-p1 x       xD2 p4 x-p3 x       yD1 p2 y-p1 y       yD2 p4 y-p3 y       xD3 p1 x-p3 x       yD3 p1 y-p3 y             calculate the lengths of the two lines      len1 sqrt xD1 xD1 yD1 yD1        len2 sqrt xD2 xD2 yD2 yD2            calculate angle between the two lines       dot  xD1 xD2 yD1 yD2      dot product      deg dot  len1 len2            if abs angle   1 then the lines are parallell          so no intersection is possible      if abs deg   1  return null           find intersection Pt between two lines      Point pt new Point 0 0        div yD2 xD1-xD2 yD1       ua  xD2 yD3-yD2 xD3  div       ub  xD1 yD3-yD1 xD3  div       pt x p1 x ua xD1       pt y p1 y ua yD1           calculate the combined length of the two segments         between Pt-p1 and Pt-p2      xD1 pt x-p1 x       xD2 pt x-p2 x       yD1 pt y-p1 y       yD2 pt y-p2 y       segmentLen1 sqrt xD1 xD1 yD1 yD1  sqrt xD2 xD2 yD2 yD2            calculate the combined length of the two segments         between Pt-p3 and Pt-p4      xD1 pt x-p3 x       xD2 pt x-p4 x       yD1 pt y-p3 y       yD2 pt y-p4 y       segmentLen2 sqrt xD1 xD1 yD1 yD1  sqrt xD2 xD2 yD2 yD2            if the lengths of both sets of segments are the same as         the lenghts of the two lines the point is actually         on the line segment           if the point isn   t on the line  return null      if abs len1-segmentLen1  gt 0 01    abs len2-segmentLen2  gt 0 01         return null           return the valid intersection      return pt           class Point       float x y       Point float x  float y          this x   x         this y   y               void set float x  float y          this x   x         this y   y

User · Answer

There   s a nice approach to this problem that uses vector cross products   Define the 2-dimensional vector cross product v      w to be vx  wy  -  vy  wx   Suppose the two line segments run from p to p     r and from q to q     s   Then any point on the first line is representable as p     t  r  for a scalar parameter  t  and any point on the second line as q     u  s  for a scalar parameter  u      The two lines intersect if we can find t and u such that      p   t  r   q   u  s     Cross both sides with s  getting      p   t  r     s    q   u  s     s   And since s      s   0  this means     t   r    s     q - p     s   And therefore  solving for t      t    q - p     s    r    s    In the same way  we can solve for u       p   t  r     r    q   u  s     r      u   s    r     p - q     r      u    p - q     r    s    r    To reduce the number of computation steps  it s convenient to rewrite this as follows  remembering that s      r   -  r      s       u    q - p     r    r    s    Now there are four cases    If r      s     0 and  q  -  p       r     0  then the two lines are collinear   In this case  express the endpoints of the second segment  q and q     s  in terms of the equation of the first line segment  p   t r       t0    q - p       r    r      r       t1    q   s - p       r    r      r    t0   s      r    r      r    If the interval between t0 and t1 intersects the interval  0  1  then the line segments are collinear and overlapping  otherwise they are collinear and disjoint   Note that if s and r point in opposite directions  then s      r  lt  0 and so the interval to be checked is  t1  t0  rather than  t0  t1   If r      s     0 and  q  -  p       r     0  then the two lines are parallel and non-intersecting  If r      s     0 and 0     t     1 and 0     u     1  the two line segments meet at the point p   t  r   q   u  s  Otherwise  the two line segments are not parallel but do not intersect    Credit  this method is the 2-dimensional specialization of the 3D line intersection algorithm from the article  Intersection of two lines in three-space  by Ronald Goldman  published in Graphics Gems  page 304  In three dimensions  the usual case is that the lines are skew  neither parallel nor intersecting  in which case the method gives the points of closest approach of the two lines

User · Answer

FWIW  the following function  in C  both detects line intersections and determines the intersection point  It is based on an algorithm in Andre LeMothe s  quot Tricks of the Windows Game Programming Gurus quot   It s not dissimilar to some of the algorithm s in other answers  e g  Gareth s   LeMothe then uses Cramer s Rule  don t ask me  to solve the equations themselves  I can attest that it works in my feeble asteroids clone  and seems to deal correctly with the edge cases described in other answers by Elemental  Dan and Wodzu  It s also probably faster than the code posted by KingNestor because it s all multiplication and division  no square roots  I guess there s some potential for divide by zero in there  though it hasn t been an issue in my case  Easy enough to modify to avoid the crash anyway     Returns 1 if the lines intersect  otherwise 0  In addition  if the lines     intersect the intersection point may be stored in the floats i x and i y  char get line intersection float p0 x  float p0 y  float p1 x  float p1 y       float p2 x  float p2 y  float p3 x  float p3 y  float  i x  float  i y        float s1 x  s1 y  s2 x  s2 y      s1 x   p1 x - p0 x      s1 y   p1 y - p0 y      s2 x   p3 x - p2 x      s2 y   p3 y - p2 y       float s  t      s    -s1 y    p0 x - p2 x    s1 x    p0 y - p2 y      -s2 x   s1 y   s1 x   s2 y       t     s2 x    p0 y - p2 y  - s2 y    p0 x - p2 x      -s2 x   s1 y   s1 x   s2 y        if  s  gt   0  amp  amp  s  lt   1  amp  amp  t  gt   0  amp  amp  t  lt   1                   Collision detected         if  i x    NULL               i x   p0 x    t   s1 x           if  i y    NULL               i y   p0 y    t   s1 y           return 1             return 0     No collision    BTW  I must say that in LeMothe s book  though he apparently gets the algorithm right  the concrete example he shows plugs in the wrong numbers and does calculations wrong  For example    4    4 - 1    12    7 - 1      17   4   12   10    844 0 88   0 44  That confused me for hours

User · Answer

C and Objective-C Based on Gareth Rees  answer const AGKLine AGKLineZero    AGKLine   CGPoint  0 0  0 0    CGPoint  0 0  0 0     AGKLine AGKLineMake CGPoint start  CGPoint end        return  AGKLine  start  end      double AGKLineLength AGKLine l        return CGPointLengthBetween AGK l start  l end      BOOL AGKLineIntersection AGKLine l1  AGKLine l2  CGPoint  out pointOfIntersection           http   stackoverflow com a 565282 202451      CGPoint p   l1 start      CGPoint q   l2 start      CGPoint r   CGPointSubtract AGK l1 end  l1 start       CGPoint s   CGPointSubtract AGK l2 end  l2 start            double s r crossProduct   CGPointCrossProductZComponent AGK r  s       double t   CGPointCrossProductZComponent AGK CGPointSubtract AGK q  p   s    s r crossProduct      double u   CGPointCrossProductZComponent AGK CGPointSubtract AGK q  p   r    s r crossProduct           if t  lt  0    t  gt  1 0    u  lt  0    u  gt  1 0                if out pointOfIntersection    NULL                         out pointOfIntersection   CGPointZero                    return NO            else               if out pointOfIntersection    NULL                        CGPoint i   CGPointAdd AGK p  CGPointMultiply AGK r  t                 out pointOfIntersection   i                    return YES           CGFloat CGPointCrossProductZComponent AGK CGPoint v1  CGPoint v2        return v1 x   v2 y - v1 y   v2 x     CGPoint CGPointSubtract AGK CGPoint p1  CGPoint p2        return  CGPoint  p1 x - p2 x  p1 y - p2 y      CGPoint CGPointAdd AGK CGPoint p1  CGPoint p2        return  CGPoint  p1 x   p2 x  p1 y   p2 y      CGFloat CGPointCrossProductZComponent AGK CGPoint v1  CGPoint v2        return v1 x   v2 y - v1 y   v2 x     CGPoint CGPointMultiply AGK CGPoint p1  CGFloat factor        return  CGPoint  p1 x   factor  p1 y   factor      Many of the functions and structs are private  but you should pretty easy be able to know what s going on  This is public on this repo https   github com hfossli AGGeometryKit

User · Answer

I have tried to implement the algorithm so elegantly described by Jason above  unfortunately while working though the mathematics in the debugging I found many cases for which it doesn t work   For example consider the points A 10 10  B 20 20  C 10 1  D 1 10  gives h  5 and yet it is clear by examination that these segments are no-where near each other    Graphing this makes it clear that 0  lt  h  lt  1 criteria only indicates that the intercept point would lie on CD if it existed but tells one nothing of whether that point lies on AB  To ensure that there is a cross point you must do the symmetrical calculation for the variable g and the requirement for interception is  0  lt  g  lt  1 AND 0  lt  h  lt  1

User · Answer

The answer once accepted here is incorrect  it has since been unaccepted  so hooray     It does not correctly eliminate all non-intersections   Trivially it may appear to work but it can fail  especially in the case that 0 and 1 are considered valid for h   Consider the following case   Lines at  4 1 - 5 1  and  0 0 - 0 2   These are perpendicular lines which clearly do not overlap   A  4 1  B  5 1  C  0 0  D  0 2  E  5 1 - 4 1   -1 0  F  0 2 - 0 0   0 -2  P  0 1  h   4 1 - 0 0   dot  0 1      0 -2  dot  0 1     0   According to the above answer  these two line segments meet at an endpoint  values of 0 and 1    That endpoint would be    0 0   0 -2  0  0 0   So  apparently the two line segments meet at  0 0   which is on line CD  but not on line AB   So what is going wrong   The answer is that the values of 0 and 1 are not valid and only sometimes HAPPEN to correctly predict endpoint intersection   When the extension of one line  but not the other  would meet the line segment  the algorithm predicts an intersection of line segments  but this is not correct   I imagine that by testing starting with AB vs CD and then also testing with CD vs AB  this problem would be eliminated   Only if both fall between 0 and 1 inclusively can they be said to intersect   I recommend using the vector cross product method if you must predict end-points   -Dan

[geometry] How do you detect where two line segments intersect?

Examples related to geometry

Examples related to line-intersection