Get spiral index from location
A 2D Cartesian plane is given. A lattice point in this plane is a point whose coordinates are integers. All lattice points of the plane are arranged into a spiral as follows:
- point (0, 0) is point number 0;
- point (0, 1) is point number 1;
- point (1, 1) is point number 2;
- thereafter the points are (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (-1, 2), (0, 2), (1, 2), (2, 2), (2, 1) etc.
Every lattice point is included in the spiral, so it can be described either by its Cartesian coordinates or by its spiral coordinate, i.e. its number on the spiral.
That, given two integers X and Y, return the spiral coordinate of the lattice point (X, Y). Assume that:
X and Y are integers within the range [-20,000..20,000]
Complexity:
expected worst-case time complexity is O(1);
expected wors-case space complexity is O(1).
public int solution2(int X, int Y) {
int index = 0;
/**
* Description: Left-upper semi-diagonal (0-4-16-36-64) contains squared layer number (4 * layer^2).
* External if-statement defines layer and finds (pre-)result for position in corresponding row or
* column of left-upper semi-plane, and internal if-statement corrects result for mirror position.
*/
if(X*X >= Y*Y) {
index = 4 * X * X - X - Y;
if(X < Y)
index = index - 2 * (X - Y);
} else {
index = 4 *Y*Y -X - Y;
if(X < Y)
index = index + 2 * (X - Y);
}
return index;
}
References:
1 Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin