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

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.

Answer 2

If your objects are dense, then just searching the nearby points will probably be the best way to find the nearest object, spiraling out from the center. If your objects are sparse, then a quadtree or related data structure (R-tree, etc.) is probably better. Here is a writeup with examples.

I do not know of a good online algorithm reference, but I can say that if you are going to write more than the occasional line of code, saving your pennies to buy CLRS will be worth the money. There are lectures based on this book online that have been painstakingly annotated by Peteris Krumins, but they only cover part of the book. This is one of the few books that you need to own.

Answer 3

Udate

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 + d - i;
        int y2 = ys - 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 4

The following simple solution assumes that you can afford storing extra information per grid cell, and that the time cost of adding new objects to the grid is allowed to be relatively high.

The idea is that every cell holds a reference to the closest occupied cell, thus allowing O(1) query time. Whenever an object is added to position (i,j), perform a scan of the surrounding cells, covering rings of increasing size. For each cell being scanned, evaluate its current closest occupied cell reference, and replace it if necessary. The process ends when the last ring being scanned isn't modified at all. In the worst case the process scans all grid cells, but eventually it becomes better when the grid becomes dense enough.

This solution is simple to implement, may have a significant space overhead (depending on how your grid is organized in memory), but provides optimal query time.