How do I rotate 2D matrix properly?

Question

I am given a square matrix size n and characters that the matrix contains.

For example:

3
one
two
row

I have to rotate the matrix by 45 degrees.

              | | |o| | |
  |o|n|e|     | |t| |n| |         
  |t|w|o| ->  |r| |w| |e|
  |r|o|w|     | |o| |o| |
              | | |w| | |

I get

               | | |o| | |
   |o|n|e|     | |t| |n| |         
   |t|w|o| ->  |r| |w| |e|
   |r|o|w|     | |o|w|o| |
               | | | | | |

This is due to rounding values.

I wrote the code. My solution is very limited, I represent it only to show the Idea and my mistakes.

The main thing I don't understand is how to store characters in array so that they have right place (coordinates x, y) after rounding floating point values to integer values. Is there a proper way of doing it?

Are there any advices or observations?

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>

struct Coordinates
{
    int x, y;
};

int main()
{
    int n;
    std::ifstream fin("U3.txt");
    fin >> n;
    fin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

    std::vector<std::vector<char>> matrix;
    for (int i = 0; i < n; i++)
    {
        std::string temp_s;
        std::vector<char> temp_v(n);
        std::getline(fin, temp_s, '\n');
        for (int j = 0; j < n; j++)
        {
            temp_v[j] = temp_s[j];
        }
        matrix.push_back(temp_v);
    }
    fin.close();
    
    std::vector<Coordinates> cord(n * n); // Store coordinates after rotation
    int index = 0;
    for (int y = 0; y < n; y++)
    {
        for (int x = 0; x < n; x++)
        {
            // Multiplying two matrices
            /*
                [ cos(45) -sin(45) ] [ x ]
                [ sin(45)  con(45) ] [ y ]
                =
                [ sqrt(2)/2 -sqrt(2)/2 ] [ x ]
                [ sqrt(2)/2  sqrt(2)/2 ] [ y ]
                =
                [ sqrt(2)/2 * (x - y) ]
                [ sqrt(2)/2 * (x + y) ]
            */
            double new_x = (std::sqrt(2) / 2 * (x - y));
            double new_y = (std::sqrt(2) / 2 * (x + y));
            
            // Trying to round value to int because the index of array is int
            cord[index].x = (new_x >= 0.0 ? std::ceil(new_x) : std::floor(new_x));
            cord[index].y = (new_y >= 0.0 ? std::ceil(new_y) : std::floor(new_y));
            index++;
        }
    }
    /*
    
    Finding the min_x and min_y to know how much should I add to
    the new x and y coordinates to keep the coordinates positive,
    as I have to store them in array. 

    */
    int min_x = std::numeric_limits<int>::max();
    int min_y = std::numeric_limits<int>::max();

    for (int i = 0; i < n * n; i++)
    {
        if (min_x > cord[i].x) { min_x = cord[i].x; }
        if (min_y > cord[i].y) { min_y = cord[i].y; }
    }

    // If there are no negative coordinates then there is nothing to add
    // So I initialize min_x and min_y to 0
    if (min_x >= 0) { min_x = 0; }
    if (min_y >= 0) { min_y = 0; }

    std::vector<std::vector<char>> new_matrix(10, std::vector<char>(10, ' '));

    int row = 0, column = 0;
    for (int i = 0; i < cord.size(); i++)
    {
        new_matrix[cord[i].y + min_y * (-1)][cord[i].x + min_x * (-1)] = matrix[row][column];
        if ((i + 1) % n == 0) { row++; column = 0; continue; }
        column++;
    }

    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            std::cout << new_matrix[i][j];
        }
        std::cout << std::endl;
    }


    return 0;
}

Answer 1

Hm, in my understanding, your algorithm using a rotation matrix will not work. You will always have problems with rounding. And with the correct placement of the values at the correct position in the destination matrix.

And it is even not needed, because the indices for the 2 dimensional can be calculated really simply, without any float operation.

To find a better approach, let us first analyse the possible data:

As you can see. The "next value" of an original row, has to be placed always one to the right and one down. So, for n=3. Print 1, goto right, go down, print 2, goto right, go down. And so on.

If a new source row starts, then the destination start row and start column, are the above value, but then one left and one down. And then again the same as above. Right, down, right, down. And so on and so on.

So, very simple.

Then, the size of the new matrix is always 2*n-1, because we will always have a space between 2 characters.

The destination start row is of course also 0 and the destination start column is simply n-1.

All indices are of course 0 based.

With that approach, no shifting is necessary. Target values can be placed at the correct coordinates immediately.

The solution is then straightforward:

#include <string>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <iterator>

const std::string sourceFileName{ "U3.txt" };

int main() {

    // Open the source File and check, if it could be opened
    if (std::ifstream sourceFileStream{ sourceFileName }; sourceFileStream) {

        // Read the size of the matrix (Must be > 0). Eat trailing white spaces
        if (size_t matrixSize{}; (sourceFileStream >> matrixSize >> std::ws) and (matrixSize > 0)) {

            // Read the complete source file
            std::vector sourceRow(std::istream_iterator<std::string>(sourceFileStream), {});

            // Define a 2 dim vector for target. Size is 2*n-1
            std::vector<std::vector<char>> destination(matrixSize*2-1, std::vector<char>(matrixSize*2-1, ' '));

            // Set start indices for destination. Please note: XStart, or Column start is always matrixSize-1 
            size_t startOffsetIndexDestinationColumn{ matrixSize - 1 };
            size_t startOffsetIndexDestinationRow{};

            // Iterate over all source rows
            for (size_t row{}; (row < matrixSize) and (row < sourceRow.size()); ++row) {

                // Calculate offset for coordinates in destination table
                size_t offsetRow{ startOffsetIndexDestinationRow };
                size_t offsetColumn{ startOffsetIndexDestinationColumn - row};

                // Iterate over source columns in rows and assign value to calculated destination coordinates
                for (size_t column{}; (column < matrixSize) and (column < sourceRow[row].size()); ++column) {
                    // Assign value
                    destination[row + offsetRow++][column + offsetColumn] = sourceRow[row][column];
                }
            }
            // Show result to user. For each row in the destination vector
            for (const auto& row : destination) {

                // And for each column in this row
                for (const char c : row) std::cout << c;

                // Next row
                std::cout << '\n';
            }
        }
        else std::cerr << "\nError: Wrong dimension in source file ' " << sourceFileName << "'\n";
    }
    else std::cerr << "\nError: Could not open source file '" << sourceFileName << "'\n";
    return 0;
}

So, selecting the proper algorithm will save you a lot of headaches.