Sign in to follow this  
Toolmaker

Storing a very large number of coordinates and making them enumerable

Recommended Posts

I'm currently toying a bit with an idea that requires me to store a potentially large amount of coordinates in memory. These coordinates can be close to each other or apart quite far. I was thinking about using a quad tree for this, but I'm not sure if that's the best way to go and if there are better approaches to this. The idea is to divide up the tree in smaller cells(like a regular quad tree) and store the accompanying objects in it. When the time comes I need to examine the direct surroundings of a stored object, I can just check out the cell(and potentially accompanying cells). I however do see a potential problem here: The amount of space required by just the quad tree could be potentially be quite large if it is static or if cells are populated densely. For a small sized area I am looking at a potential of 1 million cells alone, because searching through the cells and matching close by objects has to be fast. I am looking for ideas and solutions that can make this work quickly with the minimal amount of memory consumption. I do know that certain spots in the tree will serve as hot spots, and other spots are hardly populated. I was thinking about making the tree cells dynamic. If a cell becomes empty and it's adjacent cells are empty as well, I could have their parent delete them and when the amount of objects in child cells is below a certain threshold, merge them as well. Any other ideas?

Share this post


Link to post
Share on other sites
A kd-tree sounds like it would be a good start. Since you know where the hotspots are you can better guide the subdivisions, and if you find that the kd-tree itself is consuming too much overhead you can switch to a more general BSP tree approach and limit the depth of the tree. It will function much like a kd-tree, except each node can have the potential to store multiple points.

Share this post


Link to post
Share on other sites
While I haven't read into kd-trees except skimmed a bit over the Wikipedia page for a bit of background info. It appears that kd-trees are meant for 3D space partitioning, and I have no use for the Z value. All the coordinates are stored in 2D.

This is why I initially came up with a quad tree. The hot spots can be somewhat predicted before run-time but not by the software itself, and don't necessarily have to occur or can change based on time. So the welding of leafs has to be done dynamically at run-time.

If I were to go with a quad-tree, I'd go with a point quad-tree, because the locations I am storing are just X,Y coordinates. What I'm doing is a bit more related to storing geographical data, but it's not static. I'm not sure if an R-tree(R+ seems interesting here) or variants are suitable for it.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this