I've got an extremely large list of 2D points that are almost constantly moving. I'm in need of an easy to understand method of always knowing the closest point to every other point. I'm thinking if I had an array of the points sorted by their x or y, that there would be a method to do what I'm thinking. Once I had that method, I could simply match every point to it's nearest buddy, and assign them to each other and then remove them from the primary list. Anyone care to help me continue? Thanks, Mythics

What ideas will help here depend on many factors including how many of the points are moving each frame (nearly all?), how large a distance they are moving (relative to the world size and each other - ie there are certain techniques that only help if they are each moving no faster than a known amount), how many points (you said extremely large list, but are we talking millions?).

So about the sorting points, 1 option is 1 sorted list per axis (ie in 2 dimentional game, 2 lists 1 each for x and y).

Then basically you can walk 4 directions, 1 step at a time ... until you get to where the single axis distance is greater than the minimum distance found so far.

Now lists may or may not be lists ... if your distance moved each frame is small, you might use a radix like system - where you have lists of lists (of lists ...) such that each level represents a smaller amount of space ... for instance the outer lists could each be a 10x10 of the world, then instead each is a 10x10 of lists for local points, etc. But this is only useful if the number of objects moving across list boundries is small compared to the total number moving (ie movement speed small compared to list space size).

Now how to update the "lists"? The main choices is either maintain on move, or regerate each frame. This is imposible to really know without profiling the situation you have ... but I usually start with the regenerate version as it is easier to implement, then add the maintenence code if it seems useful.

Well, the 'game' in itself is more of a demonstrative example of a theory I'm in the process of tinkering with. Frame rate doesn't matter much, as long as it processes fast enough to see the changes within a reasonable amount of time.

The number of points will increase from 2 exponentially to a potential of around 100k in the demo, but I'd like it to be capable of handling millions if the concept works out the way I'm hoping.

The number of points that move will start at 100%, and decrease by an amount equal to a variable input by the user (until it reaches 0, which ends the program).

The amount they move will be based on a user input percentage multiplied by their distance from one another. So, the maximum distance they ever move would be a known (since the grid's size is also predefined, meaning one corner to the other at 100% would be the rare possible maximum).


Does that help any?

I just re-read your reply a bit, and thought I'd ask..

Regarding this:
"So about the sorting points, 1 option is 1 sorted list per axis (ie in 2 dimentional game, 2 lists 1 each for x and y).

Then basically you can walk 4 directions, 1 step at a time ... until you get to where the single axis distance is greater than the minimum distance found so far."

Mind going into a bit more detail? Or perhaps someone else can help me understand?

What you're looking for is a spatial index.
For a dynamic one, a r-tree seems like the way to go.

Also, this is a well-known problem within computational geometry. More on wikipedia: http://en.wikipedia.org/wiki/Nearest_neighbour_problem