Explore the fractal space-filling Hilbert curve with adjustable order, color-coded traversal, and coordinate mapping
A space-filling curve is a continuous surjective mapping f: [0,1] → [0,1]². David Hilbert described his curve in 1891 as a geometric construction that fills an entire square. The Hilbert curve is defined recursively: at order 1, the curve visits a 2×2 grid in a U-shape pattern. At each higher order, every cell of the previous grid is replaced by a rotated/reflected copy of the U pattern, quadrupling the resolution. At order n, the curve visits all 2ⁿ × 2ⁿ = 4ⁿ cells exactly once. Key properties: (1) Continuity — the curve is a continuous path with no jumps. (2) Self-similarity — each quadrant is a rotated copy of the whole. (3) Locality — nearby points on the 1D line tend to be nearby in 2D, making it useful for spatial indexing. (4) Non-differentiability — the limit curve has no tangent anywhere.
The Hilbert curve is built by Lindenmayer-style replacement rules. At order 1, the curve traces four quadrants in the order: lower-left → upper-left → upper-right → lower-right (a U shape). To go from order n to order n+1, each cell is subdivided into four sub-cells. The sub-curve in each quadrant is rotated 90° or reflected so that the entry and exit points connect properly. The algorithm uses two functions: xy2d(x, y, n) converts a 2D grid coordinate to its 1D distance along the curve (0 to 4ⁿ−1), and d2xy(d, n) converts a 1D distance back to 2D coordinates. Both run in O(n) time by processing one bit pair per level. The lower chart is a sampled locality scatter: it plots sampled cell pairs across a range of curve separations, comparing 1D curve distance |d₁−d₂| with actual 2D Euclidean distance. Tighter clustering toward the lower-left indicates stronger locality preservation.
Spatial indexing: databases (Google's S2 geometry, PostgreSQL) use Hilbert curves to map 2D/3D coordinates to 1D keys, enabling efficient range queries. Image processing: Hilbert-curve scanning orders convert 2D images to 1D sequences that preserve spatial locality better than raster scan, improving compression and cache performance. Data visualization: mapping high-dimensional data to a Hilbert curve preserves clusters — used in flame graphs and genome browsers. Numerical methods: space-filling curves partition domains for parallel computation with guaranteed neighbor adjacency. Computer graphics: texture mapping and level-of-detail selection benefit from the curve's locality. Geospatial: Uber's H3 hexagonal grid uses Hilbert curves internally for cell ordering. Mathematics: Hilbert curves are a constructive proof that [0,1] and [0,1]² have the same cardinality (Cantor's surprising result of 1877).
Use the Order slider to change the recursion depth (1–7). At order 1 you see a simple U shape visiting 4 cells; at order 7 the curve visits 16,384 cells. Switch between Curve view (colored line), Heatmap (color-coded cells by traversal order), or Both. The color gradient from blue (start, d=0) to red (end, d=4ⁿ−1) shows the traversal order. Enter x,y coordinates and click Find to highlight that cell and show its position d on the curve. You can also click directly on the canvas to find a cell. Use Play to progressively animate the curve being drawn — watch how the U-shape pattern replicates and connects at each level. The bottom chart shows sampled locality preservation: nearby cells in 2D usually correspond to smaller curve distances, even though the relationship is not exact.