How can I check if two segments intersect

Question

How can I check if 2 segments intersect   I ve the following data   Segment1    x1 y1    x2 y2    Segment2    x1 y1    x2 y2       I need to write a small algorithm in Python to detect if the 2 lines are intersecting

User · Answer

Checking if line segments intersect is very easy with Shapely library using intersects method:

from shapely.geometry import LineString

line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 0)])
print(line.intersects(other))
# True

line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 2)])
print(line.intersects(other))
# False

User · Answer

The answer by Georgy is the cleanest to implement  by far    Had to chase this down  since the brycboe example  while simple as well  had issues with colinearity   Code for testing      usr bin python     Notes on intersection      https   bryceboe com 2006 10 23 line-segment-intersection-algorithm      https   stackoverflow com questions 3838329 how-can-i-check-if-two-segments-intersect  from shapely geometry import LineString  class Point      def   init   self x y           self x   x         self y   y  def ccw A B C       return  C y-A y   B x-A x   gt   B y-A y   C x-A x   def intersect A B C D       return ccw A C D     ccw B C D  and ccw A B C     ccw A B D    def ShapelyIntersect A B C D       return LineString   A x A y   B x B y    intersects LineString   C x C y   D x D y       a   Point 0 0  b   Point 0 1  c   Point 1 1  d   Point 1 0       Test points   b 0 1    c 1 1      a 0 0    d 1 0         F print intersect a b c d      T print intersect a c b d   print intersect b d a c   print intersect d b a c      F print intersect a d b c      same end point cases  print  same end points     F - not intersected print intersect a b a d     T - This shows as intersected print intersect b a a d     F - this does not print intersect b a d a     F - this does not print intersect a b d a    print  same end points  using shapely     T print ShapelyIntersect a b a d     T print ShapelyIntersect b a a d     T print ShapelyIntersect b a d a     T print ShapelyIntersect a b d a

User · Answer

You have two line segments  Define one segment by endpoints A  amp  B and the second segment by endpoints C  amp  D  There is a nice trick to show that they must intersect  WITHIN the bounds of the segments   Note that the lines themselves may intersect beyond the bounds of the segments  so you must be careful  Good code will also watch for parallel lines    The trick is to test that points A and B must line on opposite sides of line CD  AND that points C and D must lie on opposite sides of line AB   Since this is homework  I won t give you an explicit solution  But a simple test to see which side of a line a point falls on  is to use a dot product  Thus  for a given line CD  compute the normal vector to that line  I ll call it N C   Now  simply test the signs of these two results   dot A-C N C    and  dot B-C N C    If those results have opposite signs  then A and B are opposite sides of line CD  Now do the same test for the other line  AB  It has normal vector N A  Compare the signs of  dot C-A N A    and  dot D-A N A    I ll leave it to you to figure out how to compute a normal vector   In 2-d  that is trivial  but will your code worry about whether A and B are distinct points  Likewise  are C and D distinct    You still need to worry about line segments that lie along the same infinite line  or if one point actually falls on the other line segment itself  Good code will cater to every possible problem

User · Answer

One of the solutions above worked so well I decided to write a complete demonstration program using wxPython  You should be able to run this program like this  python  your file name     Click on the window to draw a line    The program will tell you if this and the other line intersect   import wx  class Point      def   init   self  newX  newY           self x   newX         self y   newY  app   wx App   frame   wx Frame None  wx ID ANY   Main   p1   Point 90 200  p2   Point 150 80  mp   Point 0 0    mouse point highestX   0   def ccw A B C       return  C y-A y     B x-A x   gt   B y-A y     C x-A x     Return true if line segments AB and CD intersect def intersect A B C D       return ccw A C D     ccw B C D  and ccw A B C     ccw A B D   def is intersection p1  p2  p3  p4       return intersect p1  p2  p3  p4   def drawIntersection pc       mp2   Point highestX  mp y      if is intersection p1  p2  mp  mp2           pc DrawText  intersection   10  10      else          pc DrawText  no intersection   10  10   def do paint evt       pc   wx PaintDC frame      pc DrawLine p1 x  p1 y  p2 x  p2 y      pc DrawLine mp x  mp y  highestX  mp y      drawIntersection pc   def do left mouse evt       global mp  highestX     point   evt GetPosition       mp   Point point 0   point 1       highestX   frame Size 0      frame Refresh    frame Bind wx EVT PAINT  do paint  frame Bind wx EVT LEFT DOWN  do left mouse  frame Show   app MainLoop

User · Answer

for segments AB and CD  find the slope of CD  slope  Dy-Cy   Dx-Cx    extend CD over A and B  and take the distance to CD going straight up  dist1 slope  Cx-Ax  Ay-Cy dist2 slope  Dx-Ax  Ay-Dy   check if they are on opposite sides  return dist1 dist2 lt 0

