Computational Geometry
Points, lines, polygons and circles: the basic operations and the classic algorithms built on them.
26 articles~185 min total
0/26
Elementary operations
- Basic Geometry: Vectors, Dot and Cross ProductsThe toolkit behind almost every geometry algorithm: points as vectors, the dot product, the cross product, and how to intersect lines and planes with them.8 minBeginner
- Equation of a Line Through a SegmentTurn two endpoints into the line A·x + B·y + C = 0, keep the coefficients integer and canonical, and normalize them when working with floats.4 minBeginner
- Intersection Point of Two LinesSolve two line equations with Cramer's rule, and tell apart the three cases: one point, parallel, or the same line.3 minBeginner
- Oriented Area of a TriangleThe signed area of a triangle, computed with one cross product, tells you the area and whether three points turn left, right, or lie on a line.3 minBeginner
- Checking Whether Two Segments IntersectAn exact integer test using only cross products: the endpoints of each segment must lie on opposite sides of the other, with a special case for collinear segments.4 minIntermediate
- Intersection of Two SegmentsCompute the exact intersection of two segments: empty, a single point, or a whole overlapping segment, handling parallel and degenerate cases.5 minIntermediate
- Circle-Line IntersectionFind the 0, 1 or 2 points where a line meets a circle, using the closest point to the center and a stable geometric construction.4 minIntermediate
- Circle-Circle IntersectionIntersect two circles by subtracting their equations, which turns the problem into a circle-line intersection.4 minIntermediate
- Common Tangents to Two CirclesFind all lines touching two circles at once (up to four), or the tangents from a point to a circle, with a small algebraic derivation.6 minIntermediate
- Length of the Union of SegmentsKlee's O(n log n) sweep: sort all endpoints and add up the stretches during which at least one segment is open.4 minBeginner
Polygons
- Area of a Simple PolygonThe shoelace formula: add the signed trapezoids under every edge, or the signed triangles from any fixed point, in O(n).4 minBeginner
- Pick's TheoremThe area of a lattice polygon from its interior and boundary lattice points: S = I + B/2 − 1, with a proof outline and a brute-force verification.6 minIntermediate
- Counting Lattice Points Under a LineCount the integer points under a line segment, and hence inside a polygon with arbitrary vertices, in O(log n) with a Euclid-like recursion.6 minAdvanced
- Point in a Convex Polygon in O(log n)Answer many point-in-polygon queries against a convex polygon by binary searching the fan of triangles around its lowest-leftmost vertex.6 minAdvanced
- Minkowski Sum of Convex PolygonsMerge the edges of two convex polygons by polar angle to build their Minkowski sum in linear time, and use it to get the distance between polygons.7 minAdvanced
Convex hull
- Convex Hull: Monotone Chain and Graham ScanBuild the smallest convex polygon containing a point set in O(n log n) with Andrew's monotone chain or Graham's scan, with or without collinear points.7 minIntermediate
- Convex Hull Trick and Li Chao TreeSpeed up DPs of the form min over j of (k_j·x + b_j) with a convex hull of lines or a Li Chao tree, going from O(n²) to O(n log n).11 minAdvanced
Sweep line
Planar graphs
- Faces of a Planar GraphEnumerate the faces of a straight-line planar graph by walking around them along angularly sorted edges, and build such a graph from intersecting segments.10 minAdvanced
- Point Location in a Planar SubdivisionAnswer many queries 'which face contains this point?' offline with a sweep line and an ordered set of non-crossing edges.9 minAdvanced
- Vertical DecompositionCut the plane into vertical stripes where shapes become simple trapezoids: the area of a union of triangles in O(n² log n), and convex polygon intersection.11 minAdvanced
Advanced topics
- Closest Pair of PointsFind the two nearest points among n in O(n log n) by divide and conquer, and in expected O(n) with randomized grid algorithms.10 minAdvanced
- Delaunay Triangulation and Voronoi DiagramBuild the Delaunay triangulation of a point set in O(n log n) with the Guibas–Stolfi divide and conquer on the quad-edge structure, and get the Voronoi diagram by duality.16 minAdvanced
- Half-plane IntersectionIntersect N half-planes in O(N log N) by sorting them by angle and keeping a deque; applications to polygon kernels, polygon intersection and inscribed circles.12 minAdvanced
- Manhattan Distance: Farthest Pair, Rotation and MSTTricks for the taxicab metric: the farthest pair by trying sign patterns, the 45° rotation to Chebyshev distance, and a Manhattan minimum spanning tree in O(n log n).9 minAdvanced
- Minimum Enclosing CircleWelzl's randomized algorithm finds the smallest circle containing n points in expected O(n) time; the point-in-circle test is done exactly in integers.8 minAdvanced