Efficient maths algorithm to calculate intersections

Question

For a game I am developing I need an algorithm that can calculate intersections. I have solved the problem, but the way I have done it is really nasty and I am hoping someone here might have a more elegant solution.

A pair of points represent the end points of a line drawn between them. Given two pairs of points, do the drawn lines intersect, and if so, at what point?

So for example call the lines (A.x, A.y)-(B.x, B.y) and (C.x, C.y)-(D.x, D.y)

Can anyone think of a solution? A solution in any language will do.

Edit: A point I should have made clearer, the algorithm must return false if the point of intersection is beyond the lengths of the line segments.

Answer 1

Most of the answers already here seem to follow the general idea that:

1. find the intersection of two straight lines passing the given points.
2. determine if the intersection belong to both line segments.

But when intersection does not occur often, a better way probably is to reverse these steps:

1. express the straight lines in the form of y = ax + b (line passing A,B) and y = cx + d (line passing C,D)
2. see if C and D are on the same side of y = ax+b
3. see if A and B are on the same side of y = cx+d
4. if the answer to the above are both no, then there is an intersection. otherwise there is no intersection.
5. find the intersection if there is one.

Note: to do step 2, just check if (C.y - a(C.x) - b) and (D.y - a(D.x) - b) have the same sign. Step 3 is similar. Step 5 is just standard math from the two equations.

Furthermore, if you need to compare each line segment with (n-1) other line segments, precomputing step 1 for all lines saves you time.