Back to Study Material Data Structures and Algorithms

Computational Geometry Basics

Computational geometry deals with algorithms for solving geometric problems, from finding the convex hull of a point set to determining whether two line se...

Computational Geometry Basics

Representing Points, Vectors, and the Coordinate Framework

Computational geometry deals with algorithms for solving geometric problems, from finding the convex hull of a point set to determining whether two line segments intersect. The foundation is a clean representation of geometric objects. In most implementations, a point is a pair (x, y) of floating-point or integer coordinates. Using integers wherever possible avoids floating-point precision errors, which are the primary source of bugs in geometric code.

Vectors are the workhorses of computational geometry. The vector from point A to point B is (B.x - A.x, B.y - A.y). Two fundamental vector operations are the dot product and the cross product. For 2D vectors u = (ux, uy) and v = (vx, vy), the dot product is ux*vx + uy*vy, which equals |u||v|cos(theta) where theta is the angle between them. The 2D cross product (technically the z-component of the 3D cross product) is ux*vy - uy*vx, which equals |u||v|sin(theta) and is positive if v is counterclockwise from u, negative if clockwise, and zero if they are collinear.

The cross product of vectors AB and AC, computed as (B-A) x (C-A), determines the orientation of the ordered triple (A, B, C). If the result is positive, the points make a counterclockwise turn. If negative, a clockwise turn. If zero, they are collinear. This orientation test is the most frequently used primitive in computational geometry, underlying point-in-polygon tests, convex hull algorithms, and segment intersection detection.

Line Segment Intersection and the Sweep Line Paradigm

Determining whether two line segments AB and CD intersect is a fundamental geometric query. The standard approach uses orientation tests: segments intersect if and only if A and B are on opposite sides of line CD, and C and D are on opposite sides of line AB. Formally, segments properly intersect if orientation(A, B, C) and orientation(A, B, D) have opposite signs, and orientation(C, D, A) and orientation(C, D, B) have opposite signs. You must also handle collinear edge cases where a point lies on the opposite segment.

The sweep line paradigm processes geometric objects by moving a vertical line from left to right across the plane and maintaining a data structure of active objects. The Bentley-Ottmann algorithm uses this idea to find all intersections among n line segments in O((n + k) log n) time, where k is the number of intersections. The sweep line intersects segments and maintains them in sorted order by y-coordinate at the current x position, swapping adjacent pairs whenever they intersect.

A simpler but practically important sweep line application is computing the area of the union of rectangles. Sort all vertical edges by x-coordinate, process them left-to-right, and use a segment tree with lazy propagation to maintain the total covered length of the horizontal interval at each step. Multiplying covered lengths by horizontal distances and summing gives the total union area in O(n log n) time. This approach generalizes to unions of other shapes with appropriate interval coverage data structures.

Convex Hull Algorithms and Their Practical Significance

The convex hull of a set of points is the smallest convex polygon that contains all of them. Intuitively, it is the shape formed by stretching a rubber band around the outermost points. Computing convex hulls is a prerequisite for many geometric algorithms, including rotating calipers for diameter computation, minimum enclosing circle, and certain DP optimizations.

Graham scan computes the convex hull in O(n log n) time. It sorts all points by polar angle relative to the bottommost point, then processes them in order, maintaining a stack. For each new point, it pops stack elements while they make a clockwise turn with the top two stack elements, then pushes the new point. The result is the counterclockwise convex hull. Andrew's monotone chain is a practical variant that sorts by x-coordinate and builds the upper and lower hull separately, producing the same result with cleaner implementation.

The rotating calipers technique exploits the convex hull to answer queries about the farthest pair of points (diameter) in O(n) time after O(n log n) hull construction. Imagine two parallel supporting lines rotating around the hull — the distance between the lines at each step gives a candidate for the diameter. A concrete tip: when implementing convex hull code for a contest, always include a check for degenerate inputs — all collinear points, all identical points, or fewer than three points — since these edge cases commonly cause crashes in hull code that assumes general position. Test your implementation on three collinear points before submitting.