CODEWITHSUNDEEP
algorithmsearchgridradial
grey
grey

Reputation: 1150

Radial Grid Search Algorithm

I'm sure there's a clean way to do this, but I'm probably not using the right keywords for find it.

So let's say I have a grid. Starting from a position on the grid, return all of the grid coordinates that fall within a given distance. So I call something like:

getCoordinates( currentPosition, distance )

And for each coordinate, starting from the initial position, add all cardinal directions, and then add the spaces around those and so forth until the distance is reached. I imagine that on a grid this would look like a diamond. The function would return that array of coordinates. Can someone point me to a routine that will do this efficiently ( I'm working in AS3, for what it's worth )?

In the desired output, iteration 1 would be:

.x.
xxx
.x.

Iteration 2 would be:

..x..
.xxx.
xxxxx
.xxx.
..x..

Iteration 3:

...x...
..xxx..
.xxxxx.
xxxxxxx
.xxxxx.
..xxx..
...x...

and so on...

Upvotes: 1

Views: 2218

Answers (6)

Miicck
Miicck

Reputation: 192

I realise this question is 9 years old, but an algorithm that actually iterates radially from the centre (in a diamond) would look like:

for (int mag = 0; mag <= range; ++mag)
    for (int xm = 0; xm <= mag; ++xm)
    {
        int ym = mag - xm;
        int xms = (xm == 0) ? -1 : 1;
        int yms = (ym == 0) ? -1 : 1;
        for (int xs = -1; xs <= xms; xs += 2)
            for (int ys = -1; ys <= yms; ys += 2)
            {
                int x = x_centre + xm * xs;
                int y = y_centre + ym * ys;
                // Do whatever with x, y here
            }
    }

Upvotes: 0

mbeckish
mbeckish

Reputation: 10579

For Iteration N, you want all points P' such that distance from P to P' <= N, where distance is |X' - X| + |Y' - Y|.

for (int i = -N; i <= N; i++)
   for (int j = abs(i) - N; j <= N - abs(i); j++)
   {
      results.Add(new Point(X+i, Y+j));
   }
}

return results;

Upvotes: 0

Vladislav
Vladislav

Reputation: 4976

Edit: Updated the algorithm to reflect what the OP wanted.

Iteration 1:

.x.
xxx
.x.

Iteration 2:

..x..
.xxx.
xxxxx
.xxx.
..x..

... Iteration 4:

....x....
...xxx...
..xxxxx..
.xxxxxxx.
xxxxxxxxx
.xxxxxxx.
..xxxxx..
...xxx...
....x....

Clearly, you can determine the coordinates without iterating.

If the starting point is (X, Y), and the iteration is n

for(int i = x - n; i <= x + n; i++)
{
    for(int j = y - n; j <= y + n; j++)
    {
        int dx = abs(i - x);
        int dy = abs(j - y);
        if(dx + dy <= n) //Produces a diamond, n+1 would produce a diamond with cut corners
        {
            //The point at (i, j) is within the marked area.
        }
    }
}

Upvotes: 7

IVlad
IVlad

Reputation: 43487

BFS + FIFO queue:

P = U = 0;
Q[P] = currentPosition;
D[ Q[P] ] = 0; D[~all the rest~] = infinity (or really any flag, such as -1)

while ( P <= U )
{
  current = Q[P];
  ++P;

  for ( each neighbor N = (X', Y') of (current.X, current.Y) )
    if ( D[N] == inf && D[current] + 1 <= distance )
    {
      D[N] = D[current] + 1;

      ++U;
      Q[U] = N;
    }    
}

Upvotes: 0

AVB
AVB

Reputation: 4024

Two possibilities, depending on what kins of distance you want and how much programming you are willing to do:

(1) Dijkstra's algorithm. If you imagine that each two neighboring points on you grid are connected (only vertical and horizontal connections, so each point has 4 neighbors), you'll get your diamond. You don't have to implement any data structure for the graph -- you only need to generate lists of neighbors for current vertex, as you go.

(2) Fast marching. This'll give you true Euclidean distance within the numerical error, so you'll get an approximate circle, not a diamond.

Upvotes: 0

newdayrising
newdayrising

Reputation: 3802

It depends what kind of data structure you're using to represent your grid, but generally a breadth-first search should take care of this for you.

Upvotes: 2

Related Questions