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 monotone chain: sort by x, walk left to right keeping only left turns to get the lower hull, then walk right to left for the upper hull. A point that makes a right turn would be inside the rubber band, so it is popped.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 18, with their answers.
A, H, B: keep H on the lower hull?
Answer: Pop it, not a left turn. The turn at H is right turn.
A, B, C: keep B on the lower hull?
Answer: Keep it, a left turn. The turn is left, so the chain stays convex.
B, C, D: keep C on the lower hull?
Answer: Pop it, not a left turn. The turn at C is right turn.
A, B, D: keep B on the lower hull?
Answer: Keep it, a left turn. The turn is left, so the chain stays convex.
B, D, G: keep D on the lower hull?
Answer: Keep it, a left turn. The turn is left, so the chain stays convex.
D, G, E: keep G on the lower hull?
Answer: Pop it, not a left turn. The turn at G is right turn.
B, D, E: keep D on the lower hull?
Answer: Pop it, not a left turn. The turn at D is right turn.
A, B, E: keep B on the lower hull?
Answer: Keep it, a left turn. The turn is left, so the chain stays convex.
B, E, F: keep E on the lower hull?
Answer: Keep it, a left turn. The turn is left, so the chain stays convex.
F, E, G: keep E on the upper hull?
Answer: Pop it, not a left turn. The turn at E is right turn.
F, G, D: keep G on the upper hull?
Answer: Keep it, a left turn. The turn is left, so the chain stays convex.
G, D, C: keep D on the upper hull?
Answer: Pop it, not a left turn. The turn at D is right turn.
F, G, C: keep G on the upper hull?
Answer: Keep it, a left turn. The turn is left, so the chain stays convex.
G, C, B: keep C on the upper hull?
Answer: Keep it, a left turn. The turn is left, so the chain stays convex.
C, B, H: keep B on the upper hull?
Answer: Pop it, not a left turn. The turn at B is right turn.
G, C, H: keep C on the upper hull?
Answer: Pop it, not a left turn. The turn at C is right turn.
F, G, H: keep G on the upper hull?
Answer: Keep it, a left turn. The turn is left, so the chain stays convex.
G, H, A: keep H on the upper 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 monotone chain: sort by x, walk left to right keeping only left turns to get the lower hull, then walk right to left for the upper hull. A point that makes a right turn would be inside the rubber band, so it is popped.
Convex hull of 8 points.
lower hull: push A (1, 3).
Push A.
lower hull: push H (2, 8).
Push H.
lower hull: A, H, B is not a left turn (right turn), so H cannot be on the hull between them. Pop it.
Pop H.
lower hull: push B (3, 1).
Push B.
lower hull: push C (4, 6), since A, B, C turns left.
Push C.
lower hull: B, C, D is not a left turn (right turn), so C cannot be on the hull between them. Pop it.
Pop C.
lower hull: push D (5, 4), since A, B, D turns left.
Push D.
lower hull: push G (6, 8), since B, D, G turns left.
Push G.
lower hull: D, G, E is not a left turn (right turn), so G cannot be on the hull between them. Pop it.
Pop G.
lower hull: B, D, E is not a left turn (right turn), so D cannot be on the hull between them. Pop it.
Pop D.
lower hull: push E (7, 2), since A, B, E turns left.
Push E.
lower hull: push F (8, 7), since B, E, F turns left.
Push F.
upper hull: push F (8, 7).
Push F.
upper hull: push E (7, 2).
Push E.
upper hull: F, E, G is not a left turn (right turn), so E cannot be on the hull between them. Pop it.
Pop E.
upper hull: push G (6, 8).
Push G.
upper hull: push D (5, 4), since F, G, D turns left.
Push D.
upper hull: G, D, C is not a left turn (right turn), so D cannot be on the hull between them. Pop it.
Pop D.
upper hull: push C (4, 6), since F, G, C turns left.
Push C.
upper hull: push B (3, 1), since G, C, B turns left.
Push B.
upper hull: C, B, H is not a left turn (right turn), so B cannot be on the hull between them. Pop it.
Pop B.
upper hull: G, C, H is not a left turn (right turn), so C cannot be on the hull between them. Pop it.
Pop C.
upper hull: push H (2, 8), since F, G, H turns left.
Push H.
upper hull: push A (1, 3), since G, H, A turns left.
Push A.
Hull: A, B, E, F, G, H, 6 of 8 points, listed counter-clockwise. Sorting costs O(n log n) and each point is pushed and popped at most twice, so the chains take O(n).
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