Hilbert

Each point is encoded to its cell on a Hilbert curve, and a contested cell is resolved by walking the curve outward to the nearest free one. Because neighbours along a Hilbert curve are neighbours in the plane, a displaced point lands close to where it started.

The grid is square, $2^L$ cells on a side at level $L$, for $4^L$ cells in all.

Data

Points 400 Seed 1

Technique

Whitespace (cells per point) 1.0 Extra levels 0 Keep aspect

Vis

Colour

OriginMovement

Show

OriginsGrid

…

400 points 0 of 400 cells filled 0.00 cells moved — ms

Six gaussian blobs. The ordinary case.

Parameters

name	default	meaning
whitespace	1	inflates the grid so cells outnumber points
pluslevel	0	extra curve levels beyond the fitted minimum — each one quadruples the cells
keep_aspect_ratio	false	pads the shorter axis so the data’s shape survives the mapping

gridify picks the level for you — the smallest one whose $4^L$ cells hold $N$ points with the requested whitespace:

$$L = \left\lceil \frac{\log_2 (N \cdot w)}{2} \right\rceil + \texttt{pluslevel}$$

N points, w the whitespace factor. The 2 in the denominator is log₂4 — each level quadruples the cell count, so a level is worth two bits.

const level = Math.ceil(Math.log2(N * whitespace) / Math.log2(4)) + pluslevel;

Call gridify_hilbert directly and you pass level yourself.

const { positions } = hagrid.gridify(data, "hilbert", { whitespace: 2 });
const positions = hagrid.gridify_hilbert(data, { level: 6 });

Output space

Integer cell indices on a $2^L \times 2^L$ lattice, not the input’s coordinates. To draw the originals alongside, project them with the same affine the method uses — see Getting started.

Encoding directly

hilbert_encode and hilbert_decode are exported, and are fast enough to use per frame:

const index = hagrid.hilbert_encode([x, y], size);   // 10.1 M/s
const [cx, cy] = hagrid.hilbert_decode(index, size); //  2.0 M/s

size must be a power of two. The index is kept in floating point — exact to $2^{53}$, so level 26 — and anything beyond HILBERT_MAX_LEVEL, or a non-power-of-two size, is rejected outright rather than silently returning wrong coordinates.

When it goes wrong

Elongated data. The grid must be square, so a wide dataset is either stretched out of shape or padded into a mostly-empty square. At a 1000×10 extent roughly 1% of the cells are usable, so holding the same number of points needs about 100× more of them:

N, at 1000×10 aspect	Gilbert	Hilbert (padded square)
1 000	1 000 cells (250×4)	262 144
10 000	10 000 cells (1000×10)	1 048 576
100 000	100 000 cells (3125×32)	16 777 216

Switch the demo above to the elongated dataset to see it. Gilbert is the same curve without the square constraint.

Dense regions and extreme outliers. Both are the same failure wearing different clothes: the mapping onto the grid is a plain linear scale of the data’s bounding box, so how many cells a region gets depends on how much space it occupies, not on how many points are in it.

Every point that wants a cell already taken is placed by walking the curve to the nearest free one, and that walk is what you pay. Measured over 600 points on a 32×32 grid:

data	cells the points ask for	contested	mean move	furthest
uniform	450	150	0.36 cells	3.6
six loose clusters	322	278	1.99	11.0
six tight clusters	69	531	4.70	11.7
one far outlier	9	591	18.99	34.5

Tight clusters ask for 69 of the 1 024 cells, so 531 of the 600 points arrive at an occupied one and get walked outward — the layout is decided by the collision walk rather than by the curve. A single distant outlier is worse: it stretches the bounding box until the rest of the data falls into nine cells, and the mean point travels nineteen of them. The grid is mostly empty while every point fights for the same corner.

The dial is whitespace, but it is a coarse one here — it only bites when it crosses a power of four, so the next step up is four times the cells. For an outlier, clipping or transforming the input is the real fix; the technique cannot tell an outlier from a wide dataset. DGrid and GridFit assign cells by rank rather than by scaled position, so neither is affected by how the data is spread.

References

Rene Cutura, Cristina Morariu, Zhanglin Cheng, Yunhai Wang, Daniel Weiskopf and Michael Sedlmair Hagrid: using Hilbert and Gosper curves to gridify scatterplots Journal of Visualization 25(6), 1291–1307, 2022. doi:10.1007/s12650-022-00854-7

The method this page documents.

David Hilbert Ueber die stetige Abbildung einer Linie auf ein Flächenstück Mathematische Annalen 38, 459–460, 1891. doi:10.1007/BF01199431

The curve itself.