
December 31st, 2003, 12:24 PM
#1
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

December 31st, 2003, 10:13 PM
#2
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 1D 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

January 1st, 2004, 04:39 AM
#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 onetoone onto relationship
between the desired sets.
This function "moves" in the zigzag 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 05:36 AM.
Wakeup in the morning and kick the day in the teeth!! Or something like that.
"i don't want to write leak free code or most efficient code, like others traditional (so called expert) coders do."

January 1st, 2004, 06:08 AM
#4
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

January 1st, 2004, 01:17 PM
#5
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

January 1st, 2004, 01:26 PM
#6
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 zigzag sequence algorithmically
And I have suggested to hardcode it in your code itself in the form of 8x8 matrix.
Ofcourse assuming 8x8 the only type you deal with.
Regards,

January 1st, 2004, 02:03 PM
#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
Wakeup in the morning and kick the day in the teeth!! Or something like that.
"i don't want to write leak free code or most efficient code, like others traditional (so called expert) coders do."

January 2nd, 2004, 12:42 AM
#8
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
advance_1(); up = !up; // advance and change direction
} else if (border_2()) {
advance_2(); up = !up;
} else if (border_3()) {
advance_3(); up = !up;
} else if (border_4()) {
advance_4(); up = !up;
} 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++.

January 2nd, 2004, 12:55 AM
#9
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 twoborder position constitutes the end criteria.

January 2nd, 2004, 12:56 AM
#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.
Wakeup in the morning and kick the day in the teeth!! Or something like that.
"i don't want to write leak free code or most efficient code, like others traditional (so called expert) coders do."

January 2nd, 2004, 04:12 AM
#11
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;
}
}

January 2nd, 2004, 08:14 AM
#12
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.
your quote
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

January 2nd, 2004, 08:47 AM
#13
You my_index matrix is wrong, look at nsh's post again.

January 2nd, 2004, 09:49 AM
#14
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.

January 2nd, 2004, 12:07 PM
#15
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(antizigzag ) 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

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