User · Answer

Since you do not mention that you want to find the intersection point of the line  the problem becomes simpler to solve  If you need the intersection point  then the answer by OMG peanuts is a faster approach  However  if you just want to find whether the lines intersect or not  you can do so by using the line equation  ax   by   c   0   The approach is as follows    Let s start with two line segments  segment 1 and segment 2    segment1     x1 y1    x2 y2   segment2     x3 y3    x4 y4    Check if the two line segments are non zero length line and distinct segments   From hereon  I assume that the two segments are non-zero length and distinct  For each line segment  compute the slope of the line and then obtain the equation of a line in the form of ax   by   c   0  Now  compute the value of f   ax   by   c for the two points of the other line segment  repeat this for the other line segment as well    a2    y3-y4   x3-x4   b1   -1  b2   -1  c1   y1 - a1 x1  c2   y3 - a2 x3     using the sign function from numpy f1 1   sign a1 x3   b1 y3   c1   f1 2   sign a1 x4   b1 y4   c1   f2 1   sign a2 x1   b2 y1   c2   f2 2   sign a2 x2   b2 y2   c2    Now all that is left is the different cases  If f   0 for any point  then the two lines touch at a point  If f1 1 and f1 2 are equal or f2 1 and f2 2 are equal  then the lines do not intersect  If f1 1 and f1 2 are unequal and f2 1 and f2 2 are unequal  then the line segments intersect  Depending on whether you want to consider the lines which touch as  intersecting  or not  you can adapt your conditions

User · Answer

Here s a solution using dot products    assumes line segments are stored in the format   x0 y0   x1 y1   def intersects s0 s1       dx0   s0 1  0 -s0 0  0      dx1   s1 1  0 -s1 0  0      dy0   s0 1  1 -s0 0  1      dy1   s1 1  1 -s1 0  1      p0   dy1  s1 1  0 -s0 0  0   - dx1  s1 1  1 -s0 0  1       p1   dy1  s1 1  0 -s0 1  0   - dx1  s1 1  1 -s0 1  1       p2   dy0  s0 1  0 -s1 0  0   - dx0  s0 1  1 -s1 0  1       p3   dy0  s0 1  0 -s1 1  0   - dx0  s0 1  1 -s1 1  1       return  p0 p1 lt  0   amp   p2 p3 lt  0   Here s a visualization in Desmos  Line Segment Intersection

User · Answer

