14,550,875 members

ZigZag Algorithm in a Grid (revised version, 2.1)

Rate this:
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:

Here is the new version:

Drawing the 'RowMajor'-method:

Drawing the 'ColumnMajor'-method:

Drawing the 'Random'-method:

Drawing the 'Circular'-method:

Drawing the 'DiagonalUp'-method:

Points of Interest

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

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.

Share

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

 First Prev Next
 My vote of 5 Polinia26-May-20 1:21 Polinia 26-May-20 1:21
 An Alternative Approach George Swan24-May-20 20:22 George Swan 24-May-20 20:22
 Is your ZigZag pattern correct? George Swan24-May-20 8:00 George Swan 24-May-20 8:00
 Re: Is your ZigZag pattern correct? Jonas Vago24-May-20 12:08 Jonas Vago 24-May-20 12:08
 Why? degski6-Aug-16 20:22 degski 6-Aug-16 20:22
 Re: Why? Jonas Vago15-Feb-20 7:15 Jonas Vago 15-Feb-20 7:15
 Add indentation Philippe Mori3-Aug-16 11:28 Philippe Mori 3-Aug-16 11:28
 Re: Add indentation Paw Jershauge3-Aug-16 20:22 Paw Jershauge 3-Aug-16 20:22
 Re: Add indentation Jonas Vago (+45-1981)1-May-20 2:25 Jonas Vago (+45-1981) 1-May-20 2:25
 Last Visit: 6-Jun-20 9:52     Last Update: 6-Jun-20 9:52 Refresh 1