Pages: [1] 2   Go Down
 Author Topic: Algorithm to rotate data  (Read 525 times) 0 Members and 1 Guest are viewing this topic.
Offline
Sr. Member
Karma: 15
Posts: 463
 « on: January 09, 2013, 09:36:47 am » Bigger Smaller Reset

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

A B C D
E F G H
I J K L
M N O P

after rotation

M I E A
N J F B
O K G C
P L H D

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
 Logged

Leeds, UK
Offline
God Member
Karma: 35
Posts: 986
Once the magic blue smoke is released, it won't go back in!
 « Reply #1 on: January 09, 2013, 10:03:56 am » Bigger Smaller Reset

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.
 « Last Edit: January 09, 2013, 10:13:37 am by Tom Carpenter » Logged

~Tom~

France
Offline
God Member
Karma: 19
Posts: 618
Scientia potentia est.
 « Reply #2 on: January 09, 2013, 10:30:23 am » Bigger Smaller Reset

Something like this should work:
Code:
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:
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];
 « Last Edit: January 09, 2013, 10:40:52 am by guix » Logged

Temple, Texas
Offline
Sr. Member
Karma: 14
Posts: 354
 « Reply #3 on: January 09, 2013, 10:37:38 am » Bigger Smaller Reset

Here's an approach I might take:

Code:
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 thing

void 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);
}

 Logged

Leeds, UK
Offline
God Member
Karma: 35
Posts: 986
Once the magic blue smoke is released, it won't go back in!
 « Reply #4 on: January 09, 2013, 11:45:18 am » Bigger Smaller Reset

After a little bit of playing around with how coordinates map, it is really rather simple:
Code:
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:
In
A B C D
E F G H
I J K L
M N O P

Out
M I E A
N J F B
O K G C
P L H D
 « Last Edit: January 09, 2013, 11:47:38 am by Tom Carpenter » Logged

~Tom~

Offline
God Member
Karma: 14
Posts: 905
 « Reply #5 on: January 09, 2013, 12:29:00 pm » Bigger Smaller Reset

This rotates the bits of an 8x8 font:
Code:
unsigned char font[8] = {
0B10101010,
0B11001100,
0B11100111,
0B00111100,
0B01001001,
0B10110111,
0B11000101,
0B01011101
};
unsigned char font_r[8];

// print an 8x8 bit font
void 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 font
void 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
 Logged

Offline
Sr. Member
Karma: 15
Posts: 463
 « Reply #6 on: January 09, 2013, 01:10:50 pm » Bigger Smaller Reset

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":

0b00010000
0b00101000
0b01000100
0b11111110
0b10000010
0b10000010
0b10000010
0b00000000

I need to rotate the letter 90 degrees clockwise:

0b01111000
0b00001100
0b00001010
0b00001001
0b00001010
0b00001100
0b01111000
0b00000000

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:
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+b
100     fin(b)=asc(d\$) ' fin(0..7) is the 8 bytes of a char unrotated
110   next b
120   gosub 160
130 next c
140 end
150 for x=0 to 7
160   fout(x)=0 ' initialize fout(x)
170   for y=0 to 7
180     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 y
200 next x
210 for x=0 to 7
220   print #2,chr\$(fout(x));
230 next x
240 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
 Logged

Global Moderator
UK
Offline
Brattain Member
Karma: 138
Posts: 19067
I don't think you connected the grounds, Dave.
 « Reply #7 on: January 09, 2013, 01:49:18 pm » Bigger Smaller Reset

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

Pete, it's a fool looks for logic in the chambers of the human heart.

Leeds, UK
Offline
God Member
Karma: 35
Posts: 986
Once the magic blue smoke is released, it won't go back in!
 « Reply #8 on: January 09, 2013, 02:08:01 pm » Bigger Smaller Reset

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

Code:
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:

}
 Logged

~Tom~

Offline
Sr. Member
Karma: 15
Posts: 463
 « Reply #9 on: January 09, 2013, 08:22:30 pm » Bigger Smaller Reset

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
 Logged

Offline
Sr. Member
Karma: 15
Posts: 463
 « Reply #10 on: January 10, 2013, 09:01:17 am » Bigger Smaller Reset

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

Sure.

-- 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
------------------------------------------------------------------------------------------------------------

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
 Logged

Global Moderator
UK
Offline
Brattain Member
Karma: 138
Posts: 19067
I don't think you connected the grounds, Dave.
 « Reply #11 on: January 10, 2013, 09:13:41 am » Bigger Smaller Reset

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) ?
 Logged

Pete, it's a fool looks for logic in the chambers of the human heart.

Temple, Texas
Offline
Sr. Member
Karma: 14
Posts: 354
 « Reply #12 on: January 10, 2013, 09:30:14 am » Bigger Smaller Reset

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
 Logged

Global Moderator
UK
Offline
Brattain Member
Karma: 138
Posts: 19067
I don't think you connected the grounds, Dave.
 « Reply #13 on: January 10, 2013, 09:35:30 am » Bigger Smaller Reset

Quote
Basic uses 1-based arrays.
I know that
Code:
90     get #1,c+b // read byte "offset + index"
But that's not an array - it's file, isn't it?
 Logged

Pete, it's a fool looks for logic in the chambers of the human heart.

Offline
Sr. Member
Karma: 15
Posts: 463
 « Reply #14 on: January 10, 2013, 09:40:33 am » Bigger Smaller Reset

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.
 Logged

 Pages: [1] 2   Go Up