How
to tell whether two line segments intersect. First, convert to equations for lines.
(x1,y1) (x2,y2) goes to y = (y2-y1)/(x2-x1)x + (y1(x2-x1) –
x1(y2-y1). Now suppose we have two lines, y = m1x+b1, y =
m2x+b2. Solve for x and y. For
example, we have m1x+b1=m2x+b2. x =
(b1-b2)/(m2-m1). Now we want to know whether (x,y) is in between (x1,y1) and (x2,y2),
and the same for the other line
segment. One simple way is to tell
whether the sum of the distance from each
end point to (x,y) is the same as the distance between the end points.
This
is a bit cumbersome. We can do things
with less computation by checking whether
the line of line segment one divides the endpoints of line segment two, and vice versa.
To do this, compute the line the first line segment lies on, and represent it as:
ax + by = c, where (a,b) is a unit vector. Then compute (a,b)*(x1,y1) = c1, and (a,b)*(x2,y2) = c2. We should have either c1 <= c <= c2, or c2 <= c <= c1.