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.
Do segments AB and CD cross? AB crosses the line CD only if A and B lie on opposite sides of it, and CD must likewise straddle the line AB. Four orientation tests settle it, no division needed.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 4, with their answers.
orient(A, B, C): is C left of, right of, or on the line AB?
Answer: Left, +1. The cross product of the two vectors from A gives 1.
orient(A, B, D): is D left of, right of, or on the line AB?
Answer: Right, -1. The cross product of the two vectors from A gives -1.
orient(C, D, A): is A left of, right of, or on the line CD?
Answer: Right, -1. The cross product of the two vectors from C gives -1.
orient(C, D, B): is B left of, right of, or on the line CD?
Answer: Left, +1. The cross product of the two vectors from C gives 1.
How it runs, step by step
Do segments AB and CD cross? AB crosses the line CD only if A and B lie on opposite sides of it, and CD must likewise straddle the line AB. Four orientation tests settle it, no division needed.
Segment intersection test for AB and CD.
orient(A, B, C) = 1: C is to the left of the line through A and B.
orient(A, B, C) is 1.
orient(A, B, D) = -1: D is to the right of the line through A and B.
orient(A, B, D) is -1.
orient(C, D, A) = -1: A is to the right of the line through C and D.
orient(C, D, A) is -1.
orient(C, D, B) = 1: B is to the left of the line through C and D.
orient(C, D, B) is 1.
C and D are on opposite sides of AB (1 vs -1) and A and B on opposite sides of CD (-1 vs 1): the segments cross.
The segments intersect.
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