Rotate Array

cable_guy_67 · #1 09-Jun-2007, 08:02

I was working on some code to rotate simple image arrays in FLTK and ended up doing a lot of questing through math sites looking for a reasonable way to do it. Can anyone direct me (or explain) a better way to do this? Unfortunately trig was never one of my best subjects. Also, could someone explain in simple terms what a transformation matrix is. I can't seem to wrap my brain around it. I've read and read and while they seemed to be what I was looking for I really just couldn't make any sense of the math.

BACKGROUND:
FLTK uses a static char array for it's internal representation of images. What it boils down to is a 3 or 4 char per bit array that is very similar to a xbm or xpm image representation. Since I intend on using common base images that will sometimes be rotated (for a battleship type game) I wanted to avoid having each rotation be a seperate image. By only declaring a new image buffer if I need one, I can have the base image as the only part stored in the exe.

Here is the code, which as FLTK does, is more C than C++. If the comments are confusing just ask for clarification.

CPP / C++ / C Code:

#include <iostream>
#include <iomanip>
using std::cout;
using std::endl;
using std::setw;

struct pixel
{
  unsigned int p_red;
  unsigned int p_green;
  unsigned int p_blue;
};

enum ROTATE { ROTCW, ROT180, ROTCCW };

void rotate_array( unsigned char* i_data,
                   unsigned int c_per_px, ROTATE rot_dir,
                   unsigned int o_width, unsigned int o_height )
{
  // working arrays with pixel RGB components
  pixel* o_array = new pixel[o_width * o_height];
  pixel* n_array = new pixel[o_width * o_height];

  // new array width and height
  unsigned int n_width, n_height;

  // coordinates of the images
  int o_pixel_x, o_pixel_y;
  int n_pixel_x, n_pixel_y;
  
  // set up the new array dimensions based on ROTATION type
  switch ( rot_dir )
  {
    case ROTCW:
    case ROTCCW:
      n_width = o_height;
      n_height = o_width;
      break;
    case ROT180:
    default:
      n_width = o_width;
      n_height = o_height;
      break;
  }

  // load o_array with pixel info
  for ( unsigned int idx = 0, data_idx = 0;
                     data_idx < ( o_width * o_height * c_per_px );
                     idx++, data_idx += c_per_px )
  {
    o_array[idx].p_red =   i_data[data_idx];
    o_array[idx].p_green = i_data[data_idx+1];
    o_array[idx].p_blue =  i_data[data_idx+2];
  }

  // walk o_array, rotate and place in n_array
  for( unsigned int idx = 0; idx < (o_width * o_height); idx++)
  {
    // convert the original image data index to x,y coords
    o_pixel_x = idx % o_width;
    o_pixel_y = -(idx / o_width);

    // transform x,y to new location and place in n_array
    // based on new x = (cos(angle)*x)-(sin(angle)*y)
    //          new y = (sin(angle)*x)+(cos(angle)*y)
    // ROTCCW = 90, ROT180 = 180, ROTCW = -90
    // simplified ROTCCW newx = -y       newy =  x-(h-1)
    //            ROT180 newx = -x+(w-1) newy = -y-(h-1)
    //            ROTCW  newx =  y+(w-1) newy = -x
    switch ( rot_dir )
    {
      case ROTCCW:
        n_pixel_x = -o_pixel_y;
        n_pixel_y = o_pixel_x - ( n_height - 1 );
        break;
      case ROT180:
        n_pixel_x = -o_pixel_x + ( n_width - 1 );
        n_pixel_y = -o_pixel_y - ( n_height - 1 );
        break;
      case ROTCW:
        n_pixel_x = o_pixel_y + ( n_width - 1 );
        n_pixel_y = -o_pixel_x;
        break;
      default:
        cout << "some bad juju" << endl;
        break;
    }
    // put pixel in n_array
    n_array[n_pixel_x + (-(n_pixel_y) * n_width)] = o_array[idx];
  }

  // put pixel info back in i_data
  for ( unsigned int idx = 0, data_idx = 0;
                     data_idx < ( n_width * n_height * c_per_px );
                     idx++, data_idx += c_per_px )
  {
    i_data[data_idx]   = n_array[idx].p_red;
    i_data[data_idx+1] = n_array[idx].p_green;
    i_data[data_idx+2] = n_array[idx].p_blue;
  }

  delete[] o_array;
  delete[] n_array;
  o_array = NULL;
  n_array = NULL;

  return;
}

