Rotate M*N matrix 90 Degrees Clockwise ,C++

Question

I am trying to rotate a vector of Vectors of chars.

I made a 2d vector matrix setup. right now the matrix takes input from a file, I use vector.push_back(c) to add the characters to the vvc; An example of the vvc array would be something like this

aaaaa
azzza
azaza
azzza
azaaa
azaaa
azaaa
aaaaa

I have the vvc setup, But I am trying to rotate it 90 degrees. I rotated it 90 degrees counter clockwise but I need to rotate it 90 degrees clockwise.

as of right now my code does this

90 counter clock
aaaaaaaa
azzzzzza
azazaaaa
azzzaaaa
aaaaaaaa

and it does it through this loop;

cout <<"\n90 counter clock"<<endl;
    for (size_t colNo = 0; colNo < kvsize2; colNo++)
    {
        for (const auto &row : twovector)
        {
            char colVal = row.at(colNo);
            cout << colVal;
        }
        cout << endl;
    }

I am just learning about vectors, and the range for. Trying to do a decrement loop almost works, but keeps throwing me into a segfault.

"Solved" I was using

twovector.push_back(temp);

using

twovector.insert(twovector.begin(),temp);

gives me

90 counter clock aaaaaaaa azzzzzza aaaazaza aaaazzza aaaaaaaa

Answer 1

Tackling a specific part of the question :

If anyone has any tips or suggestions on how to rotate a M*N 2d vector array

C++ is good at segregating algorithms from data.

Kindly note that the answer is a bit lengthy and has been written with the objective of a tutorial.
Lets begin !!

We want 3 features from our rotate_2d_matrix_clockwise algorithm :

• It should work with all datatypes, i.e. int, char, double or any user defined type.
• It should work with different types of containers, such as std::array and std::vector
• It should be chain-able, i.e. user should be able to call rotate_2d_matrix_clockwise on the result returned by rotate_2d_matrix_clockwise, to achieve 2 times rotation.

Once we are clear with our requirements, we can draft some use-cases for our algorithm.

std::vector<std::vector<char>> data = { {'a', 'b', 'c', 'd'}, 
                                        {'e', 'f', 'g', 'h'}, 
                                        {'i', 'j', 'k', 'l'} };
rotate_2d_matrix_clockwise(data); // rotating 2d-matrix of vector<char>

std::array<std::array<int, 4>, 3> data2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
// rotating 2d-matrix of array<int>, twice
rotate_2d_matrix_clockwise(rotate_2d_matrix_clockwise(data2))); 

So lets use some templates to create a generic 2d-clockwise-rotate function.

Our rotate_2d_matrix_clockwise will :

• take the original_matrix and return a new rotated_matrix.
• automatically deduce the dimensions i.e. M x N of the container passed to it.
• create the rotated_matrix and pass it to a helper function rotate_2d_matrix_clockwise_impl where the actual work would be done.

So how will the implementation of rotate_2d_matrix_clockwise for std::array look ?

template<typename T, size_t M, size_t N>
auto rotate_2d_matrix_clockwise(std::array<std::array<T, M>, N> const & original_matrix)
    -> std::array<std::array<T, N>, M>
{
    std::array<std::array<T, N>, M> rotated_matrix;
    rotate_2d_matrix_clockwise_impl(original_matrix, rotated_matrix, M, N); // rotate
    return rotated_matrix;
}

Neat and precise.
The implementation of rotate_2d_matrix_clockwise for std::vector is a bit messy, though.

template<typename Matrix2D>
auto rotate_2d_matrix_clockwise(Matrix2D const & original_matrix) -> Matrix2D
{
    int const M = original_matrix[0].size(); // deduce M and N
    int const N = original_matrix.size();

    Matrix2D rotated_matrix; // vector has no form, hence we have to resize it for `N x M`
    rotated_matrix.resize(M);
    for (auto x = 0; x < M; ++x) {
        rotated_matrix[x].resize(N);
    }

    rotate_2d_matrix_clockwise_impl(original_matrix, rotated_matrix, M, N); // rotate
    return rotated_matrix;
}

