Lesson 14 of 16

Geometry: Points and Turns

Coordinates represent locations, and segments represent movement. Geometry algorithms seek conditions that can be calculated from coordinates, rather than relying on a picture’s appearance.

Closest pair on a line

For [1, 4, 5, 12], sort and compare neighboring gaps: 3, 1, and 7. The closest pair is 4 and 5. A non-neighboring pair has an intervening point, giving a closer adjacent pair.

The scan takes O(n) if already sorted, or typically O(n log n) including sorting. Coincident points have distance zero.

Determine a turn in the plane

For points A, B, and C, consider moving A to B and then toward C. With y increasing upward, a positive result below means counterclockwise, negative means clockwise, and zero means collinear.

def cross(a, b, c):
    return ((b[0] - a[0]) * (c[1] - a[1])
            - (b[1] - a[1]) * (c[0] - a[0]))

print(cross((0, 0), (3, 0), (1, 2)))

The result is 6, so the turn is counterclockwise. This is a two-dimensional cross product, useful for segment intersections and convex hulls. With screen coordinates whose y-axis points downward, the visible turn direction reverses.

More dimensions change the argument

The closest pair in a plane need not be adjacent after sorting by x. For (0,0), (1,100), (2,0), the first and last points are closest. Reusing the one-dimensional solution fails. Planar methods such as divide and conquer must also examine candidates near partition boundaries.

Floating-point rounding can make exact-zero checks unreliable. Keeping integer arithmetic when the input is integral can help.

Check your understanding

For A=(0,0), B=(2,0), C=(1,0), does a zero cross product alone prove that C lies on segment AB?