rotating array

This is a discussion on rotating array within the C++ Programming forums, part of the General Programming Boards category; I wanted to created a rotation function for rotating unsigned int arrays. After browsing for some good sources, I came ...

  1. #1
    Registered User
    Join Date
    Oct 2006
    Location
    New York
    Posts
    121

    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... ^_^
    Attached Files Attached Files

  2. #2
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    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));
    	}

  3. #3
    Registered User
    Join Date
    Oct 2006
    Location
    New York
    Posts
    121
    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...
    Attached Files Attached Files

  4. #4
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    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.

  5. #5
    Registered User
    Join Date
    Oct 2006
    Location
    New York
    Posts
    121
    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

  6. #6
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    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.

  7. #7
    Registered User
    Join Date
    Oct 2006
    Location
    New York
    Posts
    121
    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...
    Last edited by Darkinyuasha1; 08-13-2009 at 02:18 AM.

  8. #8
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    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*)&degenerateCase[0][0], 1, 1, 0);
        //rotate((unsigned int*)&degenerateCase[0][0], 1, 1, 45);
        //rotate((unsigned int*)&degenerateCase[0][0], 1, 1, 90);
        //rotate((unsigned int*)&degenerateCase[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
    Last edited by Zlatko; 08-15-2009 at 09:23 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  2. from 2D array to 1D array
    By cfdprogrammer in forum C Programming
    Replies: 17
    Last Post: 03-24-2009, 10:33 AM
  3. [question]Analyzing data in a two-dimensional array
    By burbose in forum C Programming
    Replies: 2
    Last Post: 06-13-2005, 07:31 AM
  4. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM
  5. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21