You are given two straight line segments, each defined by the coordinates of its endpoints. Segment AB goes from (Ax,Ay) to (Bx,By) and segment CD - from (Cx,Cy) to (Dx,Dy).
How would you determine if the two line segments intersect?
(Assume that you can't just draw the lines and see)
The two segments intersect if and only if C and D do not lie on the same side of the line through AB and A and B do not lie on the same side of the line through CD.
So the trick is finding out which side of a line a point lies upon. Probably the most straightforward way to do this is to convert the line to its implicit form: L(x, y) = Px + Qy + R. If L(x, y) > 0 then <x, y> is on one side of the line, if L(x, y) < 0 then <x, y> is on the other side, and if L(x, y) = 0, then <x, y> is on the line.
It's possible to find P, Q, and R by solving some system of linear equations, but there are some shortcuts that can be taken. Assume that we're looking for the values corresponding to the line through A and B. <P, Q> is actually a vector that points perpendicular to the line. The direction of the line through A and B is given by <Bx - Ax, By - Ay>.
In 2D, it's easy to find one vector that is perpendicular to another: just switch the x and y coordinates, and multiply one of them by -1 (try it and see).
This means that we can use <By - Ay, Ax - Bx> for our perpendicular vector. The length of the vector doesn't really matter, just its direction. This gives us P = By - Ay and Q = Ax - Bx.
To find R, just plug one of the points (say, A) into the function. Since the point is on the line, the function evaluates to 0. Thus,
L(Ax, Ay) = P Ax + Q Ay + R = 0
(By - Ay) Ax + (Ax - Bx) Ay + R = 0
AxBy - AxAy + AxAy - AyBx + R = 0
R = AyBx - AxBy
To see whether C and D lie on the same side of the line, substitute them into L(x, y) and multiply the results together. If the value is positive, they intersect.
L(Cx, Cy) L(Dx, Dy) = [(By - Ay)Cx + (Ax - By)Cy + AyBx - AxBy][(By - Ay)Dx + (Ax - By)Dy + AyBx - AxBy]
= (ByCx - AyCx + AxCy - ByCy + AyBx - AxBy)(ByDx - AyDx + AxDy - ByDy + AyBx - AxBy)
(I won't bother multiplying these together, as I think it will make the expression even uglier)
To see whether A and B lie on the same side of the line through C and D, just switch the A's and B's with the C's and D's:
(DyAx - CyAx + CxAy - DyAy + CyDx - CxDy)(DyBx - CyBx + CxBy - DyBy + CyDx - CxDy)
The whole algorithm can thus be written in one statement:
return (ByCx - AyCx + AxCy - ByCy + AyBx - AxBy) *
(ByDx - AyDx + AxDy - ByDy + AyBx - AxBy) > 0
&& (DyAx - CyAx + CxAy - DyAy + CyDx - CxDy) *
(DyBx - CyBx + CxBy - DyBy + CyDx - CxDy) > 0;
Solution
