468,512 Members | 1,341 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,512 developers. It's quick & easy.

Rotate a matrix of any size

I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.

Can I extend it to work on a matrix of any size (or even any type, not
just integers) for the logic may be the same when it applies to a
matrix of different size?

#include <stddef.h>
#include <stdlib.h>
#include <string.h>

/*Rotate a 4*4 matrix of integers by 90 degrees clockwise.*/

void rotate(void *matrix, const int width){
int (*array)[4] = matrix;
int (*tmp)[4];
int i, j;
size_t n = width * width * sizeof **array;

if(tmp = malloc(n)){
for (i = 0; i < width; ++i)
for (j = 0; j < width; ++j)
*(*(tmp + i) + j) = *(*(array + i) + j);

for (i = 0; i < width; ++i)
for (j = 0; j < width; ++j)
*(*(array + j) + (width - 1 - i)) = *(*(tmp + i) + j);

free(tmp);
}
}

/*test*/
#include <stdio.h>

/*print the content of a matrix*/
void printa(void *matrix, const int width){
int (*array)[4] = matrix;
int i, j;
for (i = 0; i < width; ++i){
for (j = 0; j < width; ++j)
printf("%2d ", *(*(array + i) + j));
printf("\n");
}
}

#define WTH 4
int main(void){
int a[][WTH] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}};

printa(a, WTH);
printf("\n");

rotate(a, WTH);
printa(a, WTH);
printf("\n");

rotate(a, WTH);
printa(a, WTH);
printf("\n");

rotate(a, WTH);
printa(a, WTH);
printf("\n");

rotate(a, WTH);
printa(a, WTH);
printf("\n");

return 0;
}

