Geometric Algorithms Mind Map

Every geometric algorithms visualization on this site on one map. The branches are the main ideas. Each leaf is a page; the grey line under it is the one thing to remember about it. Click a branch to focus on it, click a page to open it.

Recall mode hides the page names. Read the hint, say the name, then click the "?" to check.

1. How the map is organized

Overview of the geometric algorithms mind map: Transform matrices, Coordinate frames, Hulls and curves, Rendering, Fourier and DCT, Triangulations, Segments and polygons. — The map at a glance: 7 branches, 16 pages.

Ask what the algorithm takes in and gives back:

Points in, moved points out? One move is a transform matrix; reading a point in another object's axes is a coordinate frame.
Points in, a shape out? The outline around them or a smooth curve through control points is hulls and curves.
A 3D scene in, pixels out? That is rendering: loop over triangles (rasterization) or over pixels (ray tracing).
Samples in, frequencies out? That is Fourier and DCT.

2. The branches side by side

Branch	Input	Output	Key tool
Transform matrices	shape vertices	moved vertices	matrix times vector
Coordinate frames	point in one frame	same point in another	chain of rotate + translate
Hulls and curves	points	outline or curve	cross product, lerp
Rendering	triangles or spheres	pixel colours	edge functions, ray hits, depth
Fourier and DCT	samples	frequency coefficients	sums of sines and cosines

3. Five facts to remember

Adding a 1 to each point, (x, y, 1), turns translation into a matrix product.
The sign of a 2D cross product tells a left turn from a right turn.
Graham scan builds a convex hull in O(n log n); gift wrapping takes O(nh) for h hull points.
A Bézier curve always stays inside the convex hull of its control points.
The FFT computes an n-point DFT in O(n log n) instead of O(n²).

See all geometric algorithms pages in the index, or the other mind maps.