Computational Geometry Algorithms Cheat Sheet

Updated 2026-05-21

Next Topic: Convex Optimization Cheat Sheet

Computational geometry is the branch of computer science devoted to algorithms and data structures for geometric problems arising in graphics, GIS, CAD, robotics, and scientific computing. This cheat sheet covers the essential primitives, classical algorithms (convex hull, sweep line, Voronoi, Delaunay), polygon operations, spatial data structures, and robustness techniques that form the backbone of practical geometric computing.

What This Cheat Sheet Covers

This topic spans 15 focused tables and 129 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Point and Vector PrimitivesTable 2: Convex Hull AlgorithmsTable 3: Line Segment IntersectionTable 4: Polygon Area and OrientationTable 5: Point-in-PolygonTable 6: Closest Pair of PointsTable 7: Voronoi Diagrams and Delaunay TriangulationTable 8: Polygon TriangulationTable 9: Rotating CalipersTable 10: Half-Plane IntersectionTable 11: k-d Trees and Geometric Range SearchingTable 12: Sweep Line FrameworkTable 13: Robustness and Floating-Point PrecisionTable 14: Minkowski Sum, Minimum Enclosing Circle, and Advanced OperationsTable 15: Computational Geometry Libraries and Applications

Table 1: Point and Vector Primitives

The basic building blocks of all computational geometry algorithms are operations on 2D points and vectors. These primitives—dot product, cross product, distance, and the orientation predicate—appear in virtually every higher-level algorithm.

Technique / Algorithm	Example	Description
Dot product	$\vec{a} \cdot \vec{b} = a_x b_x + a_y b_y$	• Returns scalar • positive if vectors point same direction, zero if perpendicular • Used to project one vector onto another
Cross product (2D)	$\vec{a} \times \vec{b} = a_x b_y - a_y b_x$	Returns signed scalar (z-component of 3D cross product). Positive = CCW turn from a to b, negative = CW.
Orientation predicate	$v = (b.x-a.x)(c.y-a.y)-(b.y-a.y)(c.x-a.x)$	• Sign of cross product of (b−a) and (c−a) • v>0 = CCW, v<0 = CW, v=0 = collinear • Core primitive used in convex hull, point-in-polygon, and segment intersection
Euclidean distance	$d(p,q) = \sqrt{(q.x-p.x)^2+(q.y-p.y)^2}$	• Straight-line distance between two points • Avoid sqrt when comparing distances (compare squared distances instead).
Squared distance	$d^2(p,q) = (q.x-p.x)^2+(q.y-p.y)^2$	• Avoids expensive square root • sufficient for distance comparisons and closest-pair strip checks

Table 1: Point and Vector Primitives

Technique / Algorithm	Example	Description
Dot product	$\vec{a} \cdot \vec{b} = a_x b_x + a_y b_y$	• Returns scalar • positive if vectors point same direction, zero if perpendicular • Used to project one vector onto another
Cross product (2D)	$\vec{a} \times \vec{b} = a_x b_y - a_y b_x$	Returns signed scalar (z-component of 3D cross product). Positive = CCW turn from a to b, negative = CW.
Orientation predicate	$v = (b.x-a.x)(c.y-a.y)-(b.y-a.y)(c.x-a.x)$	• Sign of cross product of (b−a) and (c−a) • v>0 = CCW, v<0 = CW, v=0 = collinear • Core primitive used in convex hull, point-in-polygon, and segment intersection
Euclidean distance	$d(p,q) = \sqrt{(q.x-p.x)^2+(q.y-p.y)^2}$	• Straight-line distance between two points • Avoid sqrt when comparing distances (compare squared distances instead).
Squared distance	$d^2(p,q) = (q.x-p.x)^2+(q.y-p.y)^2$	• Avoids expensive square root • sufficient for distance comparisons and closest-pair strip checks