logo

Show HN: Simple, multi-key sorting algorithm for 2D+ points gridification

Posted by adec314 |6 hours ago |1 comments

adec314 5 hours ago

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)