line segment intersection
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 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.
- 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
- 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).
- 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/