Using OMG Peanuts solution  I translated to SQL   HANA Scalar Function  Thanks OMG Peanuts  it works great  I am using round earth  but distances are small  so I figure its okay  FUNCTION GA INTERSECT quot    IN LAT A1 DOUBLE           IN LONG A1 DOUBLE           IN LAT A2 DOUBLE           IN LONG A2 DOUBLE           IN LAT B1 DOUBLE           IN LONG B1 DOUBLE           IN LAT B2 DOUBLE           IN LONG B2 DOUBLE        RETURNS RET DOESINTERSECT DOUBLE     LANGUAGE SQLSCRIPT     SQL SECURITY INVOKER AS BEGIN      DECLARE MA DOUBLE      DECLARE MB DOUBLE      DECLARE BA DOUBLE      DECLARE BB DOUBLE      DECLARE XA DOUBLE      DECLARE MAX MIN X DOUBLE      DECLARE MIN MAX X DOUBLE      DECLARE DOESINTERSECT INTEGER           SELECT 1 INTO DOESINTERSECT FROM DUMMY           IF LAT A2-LAT A1    0 AND LAT B2-LAT B1    0 THEN         SELECT  LONG A2 - LONG A1   LAT A2 - LAT A1  INTO MA FROM DUMMY           SELECT  LONG B2 - LONG B1   LAT B2 - LAT B1  INTO MB FROM DUMMY          IF MA   MB THEN             SELECT 0 INTO DOESINTERSECT FROM DUMMY          END IF      END IF           SELECT LONG A1-MA LAT A1 INTO BA FROM DUMMY      SELECT LONG B1-MB LAT B1 INTO BB FROM DUMMY      SELECT  BB - BA     MA - MB  INTO XA FROM DUMMY           -- Max of Mins     IF LAT A1  lt  LAT A2 THEN         -- MIN LAT A1  LAT A2    LAT A1         IF LAT B1  lt  LAT B2 THEN        -- MIN LAT B1  LAT B2    LAT B1             IF LAT A1  gt  LAT B1 THEN       -- MAX LAT A1  LAT B1    LAT A1                 SELECT LAT A1 INTO MAX MIN X FROM DUMMY              ELSE                          -- MAX LAT A1  LAT B1    LAT B1                 SELECT LAT B1 INTO MAX MIN X FROM DUMMY              END IF          ELSEIF LAT B2  lt  LAT B1 THEN   -- MIN LAT B1  LAT B2    LAT B2             IF LAT A1  gt  LAT B2 THEN       -- MAX LAT A1  LAT B2    LAT A1                 SELECT LAT A1 INTO MAX MIN X FROM DUMMY              ELSE                          -- MAX LAT A1  LAT B2    LAT B2                 SELECT LAT B2 INTO MAX MIN X FROM DUMMY              END IF          END IF      ELSEIF LAT A2  lt  LAT A1 THEN     -- MIN LAT A1  LAT A2    LAT A2         IF LAT B1  lt  LAT B2 THEN        -- MIN LAT B1  LAT B2    LAT B1             IF LAT A2  gt  LAT B1 THEN       -- MAX LAT A2  LAT B1    LAT A2                 SELECT LAT A2 INTO MAX MIN X FROM DUMMY              ELSE                          -- MAX LAT A2  LAT B1    LAT B1                 SELECT LAT B1 INTO MAX MIN X FROM DUMMY              END IF          ELSEIF LAT B2  lt  LAT B1 THEN   -- MIN LAT B1  LAT B2    LAT B2             IF LAT A2  gt  LAT B2 THEN       -- MAX LAT A2  LAT B2    LAT A2                 SELECT LAT A2 INTO MAX MIN X FROM DUMMY              ELSE                          -- MAX LAT A2  LAT B2    LAT B2                 SELECT LAT B2 INTO MAX MIN X FROM DUMMY              END IF          END IF      END IF           -- Min of Max     IF LAT A1  gt  LAT A2 THEN         -- MAX LAT A1  LAT A2    LAT A1         IF LAT B1  gt  LAT B2 THEN        -- MAX LAT B1  LAT B2    LAT B1             IF LAT A1  lt  LAT B1 THEN       -- MIN LAT A1  LAT B1    LAT A1                 SELECT LAT A1 INTO MIN MAX X FROM DUMMY              ELSE                          -- MIN LAT A1  LAT B1    LAT B1                 SELECT LAT B1 INTO MIN MAX X FROM DUMMY              END IF          ELSEIF LAT B2  gt  LAT B1 THEN   -- MAX LAT B1  LAT B2    LAT B2             IF LAT A1  lt  LAT B2 THEN       -- MIN LAT A1  LAT B2    LAT A1                 SELECT LAT A1 INTO MIN MAX X FROM DUMMY              ELSE                          -- MIN LAT A1  LAT B2    LAT B2                 SELECT LAT B2 INTO MIN MAX X FROM DUMMY              END IF          END IF      ELSEIF LAT A2  gt  LAT A1 THEN     -- MAX LAT A1  LAT A2    LAT A2         IF LAT B1  gt  LAT B2 THEN        -- MAX LAT B1  LAT B2    LAT B1             IF LAT A2  lt  LAT B1 THEN       -- MIN LAT A2  LAT B1    LAT A2                 SELECT LAT A2 INTO MIN MAX X FROM DUMMY              ELSE                          -- MIN LAT A2  LAT B1    LAT B1                 SELECT LAT B1 INTO MIN MAX X FROM DUMMY              END IF          ELSEIF LAT B2  gt  LAT B1 THEN   -- MAX LAT B1  LAT B2    LAT B2             IF LAT A2  lt  LAT B2 THEN       -- MIN LAT A2  LAT B2    LAT A2                 SELECT LAT A2 INTO MIN MAX X FROM DUMMY              ELSE                          -- MIN LAT A2  LAT B2    LAT B2                 SELECT LAT B2 INTO MIN MAX X FROM DUMMY              END IF          END IF      END IF                    IF XA  lt  MAX MIN X OR        XA  gt  MIN MAX X THEN          SELECT 0 INTO DOESINTERSECT FROM DUMMY      END IF           RET DOESINTERSECT     DOESINTERSECT  END

User · Answer

if your data define line you just have to prove that they are not parallel  To do this you can compute    alpha   float y2 - y1     x2 - x1     If this coefficient is equal for both Line1 and Line2  it means the line are parallel  If not  it means they will intersect    If they are parallel you then have to prove that they are not the same  For that  you compute     beta   y1 - alpha x1   If beta is the same for Line1 and Line2 it means you line intersect as they are equal  If they are segment  you still have to compute alpha and beta as described above for each Line  Then you have to check that  beta1 - beta2     alpha1 - alpha2  is greater than Min x1 line1  x2 line1  and less than Max x1 line1  x2 line1

User · Answer