void display_array( unsigned char* i_data, int c_per_px,
                    int o_width, int o_height,
                    const char* message = "Array Contents" )
{
  // working arrays with pixel RGB components
  pixel* o_array = new pixel[o_width * o_height];

  // this just displays the array as INDEX  X,Y  <RED, GREEN, BLUE>
  cout << endl << message << "   " << o_width << " x " << o_height << endl << endl;

  // load o_array with pixel info
  for ( int idx = 0, data_idx = 0;
        data_idx < o_width * o_height * c_per_px; 
        idx++, data_idx += c_per_px )
  {
    o_array[idx].p_red   = i_data[data_idx];
    o_array[idx].p_green = i_data[data_idx+1];
    o_array[idx].p_blue  = i_data[data_idx+2];

    cout << "[" << setw(4) << idx << "]" << setw(6) << idx % o_width << "," 
         << setw(4) << -(idx / o_width) << setw(5) << "<"
         << setw(3) << o_array[idx].p_red << "," << setw(3) << o_array[idx].p_green
         << "," << setw(3) << o_array[idx].p_blue << ">" << endl;
  }
  cout << endl;
  delete[] o_array;
  o_array = NULL;

  return;
}

int main()
{
// 3cpp RGB 12 pixels
static unsigned char image_data_array[] =
  {0, 0, 0, 255, 255, 255, 0, 0, 0, 
   0, 0, 0, 0, 0, 0, 0, 0, 0,
   0, 0, 0, 0, 0, 0, 0, 0, 0, 
   0, 0, 0, 100, 100, 100, 0, 0, 0};

  display_array( image_data_array, 3, 3, 4, "Original Array" );
  rotate_array( image_data_array, 3, ROTCW, 3, 4);
  display_array( image_data_array, 3, 4, 3, "Rotated Array" );

  return 0;
}

Compiled on XP with CygWin using:

Code:

g++ -Wall -pedantic rotate_test.cpp -g -o Rotate

It seems to be working as I would like. When I refer to the image the top left is set at (0,0) and after the rotation it is "slid" back to that location.

Any pointers about a better method would be appreciated. Any explanations about math would be greatly appreciated.

Mark

davekw7x · #2 10-Jun-2007, 22:49

Quote:

Originally Posted by cable_guy_67

It seems to be working as I would like...
Any pointers about a better method...

I have been trying to figure out how to express myself without contradicting my usual inclination to encourage people to look at things from a mathematical point of view. For this program, I would simply start with the desired result and "think my way back" to whatever steps would give that effect.

In fact the equations that define rotation of objects (or, equivalently, rotation of coordinate systems) are the basis of "why it works", but the expressions themselves have to take into account that the equations were based on x increasing to the right and y increasing in the upward direction, whereas I think you are using y increasing in the down direction. That is to say that the coordinate (0,0) is the upper left hand corner of your matrix, corresponding to row 0 and column 0. Also, of course, you are simply listing the pixel values at each point on a display, rather than actually moving something from one place to another on a 2-dimensional linear scale (in centimeters or whatever). At least I think that's what you mean when you say that you slide it back to the (0,0) reference point.

In fact, as your program shows, since we are rotating in multiples of 90 degrees (pi/2 radians), the sin and cosine factors are always zero, plus one, or minus one, so it's not necessary actually to call on the mathematical functions to do any of the calculations.

Also, since the matrices aren't necessarily square, rotations of odd multiples of 90 degrees, which result in exchanging rows with columns, give an output matrix that is a different dimension than the original. Of course the total number of elements is always the same, and you are representing the pixel values in a 1-Dimensional array.

I (probably) would have just looked at the results of some rotations in matrix form and induced program steps required to do the deed. See footnote.

For example, if I changed your display function to show rows and columns of the various results, and if I loaded the original matrix with values that make it easy to see where things go, I might expect something like the following output for a test case. I perform the sequence Rotate 90 degrees lockwise, Rotate 90 degrees counter-clockwise, Rotate 180 degrees

Code:


Original Array   3 x 4

( 1, 1, 1)  ( 2, 2, 2)  ( 3, 3, 3)  
( 4, 4, 4)  ( 5, 5, 5)  ( 6, 6, 6)  
( 7, 7, 7)  ( 8, 8, 8)  ( 9, 9, 9)  
(10,10,10)  (11,11,11)  (12,12,12)  


After ROTCW      4 x 3

(10,10,10)  ( 7, 7, 7)  ( 4, 4, 4)  ( 1, 1, 1)  
(11,11,11)  ( 8, 8, 8)  ( 5, 5, 5)  ( 2, 2, 2)  
(12,12,12)  ( 9, 9, 9)  ( 6, 6, 6)  ( 3, 3, 3)  


After ROTCCW     3 x 4

