SquareNet

Open In Colab PyPI version Documentation Status GitHub HF demo

❒ SquareNet — Bijective Gridification of Point Clouds

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 $[i,j]$ cells of the grid. Some extreme point in the bottom-left corner gets $[0, 0]$, a nearby point to the right gets $[0, 1]$, and so on, filling the adaptative square grid as efficiently as possible with the points of the dataset. Basically, it’s a multi-indexing or multidimensional sorting algorithm.

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)

[^1]: 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).

Visual Examples

🚀 How it works

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.

⚙️ The Cartesian Grid Sort Algorithm

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.

Three fitting modes

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)

📦 Installation

pip install squarenet

🧠 Quick Start

→ 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)      # == X

point = 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).

Index conversions

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)) # == sel

Visualizing the mapping

sn = SquareNet(gridshape=(400, 400))
sn.fit("france")
sn.plot()

📈 When to use SquareNet

License: MIT Author: ArmanddeCacqueray