Resolved but still why not with python        def islineintersect line1  line2       i1    min line1 0  0   line1 1  0    max line1 0  0   line1 1  0        i2    min line2 0  0   line2 1  0    max line2 0  0   line2 1  0        ia    max i1 0   i2 0    min i1 1   i2 1        if max line1 0  0   line1 1  0    lt  min line2 0  0   line2 1  0            return False     m1    line1 1  1  - line1 0  1     1     line1 1  0  - line1 0  0     1      m2    line2 1  1  - line2 0  1     1     line2 1  0  - line2 0  0     1      if m1    m2          return False     b1   line1 0  1  - m1   line1 0  0      b2   line2 0  1  - m2   line2 0  0      x1    b2 - b1     m1 - m2      if  x1  lt  max i1 0   i2 0    or  x1  gt  min i1 1   i2 1             return False     return True   This   print islineintersect   15  20    100  200      210  5    23  119      Output   True   And this   print islineintersect   15  20    100  200      -1  -5    -5  -5      Output   False

User · Answer

User  i 4 got points to this page with a very efficent solution in Python  I reproduce it here for convenience  since it would have made me happy to have it here    def ccw A B C       return  C y-A y     B x-A x   gt   B y-A y     C x-A x     Return true if line segments AB and CD intersect def intersect A B C D       return ccw A C D     ccw B C D  and ccw A B C     ccw A B D

User · Answer

This is what I ve got for AS3  don t know much about python but the concept is there      public function getIntersectingPointF  A Point   B Point   C Point   D Point  Number           var A Point    A clone            var B Point    B clone            var C Point    C clone            var D Point    D clone            var f ab Number    D x - C x     A y - C y  -  D y - C y     A x - C x               are lines parallel         if  f ab    0    return Infinity             var f cd Number    B x - A x     A y - C y  -  B y - A y     A x - C x           var f d Number    D y - C y     B x - A x  -  D x - C x     B y - A y           var f1 Number   f ab f d         var f2 Number   f cd   f d         if  f1    Infinity    f1  lt   0    f1  gt   1    return Infinity            if  f2    Infinity    f2  lt   0    f2  gt   1    return Infinity            return f1             public function getIntersectingPoint  A Point   B Point   C Point   D Point  Point               var f Number   getIntersectingPointF  A   B   C   D           if  f    Infinity    f  lt   0    f  gt   1    return null             var retPoint Point   Point interpolate  A   B  1 - f           return retPoint clone

User · Answer

Based on Liran s and Grumdrig s excellent answers here is a complete Python code to verify if closed segments do intersect  Works for collinear segments  segments parallel to axis Y  degenerate segments  devil is in details   Assumes integer coordinates  Floating point coordinates require a modification to points equality test   def side a b c           Returns a position of the point c relative to the line going through a and b         Points a  b are expected to be different             d    c 1 -a 1    b 0 -a 0   -  b 1 -a 1    c 0 -a 0       return 1 if d  gt  0 else  -1 if d  lt  0 else 0   def is point in closed segment a  b  c           Returns True if c is inside closed segment  False otherwise          a  b  c are expected to be collinear             if a 0   lt  b 0           return a 0   lt   c 0  and c 0   lt   b 0      if b 0   lt  a 0           return b 0   lt   c 0  and c 0   lt   a 0       if a 1   lt  b 1           return a 1   lt   c 1  and c 1   lt   b 1      if b 1   lt  a 1           return b 1   lt   c 1  and c 1   lt   a 1       return a 0     c 0  and a 1     c 1     def closed segment intersect a b c d           Verifies if closed segments a  b  c  d do intersect              if a    b          return a    c or a    d     if c    d          return c    a or c    b      s1   side a b c      s2   side a b d         All points are collinear     if s1    0 and s2    0          return               is point in closed segment a  b  c  or is point in closed segment a  b  d  or               is point in closed segment c  d  a  or is point in closed segment c  d  b         No touching and on the same side     if s1 and s1    s2          return False      s1   side c d a      s2   side c d b         No touching and on the same side     if s1 and s1    s2          return False      return True

User · Answer

