Computational Geometry Basics

The core predicates and primitives - orientation, intersection, and distance - underlying geometric algorithms.

Orientation

Most geometric algorithms rest on the orientation of an ordered triple of points, computed from the sign of the cross product (b-a) x (c-a). Positive means counterclockwise, negative clockwise, zero collinear. This single predicate decides point-in-polygon tests, segment intersection, convex-hull turns, and Delaunay in-circle tests.

Segment intersection

Kronos motion — classical

Two segments intersect when their endpoints straddle each other, checked by four orientation tests, with special handling when a point lies exactly on the other segment (the collinear case). Doing this with the sign of integer cross products avoids the rounding errors that plague slope-based methods.

Point in polygon

python

def point_in_polygon(pt, poly):
    x, y = pt; inside = False; n = len(poly)
    j = n - 1
    for i in range(n):
        xi, yi = poly[i]; xj, yj = poly[j]
        if (yi > y) != (yj > y):
            xint = (xj - xi) * (y - yi) / (yj - yi) + xi
            if x < xint:
                inside = not inside
        j = i
    return inside

Robustness

Prefer exact integer arithmetic for orientation when inputs are integers.
Use consistent tie-breaking for collinear and boundary cases.
Adaptive-precision predicates (Shewchuk) give exactness at floating-point speed for hard inputs.
Degenerate inputs - duplicates, collinear runs, coincident segments - are the main source of bugs.

Primitives to build on

With orientation, distance, and intersection in hand you can build convex hulls (Graham scan), sweep-line algorithms, nearest-neighbor structures (k-d trees), and polygon-area and centroid computations.