Zigzag path through 2D array

Processing Coding Questions
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