This is my way of checking for line crossing and where the intersection occurs   Lets use x1 through x4 and y1 through y4  Segment1     X1  Y1    X2  Y2   Segment2     X3  Y3    X4  Y4     Then we need some vectors to represent them  dx1   X2 - X1 dx2   X4 - X4 dy1   Y2 - Y1 dy2   Y4 - Y3   Now we look at the determinant  det   dx1   dy2 - dx2   dy1   If the determinant is 0 0  then the line segments are parallel   This could mean they overlap   If they overlap just at endpoints  then there is one intersection solution   Otherwise there will be infinite solutions   With infinitely many solutions  what do say is your point of intersection   So it s an interesting special case   If you know ahead of time that the lines can t overlap then you can just check if det    0 0 and if so just say they don t intersect and be done   Otherwise  lets continue on  dx3   X3 - X1 dy3   Y3 - Y1  det1   dx1   dy3 - dx3   dy1 det2   dx2   dy3 - dx3   dy2   Now  if det  det1 and det2 are all zero  then your lines are co-linear and could overlap   If det is zero but either det1 or det2 are not  then they are not co-linear  but are parallel  so there is no intersection   So what s left now if det is zero is a 1D problem instead of 2D   We will need to check one of two ways  depending if dx1 is zero or not  so we can avoid division by zero    If dx1 is zero then just do the same logic with y values rather than x below   s   X3   dx1 t   X4   dx1   This computes two scalers  such that if we scale the vector  dx1  dy1  by s we get point  x3  y3   and by t we get  x4  y4    So if either s or t is between 0 0 and 1 0  then point 3 or 4 lies on our first line   Negative would mean the point is behind the start of our vector  while   1 0 means it is further ahead of the end of our vector   0 0 means it is at  x1  y1  and 1 0 means it is at  x2  y2    If both s and t are  lt  0 0 or both are   1 0  then they don t intersect   And that handles the parallel lines special case   Now  if det    0 0 then  s   det1   det t   det2   det if  s  lt  0 0    s  gt  1 0    t  lt  0 0    t  gt  1 0      return false     no intersect   This is similar to what we were doing above really   Now if we pass the above test  then our line segments intersect  and we can calculate the intersection quite easily like so   Ix   X1   t   dx1 Iy   Y1   t   dy1   If you want to dig deeper into what the math is doing  look into Cramer s Rule

User · Answer

The equation of a line is   f x    A x   b   y   For a segment  it is exactly the same  except that x is included on an interval I   If you have two segments  defined as follow   Segment1     X1  Y1    X2  Y2   Segment2     X3  Y3    X4  Y4     The abcisse Xa of the potential point of intersection  Xa Ya  must be contained in both interval I1 and I2  defined as follow    I1    min X1 X2   max X1 X2   I2    min X3 X4   max X3 X4     And we could say that Xa is included into    Ia    max  min X1 X2   min X3 X4           min  max X1 X2   max X3 X4       Now  we need to check that this interval Ia exists    if  max X1 X2   lt  min X3 X4        return False    There is no mutual abcisses   So  we have two line formula  and a mutual interval  Your line formulas are   f1 x    A1 x   b1   y f2 x    A2 x   b2   y   As we got two points by segment  we are able to determine A1  A2  b1 and b2   A1    Y1-Y2   X1-X2     Pay attention to not dividing by zero A2    Y3-Y4   X3-X4     Pay attention to not dividing by zero b1   Y1-A1 X1   Y2-A1 X2 b2   Y3-A2 X3   Y4-A2 X4   If the segments are parallel  then A1    A2    if  A1    A2       return False    Parallel segments   A point  Xa Ya  standing on both line must verify both formulas f1 and f2   Ya   A1   Xa   b1 Ya   A2   Xa   b2 A1   Xa   b1   A2   Xa   b2 Xa    b2 - b1     A1 - A2      Once again  pay attention to not dividing by zero   The last thing to do is check that Xa is included into Ia   if    Xa  lt  max  min X1 X2   min X3 X4     or       Xa  gt  min  max X1 X2   max X3 X4            return False    intersection is out of bound else      return True   In addition to this  you may check at startup that two of the four provided points are not equals to avoid all that testing

User · Answer

We can also solve this utilizing vectors    Let s define the segments as  start  end   Given two such segments  A  B  and  C  D  that both have non-zero length  we can choose one of the endpoints to be used as a reference point so that we get three vectors   x   0 y   1 p   A-C    C x -A x   C y -A y   q   B-A    B x -A x   B y -A y   r   D-C    D x -C x   D y -C y     From there  we can look for an intersection by calculating t and u in p   t r   u q  After playing around with the equation a little  we get   t    q y  p x  - q x  p y    q x  r y  - q y  r x   u    p x    t r x   q x    Thus  the function is   def intersects a  b       p    b 0  0 -a 0  0   b 0  1 -a 0  1       q    a 1  0 -a 0  0   a 1  1 -a 0  1       r    b 1  0 -b 0  0   b 1  1 -b 0  1        t    q 1  p 0  - q 0  p 1    q 0  r 1  - q 1  r 0             if  q 0  r 1  - q 1  r 0      0           else  q 1  p 0  - q 0  p 1       u    p 0    t r 0   q 0            if q 0     0           else  p 1    t r 1   q 1       return t  gt   0 and t  lt   1 and u  gt   0 and u  lt   1

User · Answer

