Mapping elements of a matrix to its position in its spiral order traversal

Question

I am trying to find a function which takes the position of a cell(x,y) in the matrix(MXN) and gives its position(1<=p<=M*N) in the spiral order traversal of the matrix . For example : for M = 3, N = 3 , and matrix :

[1,2,3]

[4,5,6]

[7,8,9]

Spiral Order Traversal yields : { 1,2,3,6,9,8,7,4,5 } , so if the function is denoted by F(x,y) , then :

F(1,1) = 1 , F(1,2) = 2, F(1,3) = 3, F(2,3) = 6 , .. , and so on.

So basically I need a closed form formula which for a given M,N, and a position (x,y) , yields the position of that cell in the spiral order traversal.

@MrSmith42 : Yes it should be and I have corrected that . Basically I was trying for simple square matrix(NXN) , and I observed that there exists a simple quadratic formula for the diagonal elements , and similarly for the other elements as well by analysing four different cases. However , for general MXN matrix it appears to be quite tricky and challenging. — user1011, Sep 13 '13 at 11:49
Possible duplicate of [Looping in a spiral](http://stackoverflow.com/questions/398299/looping-in-a-spiral) or of one of the many other similar questions asked here. — High Performance Mark, Sep 13 '13 at 11:50
@HighPerformanceMark : The problem you mentioned considers the algorithm for looping through the matrix in spiral order(however similar to I mentioned though) . What I am talking about is an O(1) answer for getting the position(p) of any random position (x,y) in MXN matrix in its spiral order traversal — user1011, Sep 13 '13 at 11:55
@High Performance Mark: This is quite a bit different. Here the function `F(x,y)` is wanted not the sequences of positions. But the answers to the other question might help to answer this one. — MrSmith42, Sep 13 '13 at 11:56

Vincent van der Weele · Accepted Answer · 2013-09-13T12:55:12.270

Let's start with finding in which "round" the cell is. That is, how often did the spiral go fully around before hitting this cell:

int n = min(x, y, M - x - 1, N - y - 1);

The first full round consists of 2*M + N) - 4 cells, the next one of 2*(M + N) - 12 cells, and so on (I hope you believe me in this). More general, round i consists of 2*(M + N - 2) - 8*i cells.

So how many cells are in the first n rounds? Just sum the value just found:

sum(0 <= i < n : 2*(M + N - 2) - 8*i) = 2*n*(M + N - 2) - 8 * sum(0 <= i < n : i)
                                      = 2*n*(M + N - 2) - 8 * n * (n - 1) / 2
                                      = 2*n*(M + N - 2*n)

We can already add this value to the index:

int index  = 2 * n * (M + N - 2 * n);

Now we just need to check where in the current round the cell is:

if (n == y) {
    // top of this round
    index += x - n;
} else {
    // add full top of this round
    index += M - 2 * n;

    if (n == M - x - 1) {
        // right side of this round
        index += y - (n + 1);
    } else {
        // add full right side  of this round
        index += N - 2 * n - 1;

        if (n == N - y - 1) {
            // bottom of this round
            index += N - x - 1 - (n + 1);
        } else {
            // add full bottom of this round
            index += M - 2 * n - 1;

            // left side of this round
            index += M - y - 1 - (n+1);
        }
    }
}

I called the method spiral(M, N, x, y) and ran it as follows:

System.out.println(spiral(3, 3, 0, 0));
System.out.println(spiral(3, 3, 1, 0));
System.out.println(spiral(3, 3, 2, 0));
System.out.println(spiral(3, 3, 2, 1));
System.out.println(spiral(3, 3, 2, 2));
System.out.println(spiral(3, 3, 1, 2));        
System.out.println(spiral(3, 3, 0, 2));
System.out.println(spiral(3, 3, 0, 1));
System.out.println(spiral(3, 3, 1, 1));

Which results in

score 0 · Answer 2 · answered Sep 13 '13 at 12:41

Okay, I thought of a solution. I didn't write any code yet to test it out, but maybe later if I get home after work I can test it out to be 100% sure.

The first thing you need to do in algorithm is to figure out in which quarter is your position located. For instance in your matrix the center of the matrix isn't in any quarter, but you can always tell on which axis the point is. The general idea is to figure out how far from the side is the point, so how many FULL circuits should it take to get to the point we are looking for.

After we figure out how far from the side we are (it should be easy taking the x and y and the quarter we are in and the size of the matrix) we can use this formula to count the number of positions used in traversal to create these circuits. (n is a distance from the side)

sum = 2n * (M - 2n + N)

If we have the number of positions used to get to the circuit on which is the point we are looking for now the only thing is to figure out how far from this point we are on the circuit. I think it should be easily countable with the knowledge in which quarter we are located.

Mapping elements of a matrix to its position in its spiral order traversal

2 Answers2

Linked