( 1, 1, 1)  ( 2, 2, 2)  ( 3, 3, 3)  
( 4, 4, 4)  ( 5, 5, 5)  ( 6, 6, 6)  
( 7, 7, 7)  ( 8, 8, 8)  ( 9, 9, 9)  
(10,10,10)  (11,11,11)  (12,12,12)  


After ROT180     3 x 4

(12,12,12)  (11,11,11)  (10,10,10)  
( 9, 9, 9)  ( 8, 8, 8)  ( 7, 7, 7)  
( 6, 6, 6)  ( 5, 5, 5)  ( 4, 4, 4)  
( 3, 3, 3)  ( 2, 2, 2)  ( 1, 1, 1)

So, the cases for new_x and new_y in terms of old_x and old_y are seen (by inspection) to be something like:

CPP / C++ / C Code:

    for (unsigned int idx = 0; idx < (o_width * o_height); idx++) {
        old_x = idx % o_width;
        old_y = idx / o_width;

        switch (rot_dir) {

        case ROTCCW:
            new_x = old_y;
            new_y = (o_width - 1) - old_x;
            break;

        case ROTCW:
            new_x = (o_height - 1) - old_y;
            new_y = old_x;
            break;

        case ROT180:
            new_x = (o_width - 1) - old_x;
            new_y = (o_height - 1) - old_y;
            break;

        default:
            cout << "some bad juju" << endl;
            break;

        }

This gives the same results as your equations, but I just worked directly with the array index values instead of trying to figure out whether to use y or minus y or whatever.

Furthermore, it seems to me to be unnecessarily cluttersome to convert triplets of chars back and forth to rgb pixel values, so why not just work on arrays of pixels?

This also makes it a little cleaner, in that you don't have quite so many arrays to allocate in the functions.

So, I have no real quarrel with your organization or implementation, but you did ask for suggestions.

CPP / C++ / C Code:

#include <iostream>
#include <iomanip>

using namespace std;

struct pixel {
    unsigned int p_red;
    unsigned int p_green;
    unsigned int p_blue;
};

enum ROTATE { ROTCW, ROT180, ROTCCW };

void rotate_array(pixel * i_data, ROTATE rot_dir,
                  unsigned int o_width, unsigned int o_height)
{
    // new 2-D array width and height
    unsigned int n_width, n_height;
    int old_x, old_y, new_x, new_y;

    // working 1-D array of pixels
    pixel *n_array = new pixel[o_width * o_height];


    // set up the new array dimensions based on ROTATION type
    switch (rot_dir) {

    case ROTCW:
    case ROTCCW:
        n_width = o_height;
        n_height = o_width;
        break;

    case ROT180:
    default:
        n_width = o_width;
        n_height = o_height;
        break;

    }

    for (unsigned int idx = 0; idx < (o_width * o_height); idx++) {
        old_x = idx % o_width;
        old_y = idx / o_width;

        switch (rot_dir) {

        case ROTCCW:
            new_x = old_y;
            new_y = (o_width - 1) - old_x;
            break;

        case ROTCW:
            new_x = (o_height - 1) - old_y;
            new_y = old_x;
            break;

        case ROT180:
            new_x = (o_width - 1) - old_x;
            new_y = (o_height - 1) - old_y;
            break;

        default:
            cout << "some bad juju" << endl;
            break;

        }
        // put pixel into n_array
        n_array[new_x + new_y * n_width] = i_data[idx];
    }

    // put pixels back into original array for return
    for (unsigned int idx = 0; idx < n_width * n_height; idx++) {
        i_data[idx] = n_array[idx];
    }

    delete[]n_array;

    return;
}

void display_array(pixel * i_data,
                   int o_width, int o_height,
                   const char *message = "Array Contents")
{
    cout << endl << message << "   " << o_width << " x " << o_height <<
        endl << endl;

    for (int idx = 0; idx < o_width * o_height; idx++) {
        cout << "("
            << setw(2) << i_data[idx].p_red << ","
            << setw(2) << i_data[idx].p_green << ","
            << setw(2) << i_data[idx].p_blue << ")  ";

        if ((idx % o_width) == (o_width - 1)) {
            cout << endl;
        }
    }
    cout << endl;

    return;
}

int main()
{
// 3cpp RGB 12 pixels
    static pixel image_data_array[] = {
        {1, 1, 1}, {2, 2, 2}, {3, 3, 3},
        {4, 4, 4}, {5, 5, 5}, {6, 6, 6},
        {7, 7, 7}, {8, 8, 8}, {9, 9, 9},
        {10, 10, 10}, {11, 11, 11}, {12, 12, 12}
    };

    display_array(image_data_array, 3, 4, "Original Array");

    rotate_array(image_data_array, ROTCW, 3, 4);
    display_array(image_data_array, 4, 3, "After ROTCW   ");

    rotate_array(image_data_array, ROTCCW, 4, 3);
    display_array(image_data_array, 3, 4, "After ROTCCW  ");

    rotate_array(image_data_array, ROT180, 3, 4);
    display_array(image_data_array, 3, 4, "After ROT180  ");

    return 0;
}

Output was listed previously.

You might try to find places to optimize some more if it seem appropriate, but my experience is that I usually optimize the wrong thing, or I go to a lot of trouble trying to "help" the compiler and then the compiler completely blows my stuff away and does something more clever than I would have imagined.

Bottom line: it's not a "better way" of doing it, it's just a slightly different way of looking at it. The method is exactly the same as yours.

Regards,

Dave

Footnote

Richard Feynman's Problem Solving Methodology:

1. Write down the problem.
2. Think real hard.
3. Write down the solution.

---Murray Gell-Mann
Quoted in a New York Times interview

cable_guy_67 · #3 11-Jun-2007, 06:21

First off, thanks very much Dave. There are a few nuggets in your explanation that really helps me to get a grip (with my en.wikipedia.org) on minor points I was struggling with. Perhaps I will be able to implement some, perhaps not. But at the very least I will be able to learn from them. I really do appreciate another's point of view. Your example program made me scratch my head and wonder, why did I make things so complex?

When I started poking around with this a few weeks ago I, in typical fashion, took a simple little problem and let it lead me by the nose down some long and winding roads. For me, that is the joy of programming. I approach it kind of like a short story that has the last few pages written (the desired result) but a bunch of blank pages on how to get there. Filling the blank pages, even if it requires stapling extra ones in is the joy of it.

Quote:

Originally Posted by davekw7x

Furthermore, it seems to me to be unnecessarily cluttersome to" convert triplets of chars back and forth to rgb pixel values, so why not just work n arrays of pixels?

Good question. When I started I wasn't using the FLTK arrays at all, but was looking at using PBM, PGM and PPM's (see note at end) directly. Sometimes they are triplets and sometimes, they are not. Then I found there are times when the pixels could possibly have a fourth value for the Alpha channel. My thinking was, if I had a simple type that concerned itself with storing the pixel components I wouldn't have to bother with that during the transformation stage. There are only minor changes needed to declare the correct type (single, triplet or quads?) that the 1D array represents.

There is also the fact that I will be working with x and y coordinates since anything will be picked from an FLTK canvas widget. That's my story and I'm sticking with it.

Quote:

Originally Posted by davekw7x

In fact, as your program shows, since we are rotating in multiples of 90 degrees (pi/2 radians), the sin and cosine factors are always zero, plus one, or minus one, so it's not necessary actually to call on the mathematical functions to do any of the calculations.

When I started I didn't actually know this. Or if I did I forgot. When I started I was doing the math using sin() and cos() based on the equations. Once I started to do the math with pencil and paper (and calculator) I found that out. From that point I discovered that the x and y had the simple relationship (at 90 degree increments) shown in the programs comments. But not calling the math and not understanding why not to call the math are two very different things. It was in fact only due to trial and error that I found the simplified method currently being used.

Quote:

Originally Posted by davekw7x

Bottom line: it's not a "better way" of doing it, it's just a slightly different way of looking at it. The method is exactly the same as yours.

As usual, I misspoke. Better was not the word I wanted, just different. You have pointed out a few things I may not (or may, have stranger things have happened) have come up with on my own. But open discourse is why I like GIDForums™ so much. I don't have anyone physically close at hand to bounce these things off of. Instead, in true Gemini fashion, bounce it off anyone on the planet that takes the time to read...

NOTES:
There is an error in the first post.

Quote:

What it boils down to is a 3 or 4 char per bit array that is very similar to a xbm or xpm image representation.

bit should have been pixel
xbm or xpm should have been pbm or ppm

I used the information on www.fileformat.info for those formats.

Mark

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
How to sort in C++ alphabetically	wilen	C++ Forum	5	20-Apr-2007 14:43
1-D array	jack999	C Programming Language	16	16-May-2006 12:38
Need help deleting the last element in the array	headphone69	C++ Forum	2	15-Mar-2006 19:31
Pointer Usage in C++: Beginner to Advanced	varunhome	C++ Forum	0	19-Aug-2005 09:25
template comiling problems - need expert debugger!	crq	C++ Forum	1	01-Feb-2005 21:26

Rotate Array

Re: Rotate Array

Re: Rotate Array