Rotacionar matrizes em Java

Uma matriz é uma tabela de tamanho MxN, onde M é o número de linhas e N o número de colunas. São muito comuns em aplicações matemáticas, como resolução de equações ou transformações lineares, e também em aplicações computacionais, como no processamento de imagens.

Rotacionar matrizes pode ser interessante não apenas para trabalhar com números, mas também em outras aplicações. Um mapa 2D também pode ser representado como um array bidimensional, onde são armazenados cada região, tile, hexágono, ou outra estrutura. Uma imagem é um array bidimensional de pixels. Esse array de pixels pode ser facilmente acessado, como é o caso de um objeto do tipo BufferedImage, e rotacionar a sua matriz de pixels equivale a girar a imagem no sentido desejado. Em um jogo de Tetris, as rotações também são operações bem comuns.

Como rotacionar uma matriz em Java? Uma matriz é um array de duas dimensões:
 

[1, 2, 3],

[4, 5, 6],

[7, 8, 9],

[10, 11, 12]


No exemplo, a matriz de 4x3 pode ser declarada da seguinte forma:

         int[][] a1 = new int[][]{   new int[]{1,2,3},
                                     new int[]{4,5,6},
                                     new int[]{7,8,9},
                                     new int[]{10,11,12}};


Ou seja é um array de arrays de int. Também é possível criar como um array unidimensional, e alterá-lo para um array bidimensional, conforme explicado no artigo Dimensões em Java: Convertendo arrays unidimensionais e bidimensionais.

Neste artigo, será mostrado como rotacionar uma matriz em 90° no sentido horário ou anti-horário. O exemplo abaixo mostra a matriz do exemplo acima rotacionada em 90° no sentido horário:

[10, 7, 4, 1],
[11, 8, 5, 2],
[12, 9, 6, 3]

Note que a matriz que era 4x3 se tornou uma matrix 3x4.

Para virar uma matriz "de cabeça para baixo", basta rotacioná-la duas vezes em 90°, totalizando assim 180°:

[12, 11, 10],
[9, 8, 7],
[6, 5, 4],
[3, 2, 1]

Ao girar a matriz original em 90º três vezes, ou seja, em 270°, o resultado é o mesmo que girar a matriz em 90° no sentido anti-horário. O resultado será esse:

[3, 6, 9, 12],
[2, 5, 8, 11],
[1, 4, 7, 10]


Abaixo estão descritos os códigos para rotacionar arrays de duas dimensões no sentido horário e anti-horário, respectivamente:

    public static int[][] rotacionarMatrizHorario(int[][] matriz)
    {
        int largura = matriz.length;
        int altura = matriz[0].length;
        int[][] ret = new int[altura][largura];
        for (int i=0; i<altura; i++) {
            for (int j=0; j<largura; j++) {
                ret[i][j] = matriz[largura - j - 1][i];
            }
        }
        return ret;
    }
    public static int[][] rotacionarMatrizAntiHorario(int[][] matriz)
    {
        int largura = matriz.length;
        int altura = matriz[0].length;  
        int[][] ret = new int[altura][largura];
        for (int i=0; i<altura; i++) {
            for (int j=0; j<largura; j++) {
                ret[i][j] = matriz[j][altura - i - 1];
            }
        }
        return ret;
    }


Essa é a implementação mais simples: os métodos possuem uma complexidade da ordem de O(N²), onde N é o tamanho da matriz, ou mais precisamente O(M*N), onde M é a altura e N a largura da matriz.

Dependendo da aplicação, podem ser implementadas maneiras mais eficientes de rotacionar a matriz. É possível diminuir a complexidade para O(N)*log(N), ou até mais, se forem considerados tratamentos especiais no caso de matrizes esparsas, ou mesmo otimizações de acordo com a arquitetura do computador que fará as rotações.


Rafael.


Comments