Orientation Tests and Segment Intersection

The whole subject leans on one question

Welcome to geometry on the algorithm-design ladder. Coming up this rung you will build a convex hull, learn the sweep-line paradigm, and meet number-theoretic algorithms — but nearly all of the geometric work rests on a single, almost laughably small operation. Given three points A, B, C in the plane, when you walk from A to B and then turn toward C, do you turn left, turn right, or keep going straight? That is the orientation test, and it is the geometric equivalent of comparing two numbers: tiny, exact, and everywhere. Graham scan, segment crossing, point-in-polygon, and the gift-wrapping hull all reduce to asking this question over and over.

Why insist on a left/right/straight primitive instead of, say, computing the slopes of AB and AC and comparing them? Because slopes blow up for vertical lines (division by zero), they hide sign information, and they invite floating-point division exactly where you least want it. The orientation test answers the turn question with a single signed quantity built from additions and multiplications only — no division, no square roots, no angles. Keeping it that simple is not laziness; as we will see, it is what lets us run the whole thing in exact integer arithmetic when the input coordinates are integers, and that exactness is the difference between a hull algorithm that works and one that crashes on a tie.

The cross product, and why its sign is the answer

Here is the formula, and then the picture that makes it obvious. Form the two vectors leaving A: vector AB = (B - A) and vector AC = (C - A). The 2D cross product of these is the single number cross = (Bx - Ax)(Cy - Ay) - (By - Ay)(Cx - Ax). Its sign is the orientation: positive means A -> B -> C makes a left (counterclockwise) turn, negative means a right (clockwise) turn, and exactly zero means the three points are collinear — you went straight. One subtraction-heavy expression, one sign check, and the turn question is answered.

Why does that particular combination of products encode the turn? Because the cross product equals twice the signed area of triangle ABC. Signed area is positive when the vertices are listed counterclockwise and negative when clockwise — that is its definition — so its sign and the turn direction are the same fact wearing two outfits. And when the three points lie on one line, the triangle is degenerate with zero area, which is exactly the collinear case giving cross = 0. So the orientation test is not a magic trick; it is reading off the sign of an area you could have computed in high school. Knowing this is what makes the test trustworthy rather than memorized.

orient(A, B, C):
    cross = (Bx - Ax)*(Cy - Ay) - (By - Ay)*(Cx - Ax)
    if cross > 0: return LEFT      # counterclockwise, signed area > 0
    if cross < 0: return RIGHT     # clockwise,        signed area < 0
    return COLLINEAR               # signed area = 0

A tiny trace, and the trap that ends careers

Let us run it once. Take A = (0,0), B = (4,0), C = (2,3). Then cross = (4 - 0)(3 - 0) - (0 - 0)(2 - 0) = 12 - 0 = 12 > 0, so the turn from AB toward C is LEFT — C sits above the line through A and B, which matches the picture. Move C down to (2,-3) and the same arithmetic gives -12, a RIGHT turn. Put C on the line at (2,0) and cross = 0, COLLINEAR. Three evaluations, three answers, all from one formula — and notice we never divided or took an angle, so with integer inputs each of these is an exact integer comparison on the RAM model.

There is a second, quieter trap: overflow. With large integer coordinates the products inside cross can exceed a 32-bit integer even though the inputs fit comfortably. If coordinates can be up to about 10^9, a product of two coordinate differences can reach about 10^18, which overflows 32-bit but still fits a 64-bit signed integer. The fix is boring and essential — do the arithmetic in 64-bit (or wider) integers. This is a concrete reminder that the asymptotic cost hides constants, but it also hides assumptions about machine word size; the abstract "O(1) orientation test" is only O(1) if your numbers actually fit in a machine word.

From orientation to "do these two segments cross?"

Now the payoff. We want a segment intersection test: given segments P1-P2 and P3-P4, do they share at least one point? It is tempting to find the infinite lines, solve for their crossing point, and check it lies on both segments — but that route does division and floating-point and special cases for parallel lines. The orientation test gives a cleaner, division-free idea. Two segments cross iff each segment straddles the line through the other: P1 and P2 are on opposite sides of line P3-P4, and simultaneously P3 and P4 are on opposite sides of line P1-P2. "Opposite sides" is exactly two orientation tests with different signs.

1. Compute four orientations: d1 = orient(P3, P4, P1), d2 = orient(P3, P4, P2), d3 = orient(P1, P2, P3), d4 = orient(P1, P2, P4). Each tells which side of one segment's line an endpoint of the other segment falls on.
2. Proper-crossing case: if d1 and d2 have strictly opposite signs AND d3 and d4 have strictly opposite signs, the segments cross at a single interior point — return true. Each pair straddling the other is exactly the geometric condition for an X-shaped crossing.
3. Collinear / touching cases: if any di is zero, an endpoint lies on the other line. Then test whether that endpoint actually lies within the other segment's bounding box (its x and y ranges). If so, they touch or overlap — return true. This catches endpoints that graze a segment and collinear overlap that the straddle test alone would miss.
4. Otherwise return false. If neither straddle holds and no endpoint lies on the other segment, the segments are apart.

Why is the straddle condition correct? Segment P1-P2 crosses the full line through P3-P4 exactly when its two endpoints sit on opposite sides of that line — that is the intermediate-value idea: as you slide from P1 to P2 the signed distance to the line changes sign, so it passes through zero somewhere on the segment. Requiring this for both segments pins the crossing point onto both segments at once, not merely onto the infinite lines. The reason we still need the collinear branch is that "opposite sides" is a strict condition; when an orientation is zero the point is on the line, not strictly across it, and those boundary touches are real intersections the strict test silently drops.

Honest limits, and where this primitive is heading

Be clear about what this test does and does not give. It answers the decision question — do they intersect, yes or no — in O(1) time per pair, with no division, fully exact on integer inputs. It does not by itself hand you the intersection point; computing that does require solving the line equations (and reintroduces division and floating-point, so do it only once you already know an intersection exists). And for n segments, the brute-force "test every pair" approach is O(n^2) calls — fine for small n, but for many segments the sweep-line method later in this rung reports all intersections in O((n + k) log n) time, where k is the number of intersections found, by cleverly avoiding most of the pairwise tests.

One last honesty check about cost. We keep calling the orientation test "O(1)," and on the RAM model with fixed-width words it truly is. But that assumes each multiply is a unit-cost step — true while products fit in a machine word, as we arranged with 64-bit arithmetic. If coordinates grow without bound, the numbers themselves grow and arithmetic stops being constant-time, so the abstraction has a boundary like every abstraction does. For the integer ranges of ordinary problems the O(1) claim is exactly right; just remember it is a claim about a model, not a law of nature, and it is the assumption that lets the whole geometric edifice above stand on a constant-time foundation.