DGrid

DGrid is a reimplementation of Hilasaca et al.’s Distance-preserving Grid. It recursively bisects the point set and the cell block together, splitting along whichever axis has more cells to give, until each subset holds a single point.

It fills the whole visualization area, keeping the requested cell aspect ratio.

Data

Points 400 Seed 1

Technique

Cell aspect 1.0

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
aspect_ratio	1	cell aspect ratio, used to derive the grid
rows, cols	derived	explicit grid size; both must be given, and together they override aspect_ratio

const positions = hagrid.gridify_dgrid(data, { aspect_ratio: 1 });

Left to itself the grid is

$$\text{rows} = \max\bigl(1,\ \lfloor \sqrt{N \cdot a} \rfloor\bigr), \qquad \text{cols} = \left\lceil \frac{N}{\text{rows}} \right\rceil$$

N points at cell aspect a.

const rows = Math.max(1, Math.floor(Math.sqrt(N * aspect_ratio)));
const cols = Math.ceil(N / rows);

which is as dense as a grid can be: rows × cols is barely more than $N$, so almost every cell is occupied. That is the trade — DGrid gives up whitespace, and with it some of the freedom to keep a point near where it started.

Assignment is by rank, not by position

Each split sorts the remaining points along one axis and cuts at a fixed count, so a point’s cell is decided by its rank among its neighbours rather than by scaling its coordinates. There is no affine map from input position to cell.

That matters when you draw it: the displacement readout in the demo above is marked with an asterisk because the “original” positions are shown in a fair reference frame — the data’s bounding box scaled onto the lattice — rather than an exact preimage. Read it as indicative.

Output space

Integer [column, row] cells on the cols × rows lattice.

References

Gladys M. Hilasaca, Wilson E. Marcílio-Jr, Danilo M. Eler, Rafael M. Martins and Fernando V. Paulovich A Grid-Based Method for Removing Overlaps of Dimensionality Reduction Scatterplot Layouts IEEE Transactions on Visualization and Computer Graphics 30(8), 5733–5749, 2024. doi:10.1109/TVCG.2023.3309941

The Distance-preserving Grid this method reimplements.