# Zigzag path through 2D array

**URL:** <https://discourse.processing.org/t/zigzag-path-through-2d-array/15093>\
**Category:** Coding Questions\
**Created:** [October 31, 2019, 11:05pm UTC](https://discourse.processing.org/t/zigzag-path-through-2d-array/15093 "2019-10-31T23:05:25Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![dangerousclive](https://avatars.discourse-cdn.com/v4/letter/d/da6949/32.png) [@dangerousclive](https://discourse.processing.org/u/dangerousclive)\
**Post date:** [October 31, 2019, 11:05pm UTC](https://discourse.processing.org/t/zigzag-path-through-2d-array/15093/1 "2019-10-31T23:05:25Z")

</div>

Hi,

I’m attempting to reorder a 2D array to follow a zigzag path. This image illustrates the path I wish to follow:  
[https://en.wikipedia.org/wiki/JPEG#/media/File:JPEG\_ZigZag.svg](https://en.wikipedia.org/wiki/JPEG#/media/File:JPEG_ZigZag.svg)

I’m having a bit of a problem moving backwards and forwards across the array.

The code below is what I have at the moment, generating a 2D array of colours in an image:

```auto
import java.util.Arrays;

int sizeX = 1200;
int sizeY = 800;
int detail = 30;

String[][] colourList = new String[ceil(sizeX/detail)][ceil(sizeY/detail)];

void setup() {
  size(1200, 800);
  PImage img = loadImage("image.jpg");

  for (int i=0; i<ceil(sizeX/detail); i++) {
    for (int j=0; j<ceil(sizeY/detail); j++) {
      PImage newImg = img.get(i*detail, j*detail, detail, detail);
      int colourExtracted = extractColorFromImage(newImg);
      String thisCol = hex(colourExtracted, 6);
      colourList[i][j] = thisCol;
      fill(colourExtracted);
      noStroke();
      rect(i*detail, j*detail, detail, detail);
    }
  }

  // print 2d array
  println(Arrays.deepToString(colourList));
  println();
  println(Arrays.deepToString(colourList)
    .replace("[[", "")
    .replace("], [", "\n")
    .replace("]]", "")
    .replace(" ", " "));
}

color extractColorFromImage(final PImage img) {
  img.loadPixels();
  color r = 0, g = 0, b = 0;

  for (final color c : img.pixels) {
    r += c >> 020 & 0xFF;
    g += c >> 010 & 0xFF;
    b += c & 0xFF;
  }

  r /= img.pixels.length;
  g /= img.pixels.length;
  b /= img.pixels.length;

  return color(r, g, b);
}

```

If there’s any pointers that anyone could share, I’d be most grateful.

Thanks in advance.

---

<div class="post-metadata">

**Author:** ![solub](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/solub/32/333_2.png) [@solub](https://discourse.processing.org/u/solub)\
**Post date:** [November 1, 2019, 4:12am UTC](https://discourse.processing.org/t/zigzag-path-through-2d-array/15093/2 "2019-11-01T04:12:52Z")

</div>

Hi @dangerousclive ,

How about finding the diagonals first and then reverse them alternatively.

Example code in Python

```auto
W = img.width #width of image
H = img.height #height of image

diagonals = [] #store diagonals
current = 0 #index of pixel currently visited

#for each pixel on top + right side of image
for i in xrange(W+H-1):
	
	nxt = current
	diag = [nxt]
	
	#traverse diagonal until it reaches left side or bottom of image
	while (nxt%W) != 0 and (nxt/W) != H-1:
		nxt += W - 1
		diag.append(nxt)
	
	#increment index by 1 until it reaches the top right corner
	#then increment by W (to skip row one by one)	
	n = 1 if current < W-1 else W
	current += n
	
	#reverse list alternatively 
	diag = diag[::-1] if i%2 == 0 else diag
	diagonals.append(diag)

```

**Edit** : Below a much efficient and pythonic version of this script. You can find a Java implementation of a Zig-Zag traversal [here](https://www.geeksforgeeks.org/zigzag-or-diagonal-traversal-of-matrix/).

```auto
W, H = img.width, img.height
idx = range(W-1) + range(W-1, W*H, W)
rng = range(1, W) + range(H, 0, -1)
rng = map(lambda x: x if (x < min(W, H)) else min(W, H), rng)
dia = [[i + (W-1) * m for m in xrange(r)] for i, r in zip(idx, rng)]

```

That being said, if your objective is to do some data compression on large images I would suggest to resort to vectorized operations. There are [plenty of libraries](https://discourse.processing.org/t/libraries-not-listed-on-libraries-page/11806/7) that you could use for this. [EJML](https://github.com/lessthanoptimal/ejml) for instance has a `getDiagonal` function that could come in very handy.

---

<div class="post-metadata">

**Author:** ![dangerousclive](https://avatars.discourse-cdn.com/v4/letter/d/da6949/32.png) [@dangerousclive](https://discourse.processing.org/u/dangerousclive)\
**Post date:** [November 1, 2019, 12:03pm UTC](https://discourse.processing.org/t/zigzag-path-through-2d-array/15093/3 "2019-11-01T12:03:32Z")

</div>

Hi @solub,

Many thanks! The code example and link to the libraries are very interesting indeed.

Image compression wasn’t my intention, just to out put the arrays in the zigzag order, but I now see how it could so, so thanks for that little idea too 😃