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: one point, one cell, no overlap, fully invertible.

The practical payoff: 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.

āœ” Works in any dimension
āœ” 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)

Example of gridification

šŸš€ 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 ā€” no information lost.

āš™ļø The Cartesian Grid Sort Algorithm

General Optimal Transport (the theoretically correct solution to gridification) is O(NĀ²) to O(NĀ³) ā€” 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 depending on scale and geometry sometimes 100 iterations are fine, sometimes best results require 10_000 iterations = 20 minutes fit for 1-M points dataset)

šŸ“¦ 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