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!

  • Question is, do you really need that? Instead you could also use and external library like Eigen2/3 – PSquall Aug 10 at 10:25
  • When you say "Rotate the matrix" are you referring to applying a rotate transformation to the matrix, so that you can rotate a mesh that is using that matrix? – TomTsagk Aug 10 at 10:26
  • 1
    @PSquall I think the "why" someone asks a question is irrelevant. Someone is curious how to do this, for all we know, they might just want to practise using Matrices, which is an amazing skill to have for a variety of reasons. – TomTsagk Aug 10 at 10:28
  • @TomTsagk myself, I find we can usually offer better answers to questions that include some context of "why." It gives us a more complete understanding of the situation, avoiding XY problem-style misunderstandings. – DMGregory Aug 10 at 11:09
  • @PSquall I really love doing stuff like this, that way while learning a language (C++ for example) I learn a lot about the topic as well. – Kerdo Aug 10 at 11:18

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.

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
  • I got something working, but don't quite understand how to remove the temporary rows/cols that got added. Rotation code: pastebin.com/2gZJJT6E and matrix before and after rotating: goo.gl/xCUut4 – Kerdo Aug 10 at 13:08
  • Also, I edited my question a bit to make the table more understandable, because I didn't mention before that the zeros and and ones are indexes of the matrix array. – Kerdo Aug 10 at 13:19
  • now i understand it, i was already wondering why you would mix numbers with letters :D. I will edit my answer aswell to adress your problem with the additional rows/coloumsn/elements. – PSquall Aug 10 at 13:29
  • Got it working finally (it seems at least). Posting the full code as an answer to my question. Thanks! – Kerdo Aug 10 at 14:54

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!

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.