Algorithm for finding nearest object on 2D grid

Question

Say you have a 2D grid with each spot on the grid having x number of objects (with x >=0). I am having trouble thinking of a clean algorithm so that when a user specifies a coordinate, the algorithm finds the closest coordinate (including the one specified) with an object on it.

For simplicity's sake, we'll assume that if 2 coordinates are the same distance away the first one will be returned (or if your algorithm doesn't work this way then the last one, doesn't matter).

Edit: A coordinate that is 1 away must be either 1 up, down, left or right. Coordinates that are away diagonally are 2.

As a side note, what is a great, free, online reference for algorithms?

Answer 1

Update

With new information:

Assuming that a coordinate diagonally is 2 away

This algorithm would work. The algorithm searches outwards in a spiral kinda way testing each point in each 'ring' started from the inside.

Note that it does not handle out of bounds situations. So you should change this to fit your needs.

int xs, ys; // Start coordinates  // Check point (xs, ys)  for (int d = 1; d<maxDistance; d++) {     for (int i = 0; i < d + 1; i++)     {         int x1 = xs - d + i;         int y1 = ys - i;          // Check point (x1, y1)          int x2 = xs + d - i;         int y2 = ys + i;          // Check point (x2, y2)     }       for (int i = 1; i < d; i++)     {         int x1 = xs - i;         int y1 = ys + d - i;          // Check point (x1, y1)          int x2 = xs + i;         int y2 = ys - d + i;          // Check point (x2, y2)     } } 

Old version

Assuming that in your 2D grid the distance between (0, 0) and (1, 0) is the same as (0, 0) and (1, 1). This algorithm would work. The algorithm searches outwards in a spiral kinda way testing each point in each 'ring' started from the inside.

Note that it does not handle out of bounds situations. So you should change this to fit your needs.

int xs, ys; // Start coordinates  if (CheckPoint(xs, ys) == true) {     return (xs, ys); }  for (int d = 0; d<maxDistance; d++) {     for (int x = xs-d; x < xs+d+1; x++)     {         // Point to check: (x, ys - d) and (x, ys + d)          if (CheckPoint(x, ys - d) == true)         {             return (x, ys - d);         }          if (CheckPoint(x, ys + d) == true)         {             return (x, ys - d);         }     }      for (int y = ys-d+1; y < ys+d; y++)     {         // Point to check = (xs - d, y) and (xs + d, y)          if (CheckPoint(x, ys - d) == true)         {             return (xs - d, y);         }          if (CheckPoint(x, ys + d) == true)         {             return (xs - d, y);         }     } } 

Answer 2

If you have a list of objects

If you had all the positions of all the objects in a list, this would be a lot easier as you wouldn't need to search all the empty squares and could perform 2D distance calculations to determine the one closest to you. Loop through your list of objects and calculate the distance as follows:

Define your two points. Point 1 at (x1, y1) and Point 2 at (x2, y2).      xd = x2-x1     yd = y2-y1     Distance = SquareRoot(xd*xd + yd*yd) 

Then simply pick the one with the shortest distance.

If you only have a 2D array

If however the problem as described assumes a 2D array where the locations of the objects cannot be listed without first searching for all of them, then you are going to have to do a spiral loop.

Searching for 'Spiral Search Method' comes up with a few interesting links. Here is some code that does a spiral loop around an array, however this doesn't work from an arbitrary point and spiral outwards, but should give you some good ideas about how to achieve what you want.

Here is a similar question about filling values in spiral order in a 2D array.

Anyway, here is how I would tackle the problem:

Given point P, create a vector pair that specifies an area around P.

So if P = 4,4 Then your vector pair would be 3,3|5,5

Loop each value in those bounds.

for x = 3 to 5     for y = 3 to 5         check(x,y)     next next 

If a value is found, exit. If not, increase the bounds by one again. So in this case we would go to 2,2|6,6

When looping to check the values, ensure we haven't gone into any negative indexes, and also ensure we haven't exceeded the size of the array.

Also if you extend the bounds n times, you only need to loop the outer boundary values, you do not need to recheck inner values.

Which method is faster?

It all depends on:

• The density of your array
• Distribution technique
• Number of objects

Density of Array

If you have a 500x500 array with 2 objects in it, then looping the list will always outperform doing a spiral

Distribution technique

If there are patterns of distribution (IE the objects tend to cluster around one another) then a spiral may perform faster.

Number of objects

A spiral will probably perform faster if there are a million objects, as the list technique requires you to check and calculate every distance.

You should be able to calculate the fastest solution by working out the probability of a space being filled, compared to the fact that the list solution has to check every object every time.

However, with the list technique, you may be able to do some smart sorting to improve performance. It's probably worth looking into.