# Getting two-dimensional coordinates from a one-dimensional array

If you're working in the 2D canvas context, and you'd like to fill your canvas with objects on both `x`

and `y`

axes, you might not need to reach for nested `for`

loops! It's possible to get `x`

and `y`

coordinates **from a single, one-dimensional array**.

This is a *little* math-y, and not as easy as just using nested loops, but it (might? could? possibly?) lead to performance benefits, depending on your use case.

Whereas nested loops can lead to *exponential* complexity (`O(n^i)`

and therefore, possibly, degraded performance), a single `for`

loop (or multiple loops side-by-side) scales in a *linear* way (`i * O(n)`

, if I'm not mistaken), which *can* lead to better performance. More on Big O notation at ye olde Wikipedia.

That said, browsers are pretty heckin' fast at drawing to the canvas, so if your canvas program is performing well with nested loops, no reason to change. Also if you're using the GPU to draw to canvas, this is almost certainly unnecessary.

I just liked the challenge.

**Anywhey**, here's how to do it.

Say you have an array that represents ten blocks in your drawing. You know you want the drawing to be five blocks wide (that is, you want it to have five columns of blocks), and each block will be 5 pixels wide. You can use the following formula to derive each individual item's `x`

and `y`

coordinates:

` ````
// i = the index of the block whose coordinates you'd like to calculate
// columns = the total width of your drawing, divided by its pixel scale
// scale = the width of one of your drawing's blocks in canvas pixels
x = Math.floor(i % columns) * scale
y = Math.floor(i / columns) * scale
```

Doing the math manually bears this out. Our original array looks like this:

` ````
var arr = [a, b, c, d, e, f, g, h, i, j]
```

If our scale is 5 and our number of columns is 5 (which means the total area of the canvas is 250px, or `(columns * scale) * (rows * scale)`

), let's get the X and Y position on the canvas of item 7 in the array (which has a value of `h`

).

First, X:

` ````
var i = 7, columns = 5
// In our imaginary coordinate system based on the width of our blocks, X = 2:
var x = Math.floor(i % columns) // 2
// Now we can convert that to our real, pixel-based coordinate system
// that exists in the canvas
x = x * scale // 10
```

...and Y:

` ````
var y = Math.floor(i / columns) // 1
// ...and our actual canvas pixels:
y = y * scale // 5
```

So if we were to split our array onto two lines, item 7 would be at position `2, 1`

, which means in our actual pixel-based canvas coordinates, the item's position is `10, 5`

.

It helps to imagine the array broken onto multiple lines, like a matrix:

` ````
a b c d e
f g h i j
```

There you can see that item 7 is `2`

items over, `1`

item down (remember to start at 0, though).

What about going the other way around? What if you have X and Y coordinates (in real pixels), but you want to know what block exists at that position (for instance, to react to user input)?

We just reverse the formula. Y is the easiest one to reverse, so let's start there. First, let's take our Y coordinate and convert it back to the imaginary coordinate system:

` ````
// The user clicked at position 13, 8. Here's what we know
var x = 13, y = 8, columns = 5, scale = 5, i // i = undefined
// First we should convert our pixel coordinates back to our drawing's scale
x = Math.floor(x / scale) // 2
y = Math.floor(y / scale) // 1
// Now we can solve for Y. If i / columns == y...
// i = columns / y
i = columns / y // 5
// And we can just add the X value (in our imaginary coordinates)
// to our Y value to get the real `i`:
i = i + x // 7
arr[i] // h! Just what we expected.
```

If you can get away with only doing that calculation once, you might see a nice performance bump, compared to nested arrays!

I used this technique on a couple of demos, most recently on a Conway's Game of Life demo. Click and drag around---no loss in framerate, even on my iPhone 6 Plus!

So, there you have it. It's definitely **easier** to reach for nested arrays when you need to work in two dimensions, and it might not hurt your app's performance in the slightest. The only way to know for sure is to test. But with a little algebra, you can keep your arrays one-dimensional and possibly save some cycles!

A nice trick for taking a list of things to display in HTML in a column format (if for some reason you can't just let it flow naturally)

Why not odds = x, evens = y?

@jemminger I don’t follow. How do you mean?

@bigsweater Ah, I see: it's not a 2 x N grid, it's N x M.

@jemminger Haha, I'd thought I'd unnecessarily complicated things.

I think you are missing the point with this blog post: The complexity doesn't change by storing all the same data in a one-dimensional array instead, because in a matrix of

`X`

times`Y`

, you will still have to allocate`X`

new array items for adding a new row. The only real difference is reading from the array: you either have two read operations or only one (but instead the calculation on top). All in all, the difference will be negligible.Instead, for a performance boost, try using

Typed Arrays.Source: https://stackoverflow.com/questions/22004670/is-flattening-javascript-2d-arrays-worth-any-performance-gain?answertab=votes#tab-top

According to that stackoverflow, flat arrays are faster than typed arrays in most browsers. If you look at the benchmarks they link, 1D arrays are nearly 2x as fast as 2D arrays, and typically faster than or comparable to Typed arrays, depending on the browser.

@irisschaffer

Really interesting mix of results in those benchmarks! Firefox especially seems to handle flat, typed arrays incredibly fast, though in later versions of Chrome and Chromium, flat arrays perform about as well as (or better than) flat/typed.

I'd never used typed arrays before--I'll try to find some time to do a couple forks of this pen to see which is faster.

Thanks for this; as much as I've researched this (on Stack Overflow, too!) I hadn't come across that answer.

An great trick that we had to use back when one worked with linear video addressing, ala mode 13h

I do this in Sass all the time because I have no other choice, but if I write JS, I use

`reduce()`

, which reduces 😜 to 1 line:Basically, I don't do anything for even indices of the flat array (

`i%2 == 0`

, the second option of the ternary) and add an array made up of the previous item and the current one to the accumulator for odd indices (first option of the ternary).So if my

`arr`

is`[1, 2, 3, 4]`

initially, it becomes`[[1, 2], [3, 4]]`

after the above line of JS.While I agree on the general premise: > flat is better than nested

Using a flat data structure doesn't actually change the complexity of an algorithm in this case. The performance gain is purely due to the implementation of JavaScript and hardware.

Using nested for loop doesn't make exponential complexity and

`O(n)`

or`O(n^k)`

doesn't mean anything unless you define what`n`

or`k`

is - in this case, it could be the width and height of the canvas or total the number of pixels.