Geometry Basics: Orientation, Line Sweep, Closest Pair

Why this module exists

Geometry shows up in interval overlap, intersection tests, and nearest neighbor queries. You mostly need vector math and sweep-line thinking.

Orientation (cross product)

Given points A, B, C, compute: cross = (B-A) x (C-A)

• cross > 0 → counterclockwise
• cross < 0 → clockwise
• cross = 0 → collinear

Orientation powers segment intersection, convex hull, and polygon tests.

Line sweep (events)

Convert geometry to events along one axis.

Example for interval overlap:

• +1 at start
• -1 after end

Sort events and sweep to maintain active count.

Closest pair of points

Divide-and-conquer approach:

1. Sort by x
2. Recurse on left/right
3. Check a vertical strip around mid (only ~7 neighbors in y-order)

Time: O(n log n)

What you will build

• Segment intersection using orientation.
• Maximum overlap via line sweep.
• Closest pair distance (squared) using divide-and-conquer.