Click here to Skip to main content
14,550,875 members

ZigZag Algorithm in a Grid (revised version, 2.1)

Rate this:
5.00 (5 votes)
Please Sign up or sign in to vote.
5.00 (5 votes)
24 May 2020CPOL
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...

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)

Share

About the Author

Jonas Vago
Software Developer Specialisterne ApS
Denmark Denmark
I am sometimes very interested in software development.

Comments and Discussions

 
GeneralMy vote of 5 Pin
Polinia26-May-20 1:21
MemberPolinia26-May-20 1:21 
QuestionAn Alternative Approach Pin
George Swan24-May-20 20:22
MemberGeorge Swan24-May-20 20:22 
QuestionIs your ZigZag pattern correct? Pin
George Swan24-May-20 8:00
MemberGeorge Swan24-May-20 8:00 
AnswerRe: Is your ZigZag pattern correct? Pin
Jonas Vago24-May-20 12:08
MemberJonas Vago24-May-20 12:08 
QuestionWhy? Pin
degski6-Aug-16 20:22
Memberdegski6-Aug-16 20:22 
AnswerRe: Why? Pin
Jonas Vago15-Feb-20 7:15
MemberJonas Vago15-Feb-20 7:15 
SuggestionAdd indentation Pin
Philippe Mori3-Aug-16 11:28
MemberPhilippe Mori3-Aug-16 11:28 
GeneralRe: Add indentation Pin
Paw Jershauge3-Aug-16 20:22
MemberPaw Jershauge3-Aug-16 20:22 
GeneralRe: Add indentation Pin
Jonas Vago (+45-1981)1-May-20 2:25
professionalJonas Vago (+45-1981)1-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.

Tip/Trick
Posted 3 Aug 2016

Stats

15.7K views
287 downloads
14 bookmarked