Cartesian grid sort assign raw input points (x_k, y_k) to a grid by mapping the initial flat index k to a multi-index [ij]. Point set become (x_[ij], y_[ij]).
Alternated 1d sorts make the [ij] grid structure converge to monotonic, spatially coherent multi index with a simple and fast algorithm (<80 lines basic C++ code, <200 ms runtime / million points)
1 comment
[ 1.9 ms ] story [ 9.0 ms ] threadAlternated 1d sorts make the [ij] grid structure converge to monotonic, spatially coherent multi index with a simple and fast algorithm (<80 lines basic C++ code, <200 ms runtime / million points)