473,573 Members | 2,412 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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 11013

lovecreatesbeau ty 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:
lovecreatesbeau ty 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
lovecreatesbeau ty 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:
lovecreatesbeau ty 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:
lovecreatesbeau ty 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********@gma il.comwrites:
lovecreatesbeau ty 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
lovecreatesbeau ty 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...divi ding 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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
2290
by: JustSomeGuy | last post by:
mx = Cols/2; if ((mx * 2) != Cols) // Odd. ++mx; } for (y1=0; y1 < Rows; ++y1) { y2 = Rows-1 - y1; for (x1=0; x1 < mx; ++x1)
21
8473
by: Nik Coughlin | last post by:
Are there methods for manipulating images in JavaScript that would allow me to write functions to rotate, skew, mask and resize images (bitmaps)? The functions need to be fast enough for use in a top-down scrolling game. Or would I be better off preprocessing all of the images with something server side such as PHP and then preloading them...
2
2678
by: Peter Proost | last post by:
Hi group, I got the following piece of code which draws a square with stars round it, now I want the stars to rotate round the square, I can do this with the mx.rotate and a timer and an angle, but this rotates the whole drawing of the stars but what I realy want is for the stars to rotate round it's center point, is this possible? I hope...
1
3064
by: iwdu15 | last post by:
hi, im trying to rotate a gdi drawn object on my form with a keypress....forinstance when i push the down arrow, for it to rotate the object drawn until the top is down, or if i push the right arrow key, to rotate the object until its pointed to the right. i tried using a drawing matrix to accomplish this, but all it did was rotate my entire...
3
6707
by: Eduard Witteveen | last post by:
Hello list, I have code the draw MyDrawingObject information on a System.Drawing.Graphics object. The code is more/less the following: I now want to rotate / mirror the object i draw. I've looked at the System.Drawing.Drawing2D.Matrix, which can be applied on the Transform property of the Graphics object, but it will work on the...
3
5105
by: Diego F. | last post by:
Hi all. I have a listview with images and my application must be able to rotate one image. I need a method to rotate 90 degrees rigth (i.e.). Is that possible? -- Regards, Diego F.
5
6941
by: Gina_Marano | last post by:
Hey All, Is it possible to draw an image upside down? I am using Microsofts example of "Printing a local report without preview". The only trick is that I want to flip the image upside down. Reason: I need to guarantee that I print a barcode in the exact same
13
5352
by: =?Utf-8?B?dmlubw==?= | last post by:
Hello, I have created my proper control and i would to rotate it. In the paint event of my object, i have written : Dim graph As Graphics = myObject.CreateGraphics myMatrix = New System.Drawing.Drawing2D.Matrix myMatrix.Rotate(45, System.Drawing.Drawing2D.MatrixOrder.Append) graph.Transform = myMatrix but it don't work.
8
1930
by: Syoam4ka | last post by:
Hi, I have a WinApp in which I have a pictureBox. I can draw in it like in the paint of windows - I accomplish that with an arrayList of Points and DrawLines method of the Graphics. So it really paints like in the Paint of windows. When I let the mouse left button up it stops drawing of course. Now I want to rotate that paint (which is...
0
7789
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
7707
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
8037
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
1
7800
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
1
5605
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
5296
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3737
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
0
3743
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
1325
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.