CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member
Join Date
Dec 2003
Location
indiana
Posts
21

## algorithm needed

hi, i need algorithm to read the elements of an 8 x 8 matrix in a zigzag way. and also want the antizigzag algorithm to recover the elements.

i am giving link below..... that will show how actually i want to read the elemnts of the matrix.

http://www.ascc.net/nl/84/1110/05.html

there is a figure which shows the zigzag scan.

can you suggest any algorithm how to read and recover (anti zigzag) the elements in that way???

thanks

2. Junior Member
Join Date
Dec 2003
Location
indiana
Posts
21
let me put my question in a simpler way,i have a 8 x 8 matrix.... from that matrix i want to read the elements like the link below and want to store in a 1-D buffer .

http://www.ascc.net/nl/84/1110/turn.gif

of course the elements could be anything(positive/negative/fraction)

can anybody suggest algorithm/pseuodocode plz

3. There is a function used to show that NxN has the same
cardinality as N (Here N is the set of natural numbers starting at
zero)
consider a point in NxN, <m,n>, then
f(m,n) = 1/2[(m+n)^2 +3m+n] defines a one-to-one onto relationship
between the desired sets.

This function "moves" in the zig-zag pattern you want.

so given an 8x8 matrix (however you implement that) I will
assume you access it as your_matrix[m][n], then the assignement
to a vector would be
first you need to compute a number
int j = (7 >= m+n ? 0:(m+n - 7));
for(int i = 1; i < (7 >= m+n ? 0:(m+n - 7)); i++)
j += 2i ;

your_vector[1/2((m+n)^2 +3m+n) - j] = your_matrix[m][n]

any way this is the idea
Last edited by souldog; January 1st, 2004 at 04:36 AM.

4. Member
Join Date
Dec 2003
Posts
99
Looks like you are involved some way in image codecs.

In so, the better way is to have another 8x8 matrix for storing appropriate indexes.

for eg for 4x4 matrix you would have used the following
4x4 matrix

Zig Zag Seq:

0 1 5 6
2 4 7 9
3 8 10 11

Index Matrix
0 1 4 8
5 2 3 6
9 10 7 11

