Rotation of a matrix with unequal rows and columns

Question

I have this simple matrix class which has a char** array for storing the data. The data array gets initialized like this:

data = new char*[cols];
  for (int x = 0; x < cols; x++)
    data[x] = new char[rows];

Is it possible to rotate this kind of matrix when its let's say 3x2? So that the rotation will result in this (or counter clockwise works as well)

a b
c d    ->    e c a
e f          f d b

Got some kind of atable here which shows where certain elements move when the matrix is rotated, but cannot get it working in code (those numbers around a&b are the x and y indexes):

  0                               0
0 a              0 1            0 b
1 b     ->     0 b a     ->     1 a
   (0,0)->(1,0)     (0,0)->(0,0)
   (1,0)->(0,0)     (1,0)->(0,1)

I'm currently rotating with these methods (they rotate clockwise):

void Matrix::reverseCols() {
  for (int x = 0; x < cols; x++)
    for (int y = 0, i = cols - 1; y < i; y++, i--)
      std::swap(data[y][x], data[i][x]);
}

void Matrix::transpose() {
  for (int y = 0; y < rows; y++)
    for (int x = y; x < cols; x++)
      std::swap(data[y][x], data[x][y]);
}

Should I keep it like this or should I go with a one-dimensional array and calculate the index when accessing the data by a method? And should I initialize the data array by columns (like I'm doing right now) or rows?

Wouldn't really bother doing this, but while learning C++ I want to build an console window engine and test it with a Tetris clone.

Thanks!

Answer 1

Using a linear matrix rather than a multidimensional array,

(Click here to run this)

#include <iostream>
#include <cassert>

using namespace std;

template<typename T>
void printMatrix(T data, const int cols, const int rows)
{
    for(int j = 0; j < rows; ++j)
    {
        for(int i = 0; i < cols; ++i)
        {
            cout << data[j * cols + i] << '\t';
        }
        cout << '\n';
    }

}

/* 
rotate src matrix 90 degrees clockwise and store in dest
Assumes dest has sufficient space. 
*/
template<typename T>
void rotateMatrix(T dest, T src, int cols, int rows)
{
    /*
    rotate - 
    y' = x
    x' = -y
    */

    // one loop, but costs a mod and a div        
    for(int i = 0; i < rows * cols; ++i)
    {
        // source coordinates
        int x = i % cols;
        int y = i / cols;
        // destination coordinates
        int x1 = (rows - 1) - y;
        int y1 = x;

        dest[y1 * rows + x1] = src[y * cols + x];
    }


}

// or, if you'd prefer a nested loop to division:
template<typename T>
void rotateMatrixLoop(T dest, T src, int cols, int rows)
{
    for(int j=0; j < rows; ++j)
    {
        int dx = (rows - 1) - j;
        for(int i = 0; i < cols; ++i)
        {
            int dy = i;
            dest[dy * rows + dx] = src[j * cols + i];
            // for a 2d Array, you'd just
            // dest[dy][dx] = src[j][i];
        }

    }

}

// pointlessly optimized version
template<typename T>
void rotateMatrixSilly(T dest, T src, int cols, int rows)
{
    int srcOffset = 0;
    for(int j=0; j < rows; ++j)
    {
        int destOffset = rows - 1 - j;
        for(int i = 0; i < cols; ++i)
        {
            dest[destOffset =+ rows] = src[srcOffset++];
        }

    }

}    

int main()
{
    int cols = 2;
    int rows = 3;
    char source[] { 
        'a', 'b', 
        'c', 'd',
        'e', 'f',

    };
    char dest[sizeof(source) / sizeof(source[0])];
    int destRows = cols;
    int destCols = rows;

    cout << "Original matrix:\n";
    printMatrix(source,cols,rows);


    cout << "Rotated matrix with division:\n";
    rotateMatrix(dest, source, cols, rows);
    printMatrix(dest, destCols, destRows);

    cout << "Rotated matrix with nested loop\n";
    rotateMatrixLoop(dest, source, cols, rows);
    printMatrix(dest, destCols, destRows);

    cout << "Slightly optimized rotation...\n";
    rotateMatrixSilly(dest, source, cols, rows);
    printMatrix(dest, destCols, destRows);


    return 0;
}

You could do this in place with a little more work, and changing it to use a multidimensional array as in your original sample is trivial. I templated the rotate and print functions which may not be necessary in your implementation; but hey, why not.

Answer 2

Depending on what your matrix should be able to do, you should simplify your matrices you calculate with. If you have a 2x3 Matrix, fill the missing row with zeros, then invert/transpose and then remove the column you added.

If you can't use 0 for that, use null for that and just move the values from one coordinate to another.

Edit: To fill up the elements in your Matrix, you can simply use null values. Convert your char* array into a complete matrix (n x n), then traverse/invert/rotate, then create a new 2d char* array with the null-values removed. E.G.:

a b c        a  b    c                    e    d   a    e d a     e d a
d       =>   d null null  (rotate R) =>   f   null b => f   b OR  f b 
e f          e  f   null                 null null c        c     c

The Problem is, what happens if elements are not the next element in a row after the rotation (in my example the c and b. You either have a 2d array with Rows then Coloumns, or Coloumns then Rows.

This depens on what you want and there is no general answer (as this is in math not stictly defined)

If you have no rows with empty elements, n x m matrix, its simple, as you get a m x n matrix instead with no elements left out. If n > m, add x Coloumns till n + Y = m, if m > n add rows Y. Then rotate and remove either Y rows or coloumn (always the last ones).

a b                        a b 0               e c a     e c a
c d  (add coloumn of 0s)=> c d 0 (rotate R) => f d b =>  f d b
e f                        e f 0               0 0 0

Answer 3

After many hours of behind the computer, I've seem to get it working. The full code rotation code (keep in mind, that the char** data array gets initialized column by column):

void Matrix::rotate(int amt) {
  for (int i = 0; i < amt; i++) {
    int cols = this->cols, rows = this->rows;
    int size = (cols > rows) ? cols : rows;

    char** oldData = this->data;

    char** data = new char*[size];
    for (int x = 0; x < size; x++) {
      data[x] = new char[size];
      for (int y = 0; y < size; y++)
        data[x][y] = ' ';
    }

    this->cols = size;
    this->rows = size;

    for (int x = 0; x < cols; x++)
      for (int y = 0; y < rows; y++)
        data[x][y] = oldData[x][y];

    this->data = data;

    transpose();
    reverseCols();

    char** newData = new char*[rows];
    for (int x = 0; x < rows; x++) {
      newData[x] = new char[cols];
      for (int y = 0; y < cols; y++)
        newData[x][y] = ' ';
    }

    if (cols > rows) {
      //Remove enough columns from the left
      int diff = cols - rows;
      for (int x = 0; x < rows; x++)
        for (int y = 0; y < cols; y++)
          newData[x][y] = this->data[x + diff][y];
    } else {
      //Remove enough bottom rows
      for (int x = 0; x < rows; x++)
        for (int y = 0; y < cols; y++)
          newData[x][y] = this->data[x][y];
    }

    this->data = newData;
    this->cols = rows;
    this->rows = cols;
}

void Matrix::reverseCols() {
  for (int x = 0; x < cols; x++)
    for (int y = 0, i = cols - 1; y < i; y++, i--)
      std::swap(data[y][x], data[i][x]);
}

void Matrix::transpose() {
  for (int y = 0; y < rows; y++)
    for (int x = y; x < cols; x++)
      std::swap(data[y][x], data[x][y]);
}

I'm pretty sure that it's not the most optimal way to do this, but it works as it should.

Special thanks to @PSquall for pointing out to change the matrix to a N x N matrix!