You don t have to compute exactly where does the segments intersect  but only understand whether they intersect at all  This will simplify the solution   The idea is to treat one segment as the  anchor  and separate the second segment into 2 points  Now  you will have to find the relative position of each point to the  anchored  segment  OnLeft  OnRight or Collinear   After doing so for both points  check that one of the points is OnLeft and the other is OnRight  or perhaps include Collinear position  if you wish to include improper intersections as well    You must then repeat the process with the roles of anchor and separated segments   An intersection exists if  and only if  one of the points is OnLeft and the other is OnRight  See this link for a more detailed explanation with example images for each possible case   Implementing such method will be much easier than actually implementing a method that finds the intersection point  given the many corner cases which you will have to handle as well    Update  The following functions should illustrate the idea  source  Computational Geometry in C   Remark  This sample assumes the usage of integers  If you re using some floating-point representation instead  which could obviously complicate things   then you should determine some epsilon value to indicate  equality   mostly for the IsCollinear evaluation       points  a  and  b  forms the anchored segment     point  c  is the evaluated point bool IsOnLeft Point a  Point b  Point c         return Area2 a  b  c   gt  0     bool IsOnRight Point a  Point b  Point c         return Area2 a  b  c   lt  0     bool IsCollinear Point a  Point b  Point c         return Area2 a  b  c     0        calculates the triangle s size  formed by the  anchor  segment and additional point  int Area2 Point a  Point b  Point c         return  b X - a X     c Y - a Y  -              c X - a X     b Y - a Y       Of course  when using these functions  one must remember to check that each segment lies  between  the other segment  since these are finite segments  and not infinite lines      Also  using these functions you can understand whether you ve got a proper or improper intersection    Proper  There are no collinear points  The segments crosses each other  from side to side   Improper  One segment only  touches  the other  at least one of the points is collinear to the anchored segment

User · Answer

Implemented in JAVA   However It seems that it does not work for co-linear lines  aka line segments that exist within each other L1 0 0  10 10  L2 1 1  2 2   public class TestCode      public class Point         public double x   0      public double y   0      public Point            public class Line         public Point p1  p2      public Line  double x1  double y1  double x2  double y2               p1   new Point          p2   new Point          p1 x   x1        p1 y   y1        p2 x   x2        p2 y   y2                 line segments   private static Line s1    private static Line s2     public TestCode           s1   new Line 0 0 0 10       s2   new Line -1 0 0 10          public TestCode double x1  double y1       double x2  double y2      double x3  double y3      double x4  double y4          s1   new Line x1 y1  x2 y2       s2   new Line x3 y3  x4 y4          public static void main String args             TestCode code    null                                    code   new TestCode 0 0 0 10                           0 1 0 5        if  intersect code           System out println   OK COLINEAR  INTERSECTS            else        System out println   ERROR COLINEAR  DO NOT INTERSECT                                         code   new TestCode 0 0 0 10                           0 1 0 10        if  intersect code           System out println   OK COLINEAR  INTERSECTS            else        System out println   ERROR COLINEAR  DO NOT INTERSECT                                         code   new TestCode 0 0 10 0                           5 0 15 0        if  intersect code           System out println   OK COLINEAR  INTERSECTS            else        System out println   ERROR COLINEAR  DO NOT INTERSECT                                         code   new TestCode 0 0 10 0                           0 0 15 0        if  intersect code           System out println   OK COLINEAR  INTERSECTS            else        System out println   ERROR COLINEAR  DO NOT INTERSECT                                          code   new TestCode 0 0 10 10                           1 1 5 5        if  intersect code           System out println   OK COLINEAR  INTERSECTS            else        System out println   ERROR COLINEAR  DO NOT INTERSECT                                         code   new TestCode 0 0 0 10                           -1 -1 0 10        if  intersect code           System out println   OK SLOPE END  INTERSECTS            else        System out println   ERROR SLOPE END  DO NOT INTERSECT                                         code   new TestCode -10 -10 10 10                           -10 10 10 -10        if  intersect code           System out println   OK SLOPE Intersect 0 0   INTERSECTS            else        System out println   ERROR SLOPE Intersect 0 0   DO NOT INTERSECT                                         code   new TestCode -10 -10 10 10                           -3 -2 50 -2        if  intersect code           System out println   OK SLOPE Line2 VERTIAL  INTERSECTS            else        System out println   ERROR SLOPE Line2 VERTICAL  DO NOT INTERSECT                                         code   new TestCode -10 -10 10 10                           50 -2 -3 -2        if  intersect code           System out println   OK SLOPE Line2  reversed  VERTIAL  INTERSECTS            else        System out println   ERROR SLOPE Line2  reversed  VERTICAL  DO NOT INTERSECT                                         code   new TestCode 0 0 0 10                           1 0 1 10        if  intersect code           System out println   ERROR PARALLEL VERTICAL  INTERSECTS            else        System out println   OK PARALLEL VERTICAL  DO NOT INTERSECT                                         code   new TestCode 0 2 10 2                           0 10 10 10        if  intersect code           System out println   ERROR PARALLEL HORIZONTAL  INTERSECTS            else        System out println   OK PARALLEL HORIZONTAL  DO NOT INTERSECT                                         code   new TestCode 0 10 5 13 75                           0 18 75 10 15        if  intersect code           System out println   ERROR PARALLEL SLOPE  75  INTERSECTS            else        System out println   OK PARALLEL SLOPE  75  DO NOT INTERSECT                                         code   new TestCode 0 0 1 1                           2 -1 2 10        if  intersect code           System out println   ERROR SEPERATE SEGMENTS  INTERSECTS            else        System out println   OK SEPERATE SEGMENTS  DO NOT INTERSECT                                         code   new TestCode 0 0 1 1                           -1 -10 -5 10        if  intersect code           System out println   ERROR SEPERATE SEGMENTS 2  INTERSECTS            else        System out println   OK SEPERATE SEGMENTS 2  DO NOT INTERSECT              public static boolean intersect  TestCode code           return intersect  code s1  code s2          public static boolean intersect  Line line1  Line line2           double i1min   Math min line1 p1 x  line1 p2 x       double i1max   Math max line1 p1 x  line1 p2 x       double i2min   Math min line2 p1 x  line2 p2 x       double i2max   Math max line2 p1 x  line2 p2 x        double iamax   Math max i1min  i2min       double iamin   Math min i1max  i2max        if  Math max line1 p1 x  line1 p2 x   lt  Math min line2 p1 x  line2 p2 x          return false       double m1    line1 p2 y - line1 p1 y     line1 p2 x - line1 p1 x        double m2    line2 p2 y - line2 p1 y     line2 p2 x - line2 p1 x         if  m1    m2           return false         b1   line1 0  1  - m1   line1 0  0        b2   line2 0  1  - m2   line2 0  0      double b1   line1 p1 y - m1   line1 p1 x      double b2   line2 p1 y - m2   line2 p1 x      double x1    b2 - b1     m1 - m2       if   x1  lt  Math max i1min  i2min       x1  gt  Math min i1max  i2max             return false      return true          Output thus far is   ERROR COLINEAR  DO NOT INTERSECT ERROR COLINEAR  DO NOT INTERSECT ERROR COLINEAR  DO NOT INTERSECT ERROR COLINEAR  DO NOT INTERSECT ERROR COLINEAR  DO NOT INTERSECT OK SLOPE END  INTERSECTS OK SLOPE Intersect 0 0   INTERSECTS OK SLOPE Line2 VERTIAL  INTERSECTS OK SLOPE Line2  reversed  VERTIAL  INTERSECTS OK PARALLEL VERTICAL  DO NOT INTERSECT OK PARALLEL HORIZONTAL  DO NOT INTERSECT OK PARALLEL SLOPE  75  DO NOT INTERSECT OK SEPERATE SEGMENTS  DO NOT INTERSECT OK SEPERATE SEGMENTS 2  DO NOT INTERSECT

