GitHub - ArmanddeCacqueray/Cartesian-Grid-Sort: Greedy multidimensional grid assignment for point clouds · GitHub
/" data-turbo-transient="true" />
Skip to content
Type / to search
Sign in<br>Sign upAppearance settings
You signed in with another tab or window. Reload to refresh your session.<br>You signed out in another tab or window. Reload to refresh your session.<br>You switched accounts on another tab or window. Reload to refresh your session.
Dismiss alert
{{ message }}
ArmanddeCacqueray
Cartesian-Grid-Sort
Public
Notifications<br>You must be signed in to change notification settings
Fork
Star
main
BranchesTags
Go to file
CodeOpen more actions menu
Folders and files<br>NameNameLast commit message<br>Last commit date<br>Latest commit
History<br>71 Commits<br>71 Commits
README.md
README.md
cartesian_sort.gif
cartesian_sort.gif
cartesian_sort_illust.png
cartesian_sort_illust.png
cartesian_sort_illust2.png
cartesian_sort_illust2.png
main.py
main.py
sample.py
sample.py
sort.py
sort.py
sort_core.cpp
sort_core.cpp
viz.py
viz.py
View all files
Repository files navigation
Cartesian Grid Sort Algorithm
This repository illustrates the core cartesian grid sort procedure of the SquareNet ❒ gridification engine for demonstration purposes.
It showcases the live progress of the grid sorting algorithm 𝄜 and includes an animated GIF alongside the simple Python script used to generate it, as well as both the full python (slow, simple) and C++ implementation (optimized) of the cartesian grid sort.
Quick Start
The Cartesian Grid Sort allow to structure arbitrary point clouds as a multi-dimensional grid. The algorithm is quite simple once one get the main idea and could be reused in various contexts were a spatially coherent multi index structure can be usefull. Note that end user should rather refer to SquareNet gridfication package itself (see for exemple this tutorial, or this benchmark with kd-tree) which simply require to
pip install squarenet
Regarding this auxiliar repository:
Run main.py to reproduce the quick visual animated demo that showcase gridification in progress.
Feel free to look at what's inside sort.py (not optimized, simple illustration purpose) to fully understand how the algorithm work.
See sort_core.cpp for a C++ optimized version (multi-threaded).
It achieves<br>Windows (MSVC):
cl /O2 /openmp /EHsc /std:c++17 sort_core.cpp<br>.\sort_core.exe
Linux/macOS:
g++ -O3 -fopenmp -std=c++17 sort_core.cpp -o sort_core<br># or<br>clang++ -O3 -fopenmp -std=c++17 sort_core.cpp -o sort_core<br>./sort_core
Algorithm (2D Version)
Note: The generalization to higher dimensions is straightforward.
Initialization:<br>Take the $N$ arbitrary Euclidean points to be processed:
$$ (x_k, y_k)_{1 \le k \le N} $$
In the main animation example, $N = 4225 = M^2 = 65 \times 65$ points. If N is not an even square, apply padding with dummy $\pm \infty$ points that will fall in empty slots of the grid to complete $N$ to the nearest square:
$$ N \leftarrow M^2 $$
Randomly split the flat key $k$ into a 2D multi-key to form a grid (purely random initialization):
$$ k \leftrightarrow [i, j]_k \quad i,j \in 1,2,3,..., M $$
$$ (x_k, y_k) \leftrightarrow (x_{ij}, y_{ij}) $$
Iterative Sorting Procedure:
Sort the Points according to their $x$-coordinate along the row key $i$: update $[i, j] \leftarrow [i', j]$ where $i'$ ensures the $x_{ij}$ coordinates are sorted along the $i$-axis (all columns $j$ are processed in parallel).
Sort the Points according to their $y$-coordinate along the column key $j$: update $[i, j] \leftarrow [i, j']$ to ensure monotonic y coordinate.
Check if the $x$-sorting was broken by applying the $y$-sorting step (which is highly probable). If so, return to step 1 and repeat until both dimensions are simultaneously satisfied.
Output
The algorithm produces a bijective mapping from the raw points RP, shape [4225, 2]: $(x_k, y_k)$ to a gridded tensor GT, shape [65, 65, 2]: $(x_{ij}, y_{ij})$.
Upon termination, the resulting gridded view GT is guaranteed to be monotonic 📈 :
$x$ strictly increases along $i$ ($\rightarrow$)
$y$ strictly increases along $j$ ($\uparrow$)
This ensures that the multi-key $[i, j]$ is spatially coherent, meaning local neighborhoods are roughly preserved: the nearest spatial neighbors of a point with multi-key $[i, j]$ will likely have adjacent multi-keys $[i\pm1, j\pm1]$. Though a few outliers will unavoidably land at $[i\pm2, j\pm2]$ or further.
By construction, the transformation is a bijective assignement between the raw point key $k$ and the grid multi-key $[i, j]$. This allows for seamless data transfer between the flat point list and the grid using simple fancy indexing operations.
Proof of Termination & link to Optimal Transport
A notable aspect of Cartesian Grid Sort algorithm is its proof of termination, which is relatively simple and establishes a link to Optimal Transport (thought the cartesian grid sort algorithm doesn't provide exact optimal transport...