Algorithms
Computational Geometry
Difficulty: Advanced
The sign of a single 2D cross product tells you whether three points turn left, turn right, or are collinear, and that one signed scalar is the workhorse behind almost every algorithm in the plane. Convex hulls, polygon area, segment...
Computational Geometry
The sign of a single 2D cross product tells you whether three points turn left, turn right, or are collinear, and that one signed scalar is the workhorse behind almost every algorithm in the plane. Convex hulls, polygon area, segment intersection, and point-in-polygon tests all reduce to a sequence of cross-product evaluations with a careful eye on edge cases. Get the geometric primitive right and the rest of the field follows.
Computational Geometry introduces those primitives and the algorithms built on them. You will start with cross products and the orientation test, then implement convex-hull algorithms three ways: Graham scan in O(n log n) (sort by polar angle, maintain a stack with the orientation invariant), Jarvis march in O(nh) for hulls with few vertices, and Andrew's monotone chain. The lesson then covers line-segment intersection, the sweep-line algorithm for many segments, the closest-pair-of-points algorithm in 2D, polygon computations using the Shoelace formula, and the ray-casting point-in-polygon test.
In Sorting (Elementary), you learned the comparison-based sorting that drives polar-angle preprocessing. Divide and Conquer (Advanced) taught you the closest-pair O(n log n) template via the strip combine step, which reappears here.
Next, Advanced Tree Algorithms moves from planar geometry back to hierarchical structures with Binary Lifting and centroid decomposition.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Compute the cross product of two 2D vectors and use it for orientation testing (clockwise, counterclockwise, collinear).
Implement Graham Scan to find the convex hull of a point set in O(n log n).
Apply the Shoelace formula to compute the area of a simple polygon in O(n).
Determine if two line segments intersect using cross-product orientation tests.
Implement the ray-casting algorithm to test whether a point lies inside a polygon.
Why This Matters
01
The cross product is the workhorse of computational geometry — it determines whether a turn is left (counterclockwise) or right (clockwise), enabling orientation tests, convex hull construction, and polygon area computation.
02
Graham Scan builds the convex hull of n points in O(n log n), and understanding it develops your ability to maintain invariants with a stack — a pattern that appears across many algorithm domains.
03
The Shoelace formula computes polygon area in O(n) using only cross products, making it a favorite in competitive programming for its simplicity and elegance.
04
Point-in-polygon testing (ray casting) is fundamental to computer graphics, GIS systems, and game development collision detection.
Key Terms
6 terms you'll encounter in this lesson
Cross Product (2D)
For vectors u=(ux,uy) and v=(vx,vy), the 2D cross product is ux*vy - uy*vx. Its sign indicates the turn direction: positive = counterclockwise, negative = clockwise, zero = collinear.
Orientation Test
Given three ordered points P, Q, R, the orientation test uses the cross product of vectors PQ and PR to determine if the path P->Q->R turns left (CCW), right (CW), or goes straight (collinear).
Convex Hull
The smallest convex polygon containing all given points. Visually, it is the shape formed by stretching a rubber band around all the points.
Graham Scan
A convex hull algorithm that sorts points by polar angle from the lowest point, then processes them in order using a stack, making only left turns. Time: O(n log n).
Shoelace Formula
A formula to compute the area of a simple polygon given its vertices: Area = |sum of (x_i * y_(i+1) - x_(i+1) * y_i)| / 2. Named for the criss-cross pattern of multiplications.
Ray Casting
A point-in-polygon test that casts a ray from the test point to infinity and counts edge crossings. An odd count means the point is inside; even means outside.
Heads Up
Common misconceptions to watch out for
"The cross product in 2D gives a vector"
In 3D, the cross product gives a vector. In 2D, the 'cross product' is actually the z-component of the 3D cross product, which is a scalar. Its sign indicates the turn direction.
"Graham Scan works without sorting"
Sorting by polar angle is essential — it ensures we process points in angular order around the anchor, maintaining the convex hull invariant. Without sorting, the stack-based approach would not produce a convex polygon.
"Convex hull always includes all boundary points"
Standard convex hull algorithms include only the vertices of the hull polygon. Collinear points on hull edges are typically excluded (only endpoints are kept). Special handling is needed if you want all boundary points.