Then the loop will be
for (i=0 to 7
j= 0 to 7
Array[i * 8 + j] = Matrix[Index[i][j]]

Atleast the idea is correct

Regards

5. Junior Member
Join Date
Dec 2003
Location
indiana
Posts
21
hi souldog,
your given function is interesting. but it is not giving me the correct result.

i wrote a small code for this.......

Code:
```#include<stdio.h>

int main()

{
int  my_vector[65];//buffer
int  my_matrix[8][8] =           {		{ 0,1,5,6,14,15, 27, 28  },

{ 2,4,7,13,16,26,29,42},

{ 3,8,12,17,25,30,41,43},

{ 9,11,18,24,31,40,44,53},

{ 10,19,23,32,39,45,52,54},

{  20,22,33,38,46,51,55,60},

{  21,34,37,47,50,56,59,61},

{ 35,36,48,49,57,58,62,63}

};

for(int m=0;m<7;m++)

for(int n =0;n<7;n++)

{

int j = (7 >= m+n ? 0 : (m+n - 7));
for(int i = 1; i < (7 >= m+n ? 0 : (m+n - 7)); i++)
j += 2*i ;

my_vector[((m+n)*(m+n)+3*m+n)/(2) - j] = my_matrix[m][n];

}

for(m=0;m<64;m++) printf("%d\n",my_vector[m]);

return 0;

}```

if i read from my_matrix[][] in a zigzag way then my_vector should print 1,2,3,4,5...........,63 is not it??? but its not giving that result...... some where there is mistake. its not reading in a zigzag way???????????

To nsh123
-----------------------

although i could not understand what exactly you wanted to mean by your example .......but i guess you want to creat a matrix(index matrix??) whose elements are the number in which way they are being acessed....so basically there would be a 8x8 index matrix i have to define at the beginig of the code.

plz can you explain more by a small code??

thanks

6. Member
Join Date
Dec 2003
Posts
99
To nsh123
-----------------------
although i could not understand what exactly you wanted to mean by your example .......but i guess you want to creat a matrix(index matrix??) whose elements are the number in which way they are being acessed....so basically there would be a 8x8 index matrix i have to define at the beginig of the code.

plz can you explain more by a small code??
You are perfectly on track !!!
The code posted earlier is exactly what is required.
To make it more clear:
You were trying to generate the zig-zag sequence algorithmically
And I have suggested to hard-code it in your code itself in the form of 8x8 matrix.
Ofcourse assuming 8x8 the only type you deal with.

Regards,

7. Thats is because your indices are wrong.
I made the change ion the code below

The function works, but It could be cleaned up a bit.

Originally posted by maxima
hi souldog,
your given function is interesting. but it is not giving me the correct result.

i wrote a small code for this.......

Code:
```#include<stdio.h>

int main()

{
int  my_vector[65];//buffer
int  my_matrix[8][8] =           {		{ 0,1,5,6,14,15, 27, 28  },

{ 2,4,7,13,16,26,29,42},

{ 3,8,12,17,25,30,41,43},

{ 9,11,18,24,31,40,44,53},

{ 10,19,23,32,39,45,52,54},

{  20,22,33,38,46,51,55,60},

{  21,34,37,47,50,56,59,61},

{ 35,36,48,49,57,58,62,63}

};

for(int m=0;m<8;m++)   //CHANGE UPPER LIMIT TO EIGHT

for(int n =0;n<8;n++)  //CHANGE UPPER LIMIT TO EIGHT

{

int j = (7 >= m+n ? 0 : (m+n - 7));
for(int i = 1; i < (7 >= m+n ? 0 : (m+n - 7)); i++)
j += 2*i ;

my_vector[((m+n)*(m+n)+3*m+n)/(2) - j] = my_matrix[m][n];

}

for(m=0;m<64;m++) printf("%d\n",my_vector[m]);

return 0;

}```

if i read from my_matrix[][] in a zigzag way then my_vector should print 1,2,3,4,5...........,63 is not it??? but its not giving that result...... some where there is mistake. its not reading in a zigzag way???????????

To nsh123
-----------------------

although i could not understand what exactly you wanted to mean by your example .......but i guess you want to creat a matrix(index matrix??) whose elements are the number in which way they are being acessed....so basically there would be a 8x8 index matrix i have to define at the beginig of the code.

plz can you explain more by a small code??

thanks

8. _uj
Banned
Join Date
Nov 2003
Posts
1,405
This is a prodecural approach using stepwise refinement.

Say you have two indexes i and j. The start condition is i=j=0 and the end condition is i=j=7. The indexes can 'move' in two diagonal directions diag_up and diag_down. There are four 'borders' that can be reached border_1 to border_4. When a border is reach the indexes can be advanced in four ways, advance_1 to advance_4 and the direction changes.

In pseudo code this translates to,
Code:
```boolean up = true;    // direction
int i=j=0;    // start
while (!(i == 7) && (j ==7 )) {     // stop
if (border_1()) {            // a border is reached
} else if (border_2()) {
} else if (border_3()) {
} else if (border_4()) {
} else {                             // no border
if (up) diag_up(); else diag_down(); // cont. is same dir.
}
}```
What remains is to identify the actual index increments/decrements. For example diag_up is i++, j--. Lim_1 is j==0. Advance_1 is i++.

9. _uj
Banned
Join Date
Nov 2003
Posts
1,405
Originally posted by _uj
This is a prodecural approach using stepwise refinement.
Well, this is the first refinement. You have to change the pseudocode a little because you can reach two borders at the same time. As a matter of fact one such two-border position constitutes the end criteria.

10. Well, I have already given the function which will do what
the op wants, if he/she can manage to implement the code.

however, I would recommend using nsh123's suggestion and
just implement some lookup tables.

11. _uj
Banned
Join Date
Nov 2003
Posts
1,405
This is a simple to understand procedural version. Say you have an 8x8 chessboard. You start in the 0,0 position then you walk diagonal up. If you land outside the chessboard you correct the position and change walking direction. You can land outside the chessboard in 5 different places,
Code:
```int d=1;	// start direction (diagonal up)
int i=0, j=0; // index
for (int k=0; k<64; k++) { // all chessboard squares
// TRACE(STR(k) + ":" + STR(i) + "/" + STR(j));
output_buffer[k] = chess_board[i,j];
i += d; // next index positions
j -= d;
if (j < 0) { // outside top
j = 0;
d = -d; // change direction
} else if (i < 0) {
if (j > 7) { // outside left and bottom
j = 7;
i += 2;
} else {	// outside left
i = 0;
}
d = -d;
} else if (i > 7) { // outside right
i = 7;
j += 2;
d = -d;
} else if (j > 7) { // outside bottom
j = 7;
i += 2;
d = -d;
}
}```

12. Junior Member
Join Date
Dec 2003
Location
indiana
Posts
21
To souldog
-----------
yes...i did mistake in the limit.....now its working... thanks

chessboard algorithm given by ._uj is also good but i have to think about chessboard algorithm a little bit.

To nash
------------------
i think nash's suggestion would be the simplest one .

so, i want to implement that....... but getting some trouble.

i am writing below what i am thinking.

Code:
```

my_matrix[8][8] =

| 30   0   0   0   0   0   0   0|
| -7   8   1   1   0   0   0   0|
|-11   6   0   1   0   0   0   0|
| -5  -3   0   0   0   0   0   0|
| -7  -3   2   0   0   0   0   0|
| -4   4   0   0   0   0   0   0|
| -1   0   1   0   0   0   0   0|
| -3   1   0   0   0   0   0   0|

my_index[8][8] =

|  1 |  2 |  6 |  7 | 15 | 16 | 28 | 29 |

|  3 |  5 |  8 | 14 | 17 | 27 | 30 | 43 |

|  4 |  9 | 13 | 18 | 26 | 31 | 42 | 44 |

| 10 | 12 | 19 | 25 | 32 | 41 | 45 | 54 |

| 11 | 20 | 24 | 33 | 40 | 46 | 53 | 55 |

| 21 | 23 | 34 | 39 | 47 | 52 | 56 | 61 |

| 22 | 35 | 38 | 48 | 51 | 57 | 60 | 62 |

| 36 | 37 | 49 | 50 | 58 | 59 | 63 | 64 |

// my_index[8][8] is the look up table/zigzag table  that u r suugesting.

Then the loop will be
for (i=0 to 7
j= 0 to 7
Array[i * 8 + j] = Matrix[Index[i][j]]

can you explicitly tell me which way i would  fetch the elements form the my_matrix[][] by looking index table?????```
as you know i am expecting in my buffer[] this sequence(i.e zigzag)
30 0 -7 -11 8 0 0 1 6 -5 -7 -3 0 1 0 0 0 1 0 -3 -4 -1 4 2 0 0 0 0
0 0 0 0 0 0 0 -3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

13. You my_index matrix is wrong, look at nsh's post again.

14. _uj
Banned
Join Date
Nov 2003
Posts
1,405
Originally posted by maxima
chessboard algorithm given by ._uj is also good but i have to think about chessboard algorithm a little bit.
I've run the chessboard algoritm with your index matrix. If you run the code snippet below you'll see that the elements come out in the expected order, namely: 1,2,3, ....... 63,64. Now you just have to plug in my_matrix instead and assign the elements to a 64 element int array using the k index. Use it if you like, it does the expected.
Code:
```int my_index[8][8] =
{{1 ,  2 ,  6 ,  7 , 15 , 16 , 28 , 29},
{3 ,  5 ,  8 , 14 , 17 , 27 , 30 , 43},
{4 ,  9 , 13 , 18 , 26 , 31 , 42 , 44},
{10 , 12 , 19 , 25 , 32 , 41 , 45 , 54},
{11 , 20 , 24 , 33 , 40 , 46 , 53 , 55},
{21 , 23 , 34 , 39 , 47 , 52 , 56 , 61},
{22 , 35 , 38 , 48 , 51 , 57 , 60 , 62},
{36 , 37 , 49 , 50 , 58 , 59 , 63 , 64}};
for (int d=1,i=0,j=0,k=0; k<64; k++) { // all chessboard squares
TRACE(STR(my_index[j][i]));	// println
i += d; // next index positions
j -= d;
if (j < 0) { // outside top
j = 0;
d = -d; // change direction
} else if (i < 0) {
if (j > 7) { // outside left and bottom
j = 7;
i += 2;
} else {	// outside left
i = 0;
}
d = -d;
} else if (i > 7) { // outside right
i = 7;
j += 2;
d = -d;
} else if (j > 7) { // outside bottom
j = 7;
i += 2;
d = -d;
}
}```
PS. TRACE and STR are just a way to print numbers.

To make the algoritm general and work for all 'chessboard' sizes like 9x9 you'll have to take care of the 'outside right and top' case too which would be easy.

15. Junior Member
Join Date
Dec 2003
Location
indiana
Posts
21
To souldog
-----------
yes...i did mistake in the limit.....now its working... thanks
i am sorry.....its not working properly. only changing the index will not be sufficient .... i checked again.....somewher there is some problem......

To _uj
------------------

yes it is going into buffer in the correct way... but i want to reconstruct the matrix from the buffer again...

ok what i wrote giving below...

Code:
```#include<stdio.h>

int main()

{

int output_buffer[64];

int new_matrix[8][8];

int my_index[8][8] =
{{1 ,  2 ,  6 ,  7 , 15 , 16 , 28 , 29},
{3 ,  5 ,  8 , 14 , 17 , 27 , 30 , 43},
{4 ,  9 , 13 , 18 , 26 , 31 , 42 , 44},
{10 , 12 , 19 , 25 , 32 , 41 , 45 , 54},
{11 , 20 , 24 , 33 , 40 , 46 , 53 , 55},
{21 , 23 , 34 , 39 , 47 , 52 , 56 , 61},
{22 , 35 , 38 , 48 , 51 , 57 , 60 , 62},
{36 , 37 , 49 , 50 , 58 , 59 , 63 , 64}};

for (int d=1,i=0,j=0,k=0; k<64; k++)

{
output_buffer[k]  = my_index[j][i];
i += d;
j -= d;
if (j < 0) {
j = 0;
d = -d; // change direction
} else if (i < 0) {
if (j > 7) { // outside left and bottom
j = 7;
i += 2;
} else {	// outside left
i = 0;
}
d = -d;
} else if (i > 7) { // outside right
i = 7;
j += 2;
d = -d;
} else if (j > 7) { // outside bottom
j = 7;
i += 2;
d = -d;
}
}

for( k=0;k<64;k++)
printf("%d\t",output_buffer[k]);

printf("\n\n\n");

/* ---reconstruction of the matrix  from the output buffer -----------------*/

// this part(anti-zigzag ) is not  reconstructing the matrix.

for ( d=1,i=0,j=0,k=0; k<64; k++)

{
new_matrix[j][i] = output_buffer[k];
i += d;
j -= d;
if (j < 0) {
j = 0;
d = -d; // change direction
} else if (i < 0) {
if (j > 7) { // outside left and bottom
j = 7;
i += 2;
} else {	// outside left
i = 0;
}
d = -d;
} else if (i > 7) { // outside right
i = 7;
j += 2;
d = -d;
} else if (j > 7) { // outside bottom
j = 7;
i += 2;
d = -d;
}
}

for(i=0;i<8;i++)

{
for(j=0;j<8;j++)

{
printf("%d\t",new_matrix[j][i]);

}

printf("\n");

}

}```

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

×