$ cc -ansi -pedantic -Wall -W rotate.c
rotate.c: In function `rotate':
rotate.c:13: warning: suggest parentheses around assignment used as
truth value
$ ./a.out
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4

16 15 14 13
12 11 10 9
8 7 6 5
4 3 2 1

4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

$

Jul 26 '06 #1
8 10371

lovecreatesbeauty wrote:
I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.
It's OT but ...

"rotate by 90 degrees" is called a transposition. You don't need a
temp, hint: the new location for a value at x,y is the new destination
for a value at y,x.

Tom

Jul 26 '06 #2
Tom St Denis wrote:
lovecreatesbeauty wrote:
I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.

It's OT but ...

"rotate by 90 degrees" is called a transposition. ...
You mean Outright Tripe? They're not even in the same equivalence
class. ;-)

--
Peter

Jul 26 '06 #3
lovecreatesbeauty wrote:
I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency?

Can the copy be saved?
Not sure what that means.
Comments on it are welcome.

Can I extend it to work on a matrix of any size (or even any type, not
just integers) for the logic may be the same when it applies to a
matrix of different size?
Yes.
#include <stddef.h>
You don't need this as size_t is supplied by both of the following
headers.
#include <stdlib.h>
#include <string.h>

/*Rotate a 4*4 matrix of integers by 90 degrees clockwise.*/

void rotate(void *matrix, const int width){
int (*array)[4] = matrix;
int (*tmp)[4];
int i, j;
size_t n = width * width * sizeof **array;
size_t n = width * sizeof *array;
if(tmp = malloc(n)){
Given that the matrix is relatively small, just create a temp locally.
for (i = 0; i < width; ++i)
for (j = 0; j < width; ++j)
*(*(tmp + i) + j) = *(*(array + i) + j);
Much clearer is...

tmp[i][j] = array[i][j];

But you can replace that whole thing with...

memcpy(tmp, array, n);
>
for (i = 0; i < width; ++i)
for (j = 0; j < width; ++j)
*(*(array + j) + (width - 1 - i)) = *(*(tmp + i) + j);
array[j][width - 1 -i] = tmp[i][j];
free(tmp);
}
}
Just an alternative...

#include <stddef.h>

#define countof(x) ((size_t) (sizeof (x) / sizeof *(x)))

void rotate(int array[][4])
{
size_t i, mi;
size_t j, mj;
size_t width = countof(array[0]);

for (i = 0, mi = width; i < mi--; i++)
for (j = 0, mj = width; j < mj--; j++)
{
int tmp = array[ i][ j];
array[ i][ j] = array[mj][ i];
array[mj][ i] = array[mi][mj];
array[mi][mj] = array[ j][mi];
array[ j][mi] = tmp;
}
}

--
Peter

Jul 26 '06 #4
Tom St Denis wrote:
lovecreatesbeauty wrote:
>>I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.


It's OT but ...

"rotate by 90 degrees" is called a transposition. [...]
Well, I can't say "No, it's not" because the very fact
that you describe the maneuver as a transposition demonstrates
that the maneuver "is called" a transposition by at least one
person, to wit, you.

"Is *correctly* called" would be a different matter.

Myself, I call it "Haddocks' Eyes."

--
Eric Sosman
es*****@acm-dot-org.invalid

Jul 26 '06 #5

Peter Nilsson wrote:
Just an alternative...

#include <stddef.h>

#define countof(x) ((size_t) (sizeof (x) / sizeof *(x)))

void rotate(int array[][4])
{
size_t i, mi;
size_t j, mj;
size_t width = countof(array[0]);

for (i = 0, mi = width; i < mi--; i++)
for (j = 0, mj = width; j < mj--; j++)
{
int tmp = array[ i][ j];
array[ i][ j] = array[mj][ i];
array[mj][ i] = array[mi][mj];
array[mi][mj] = array[ j][mi];
array[ j][mi] = tmp;
}
}
Yes, it's better.

Jul 26 '06 #6
Peter Nilsson wrote:
lovecreatesbeauty wrote:
Can I extend it to work on a matrix of any size (or even any type, not
just integers) for the logic may be the same when it applies to a
matrix of different size?

Yes.
How can you do this? In your later example, the size info is tied to
the type declaration of the parameter of the function, though that size
of the array is not seen inside the function.
void rotate(int array[][4])
This function accepts a 4*4 array of integers. Can it accept a 3*3
array or a 40*40 array? Can it be changed to accept an array of any
size.

Jul 26 '06 #7
"Tom St Denis" <to********@gmail.comwrites:
lovecreatesbeauty wrote:
I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.

It's OT but ...

"rotate by 90 degrees" is called a transposition. You don't need a
temp, hint: the new location for a value at x,y is the new destination
for a value at y,x.
[Still more OT, but]

Err.. no. Consider

1 2 3 4

0 1 2 3

0 0 1 2

0 0 0 1

Rotating by 90 degrees clockwise:

0 0 0 1

0 0 1 2

0 1 2 3

1 2 3 4

Transposition (a_{x,y} <- a_{y,x}):

1 0 0 0

2 1 0 0

3 2 1 0

4 3 2 1

Rotating by 90 degrees clockwise is the same as
transposition plus inversion of row numbering, i.e.,

a_{x,y} <- a_{n-y, x},

where n is the size of the matrix.

The cost is ~n^2, same as writing the matrix in the first
place. Hence, unless your matrices are really large,
I won't bother much about optimising. If you have large
matrices and fewer than ~n^2 calls for matrix elements, you
might be better off without performing the rotation at all,
but instead using a trivial function get_rotated(a, x, y),
returning a_{n-y,x}.

Best,
Jakob
Jul 26 '06 #8
lovecreatesbeauty wrote:
I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.

Can I extend it to work on a matrix of any size (or even any type, not
just integers) for the logic may be the same when it applies to a
matrix of different size?
you can do this with only one temp variable...dividing the array into a
set of 4 quadrents.
to rotate some x,y...y,-x...-x,-y...-y,x you would just use 3 swaps

//three constant time operations
swap(x,y,y,-x)
swap(-x,-y,x,y)
swap(-y,x,x,y)

Repeat this process for each element in one quadrent (loop n/4 times)

thus this operates in linear time and linear space:-)

Jul 26 '06 #9

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

2 posts views Thread by JustSomeGuy | last post: by
21 posts views Thread by Nik Coughlin | last post: by
2 posts views Thread by Peter Proost | last post: by
1 post views Thread by iwdu15 | last post: by
3 posts views Thread by Diego F. | last post: by
13 posts views Thread by =?Utf-8?B?dmlubw==?= | last post: by
reply views Thread by NPC403 | last post: by
1 post views Thread by fmendoza | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.