algorithm needed

[maxima]

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

[maxima]

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

[souldog]

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

[nsh123]

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

[maxima]

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

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

#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

[nsh123]

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,

[souldog]

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

#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

[_uj]

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,

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

[_uj]

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.

[souldog]

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.

[_uj]

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,

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

[maxima]

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.

                                                                                                        

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

[Marc G]

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

[_uj]

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.

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.

[maxima]

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

#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");
 
}




}