Go Down

### Topic: Algorithm to rotate data (Read 3498 times)previous topic - next topic

#### Krupski

##### Jan 09, 2013, 03:36 pm
Hi all,

I am trying to rotate font data by 90 degrees and I'm hitting a brick wall... it should be simple but I'm just not getting it.

Here's what I want to do (scaled to 4 bits by 4 bits for clarity):

original
[font=monospace]
A B C D
E F G H
I J K L
M N O P
[/font]

after rotation
[font=monospace]
M I E A
N J F B
O K G C
P L H D
[/font]

Of course, I want to do it with an 8 x 8 font pattern, but above shows the idea.

Any help will be appreciated. Thanks!

-- Roger
Gentlemen may prefer Blondes, but Real Men prefer Redheads!

#### Tom Carpenter

#1
##### Jan 09, 2013, 04:03 pmLast Edit: Jan 09, 2013, 04:13 pm by Tom Carpenter Reason: 1
One approach would be the following:

1) Map each ring into a line starting at the top left and working clockwise. So:
A B C D
E F G H
I J K L
M N O P
Becomes:
outer ring: ABCDHLPONMIE. Ring size = 4
inner ring: FGKJ. Ring size = 2

2) move the last 'ring size - 1' characters to the beginning of a new array
ABCDHLPON  MIE //extract the last 3 as ring size = 4
-> MIE //new array

FGK  J //extract the last 1 as ring size = 2
-> J //new array

3) concatenate the rest:
MIE  ABCDHLPON
J   FGK

4) shift each line back into a ring (inverse of step 1)
M I E A
N J F B
O K G C
P L H D

As for realising it in code, the difficult bit is going to be extracting each ring. But it is doable. If you design a function to extract a ring of a specified size, then you could call that same function for each of the rings in turn, and it could be scaled up to 8x8 easily that way. It would be also sensible to have the function be able to do the inverse to put the lines back into the ring which would be the same code as extracting them only moving flipping destination and source.
I'll write a few lines of code as a possible hint.
~Tom~

#### guix

#2
##### Jan 09, 2013, 04:30 pmLast Edit: Jan 09, 2013, 04:40 pm by guix Reason: 1
Something like this should work:
Code: [Select]
`for (uint8_t i = 0; i < 4; i++)  for (uint8_t j = 0; j < 4; j++)    array_rotated[i][j] = array[3-j][i];`

Or, for a single dimension array:
Code: [Select]
`for (uint8_t i = 0; i < 4; i++)  for (uint8_t j = 0; j < 4; j++)    array_rotated[(i*4)+j] = array[((3-j)*4)+i];`

#### johncc

#3
##### Jan 09, 2013, 04:37 pm
Here's an approach I might take:

Code: [Select]
`char d[4][4]= { {'A','B','C','D'}, {'E','F','G','H'}, {'I','J','K','L'}, {'M','N','O','P'}};typedef char (*accessfn)(int x, int y);char normal( int x, int y){ return d[x][y]; }char rotated( int x, int y){ return d[3-y][x]; }   // <<<<<< This is the main thingvoid printMatrix( accessfn afn ){ for (int x=0;x<4;x++) Serial << afn(x,0) << " " << afn(x,1) << " " << afn(x,2) << " " << afn(x,3) << " " << endl; Serial << endl;}void setup(){ Serial << "Hello World!!!" << endl; printMatrix(normal); printMatrix(rotated); Serial << "Or..." << endl; accessfn rotationmode; rotationmode = normal; printMatrix(rotationmode); rotationmode = rotated; printMatrix(rotationmode);}`

#### Tom Carpenter

#4
##### Jan 09, 2013, 05:45 pmLast Edit: Jan 09, 2013, 05:47 pm by Tom Carpenter Reason: 1
After a little bit of playing around with how coordinates map, it is really rather simple:
Code: [Select]
`void setup() {  // put your setup code here, to run once:  const char maxSize = 4; //must be a multiple of 2, e.g. 2,4,6,8  char array[maxSize][maxSize] = {{'A','B','C','D'},{'E','F','G','H'},{'I','J','K','L'},{'M','N','O','P'}};  char rotatedArray[maxSize][maxSize];  /*  //rotate 90* anti-clockwise  for (char i = 0; i < maxSize; i++){    for (char j = 0; j < maxSize; j++){      char newI = maxSize-1-j;      char newJ = i;      rotatedArray[newI][newJ] = array[i][j];    }  }  */  //rotate 90* clockwise  for (char i = 0; i < maxSize; i++){    for (char j = 0; j < maxSize; j++){      char newI = j;      char newJ = maxSize-1-i;      rotatedArray[newI][newJ] = array[i][j];    }  }    //It should now be reversed.  Serial.begin(115200);  Serial.println("In");  for (char i = 0; i < maxSize; i++){    for (char j = 0; j < maxSize; j++){      Serial.print(array[i][j]);      Serial.print(' ');    }    Serial.println();  }  Serial.println();  Serial.println("Out");  for (char i = 0; i < maxSize; i++){    for (char j = 0; j < maxSize; j++){      Serial.print(rotatedArray[i][j]);      Serial.print(' ');    }    Serial.println();  }}void loop() {  // put your main code here, to run repeatedly:  }`
Result:
Code: [Select]
`InA B C D E F G H I J K L M N O P OutM I E A N J F B O K G C P L H D `
~Tom~

