Mapping elements of a matrix to its position in it

问题:

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.

回答1:

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

0
1
2
3
4
5
6
7
8

回答2:

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.