User · Answer

Suppose the two segments have endpoints A B and C D  The numerically robust way to determine intersection is to check the sign of the four determinants     Ax-Cx  Bx-Cx        Ax-Dx  Bx-Dx     Ay-Cy  By-Cy        Ay-Dy  By-Dy      Cx-Ax  Dx-Ax        Cx-Bx  Dx-Bx     Cy-Ay  Dy-Ay        Cy-By  Dy-By     For intersection  each determinant on the left must have the opposite sign of the one to the right  but there need not be any relationship between the two lines  You are basically checking each point of a segment against the other segment to make sure they lie on opposite sides of the line defined by the other segment   See here  http   www cs cmu edu  quake robust html

User · Answer

I thought I d contribute a nice Swift solution   struct Pt       var x  Double     var y  Double    struct LineSegment       var p1  Pt     var p2  Pt    func doLineSegmentsIntersect ls1  LineSegment  ls2  LineSegment  - gt  Bool        if  ls1 p2 x-ls1 p1 x    0      handle vertical segment1         if  ls2 p2 x-ls2 p1 x    0                  both lines are vertical and parallel             return false                    let x   ls1 p1 x          let slope2    ls2 p2 y-ls2 p1 y   ls2 p2 x-ls2 p1 x          let c2   ls2 p1 y-slope2 ls2 p1 x          let y   x slope2 c2    y intersection point          return  y  gt  ls1 p1 y  amp  amp  x  lt  ls1 p2 y      y  gt  ls1 p2 y  amp  amp  y  lt  ls1 p1 y     check if y is between y1 y2 in segment1            if  ls2 p2 x-ls2 p1 x    0      handle vertical segment2          let x   ls2 p1 x          let slope1    ls1 p2 y-ls1 p1 y   ls1 p2 x-ls1 p1 x          let c1   ls1 p1 y-slope1 ls1 p1 x          let y   x slope1 c1    y intersection point          return  y  gt  ls2 p1 y  amp  amp  x  lt  ls2 p2 y      y  gt  ls2 p2 y  amp  amp  y  lt  ls2 p1 y     validate that y is between y1 y2 in segment2             let slope1    ls1 p2 y-ls1 p1 y   ls1 p2 x-ls1 p1 x      let slope2    ls2 p2 y-ls2 p1 y   ls2 p2 x-ls2 p1 x       if  slope1    slope2      segments are parallel         return false            let c1   ls1 p1 y-slope1 ls1 p1 x     let c2   ls2 p1 y-slope2 ls2 p1 x      let x    c2-c1   slope1-slope2       return    x  gt  ls1 p1 x  amp  amp  x  lt  ls1 p2 x      x  gt  ls1 p2 x  amp  amp  x  lt  ls1 p1 x    amp  amp            x  gt  ls2 p1 x  amp  amp  x  lt  ls2 p2 x      x  gt  ls2 p2 x  amp  amp  x  lt  ls2 p1 x          validate that x is between x1 x2 in both segments

