🔒 Locked

Spatial Indexing

Started by yahn Apr 14, 2009 at 12:19 AM 2 replies 800+ views

Original Post

Apr 14, 2009 at 12:19 AM

Ok, I need to detect all instances within a varying proximity. Currently, I'm storing the instances in a quadtree. So, for example, say I need to make lists of all instances within 50, 100, 200 and 400 meters of an instance. What would be the most efficient way to query the quadtree for this information? The nodes of the quadtree have a list of the items they contain. I plan on returning a list of the leaf nodes in which the rectangle is bound. From that I can build a list of the instances. Now, the problem is that the query to get all these leaf nodes could be relatively slow, especially when the rectangle is very large in comparison to the entire tree. So, I think I should store all the leaf nodes in such a way that I can easily determine which nodes the rectangle is bound. It seems like a good way to do this would be with another quadtree. But that seems somewhat ironic. Does anyone have any advice?

LorenzoGatti

Apr 14, 2009 at 6:34 AM

If you need to process all objects in the query region individually (even without building a list), large query regions cannot be fast: regardless of data structures you can cull only a modest minority of your objects.

For each quadtree cell, computing its bounds is trivial and deciding if it is outside the query region, inside or straddling the boundary takes constant time; why would you need another quadtree?

Cygon

Apr 14, 2009 at 6:54 AM

Unless you have a huge number of objects, I'd just do the 400x400 meters query and then do the smaller distances while enumerating the returned list / enumerating the returned quad tree iterator, depending on your design.

If you do have a huge number of objects and this is only for a radar or something that's limited to the player, you could use a special quadtree that's centered on the player. This would also improve the tightness of the query rectangle since you can create a quadtree of 400x400 meters and it will have quadrant boundaries conveniently placed at 200, 100 and 50 meters.

You can also try other data structures for this purpose. An R-Tree, for example, can efficiently provide you with any nodes in a given region. There are even variants of R-Trees that take the velocity of objects into account and can efficiently deliver a very tight subset of the objects in a given rectangle between now and any future point in time.

yahn

Apr 14, 2009 at 8:45 AM

Quote:
If you need to process all objects in the query region individually (even without building a list), large query regions cannot be fast: regardless of data structures you can cull only a modest minority of your objects.

Large and fast are relative. I'm looking to meet requirements to process 20k plus instances on core 2 duo type processors. This doesn't seem unrealistic.

The queries should never be large enough to select 200 instances and should usually only query around 20 instances. I was just pointing out that I see problems if I would ever need to query large regions.

The problem is that I need to perform these small queries very frequently. The fastest way I can think to do this is:

Have each instance store the node which it is bound to. Traverse the tree backward from the current node to find the node big enough to fully contain the rectangle. Start eliminating nodes from that point.

Is this the most efficient way?

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.