Computational Geometry Algorithms Cheat Sheet

Updated 2026-05-21

Next Topic: Confidence Intervals and Estimation Cheat Sheet

🧠Study flashcards on this topic112 cards · spaced repetition→

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, 112 flashcards. 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

Quick IndexSubscribe to unlock

A jump-to index of every table row in this cheat sheet.

Mind MapSubscribe to unlock

An interactive map of every table and concept in this topic.

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
Point on segment test	cross=0 AND $\min(a.x,b.x) \le p.x \le \max(a.x,b.x)$	P lies on segment AB iff cross product (B−A)×(P−A)=0 (collinear) and P is within bounding box of AB.
Segment intersection test	signs of orient(A,B,C) and orient(A,B,D) differ	Two segments AB and CD properly intersect iff each endpoint of one straddles the line through the other (opposite orientation signs). Handle collinear/endpoint cases separately.
Polar angle	$\theta = \text{atan2}(p.y - o.y,, p.x - o.x)$	• Angle of point p relative to origin o • used in Graham scan sorting. atan2 handles all quadrants correctly
Vector normalization	$\hat{v} = \vec{v} /	\vec{v}
Perpendicular vector	$(x,y) \to (-y,x)$	Rotates vector 90° CCW; yields the inward or outward normal of a line segment, used in half-plane intersection.

Table 2: Convex Hull Algorithms

The convex hull of a point set is the smallest convex polygon containing all points. It is a fundamental structure used in collision detection, gift wrapping, furthest-pair computation, and as preprocessing for many other algorithms.

Technique / Algorithm	Example	Description
Gift Wrapping / Jarvis March	$O(nh)$, h = hull size	• Start at leftmost point • repeatedly find the point that makes the smallest CCW turn • Simple but slow when h is large

The rest of this section is part of the full cheat sheet

Table 3: Line Segment Intersection

Finding all intersections among a set of line segments is a classical problem with applications in map overlay, circuit board verification, and collision detection.

Technique / Algorithm	Example	Description
Brute-force segment intersection	$O(n^2)$	• Test every pair of segments • correct but impractical for large n

The rest of this section is part of the full cheat sheet

Table 4: Polygon Area and Orientation

Computing the area of a polygon and determining its orientation (clockwise or counter-clockwise) are fundamental operations underlying many polygon algorithms.

Technique / Algorithm	Example	Description
Shoelace formula (Gauss)	$A = \frac{1}{2}\lvert\sum_{i=0}^{n-1}(x_i y_{i+1} - x_{i+1} y_i)\rvert$	• Computes area of simple polygon from vertex coordinates • indices are cyclic ($x_n = x_0$). Also called the surveyor's formula

The rest of this section is part of the full cheat sheet

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
Point on segment test	cross=0 AND $\min(a.x,b.x) \le p.x \le \max(a.x,b.x)$	P lies on segment AB iff cross product (B−A)×(P−A)=0 (collinear) and P is within bounding box of AB.
Segment intersection test	signs of orient(A,B,C) and orient(A,B,D) differ	Two segments AB and CD properly intersect iff each endpoint of one straddles the line through the other (opposite orientation signs). Handle collinear/endpoint cases separately.
Polar angle	$\theta = \text{atan2}(p.y - o.y,, p.x - o.x)$	• Angle of point p relative to origin o • used in Graham scan sorting. atan2 handles all quadrants correctly
Vector normalization	$\hat{v} = \vec{v} /	\vec{v}
Perpendicular vector	$(x,y) \to (-y,x)$	Rotates vector 90° CCW; yields the inward or outward normal of a line segment, used in half-plane intersection.

Table 2: Convex Hull Algorithms

Technique / Algorithm	Example	Description
Gift Wrapping / Jarvis March	$O(nh)$, h = hull size	• Start at leftmost point • repeatedly find the point that makes the smallest CCW turn • Simple but slow when h is large

Table 3: Line Segment Intersection

Finding all intersections among a set of line segments is a classical problem with applications in map overlay, circuit board verification, and collision detection.

Technique / Algorithm	Example	Description
Brute-force segment intersection	$O(n^2)$	• Test every pair of segments • correct but impractical for large n

Table 4: Polygon Area and Orientation

Computing the area of a polygon and determining its orientation (clockwise or counter-clockwise) are fundamental operations underlying many polygon algorithms.

Technique / Algorithm	Example	Description
Shoelace formula (Gauss)	$A = \frac{1}{2}\lvert\sum_{i=0}^{n-1}(x_i y_{i+1} - x_{i+1} y_i)\rvert$	• Computes area of simple polygon from vertex coordinates • indices are cyclic ($x_n = x_0$). Also called the surveyor's formula