CODEWITHSUNDEEP
c++arraysalgorithmrotationin-place
GhassanPL
GhassanPL

Reputation: 2734

Rotate 2D rectangular array in-place

I have an non-square array like this:

const int dim1 = 3, dim2 = 4;
int array[12] = { 1, 2, 3, 
                  4, 5, 6,
                  7, 8, 9,
                 10,11,12};

and I need to convert it to:

{3,6,9,12,
 2,5,8,11,
 1,4,7,10}

that is, rotate/shuffle it counter-clockwise (or clockwise, the algorithm should be similiar).

The algorithm should use a minimal amount of space. I have to rotate an image in an extremely memory-constrained environment, so the less space the better. Speed is not as big an issue.

Upvotes: 7

Views: 5806

Answers (5)

Eason
Eason

Reputation: 71

Assume the arr is m x n. If you rotate it clockwise, it's easy to summarize that arr[i][j] becomes arr[j][m - 1 - i].

To reach there, we could first transpose so that arr[i][j] becomes arr[j][i]. Then we reverse current each row so that arr[j][i] becomes arr[j][m - 1 - i].

To avoid index out of bound, we need to figure out the maximal of m and n and fill the arr to make it a square. Then to apply our algorithm. I think this filling doesn't violate the in-place requirement. The code is shown as below:

pub fn rotate_matrix_90_degrees(matrix: &mut Vec<Vec<i32>>) {
    let (m, n) = (matrix.len(), matrix[0].len());
    let mx = m.max(n);
    
    if mx > m {
        for _ in m..mx {
            matrix.push(vec![i32::MIN; mx]);
        }
    }
    if mx > n {
        for i in 0..mx {
            for _ in n..mx {
                matrix[i].push(i32::MIN);
            }
        }
    }

    // arr[i][j] = arr[j][m - i - 1]
    // arr[i][j] -> arr[j][i]
    for i in 0..mx {
        for j in (i + 1)..mx {
            let tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }
    
    // arr[j][i] -> arr[j][m - i - 1]
    for i in 0..mx {
        matrix[i].reverse();
    }
   
    // Remove fillings
    if mx > m {
        for i in 0..mx {
            for _ in m..mx {
                matrix[i].pop();
            }
        }
    }

    if mx > n {
        for _ in n..mx {
            matrix.pop();
        }
    }
}

Upvotes: 2

Andreas Magnusson
Andreas Magnusson

Reputation: 7434

The 2D rotation formula is:

x' = x cos f - y sin f
y' = y cos f + x sin f

If you only rotate in 90° steps, the resulting formula becomes:

x' = -y
y' =  x

Since the array isn't square you'll have to look for assignment cycles, i.e. element (0, 0) gets assigned element (2, 0) which in turn gets assigned (2, 2) etc. You'll need to assign each cycle at the "same" time.

Thus to rotate the whole array you'll do something like (pseudo-code):

// this function rotates 90 degrees
point successor(const point &p)
{
  return (-p.y, p.x);
}

// this function rotates 90 degrees in opposite direction
point predecessor(const point &p)
{
  return (p.y, -p.x);
}

void replace_cycle(const point &start)
{
  int data = get_data(start);
  point x = predecessor(start);
  while(x != start)
  {
    set_data(successor(x), get_data(x));
    x = predecessor(x);
  }
  set_data(successor(start), data);
}

void rotate_in_place()
{
  list<point> l;
  find_cycles(l);
  foreach(c in l)
  {
    replace_cycle(c);
  }
}

Upvotes: 1

kriss
kriss

Reputation: 24207

Not rotating at all may be an option. You just set a flag that would give the way the matrix should be read.

The drawback is that if that image must be provided to some display device or such with fixed direction, that may not be possible.

Upvotes: 0

Yakov Galka
Yakov Galka

Reputation: 72539

You can transpose the matrix in-place (see http://en.wikipedia.org/wiki/In-place_matrix_transposition) and then reverse the rows which is trivial.

Upvotes: 9

Wernight
Wernight

Reputation: 37668

You can use xor to use no additional memory.

// Switch a and b
int a;
int b;
a ^= b;
b ^= a;
a ^= b;

Then you can use a simple for loop to make your whole matrix.

Upvotes: -2

Related Questions