## The Design of Software (CLOSED)A public forum for discussing the design of software, from the user interface to the code architecture. Now closed. |
||

The "Design of Software" discussion group has been merged with the main
Joel on Software discussion group.
The archives will remain online indefinitely. |
I have a simple grid data structure (2-D array) which holds elements objects at various locations in the grid (X by Y cells). Each element in the grid has a X,Y location value.
Given another X,Y location in the grid, I'm trying to figure out how to efficiently find all objects near that location within distance Z. The brute force approach will work, but I believe there must be a more efficient way. I have much to learn regarding data-structures and algorithms, but can anybody point me to some relevant information or offer some suggestions? Ideally I'd like to find something that I can understand given my experience. It doesn't have to be the end-all-be-all but hopefully is better than linear search time, etc. Thanks!
cs_wannabe Friday, May 20, 2005
If you can find all objects within a X,Y coordinates, you can start scanning from the known object outward.
For instance: Object at 4,5 Search all objects at least one cell from it, 4,4 4,6 3,5 etc. Keep doing it until you find an object, this will be the closest item. This assumes that there is a close object. The worst case is that you've two distanced objects, and you need to search the whole grid to find it, whereas you could find it more quickly if you would search by object, when you would find it on first go. You can also use strategy and switch if the number of items in the grid is above certain number. Say that you've a grid of 10X10, if you've 50 items, then it probably be more efficent to search by grid.
It seems to me that, if you need to find ALL objects within a particular distance, you will have to do a true/false test for every cell within the range, right?
Of course, if there are more constraints, like x number of objects exist, or find the closest object, or find the x closest objects, etc .... you can then start to optimize. Or ... it could be late on a Friday afternoon, and I'm not thinking through this properly.
bullwinkle Friday, May 20, 2005
I think you may be asking a little much. O(n) is pretty fast.
But before you choose an algorithm, you should think about your data. Consider two algorithms, I) Points are kept in a list, and each one is tested versus the distance and the point in question. II) Points are kept in a hash of hashes (or sorted list of sorted lists) and only the relevant ranges are checked. (I) is O(n) in terms of the number of points, but is independent of the grid and radius size. (II) is indepent of the number of points, but can approach O(n^2) in terms of the distance, depending on how sparse your points are on the grid.
You're looking for collision-detection algorithms. Try using an octree to reduce the number of points you have to compare.
If you want it seriously fast, you should think about building an index on your data. There are types of index specifically designed for spatial data, for example the D-Tree, although that may be overkill depending on your needs.
Matt Saturday, May 21, 2005
If you can run the java applets, the examples here are rather illustrative. See the various demos of spatial indexes under 'Points':
http://www.cs.umd.edu/~brabec/quadtree/ If you play about inserting lots of points it shows you how the different types of index work.
Matt Saturday, May 21, 2005 |

Powered by FogBugz