# 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:** 1\
**Showing post:** 2

<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.

---

_[View the full topic](https://discourse.processing.org/t/zigzag-path-through-2d-array/15093)._