User · Answer

Calculate the intersection point of the lines laying on your segments  it means basically to solve a linear equation system   then check whether is it between the starting and ending points of your segments

User · Answer

Here is another python code to check whether closed segments intersect  It is the rewritten version of the C   code in http   www cdn geeksforgeeks org check-if-two-given-line-segments-intersect   This implementation covers all special cases  e g  all points colinear    def on segment p  q  r          Given three colinear points p  q  r  the function checks if      point q lies on line segment  pr              if  q 0   lt   max p 0   r 0   and q 0   gt   min p 0   r 0   and         q 1   lt   max p 1   r 1   and q 1   gt   min p 1   r 1             return True     return False  def orientation p  q  r          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              val     q 1  - p 1      r 0  - q 0   -               q 0  - p 0      r 1  - q 1        if val    0          return 0    colinear     elif val  gt  0          return 1     clockwise     else          return 2    counter-clockwise  def do intersect p1  q1  p2  q2          Main function to check whether the closed line segments p1 - q1 and p2         - q2 intersect        o1   orientation p1  q1  p2      o2   orientation p1  q1  q2      o3   orientation p2  q2  p1      o4   orientation p2  q2  q1         General case     if  o1    o2 and o3    o4           return True        Special Cases       p1  q1 and p2 are colinear and p2 lies on segment p1q1     if  o1    0 and on segment p1  p2  q1            return True        p1  q1 and p2 are colinear and q2 lies on segment p1q1     if  o2    0 and on segment p1  q2  q1            return True        p2  q2 and p1 are colinear and p1 lies on segment p2q2     if  o3    0 and on segment p2  p1  q2            return True        p2  q2 and q1 are colinear and q1 lies on segment p2q2     if  o4    0 and on segment p2  q1  q2            return True      return False   Doesn t fall in any of the above cases   Below is a test function to verify that it works   import matplotlib pyplot as plt  def test intersect func        p1    1  1      q1    10  1      p2    1  2      q2    10  2      fig  ax   plt subplots       ax plot  p1 0   q1 0     p1 1   q1 1     x-       ax plot  p2 0   q2 0     p2 1   q2 1     x-       print do intersect p1  q1  p2  q2        p1    10  0      q1    0  10      p2    0  0      q2    10  10      fig  ax   plt subplots       ax plot  p1 0   q1 0     p1 1   q1 1     x-       ax plot  p2 0   q2 0     p2 1   q2 1     x-       print do intersect p1  q1  p2  q2        p1    -5  -5      q1    0  0      p2    1  1      q2    10  10      fig  ax   plt subplots       ax plot  p1 0   q1 0     p1 1   q1 1     x-       ax plot  p2 0   q2 0     p2 1   q2 1     x-       print do intersect p1  q1  p2  q2        p1    0  0      q1    1  1      p2    1  1      q2    10  10      fig  ax   plt subplots       ax plot  p1 0   q1 0     p1 1   q1 1     x-       ax plot  p2 0   q2 0     p2 1   q2 1     x-       print do intersect p1  q1  p2  q2

User · Answer

Here is C code to check if two points are on the opposite sides of the line segment  Using this code you can check if two segments intersect as well      true if points p1  p2 lie on the opposite sides of segment s1--s2 bool oppositeSide  Point2f s1  Point2f s2  Point2f p1  Point2f p2       calculate normal to the segment Point2f vec   s1-s2  Point2f normal vec y  -vec x      no need to normalize     vectors to the points Point2f v1   p1-s1  Point2f v2   p2-s1      compare signs of the projections of v1  v2 onto the normal float proj1   v1 dot normal   float proj2   v2 dot normal   if  proj1  0    proj2  0          cout lt  lt  collinear points  lt  lt endl   return SIGN proj1     SIGN proj2

[python] How can I check if two segments intersect?

Examples related to python

Examples related to math

Examples related to geometry