Check if two line segments are colliding (only check if they are intersecting, not where)

Question

I need a fast algorithm for checking if two non-infinite lines are crossing. Have to be fast because it'll run on a cell phone a lot.

The algorithm do only have to return yes or no, it does not have to find out exactly where the lines cross!

I have looked here: How do you detect where two line segments intersect? But that thread is a jungle, people keep saying that "this is the answer" but then two other guys say that it is incorrect because of this-and-that bug.

Please help me find a good and working algorithm for this.

Just to be clear: I need a function that you give...
lineApointAx
lineApointAy
lineApointBx
lineApointBy
lineBpointAx
lineBpointAy
lineBpointBx
lineBpointBy
...and that returns true or false depending on if the two lines cross or not.

I would appreciate if you answered with (pseudo-)code, not formulas.

Solution 1

It is necessary and sufficient that the two ends of one segment are on different sides of the other segment, and vise-versa. To determine which side a point is on, just take a cross-product and see whether it's positive or negative:

(B_x - A_x)(P_y - B_y) - (B_y - A_y)(P_x - B_x)

EDIT:
To spell it out: suppose you're looking at two line segments, [AB] and [CD]. The segments intersect if and only if ((A and B are of different sides of [CD]) and (C and D are on different sides of [AB])).

To see whether two points, P and Q, are on different sides of a line segment [EF], compute two cross products, one for P and one for Q:

(F_x - E_x)(P_y - F_y) - (F_y - E_y)(P_x - F_x)

(F_x - E_x)(Q_y - F_y) - (F_y - E_y)(Q_x - F_x)

If the results have the same sign (both positive or both negative) then forget it, the points are on the same side, the segments do not intersect. If one is positive and the other negative, then the points are on opposite sides.

Solution 2

If you're two given points are (X1,Y1) and (X2,Y2), imagine both are infinite lines, not just segments:

1. Determine the formula for both (see: http://en.wikipedia.org/wiki/Linear_equation#Two-point_form)

2. Determine the intersection point for the two lines (see: http://zonalandeducation.com/mmts/intersections/intersectionOfTwoLines1/intersectionOfTwoLines1.html)

3. If X1 < intersectionX < X2 and Y1 < intersectionY < Y2, then yes, the segments intersect.