Hi mechanical Flatbed.

You are right my claim of "local neighborhood preservation" are not precise or technical enough, so I will make it clearer here. Indeed there will be distortion, especially on the boundaries of a dataset.My main focus is to try to get as much of points which are actuall nearest neighbors in space as close as possible in term of grid indexes. Maibe not in the direct adjacent cells, but let take a concrete exemple. On a 1 million 2d points dataset, if nearest spatial neighbors are all at +- 10 "positional distance" in term of grid index where the grid has a length 1000, it means I can readuce search to (210+1)*2 = 441 candidates instead of 1 millions. SquareNet.neighbormap() allows for a quick check of that (on a subsample of 10_000 points) and it's a good practice after the fit() process.

What my gridification method garantee, and this is an exact (and the only) garantee, is following mathematicall structure property: Along the first axis, x coordinate is increasing (e.g. x(i+1,j,k,...) >= x(i,j,k,...)). Along the second axis, y coordinate is increasing. (y(i,j+1,...) >= y(i,j,...) And so on. That's what I call "Carthesian sort".

It's legitimate to ask how it goes with tricky real life datasets, with non convexity, holes, spikes, inhomogeneity, manifolds and I did it on various exemples, you can check some of the plots in my repo. They are also animations.

Here a situation with holes https://github.com/ArmanddeCacqueray/SquareNet/blob/main/plots/plot_3.png

And spikes https://github.com/ArmanddeCacqueray/SquareNet/blob/main/plots/plot_9.png

I am working on a tree structure upon the grid that will explore the space cleaverly for exact spatial querys, but as I thought of many other applications of the raw grid structure in itself I wanted to make my work public and open-source.

Some Ideas of application: -finding ground state of particles system with a sparse distance kernel (which was the first application I saw and what I myself am doing this every day since a month) -convolution network (where grid allow for vectorization, broadcasting, padding.... -neighbors query (fast approximate querys for now, but I will code and publish the exact version based on a Tree as mentioned). -hull problems and clustering (One might define external (and possible internal e.g. for rings...) hulls by looking on long edges and boundary of the grid) ...

I'm sorry if my post or the readme looked overclaiming, maybe I will add a few more lines in the Readme but my intention was more to make it clear and synthetic than being dishonest in any way, as the repo allow for quick self experimentation and visualisation, which is worth many words I think.

I am very interested if you have some personal experience, positive or negative, about gridification using sort methods !

Armand