Zigzag path through 2D array

Processing Coding Questions
1

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

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:

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.

1 Like
2

Hi @dangerousclive ,

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

Example code in Python

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.

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 that you could use for this. EJML for instance has a getDiagonal function that could come in very handy.

3 Likes
3

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 :smiley: