Line segment intersection is classic computer science problem related to computer graphics or computed geometry. Your given two line segments and you need to write c or c++ program to check whether they intersect or not. Line segment is different from line. The line segment has its end points information.

line segment intersectionIn the above figure the line segments AB and CD are intersecting each other while the line segments EF and GH are not intersecting.

line segment intersection

It is easy to see the line segment intersection but it is hard to write a program for detecting intersection. Actually geometrical programing problem requires good understanding of co-ordinate geometry.

How to

  • We know that every straight line can be represented by an equation in the above form
                     Ax + By = C
    where A and B are not both equal to zero. A, B and C are some numbers which defines the line.
  • The expression Ax + By = C is equation of a line. We also know that line segment is section of a line. Any line segment has at least two known points.
  • A line passing through (x1, y1) and (x2, y2) where x2 ≠ x1 can be represented in the  form

towpointform

  • The above for can be expressed as x(y2-y1) + y(x1-x2) = x1y2 – x2y1, so now it is clear that if we are given tow points (x1,y1) and (x2,y2) , we can calculate A, B and C of the generic line equation Ax + by = C.

A1 = y2-y1
B1 = x1-x2
C1 = A1*x1+B1*y1

“So now we are able to extract Ax+By =C expression from given line segment (x1,y1,x2,y2)”

“In this way from given line segments we can calculate different linear equation of the form Ax + By = C”

  • Now, suppose we have following equations after calculating A,B and C of each lines equations
      A1x + B1y = C1  ( line 1)
                  A2x + B2y = C2  (line 2 )
  • Two non parallel non collinear lines always intersect. The intersection point is common to both the lines. Let us say line 1 and line 2 intersect at point (x,y).
  • The intersection point (x,y) can be calculated by solving the two equation ( A1x + B1y = C1 and A2x + B2y = C2 ).
  • We can solve these equation using Cramer’s rule to get intersection point (x,y).

cramers rule

 

  • If the determinant det = A1B2 – A2B1 is zero, it means lines are parallel, else calculate intersection point (x,y) of lines.
  • Here is our final aim, the intersection point (x,y) calculated from Ax1 + By1 =C1 and Ax2 + By2 =C2 is the location of lines. But our problem is to find the intersecting point of line segment. In this case we need to check whether the intersecting point (x,y) is on both line segments or not.

 min(x1,x2) ≤ x ≤ max(x1,x2)

min(y1,y2) ≤ y ≤ max(y1,y2)

min(x3,x4) ≤ x ≤ max(x3,x4)

min(y3,y4) ≤ y ≤ max(y3,y4)

Read Next post for c++ line segment intersection implementation http://wikistack.com/c-program-to-check-line-segment-intersection/

 Ref:

https://en.wikipedia.org/wiki/Linear_equation

https://www.topcoder.com/community/data-science/data-science-tutorials/geometry-concepts-line-intersection-and-its-applications/