#### el_supremo

#5
##### Jan 09, 2013, 06:29 pm
This rotates the bits of an 8x8 font:
Code: [Select]
`unsigned char font[8] = {  0B10101010,  0B11001100,  0B11100111,  0B00111100,  0B01001001,  0B10110111,  0B11000101,  0B01011101};unsigned char font_r[8];// print an 8x8 bit fontvoid print_font_bits(unsigned char *font){  unsigned char c;  for(int i=0;i<8;i++) {    c = *font++;    for(int j=0;j<8;j++) {      if(c & 0x80)        Serial.print("1");      else        Serial.print("0");      c <<= 1;    }    Serial.println("");  } }// rotate the 8x8 bit font at *f and store the result in *fr// This will not do a rotate in place so the output font// must not be the same array as the input fontvoid rotate_font(unsigned char *f,unsigned char *fr){  unsigned char *fi;  unsigned char bit = 0x80;  unsigned char rf;  for(int i = 0;i<8;i++) {    fi = f;    rf = 0;    for(int j = 0;j<8;j++) {      rf >>= 1;      if(*fi++ & bit)rf |= 0x80;    }    bit >>= 1;    *fr++ = rf;  }}void setup(void){  Serial.begin(9600);  print_font_bits(font);  Serial.println("");  rotate_font(font,font_r);  print_font_bits(font_r);}void loop(void){}`

Pete

#### Krupski

#6
##### Jan 09, 2013, 07:10 pm
OK maybe I wasn't entirely clear as to what I need to do. I used the "A", "B", "C", "D" thing as an example to show where the bit positions would be.

Here is what I am trying to do: The first block of "code" is an 8 by 8 pixel letter "A":

[font=monospace]
0b00010000
0b00101000
0b01000100
0b11111110
0b10000010
0b10000010
0b10000010
0b00000000
[/font]

I need to rotate the letter 90 degrees clockwise:

[font=monospace]
0b01111000
0b00001100
0b00001010
0b00001001
0b00001010
0b00001100
0b01111000
0b00000000
[/font]

