-
rotating array
I wanted to created a rotation function for rotating unsigned int arrays. After browsing for some good sources, I came up with the following code :
Code:
void RotationFunction( unsigned int * array, int Width, int Height, int angle)
{ //calculations of the new Width and Height
long x1 = ( -Height * fp16sin[angle] );
long y1 = ( Height * fp16cos[angle] );
long x2 = ( Width * fp16cos[angle] ) - ( Height * fp16sin[angle] );
long y2 = ( Height * fp16cos[angle] ) + (Width * fp16sin[angle] );
long x3 = ( Width * fp16cos[angle] );
long y3 = ( Width * fp16sin[angle] );
long minx = min(0,min(x1,min(x2,x3 ) ) );
long miny = min(0,min(y1,min(y2,y3 ) ) );
long maxx = max(x1,max(x2,x3) );
long maxy = max(y1,max(y2,y3) );
//Created as a global variable just for this prototype test
NewWidth = ( maxx - minx )>>16;
NewHeight =( maxy - miny )>>16;
unsigned int * ptr = (unsigned int *) calloc(NewWidth * NewHeight, sizeof(unsigned int) );
if( ptr != NULL )
{
int srotx = Width >>15;
int sroty = Height >>15;
int dx = NewWidth >> 1;
int dy = NewHeight >> 1;
/*translate from the differenct between the roatation of the center of the new size with
with the center of the previous size in 16by16 fixed point */
srotx -= (int) (dx * fp16cos[angle] + dy * fp16sin[angle]);
sroty -= (int) (dx * fp16sin[angle] - dy * fp16cos[angle]);
int newx, newy, rotx, roty;
for(int y = 0; y < NewHeight; y++)
{ // Gets the rotated new coordinates
rotx = srotx = srotx - fp16sin[angle];
roty = sroty = sroty + fp16cos[angle];
for(int x = 0; x < NewWidth; x++)
{
//converts from fixed point
newx = rotx >> 16;
newy = roty >> 16;
//checks if rotated coordinates are out of boundary
if((newx >= 0 && newx < NewWidth) && (newy >= 0 && newy < NewHeight))
ptr[ (y*NewWidth)+ x ] = array[ (newy *Width) + newx];
else
{ptr[ (y*NewWidth)+ x ] = 0;} // feels up any gaps
rotx += fp16cos[angle];
roty += fp16sin[angle];
}
}
array = ptr;
}//end of if
}
The code does run without any error, but doesn't show any numbers for certain angles (not including the ones more then 256). Also, I believe the output is wrong, but i could be mistaken. Any suggestions or tips will be deeply appreciated... ^_^
-
I'd say one problem is the initialization of fp16cos and fp16sin in main. All elements are 0 (except for one), because the cast to int of tempt1 results in 0 unless tempt1 is 1.
Try this:
Code:
#define double2fp(x) ( (x) * 65526 )
for( i = 0; i < 256; i++)
{
double tempt1 = ( i * PIE * 2) / 360;
double x = cos( tempt1 );
double y = sin( tempt1 );
fp16sin[i] = long(double2fp(y));
fp16cos[i] = long(double2fp(x));
}
-
thanks.. i have changed also the increment statement to the following example
Code:
for( i = 0; i < NewHeight; ++i )
{
for( j = 0; j < NewWidth; j++)
cout<< array25[ (i*NewWidth) + j ];
cout<<endl;
}
What I did before was i + j, where it should of been (i*NewWidth) + j, but now I get this weird error... with random numbers...
-
array25[ (i*NewWidth) + j ];
Is going past the end of the array. That's why you're getting the random results.
What is your program supposed to do? Give me a sample of input and output.
-
well i was trying to create a function to rotation an image... in this case.. I'm putting the image data into a array of unsigned int. This program is just a test to see if it works using the straight line as an example.
It should out put for example
0,0,0,0,0,
0,0,1,0,0,
0,0,1,0,0,
0,0,1,0,0,
0,0,0,0,0
should transform into
0,0,0,0,0,
0,1,0,0,0,
0,0,1,0,0,
0,0,0,1,0,
0,0,0,0,0
after going through the function
-
Hello.
This is a tough problem and I don't know if I can solve it. I might devote some more time to it on the weekend, but do let me know if you have a breakthrough.
I see why you're getting the random results out. It's just a misunderstanding in how C works. In your RotationFunction you have array = ptr. That doesn't do what you expect. You need to return ptr from RotationFunction if you want to print it out in main. In production code, you would free ptr when you're done with it. For testing purposes, I found it handy to have a dump function and call it from the RotationFunction.
Code:
#define ELEM_AT(a,x,y,w) (a[y*w+x])
void dump(unsigned int* array, int width, int height)
{
for(int y = 0; y < height; ++y)
{
for(int x = 0; x < width; ++x)
{
int elem = ELEM_AT(array, x, y, width);
cout << elem;
}
cout << endl;
}
cout << endl;
}
I don't think your method to calculate NewWidth and NewHeight is correct.
Here are the results I got:
$ RotArray.exe
Angle: 45 OldDims 5x5 -> New Dims 7x7
Angle: 90 OldDims 5x5 -> New Dims 4x4
Angle: 180 OldDims 5x5 -> New Dims 4x4
Angle: 45 OldDims 6x6 -> New Dims 8x8
Angle: 90 OldDims 6x6 -> New Dims 5x5
Angle: 180 OldDims 6x6 -> New Dims 5x5
Angle: 45 OldDims 7x3 -> New Dims 7x7
Angle: 90 OldDims 7x3 -> New Dims 2x6
Angle: 180 OldDims 7x3 -> New Dims 6x2
I suppose square arrays should not change size when rotating in multiples of 90. Your's seem to be off by 1.
I used the following code to calculate the dimensions. It gave me more reasonable looking results.
Code:
// Find nearest integer
int nint(double x)
{
return int(x+0.5);
}
void calcNewDims(int Width, int Height, int angle)
{
double rads = ( angle * PIE * 2) / 360;
double sinAngle= sin(rads);
double cosAngle = cos(rads);
double dim;
double dimError;
dim = abs(sinAngle*Height) + abs(cosAngle*Width);
dimError = dim - nint(dim);
NewWidth = int(dimError > 0.0001 ? ceil(dim) : nint(dim));
dim = abs(sinAngle*Width) + abs(cosAngle*Height);
dimError = dim - nint(dim);
NewHeight = int(dimError > 0.0001 ? ceil(dim) : nint(dim));
}
I prefer to use the floating point calculations. Are you doing fixed point as an optimization?
That brings me to the actual rotation algorithm. The algorithm you have never executes
ptr[ (y*NewWidth)+ x ] = array[ (newy *Width) + newx];
and I don't pretend to understand it.
Some if it looks familiar. I understand
srotx -= (int) (dx * fp16cos[angle] + dy * fp16sin[angle]);
sroty -= (int) (dx * fp16sin[angle] - dy * fp16cos[angle]);
but I don't understand why dx and dy depend on NewHeight and NewWidth
I've been trying an approach with floating point calculations instead of fixed point but I haven't gotten very satisfactory results for angles other than multiples of 90.
For example,
0,0,0,0,0,0,0
1,2,3,4,5,6,7
0,0,0,0,0,0,0
rotated 45 degrees should give
1,0,0,0,0,0,0
0,2,0,0,0,0,0
0,0,3,0,0,0,0
0,0,0,4,0,0,0
0,0,0,0,5,0,0
0,0,0,0,0,6,0
0,0,0,0,0,0,7
Right?
I assume you want to preserve all the data.
The best I could do is
1000000
0230000
0004000
0000500
0000060
0000007
and to get that I had to add a fudge factor to account for diagonal adjacent cells being "farther apart" than vertical or horizontal adjacent cells. I think that is a fundamental problem.
If you're interested in my code, I can try to clean it up and post it. If you're going to continue with your fixed point algorithm, keep me posted on any breakthrough.
Best regards.
-
thank you for the ti[s and help.. i deeply appreciate.. sorry for the late reply since i have been sick... My calculations was in fixed point so as expected there would be some inaccuracies.. Also thank you for the dump function tip... I'll be sure to implement it as soon as possible and get back to you with any questions.. I'm also interested in your float code.. =) would help alot
oooh btw, for
Code:
ptr[ (y*NewWidth)+ x ] = array[ (newy *Width) + newx];
My intentions were to put the original source color (or this case value) into the new array using the calculated dimensions, but I guess i messed up there...
-
Ok, here is some code that does something. Maybe it does what you want.
Code:
#include <iostream>
#include <cstring>
#include <cmath>
#include <assert.h>
#define PIE 3.1415926535897
#define ALMOST_ZERO (1e-10)
using namespace::std;
#define ELEM_AT(a,x,y,w) (a[y*w+x])
// Find nearest integer
int nint(double x)
{
return int( x >= 0 ? x+0.5 : x-0.5);
}
int newWidth;
int newHeight;
// Find center index of array given the array dimension
int centerIndex(int dimension)
{
return nint(double(dimension-1)/2);
}
void dump(const unsigned int* array, int width, int height)
{
for(int y = 0; y < height; ++y)
{
for(int x = 0; x < width; ++x)
{
int elem = ELEM_AT(array, x, y, width);
cout << char(elem == 0 ? '*' : elem);
}
cout << endl;
}
cout << endl;
}
struct Location
{
Location(int X, int Y) { x = X; y = Y; }
int x;
int y;
};
ostream& operator<<(ostream& out, const Location& loc)
{
out << "(" <<
loc.x << ',' << loc.y
<< ")";
return out;
}
void rotate(const unsigned int* array, int height, int width, int angle)
{
double rads = ( angle * PIE * 2) / 360;
double sinAngle= sin(rads);
if (fabs(sinAngle) < ALMOST_ZERO) sinAngle = 0;
double cosAngle = cos(rads);
if (fabs(cosAngle) < ALMOST_ZERO) cosAngle = 0;
cout << "------------------------------------------\n";
cout << "Input:\n";
dump(array, width, height);
// Array will be rotated around this point
int centerX = centerIndex(width);
int centerY = centerIndex(height);
// These will be used to determine dimensions of the new rotated array
int lowestX = INT_MAX;
int lowestY = INT_MAX;
int highestX = INT_MIN;
int highestY = INT_MIN;
// Phase 1: Calculate new locations for each element of array
Location* newLocations = (Location*)calloc(width * height, sizeof(Location));
for(int y = 0; y < height; ++y)
{
for(int x = 0; x < width; ++x)
{
int dx = (x - centerX);
int dy = (y - centerY);
int elem = char(ELEM_AT(array, x, y, width));
if (elem != 0)
{
double newX;
double newY;
newX = centerX - dy*sinAngle + dx*cosAngle;
newY = centerY + dy*cosAngle + dx*sinAngle;
/* Account for the fact that cells that are not horizontally or vertically
adjacent are farther appart in distance
For example
AB
CD
A,B and A,C are one cell appart, but the distance A,D is 1 * square root 2
or 1 / sin of the angle
*/
if (sinAngle != 0)
{
newX /= fabs(sinAngle);
newY /= fabs(sinAngle);
}
Location loc(nint(newX), nint(newY));
if (loc.x < lowestX) lowestX = loc.x;
if (loc.y < lowestY) lowestY = loc.y;
ELEM_AT(newLocations, x, y, width) = loc;
}
}
}
cout << "New Locations:" << endl;
// Phase 2:
// Subtract lowestX and lowestY elements from each X,Y point in
// newLocation so that all locations are positive and can be used as indicies into the
// rotated array
// Determine highestX and highestY to assist in calculating newWidth and newHeight
for(int y = 0; y < height; ++y)
{
for(int x = 0; x < width; ++x)
{
cout << ELEM_AT(newLocations, x, y, width);
if (lowestX < 0) ELEM_AT(newLocations, x, y, width).x -= lowestX;
if (lowestY < 0) ELEM_AT(newLocations, x, y, width).y -= lowestY;
if (ELEM_AT(newLocations, x, y, width).x > highestX) highestX = ELEM_AT(newLocations, x, y, width).x;
if (ELEM_AT(newLocations, x, y, width).y > highestY) highestY = ELEM_AT(newLocations, x, y, width).y;
}
cout << endl;
}
cout << "Lowest X " << lowestX << endl;
cout << "Lowest Y " << lowestY << endl;
cout << "Highest X " << highestX << endl;
cout << "Highest Y " << highestY << endl;
// For the sake of appearance, do not make the new arrray dimensions smaller that the original
newWidth = max(highestX+1, width);
newHeight = max(highestY+1, height);
cout << "\nOutput: " << angle << " degrees: " << width << "x" << height << " -> " << newWidth << "x" << newHeight << endl;
// Phase 3: Create the new array and populate it
unsigned int* newArray = (unsigned int *) calloc(newWidth * newHeight, sizeof(*array));
for(int y = 0; y < height; ++y)
{
for(int x = 0; x < width; ++x)
{
int elem = char(ELEM_AT(array, x, y, width));
if (elem != 0)
{
int newX = ELEM_AT(newLocations, x, y, width).x;
int newY = ELEM_AT(newLocations, x, y, width).y;
assert(newX >= 0);
assert(newX < newWidth);
assert(newY >= 0);
assert(newY < newHeight);
ELEM_AT(newArray, newX, newY, newWidth) = elem;
}
}
}
dump(newArray, newWidth, newHeight);
// Free the work area
free(newLocations);
// Free the newArray if it is not being returned
free(newArray);
return;
}
int main(void)
{
unsigned int degenerateCase[1][1] =
{
{'X'}
};
unsigned int smallH[1][2] =
{
{'X', 'Y'}
};
unsigned int smallV[2][1] =
{
{'X'},
{'Y'}
};
unsigned int smallSq[2][2] =
{
{'a', 'b'},
{'1', '2'}
};
unsigned int rectangularH[3][7] =
{
{'a', 'b', 'c', 'd', 'e', 'f' ,'g'},
{'1', '2', '3', '4', '5', '6', '7'},
{'H', 'I', 'J', 'K', 'L', 'M', 'N'}
};
unsigned int rectangularV[7][3] =
{
{'a', '1', 'A'},
{'b', '2', 'B'},
{'c', '3', 'C'},
{'d', '4', 'D'},
{'e', '5', 'E'},
{'f', '6', 'F'},
{'g', '7', 'G'}
};
unsigned int squareEven[6][6] =
{
{0,0,'a','1',0,0},
{0,0,'b','2',0,0},
{0,0,'c','3',0,0},
{0,0,'d','4',0,0},
{0,0,'e','5',0,0},
{0,0,'f','6',0,0}
};
//rotate((unsigned int*)°enerateCase[0][0], 1, 1, 0);
//rotate((unsigned int*)°enerateCase[0][0], 1, 1, 45);
//rotate((unsigned int*)°enerateCase[0][0], 1, 1, 90);
//rotate((unsigned int*)°enerateCase[0][0], 1, 1, 180);
//rotate((unsigned int*)&smallH[0][0], 1, 2, 0);
//rotate((unsigned int*)&smallH[0][0], 1, 2, 45);
//rotate((unsigned int*)&smallH[0][0], 1, 2, 90);
//rotate((unsigned int*)&smallH[0][0], 1, 2, 180);
//rotate((unsigned int*)&smallV[0][0], 2, 1, 0);
//rotate((unsigned int*)&smallV[0][0], 2, 1, 45);
//rotate((unsigned int*)&smallV[0][0], 2, 1, 90);
//rotate((unsigned int*)&smallV[0][0], 2, 1, 180);
//rotate((unsigned int*)&smallSq[0][0], 2, 2, 0);
//rotate((unsigned int*)&smallSq[0][0], 2, 2, 45);
//rotate((unsigned int*)&smallSq[0][0], 2, 2, 90);
//rotate((unsigned int*)&smallSq[0][0], 2, 2, 180);
//rotate((unsigned int*)&rectangularH[0][0], 3, 7, 0);
rotate((unsigned int*)&rectangularH[0][0], 3, 7, 45);
//rotate((unsigned int*)&rectangularH[0][0], 3, 7, 90);
//rotate((unsigned int*)&rectangularH[0][0], 3, 7, 180);
//rotate((unsigned int*)&rectangularV[0][0], 7, 3, 0);
rotate((unsigned int*)&rectangularV[0][0], 7, 3, 45);
//rotate((unsigned int*)&rectangularV[0][0], 7, 3, 90);
//rotate((unsigned int*)&rectangularV[0][0], 7, 3, 180);
//rotate((unsigned int*)&squareEven[0][0], 6, 6, 0);
//rotate((unsigned int*)&squareEven[0][0], 6, 6, 45);
//rotate((unsigned int*)&squareEven[0][0], 6, 6, 90);
//rotate((unsigned int*)&squareEven[0][0], 6, 6, 180);
//rotate((unsigned int*)&squareEven[0][0], 6, 6, 0);
//rotate((unsigned int*)&squareEven[0][0], 6, 6, 45);
//rotate((unsigned int*)&squareEven[0][0], 6, 6, 90);
//rotate((unsigned int*)&squareEven[0][0], 6, 6, 180);
//for(int angle = 0; angle < 90; angle += 5) rotate((unsigned int*)&rectangular[0][0], 3, 7, angle);
return 0;
}
When the array is rotated, the resulting array often has empty rows or columns. Part of that is intentional, but sometimes there is more than necessary. I'll leave it up to you to trim the result if you like.
Best regards.
Zlatko
