the orientation (CCW) test

Stand at point A, walk to point B, and then ask: to reach a third point C, do I turn left, turn right, or keep going straight? That single yes/no/which-way question is the workhorse of computational geometry. Almost every geometry algorithm — testing whether two segments cross, building a convex hull, sorting points around a center — boils down to asking this turn direction over and over. The orientation test answers it with one tiny arithmetic formula and, crucially, with no division and no square roots, so it can be done exactly on integer coordinates without any rounding error.

The formula is a cross product. Given A = (ax, ay), B = (bx, by), C = (cx, cy), compute the signed quantity d = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax). If d > 0 the three points make a counterclockwise (left) turn; if d < 0 they make a clockwise (right) turn; if d = 0 the three points are collinear (they lie on one straight line). Here is why it works: d is exactly twice the signed area of triangle ABC. A positive signed area means C lies to the left of the directed line from A through B, a negative area means to the right, and zero area means the triangle is flat, i.e. the points are in a line. So one subtraction-and-multiply pattern tells you area, turn direction, and which side of a line a point is on, all at once.

This test matters because it is the atomic operation that bigger algorithms call thousands of times, and because doing it without division keeps it exact. With integer inputs every intermediate value is an integer, so d = 0 reliably detects true collinearity instead of a near-miss caused by floating-point rounding — a notorious source of bugs in geometry code. One honest caveat: the products can be large (roughly the square of the coordinate magnitude), so on fixed-width integers you must watch for overflow and pick a wide enough integer type.