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.
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.