Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Rotating a 2D pixel array by 90 degrees

I have an array of pixel data for an image. The image I am getting is already rotated to 270 degrees. So I am trying to rotate it again by 90 degrees to have the correct image. I've tried a transpose algorithm, by changing data[x][y] to data[y][x], but I don't think that's the correct way. Can anyone guide me what can I do to have it rotated?

like image 502
noob Avatar asked May 22 '13 06:05

noob


People also ask

How do you rotate a 2d array?

You can do the same with rotations (play with indices). In case n^2 is not feasible. You can create an interface which access each element. Then given (i, j), apply rotation to (i, j) access the rotated element and return.

How do you rotate 90 degrees coordinates?

The rule for a rotation by 90° about the origin is (x,y)→(−y,x) .


Video Answer


4 Answers

If you want to do it in-place with O(1) space, you can follow this:

  1. Transpose the matrix by swapping data[i][j] and data[j][i] :

    for (int i = 0; i < n; i += 1) {
        for (int j = i+1; j < n; j += 1) {
            swap(data[i][j], data[j][i]);
        }
    }
    
  2. Reverse each row or column for +90 or -90 degrees of rotation, respectively. For example for +90 degrees of rotation:

    for (int i = 0; i < n; i += 1) {
        for (int j = 0; j < n/2; j += 1) {
            swap(data[i][j], data[i][n-1-j]);
        }
    }
    
like image 116
mohaghighat Avatar answered Oct 04 '22 02:10

mohaghighat


This can be done without using any extra space, so called In-place matrix transposition (not exact the same). Remember to do some mirroring after the transposition.

  1. If the image is square

    enter image description here

  2. If the image is not square

    • For non-square matrices, the algorithms are more complicated. Many of the algorithms prior to 1980 could be described as "follow-the-cycles" algorithms. That is, they loop over the cycles, moving the data from one location to the next in the cycle. In pseudocode form:

    enter image description here

like image 31
herohuyongtao Avatar answered Oct 04 '22 02:10

herohuyongtao


You have old_data[rows][cols] and new_data[cols][rows], then:

for(int i=0; i<cols; i++) {
    for(int j=0; j<rows; j++) {
        new_data[i][j] = old_data[rows-1-j][i];
    }
}

This should rotate old_data by 90 degrees CW.

like image 32
raj raj Avatar answered Oct 04 '22 03:10

raj raj


To rotate the image (2D matrix) by 90deg, you can easily do this by mapping out a pattern between the initial state and the end state after rotating it by 90deg.


a[i][j] => a[m][n]
a[0][0] => a[0][2]
a[0][1] => a[1][2]
a[0][2] => a[2][2]
a[1][0] => a[0][1]
a[1][1] => a[1][1]
a[1][2] => a[2][1]
a[2][0] => a[0][0]
a[2][1] => a[1][0]
a[2][2] => a[2][0]

Now the solution is obvious. All the J's turn to M and N = (Size of matrix(2) - I).


const rotateImage = (a) => {
  let size = a.length;
  let results = new Array(size);
  for (let i = 0; i < size; i++) {
    results[i] = new Array(size);
  }
  for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
      results[j][(size - 1) - i] = a[i][j];
    }
  }
  return results;
}

console.log(rotateImage([
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]));
like image 42
Akinjiola Toni Avatar answered Oct 04 '22 01:10

Akinjiola Toni