Plane Geometry
Almost every question about points in the plane comes down to one number: the cross product of two vectors, which is twice the signed area of the triangle they span. Its sign says whether three points turn left, turn right or line up. From that single test you get whether two segments cross, the area of any polygon by adding up triangles from the origin, and the convex hull by keeping only the points at which the boundary turns the right way. Everything stays in integers, so there is no rounding to worry about. Three classics build on the primitives. Graham scan finds the convex hull by sorting points around the lowest one and keeping only left turns. Closest pair divides the points at the median x, solves each side, and then checks only a thin strip around the divider, which is what makes it O(n log n). The sweep line moves across the plane one endpoint at a time, keeping the segments it currently cuts in height order, and tests only neighbours in that order, because a crossing must make two segments adjacent at some moment.
Convex hull of 8 points by Graham scan. Pick the lowest point as the pivot, sort every other point by its angle around the pivot, then walk them in that order keeping a stack: a point that would make the last two turn right is popped, because the hull only ever turns left.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 9, with their answers.
Which point does Graham scan start from?
Answer: B. The lowest point, leftmost on a tie. An extreme point is always on the hull.
B, C, D: does C stay on the hull?
Answer: Keep it, a left turn. The turn is left, so the chain stays convex.
C, D, H: does D stay on the hull?
Answer: Keep it, a left turn. The turn is left, so the chain stays convex.
D, H, G: does H stay on the hull?
Answer: Keep it, a left turn. The turn is left, so the chain stays convex.
H, G, E: does G stay on the hull?
Answer: Pop it, not a left turn. The turn at G is right turn.
D, H, E: does H stay on the hull?
Answer: Pop it, not a left turn. The turn at H is right turn.
C, D, E: does D stay on the hull?
Answer: Keep it, a left turn. The turn is left, so the chain stays convex.
D, E, F: does E stay on the hull?
Answer: Keep it, a left turn. The turn is left, so the chain stays convex.
E, F, A: does F stay on the hull?
Answer: Keep it, a left turn. The turn is left, so the chain stays convex.
How it runs, step by step
Convex hull of 8 points by Graham scan. Pick the lowest point as the pivot, sort every other point by its angle around the pivot, then walk them in that order keeping a stack: a point that would make the last two turn right is popped, because the hull only ever turns left.
Graham scan over 8 points.
The pivot is B (7, 1), the lowest point. It is certainly on the hull, and every other point is now ordered by the angle it makes from here: C, D, H, G, E, F, A.
Pivot B.
Push C (9, 4): the first point after the pivot always goes on.
Push C.
Push D (6, 7), since B, C, D turns left.
Push D.
Push H (4, 6), since C, D, H turns left.
Push H.
Push G (5, 4), since D, H, G turns left.
Push G.
H, G, E is right turn, not a left turn, so G lies inside the hull between them: pop it.
Pop G.
D, H, E is right turn, not a left turn, so H lies inside the hull between them: pop it.
Pop H.
Push E (2, 8), since C, D, E turns left.
Push E.
Push F (0, 4), since D, E, F turns left.
Push F.
Push A (3, 2), since E, F, A turns left.
Push A.
Hull: B, C, D, E, F, A, 6 of 8 points, counter-clockwise from the pivot. Sorting by angle costs O(n log n); the scan pushes each point once and pops it at most once, so it is O(n). Monotone chain does the same job with two sorted sweeps instead of one angular sort; Graham scan is the older of the two and the one most textbooks show.
Hull with 6 points.
Remember
- cross(u, v) = ux vy - uy vx: zero when parallel, positive for a left turn, twice the triangle area.
- Segments cross when each one's endpoints fall on opposite sides of the other's line: four orientation tests.
- Hulls keep only left turns (monotone chain sorts by x, Graham by angle); closest pair checks a strip around the divider; a sweep line tests only neighbours in its active set.
Topics covered
Where this is used
DatabasesSpatial queries in PostGIS
ST_Intersects and ST_Contains in PostGIS hand the work to the GEOS library, where the answer bottoms out in orientation tests on triples of vertices. Because one wrong sign on a nearly collinear triple would report that two roads never meet, GEOS computes the determinant in ordinary doubles behind an error bound and, when the result is too close to zero to trust, recomputes it in double-double arithmetic. ST_Area never reaches GEOS at all: PostGIS sums the shoelace terms over each ring itself and subtracts the holes. The split is why a geometry engine ships its own predicate code instead of trusting plain doubles.
GraphicsPolygon triangulation for map tiles
A GPU draws triangles, not polygons, so Mapbox's earcut library cuts every building and lake outline in a vector tile into triangles before rendering. It picks an ear by checking that the corner turns the right way and that no other vertex falls inside that triangle, and both of those are orientation tests. It also takes the sign of the shoelace sum over each ring and reverses the ring when the sign is wrong, so an outer ring and its holes always wind in opposite directions, which is what the step that bridges a hole into the outer ring depends on.
GamesCollision shapes in physics engines
Box2D will not take an arbitrary polygon: a polygon shape is built from the convex hull of the points you supply, and anything tucked inside the hull is dropped. Collision between two convex shapes can be settled by the separating axis test, which only has to try each polygon's edge normals, and a single concave dent destroys that guarantee. So the engine forces convexity up front and makes you build a concave body out of several convex pieces.
Hardware designDesign rule checking in chip layout
A layout holds hundreds of millions of rectangles and the checker must report every pair that overlaps or sits closer than the process allows. All-pairs comparison is hopeless, so the tool sweeps a line across the die, keeps only the edges the line currently cuts in height order, and tests each new edge against its two neighbours. The textbook form is Bentley and Ottmann's 1979 algorithm, which reports every intersecting pair among n segments in O((n + k) log n) for k intersections, against O(n^2) for comparing every pair.
Why it works this way
Why the cross product and not slopes or angles?
Slope is a division, so it blows up on a vertical segment and turns exact inputs into floats you then have to compare for equality. atan2 has the same rounding problem and is far slower. cross(u, v) is two multiplications and a subtraction, it stays in integers, and its sign alone answers the question you actually asked: which side of the line through a and b does c fall on. You almost never need the angle itself, only which way it turns.
Integers do not mean safe: know where the cross product overflows
Each subtraction doubles the coordinate range, and then two of those differences are multiplied and subtracted, so for coordinates in [-c, c] the worst case is about 8c^2. On a 32-bit Int that runs out at c around 16,000, small enough to hit by accident. A signed 64-bit Long holds up to c around 1.07 x 10^9, so the 10^9 coordinates ordinary for map data stored in fixed point fit with almost no margin left, and anything larger, or a squared distance computed on the same values, breaks it. The failure is silent: you get a plausible wrong sign rather than a crash, and the hull comes back with a dent in it. Work out your own bound before you trust the sign.
What the four-orientation test really does with touching segments
The strict crossing test is o1 * o2 < 0 && o3 * o4 < 0: each segment's endpoints must land on strictly opposite sides of the other's line. The looser o1 != o2 && o3 != o4 above is not the same test, because a zero counts as different from a nonzero. Two segments sharing an endpoint, or one whose endpoint rests in the middle of the other, come back true from the loose form and false from the strict one. The case neither form handles is collinearity: two segments on the same line give all four orientations zero, so both answer false even when the segments overlap along a stretch. Covering that means adding, for each orientation that came out zero, a check that the third point actually lies between the other two. Whether touching should count is a decision about your problem, but it has to be a decision rather than an accident of which form you copied.
Why the strip in closest pair costs only O(n)
Once both halves are solved you know no two points on the same side are closer than d, so a d-by-d square lying entirely on one side holds at most four points: cut it into four squares of side d/2, and each of those has diagonal shorter than d, so each can hold only one. A strip point only needs comparing against points within d above it, a 2d-by-d rectangle straddling the divider, which by the same cut holds at most eight. So the inner loop's break on y difference fires after a constant number of steps. That constant is what turns the strip pass from quadratic into linear, and it is why the strip has to be sorted by y instead of scanned in any order.
Read more
- Basic geometry: dot and cross productscp-algorithms
- Shoelace formulaWikipedia
- Convex hull constructioncp-algorithms
- Closest pair of points problemWikipedia
- Bentley-Ottmann algorithmWikipedia