Another algorithm is described here, which is based on these slides.
Given line segments p1 -> q1 and p2 -> q2, the line segments intersect if:
- General Case:
- if (p1, q1, p2) and (p1, q1, q2) have different orientations and
- (p2, q2, p1) and (p2, q2, q1) have different orientations
- Special Case
- if (p1, q1, p2), (p1, q1, q2), (p2, q2, p1), and (p2, q2, q1) are all collinear and
- the x-projections of (p1, q1) and (p2, q2) intersect and
- the y-projections of (p1, q1) and (p2, q2) intersect
where the 'orientation' can be 'clockwise', 'counterclockwise' or 'collinear'.
Intuitively: if a line segment does not cross another line segment, it is entirely 'on one side' of the other segment. Only then will tracing (p1, q1, p2) and (p1, q1, q2) or (p2, q2, p1) and (p2, q2, q1) result in tracing the triangle in the same direction.