the segment-intersection test

Two straight lines almost always cross somewhere, but two finite line segments — each a piece of a line with two endpoints — might not, because the crossing point could fall outside one or both segments. Picture two pencils lying on a table: do they actually touch, or would they only meet if you extended them? Deciding this cleanly, for any two segments and without computing the (possibly fractional) intersection point, is a basic building block for collision detection, map overlays, and the line-sweep algorithms that find all intersections in a big set of segments.

The clean way uses four orientation tests and nothing else. For segments P1P2 and P3P4, compute the turn direction of P3 and of P4 with respect to the line P1->P2, and the turn direction of P1 and of P2 with respect to the line P3->P4. The general rule: the two segments properly cross when P3 and P4 lie on opposite sides of line P1P2 (their two orientations have opposite signs) AND P1 and P2 lie on opposite sides of line P3P4. Intuitively, if P3 is to the left of P1P2 but P4 is to the right, the segment P3P4 must cut across the line P1P2; require the symmetric condition for the other pair and the two segments must genuinely meet. Because each orientation is just a cross product, the whole test is exact on integers with no division.

The honest complication is the boundary cases, where an orientation comes out zero: an endpoint lies exactly on the other segment, or the segments are collinear and overlap. These need special handling — typically a quick on-segment bounding-box check to confirm the touching endpoint actually lies within the other segment's extent. Skipping these degenerate cases is the classic bug in beginner geometry code. The test runs in O(1) time per pair; finding all intersections among n segments is then handled by the line-sweep paradigm rather than by checking all O(n^2) pairs.