Click here to Skip to main content
15,867,453 members
Articles / Desktop Programming / Win32
Tip/Trick

ZigZag Algorithm in a Grid (revised version, 2.1)

Rate me:
Please Sign up or sign in to vote.
5.00/5 (5 votes)
24 May 2020CPOL1 min read 27.7K   448   16   9
Application to show how to zigzag order a matrix
This four year old project has had a new update. The original intention was to illuminate the serialization of a two-dimensional array into a one-dimensional array. This is often done through the JPEG (or MJPG) libraries. My project (or app-demo) now implements something further, (other than the 'ZigZag'-routine): 'RowMajor', 'ColumnMajor', 'Random', 'Circular', and 'DiagonalUp'.

Introduction

The downloadable code displays a grid of changeable size, rows and columns. The grid represents a matrix of numbers ordering by zigzag. It shows zero-based number indexing from zero to rows times columns minus one. If the matrix has 8 rows and 8 columns, the number indexing is from 0 to 63. It also shows red line segments across the numbers. The problem and why I have made this program follows: "How to serialize a matrix? That is: how to cast a two-dimensional array into a one-dimentional array? The most simple solution is to do a row-major or a column-major ordering. The more difficult part is to do zigzag ordering.

Background

The background of this problem is how e.g. image compression (JPEG) encodes and decodes blocks of frequency transformed images into a serialized stream (one-dimensional array). It is like a compromise between the row-major and column-major serialization.

Using the Code

This code snippet takes two arguments, rows count and columns count. Then generate a tuple list of zero-based indexing. (The language is C#.) The tuple consists of (0, 0), (0, 1), (1, 0), (2, 0), (1, 1) and so on...

C#
private static Tuple<int, int>[] ZigZag(int rows, int cols)
{
	Tuple<int, int>[] a = new Tuple<int, int>[rows * cols];
	int p = 0;
	int i = 0;
	int j = 0;
	a[p++] = Tuple.Create(i, j);
	while (p < rows * cols)
	{
		if (j < cols - 1)
		{
			j++;
		}
		else
		{
			i++;
		}

		while (i < rows && j >= 0)
		{
			a[p++] = Tuple.Create(i, j);
			i++;
			j--;
		}
		i--;
		j++;

		if (i < rows - 1)
		{
			i++;
		}
		else
		{
			j++;
		}

		while (i >= 0 && j < cols)
		{
			a[p++] = Tuple.Create(i, j);
			i--;
			j++;
		}
		i++;
		j--;
	}
	return a;
}

Here is the old version:

Drawing the 'ZigZag'-method:

Image 1

Here is the new version:

Drawing the 'RowMajor'-method:

Image 2

Drawing the 'ColumnMajor'-method:

Image 3

Drawing the 'Random'-method:

Image 4

Drawing the 'Circular'-method:

Image 5

Drawing the 'DiagonalUp'-method:

Image 6

Points of Interest

The interesting part is to think strategic when designing the algorithm.

Test the program/problem for correctness. Find inconsistencies. Ask questions. Report errors.

History

First designed the algorithm, tested, made sure the numbers are correct back and forth.

Then made a visual application with user interaction (buttons and checkboxes) and a grid to display the numbers and zigzag line segments.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



Comments and Discussions

 
GeneralMy vote of 5 Pin
Polinia26-May-20 1:21
Polinia26-May-20 1:21 
QuestionAn Alternative Approach Pin
George Swan24-May-20 20:22
mveGeorge Swan24-May-20 20:22 
QuestionIs your ZigZag pattern correct? Pin
George Swan24-May-20 8:00
mveGeorge Swan24-May-20 8:00 

Thanks for the interesting piece. I was wondering if the zigzag pattern was fixed? According to this. The transversal should be

txt
Matrix to ZigZag
1        2       3       4
5        6       7       8
9        10      11      12
13       14      15      16
17       18      19      20
ZigZag
1
5       2
9       6       3
13      10      7       4
17      14      11      8
18      15      12
19      16
20

AnswerRe: Is your ZigZag pattern correct? Pin
User 525047824-May-20 12:08
User 525047824-May-20 12:08 
QuestionWhy? Pin
degski6-Aug-16 20:22
degski6-Aug-16 20:22 
AnswerRe: Why? Pin
User 525047815-Feb-20 7:15
User 525047815-Feb-20 7:15 
SuggestionAdd indentation Pin
Philippe Mori3-Aug-16 11:28
Philippe Mori3-Aug-16 11:28 
GeneralRe: Add indentation Pin
Paw Jershauge3-Aug-16 20:22
Paw Jershauge3-Aug-16 20:22 
GeneralRe: Add indentation Pin
User 128592001-May-20 2:25
professionalUser 128592001-May-20 2:25 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.