I'm reading data from a raw binary file and trying to write one back out. I'm trying to do it in Basic (don't laugh!).

Here's the code I'm TRYING to make work......

Code: [Select]
` 10 dim fin(8) 20 dim fout(8) 30 open "R",#1,"ibm",1 ' raw font file 40 open "O",#2,"ibm90" ' output file rotated 90 deg 50 field #1,1 as d\$ 60 r=lof(1) 70 for c=1 to r step 8 80   for b=0 to 7 90     get #1,c+b100     fin(b)=asc(d\$) ' fin(0..7) is the 8 bytes of a char unrotated110   next b120   gosub 160130 next c140 end150 for x=0 to 7160   fout(x)=0 ' initialize fout(x)170   for y=0 to 7180     if (fin(y) and (2^y))=(2^y) then fout(x)=fout(x)+(2^y) ' if bit is set then "or" it into fout(x)190   next y200 next x210 for x=0 to 7220   print #2,chr\$(fout(x));230 next x240 return`

I can also do it in C... I did it in BASIC because I have a little test program I wrote that displays the font data to check if I did it right.

This SHOULD be simple, but I'm just not getting it. I feel like an idiot.

Any help will be greatly appreciated!

-- Roger
Gentlemen may prefer Blondes, but Real Men prefer Redheads!

#### AWOL

#7
##### Jan 09, 2013, 07:49 pm
It's been a while since I wrote any BASIC, so can you explain lines 70 and 80, please?
"Pete, it's a fool looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.

#### Tom Carpenter

#8
##### Jan 09, 2013, 08:08 pm
Same code again, but working bitwise rather than element wise.

Code: [Select]
`void setup() {  // put your setup code here, to run once:  byte array[8] = { 0b00010000,                    0b00101000,                    0b01000100,                    0b11111110,                    0b10000010,                    0b10000010,                    0b10000010,                    0b00000000 };  byte rotatedArray[8] = {0};  /*  //rotate 90* anti-clockwise  for (char i = 0; i < maxSize; i++){    for (char j = 0; j < maxSize; j++){      char newI = 7-j;      char newJ = i;      byte value = ((array[i] >> j) & 1); //extract the j-th bit of the i-th element      rotatedArray[newI] |= (value << newJ); //set the newJ-th bit of the newI-th element    }  }  */  //rotate 90* clockwise  for (char i = 0; i < 8; i++){    for (char j = 0; j < 8; j++){      char newI = j;      char newJ = 7-i;      byte value = ((array[i] >> j) & 1); //extract the j-th bit of the i-th element      rotatedArray[newI] |= (value << newJ); //set the newJ-th bit of the newI-th element    }  }        //It should now be reversed. Quick log to check.  Serial.begin(115200);  Serial.println("In");  for (char i = 0; i < 8; i++){    for (char j = 0; j < 8; j++){      Serial.print(((array[i]>>j)&1)?'1':'0');      Serial.print(' ');    }    Serial.println();  }  Serial.println();  Serial.println("Out");  for (char i = 0; i < 8; i++){    for (char j = 0; j < 8; j++){      Serial.print(((rotatedArray[i]>>j)&1)?'1':'0');      Serial.print(' ');    }    Serial.println();  }}void loop() {  // put your main code here, to run repeatedly:   }`
~Tom~

#### Krupski

#9
##### Jan 10, 2013, 02:22 am

Same code again, but working bitwise rather than element wise.

Worked like a charm! I used your code in a small C program (along with getchar and putchar) to fill and write the arrays, then converted the rotated binary file to a font file which I load into a Noritake 128x64 VFD display.

The font data is the actual IBM-PC text mode bitmap in the PC bios! It's a nice readable font, which is why I wanted to get it working with the VFD display.

Thanks for your help (and thanks also to everyone else who replied!)

-- Roger
Gentlemen may prefer Blondes, but Real Men prefer Redheads!

#### Krupski

#10
##### Jan 10, 2013, 03:01 pm

It's been a while since I wrote any BASIC, so can you explain lines 70 and 80, please?

Sure.

[font=monospace]
-- CODE: ---------------------------------------------------------------------------------------------------
70 for c=1 to r step 8 // c is the first byte of 8 to read (index into one character worth of font data)
80   for b=0 to 7 // b is an index into the character data
90     get #1,c+b // read byte "offset + index"
100     fin(b)=asc(d\$) // store byte in fin(x) (asc() returns the numeric value of the string byte)
110   next b // get next byte of char data block
120   gosub 160 // rotate one character
130 next c // do next character
------------------------------------------------------------------------------------------------------------
[/font]

BTW, the variable "r" in line 70 is the file size - i.e. it does "for 1 to 2048".

Oh and thanks for the reply. Thanks to all the replies, I've got it working. Thanks!

-- Roger
Gentlemen may prefer Blondes, but Real Men prefer Redheads!

#### AWOL

#11
##### Jan 10, 2013, 03:13 pm
I'm still confused why one loop starts at one, and the other starts at zero.
Surely the first block of data starts at (0 + 0) , not (1 + 0) ?
"Pete, it's a fool looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.

#### johncc

#12
##### Jan 10, 2013, 03:30 pm

I'm still confused why one loop starts at one, and the other starts at zero.
Surely the first block of data starts at (0 + 0) , not (1 + 0) ?

Basic uses 1-based arrays.  And he is simulating a 2d array so his lower-level index "b" is more sensibly zero-based...

John

#### AWOL

#13
##### Jan 10, 2013, 03:35 pm
Quote
Basic uses 1-based arrays.

I know that
Code: [Select]
`90     get #1,c+b // read byte "offset + index"`
But that's not an array - it's file, isn't it?
"Pete, it's a fool looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.

#### Krupski

#14
##### Jan 10, 2013, 03:40 pm

I'm still confused why one loop starts at one, and the other starts at zero.
Surely the first block of data starts at (0 + 0) , not (1 + 0) ?

In BASIC, the index of the first random record (i.e. byte) is 1, not 0. I know it looks strange, but that's how it works.

BTW, the BASIC I'm using is BAS 2.3 by Michael Haardt, compiled and running in 64 bit Linux. It's syntax identical to GWBASIC.

When I need to whip up a quick and dirty program, I usually use BASIC because it's interactive - I can write, run, debug, edit and re-run without doing the "editor / compiler / debugger / editor / complier  ...." dance.
Gentlemen may prefer Blondes, but Real Men prefer Redheads!

Go Up

Please enter a valid email to subscribe