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.

Closest points in a grid?

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.

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
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.
Ayende Rahien Send private email
Friday, May 20, 2005
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.
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.
Jim Send private email
Friday, May 20, 2005
You're looking for collision-detection algorithms.  Try using an octree to reduce the number of points you have to compare.
Art Send private email
Friday, May 20, 2005
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.
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':

If you play about inserting lots of points it shows you how the different types of index work.
Saturday, May 21, 2005
Grab yourself a copy of one of Sedgewick's Algorithms books. There's a discussion of algorithms to do exactly this kind of search in there.
Chris Tavares Send private email
Monday, May 23, 2005
Is this a homework question or something?

This can be done in O(n). All it requires is some trig. The line between x1,y1 and x2,y2 is a hypotenuse of a right triangle with its origin at x1,y2. Adjust the coordinates, apply trig, now you have the distance.
Brad Wilson Send private email
Sunday, June 05, 2005

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz