Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin

Question

For example, here is the shape of intended spiral (and each step of the iteration)

          y
          |
          |
   16 15 14 13 12
   17  4  3  2 11
-- 18  5  0  1 10 --- x
   19  6  7  8  9
   20 21 22 23 24
          |
          |

Where the lines are the x and y axes.

Here would be the actual values the algorithm would "return" with each iteration (the coordinates of the points):

[0,0],
[1,0], [1,1], [0,1], [-1,1], [-1,0], [-1,-1], [0,-1], [1,-1],
[2,-1], [2,0], [2,1], [2,2], [1,2], [0,2], [-1,2], [-2,2], [-2,1], [-2,0]..

etc.

I've tried searching, but I'm not exactly sure what to search for exactly, and what searches I've tried have come up with dead ends.

I'm not even sure where to start, other than something messy and inelegant and ad-hoc, like creating/coding a new spiral for each layer.

Can anyone help me get started?

Also, is there a way that can easily switch between clockwise and counter-clockwise (the orientation), and which direction to "start" the spiral from? (the rotation)

Also, is there a way to do this recursively?

---

My application

I have a sparse grid filled with data points, and I want to add a new data point to the grid, and have it be "as close as possible" to a given other point.

To do that, I'll call grid.find_closest_available_point_to(point), which will iterate over the spiral given above and return the first position that is empty and available.

So first, it'll check point+[0,0] (just for completeness's sake). Then it'll check point+[1,0]. Then it'll check point+[1,1]. Then point+[0,1], etc. And return the first one for which the position in the grid is empty (or not occupied already by a data point).

There is no upper bound to grid size.

Answer 1

Try searching for either parametric or polar equations. Both are suitable to plotting spirally things. Here's a page that has plenty of examples, with pictures (and equations). It should give you some more ideas of what to look for.

Answer 2

There's nothing wrong with direct, "ad-hoc" solution. It can be clean enough too.
Just notice that spiral is built from segments. And you can get next segment from current one rotating it by 90 degrees. And each two rotations, length of segment grows by 1.

edit Illustration, those segments numbered

   ... 11 10
7 7 7 7 6 10
8 3 3 2 6 10
8 4 . 1 6 10
8 4 5 5 5 10
8 9 9 9 9  9

.

    // (di, dj) is a vector - direction in which we move right now
    int di = 1;
    int dj = 0;
    // length of current segment
    int segment_length = 1;

    // current position (i, j) and how much of current segment we passed
    int i = 0;
    int j = 0;
    int segment_passed = 0;
    for (int k = 0; k < NUMBER_OF_POINTS; ++k) {
        // make a step, add 'direction' vector (di, dj) to current position (i, j)
        i += di;
        j += dj;
        ++segment_passed;
        System.out.println(i + " " + j);

        if (segment_passed == segment_length) {
            // done with current segment
            segment_passed = 0;

            // 'rotate' directions
            int buffer = di;
            di = -dj;
            dj = buffer;

            // increase segment length if necessary
            if (dj == 0) {
                ++segment_length;
            }
        }
    }

To change original direction, look at original values of di and dj. To switch rotation to clockwise, see how those values are modified.

Answer 3

I've done pretty much the same thin as a training exercise, with some differences in the output and the spiral orientation, and with an extra requirement, that the functions spatial complexity has to be O(1).

After think for a while I came to the idea that by knowing where does the spiral start and the position I was calculating the value for, I could simplify the problem by subtracting all the complete "circles" of the spiral, and then just calculate a simpler value.

Here is my implementation of that algorithm in ruby:

def print_spiral(n)
  (0...n).each do |y|
    (0...n).each do |x|
      printf("%02d ", get_value(x, y, n))
    end
    print "\n"
  end
end


def distance_to_border(x, y, n)
  [x, y, n - 1 - x, n - 1 - y].min
end

def get_value(x, y, n)
  dist = distance_to_border(x, y, n)
  initial = n * n - 1

  (0...dist).each do |i|
    initial -= 2 * (n - 2 * i) + 2 * (n - 2 * i - 2)
  end        

  x -= dist
  y -= dist
  n -= dist * 2

  if y == 0 then
    initial - x # If we are in the upper row
  elsif y == n - 1 then
    initial - n - (n - 2) - ((n - 1) - x) # If we are in the lower row
  elsif x == n - 1 then
    initial - n - y + 1# If we are in the right column
  else
    initial - 2 * n - (n - 2) - ((n - 1) - y - 1) # If we are in the left column
  end
end

print_spiral 5

This is not exactly the thing you asked for, but I believe it'll help you to think your problem

Answer 4

This problem is best understood by analyzing how changes coordinates of spiral corners. Consider this table of first 8 spiral corners (excluding origin):

 x,y   |  dx,dy  | k-th corner | N | Sign |
___________________________________________
1,0    |  1,0    | 1           | 1 |  +
1,1    |  0,1    | 2           | 1 |  +
-1,1   |  -2,0   | 3           | 2 |  -
-1,-1  |  0,-2   | 4           | 2 |  -
2,-1   |  3,0    | 5           | 3 |  +
2,2    |  0,3    | 6           | 3 |  +
-2,2   |  -4,0   | 7           | 4 |  -
-2,-2  |  0,-4   | 8           | 4 |  -

By looking at this table we can calculate X,Y of k-th corner given X,Y of (k-1) corner:

N = INT((1+k)/2)
Sign = | +1 when N is Odd
       | -1 when N is Even
[dx,dy] = | [N*Sign,0]  when k is Odd
          | [0,N*Sign]  when k is Even
[X(k),Y(k)] = [X(k-1)+dx,Y(k-1)+dy]

Now when you know coordinates of k and k+1 spiral corner you can get all data points in between k and k+1 by simply adding 1 or -1 to x or y of last point. Thats it.

good luck.

Answer 5

I would solve it using some math. Here is Ruby code (with input and output):

(0..($*.pop.to_i)).each do |i|
    j = Math.sqrt(i).round
    k = (j ** 2 - i).abs - j
    p = [k, -k].map {|l| (l + j ** 2 - i - (j % 2)) * 0.5 * (-1) ** j}.map(&:to_i)
    puts "p => #{p[0]}, #{p[1]}"
end

E.g.

$ ruby spiral.rb 10
p => 0, 0
p => 1, 0
p => 1, 1
p => 0, 1
p => -1, 1
p => -1, 0
p => -1, -1
p => 0, -1
p => 1, -1
p => 2, -1
p => 2, 0

And golfed version:

p (0..$*.pop.to_i).map{|i|j=Math.sqrt(i).round;k=(j**2-i).abs-j;[k,-k].map{|l|(l+j**2-i-j%2)*0.5*(-1)**j}.map(&:to_i)}

Edit

First try to approach the problem functionally. What do you need to know, at each step, to get to the next step?

Focus on plane's first diagonal x = y. k tells you how many steps you must take before touching it: negative values mean you have to move abs(k) steps vertically, while positive mean you have to move k steps horizontally.

Now focus on the length of the segment you're currently in (spiral's vertices - when the inclination of segments change - are considered as part of the "next" segment). It's 0 the first time, then 1 for the next two segments (= 2 points), then 2 for the next two segments (= 4 points), etc. It changes every two segments and each time the number of points part of that segments increase. That's what j is used for.

Accidentally, this can be used for getting another bit of information: (-1)**j is just a shorthand to "1 if you're decreasing some coordinate to get to this step; -1 if you're increasing" (Note that only one coordinate is changed at each step). Same holds for j%2, just replace 1 with 0 and -1 with 1 in this case. This mean they swap between two values: one for segments "heading" up or right and one for those going down or left.

This is a familiar reasoning, if you're used to functional programming: the rest is just a little bit of simple math.