Now lets look at how the actual rotation algorithm rotate_2d_matrix_clockwise_impl would look.
It should be noted, that the algorithm is independent of the container and/or the data contained. It just focuses on rotating.

template<typename OriginalMatrix2D, typename RotatedMatrix2D>
void rotate_2d_matrix_clockwise_impl(OriginalMatrix2D const & original_matrix,
                                     RotatedMatrix2D        & rotated_matrix,
                                     int              const M,
                                     int              const N)
{
    for (auto x = 0; x < N; ++x) {
        for (auto y = 0; y < M; ++y) {
            // Source : https://stackoverflow.com/questions/4780119/2d-euclidean-vector-rotations
            rotated_matrix[y][-x -1 +N] = original_matrix[x][y];
        }
    }
}

Here is a full working example compiled in C++11.

#include <iostream>
#include <vector>
#include <array>

template<typename Matrix2D>
void print_matrix(Matrix2D const & vec)
{
    std::cout << "size of matrix is [" << vec[0].size() << " x " << vec.size() << "]\n";
    for (auto const & inner_vec : vec) {
        for (auto const & item : inner_vec) {
            std::cout << item << ", ";
        }
        std::cout << std::endl;
    }
}

template<typename OriginalMatrix2D, typename RotatedMatrix2D>
void rotate_2d_matrix_clockwise_impl(OriginalMatrix2D const & matrix,
                                     RotatedMatrix2D        & rotated_matrix,
                                     int              const M,
                                     int              const N)
{
    for (auto x = 0; x < N; ++x) {
        for (auto y = 0; y < M; ++y) {
            // Source : https://stackoverflow.com/questions/4780119/2d-euclidean-vector-rotations
            rotated_matrix[y][-x -1 +N] = matrix[x][y];
        }
    }
}

template<typename T, size_t M, size_t N>
auto rotate_2d_matrix_clockwise(std::array<std::array<T, M>, N> const & original_matrix)
    -> std::array<std::array<T, N>, M>
{
    std::array<std::array<T, N>, M> rotated_matrix;
    rotate_2d_matrix_clockwise_impl(original_matrix, rotated_matrix, M, N);
    return rotated_matrix;
}

template<typename Matrix2D>
auto rotate_2d_matrix_clockwise(Matrix2D const & original_matrix) -> Matrix2D
{
    int const M = original_matrix[0].size();
    int const N = original_matrix.size();
    Matrix2D rotated_matrix;
    rotated_matrix.resize(M);
    for (auto x = 0; x < M; ++x) {
        rotated_matrix[x].resize(N);
    }
    rotate_2d_matrix_clockwise_impl(original_matrix, rotated_matrix, M, N);
    return rotated_matrix;
}


int main()
{
    std::array<std::array<int, 4>, 3> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    std::cout << "\nBefore Rotation :\n";
    print_matrix(data);
    std::cout << "\nAfter 2nd Clockwise Rotation :\n";
    print_matrix(rotate_2d_matrix_clockwise(rotate_2d_matrix_clockwise(data)));

    std::vector<std::vector<char>> data2 = { {'a', 'b', 'c', 'd'}, {'e', 'f', 'g', 'h'}, {'i', 'j', 'k', 'l'}};
    std::cout << "Before Rotation :\n";
    print_matrix(data2);
    std::cout << "\nAfter Clockwise Rotation :\n";
    print_matrix(rotate_2d_matrix_clockwise(data2));

    return 0;
}

Answer 2

If I got you right, and all you want is to print the matrix 90 degrees clockwise, try this code:

for (int colNo = 0; colNo < vec[0].size(); colNo++)
{
    for (int i = vec.size() - 1; i >= 0; i--)
    {
        const auto& row = vec[i];
        int colVal = row.at(colNo);
        cout << colVal;
    }
    cout << endl;
}