This repository hosts the SquareNet python package for bijective gridification. SquareNet maps unstructured point clouds to structured grids through a bijective transformation: Each point is assigned to exactly one cell, and conversely each cell to one point. No voids, no overlaps: points are simply reindexed and reordered into a tensor square/cubic/hypercubic layout.
Concrete visual example: 160k samples, 2D points dataset from the Germany map reshaped as a 400×400 tensor, by mapping points to
The practical payoff of the gridification preprocessing: you replace expensive spatial queries (k-NN, radius search, neighborhood graphs) with plain tensor indexing. Think of it as an alternative to kd-trees, voxelization, rasterization, or graph-based approaches, but with a regular tensor structure allowing for massive parallelisation.
✔ Runs in any dimension 1
✔ Handles non-convex geometries and irregular distributions
✔ Scales to millions of points (seconds, not minutes)
✔ Compatible with PyTorch and JAX
✔ Native pading for mismatch between number of grid slots and number of points (since version 1.2)
.png)
You initialize SquareNet with a target grid shape, then call fit() on your point cloud. Under the hood, the Cartesian grid sort algorithm rearranges point indices into structured grid multi-indices.
raw points #(N, D) → sn.fit(X) → grid #(N1, N2, ..., ND)
flat data #(N, *C) → sn.map(X) → structured tensor #(N1, ..., ND, *C)
structured tensor → sn.invert_map(X) → back to flat view
The mapping is bijective, so invert_map is exact and no information is lost.
General Optimal Transport (the theoretically correct solution to gridification) is O(N²) to O(N³) which is intractable at scale. Cartesian-grid-sort - see auxiliary repository - is a fast heuristic that exploits the tensor structure of the grid to sidestep that complexity.
| Mode | How it works | When to use |
|---|---|---|
fast (default) |
Raw Cartesian sort | General use, large datasets |
robust |
Sorts subgrids at each step | Less prone to local minima |
ultimate |
Adds random shearing perturbations | Near-zero outliers, but slow and require tuning max_iter parameter (bigger = better, but slower) |
pip install squarenet→ See 00_getting_started.ipynb
from squarenet import SquareNet
import numpy as np
# 4D example: N points → 5×11×7×13 grid
N = 5 * 11 * 7 * 13
D = 4
X = np.random.rand(N, D)
sn = SquareNet(gridshape=(5, 11, 7, 13))
sn.fit(X)
# Inspect grid quality
sn.neighbormap()
# Map point data to grid and back
Xgrid = sn.map(X) # shape (5, 11, 7, 13, D)
Xback = sn.invert_map(Xgrid) # == Xpoint = np.random.rand(D)
index = sn.search_sorted(point) # fast N-dimensional generalisation of 1D search sorted,
#will return a cell multi-index that best fit the given point (approximate method).Working on a subset? mapidx converts flat point indices to grid multi-indices and back.
# Select points inside a disk, map their indices to the grid
sel = np.where(points[:, 0]**2 + points[:, 1]**2 <= 100) #raw indexes
gridsel = sn.mapidx(sel) #grid indexes
selback = sn.invert_mapidx(np.stack(gridsel, axis=1)) # == selsn = SquareNet(gridshape=(400, 400))
sn.fit("france")
sn.plot()- Point cloud processing: fast spatial queries (neighbors, subsets) with contiguous memory lookup and vectorized tensorial processing instead of irregular kd-tree/voxels data structure
- Kernel methods: efficient approximation of large Gram matrices via the grid structure
- Deep learning: convert flat point datasets into tensors ready for CNNs or attention-based models
License: MIT | Author: ArmanddeCacqueray
Footnotes
-
To be more precise, the sweet spot for SquareNet grid structure is dimensions 2–5. Dimensions 6–10 are still OK, but increasingly challenging, while 11+ remains workable, but will require random projection techniques onto lower dimensional subspaces (see common RP-Trees/Forests tricks for more details). ↩