(x,y) to index conversion functions (programming Q)

Factual Questions
1

Ok, so I’m writing a program in which I have a grid. The grid is stored in a numbered array, and therefore each grid has an index (everything is zero-based). Now, I want to be able to access each cell/element by the index as well as by x,y coordinates. I’ve figured out functions to do this conversion easily, and I’m pretty sure they’re solid, but I’m a little weak on the math part of this so I’d like verification that they always work.

Example Grid:


+-------+-------+-------+-------+
| (0,0) | (1,0) | (2,0) | (3,0) |
|   0   |   1   |   2   |   3   |
+-------+-------+-------+-------+
| (0,1) | (1,1) | (2,1) | (3,1) |
|   4   |   5   |   6   |   7   |
+-------+-------+-------+-------+
| (0,2) | (1,2) | (2,2) | (3,2) |
|   8   |   9   |  10   |  11   |
+-------+-------+-------+-------+
| (0,3) | (1,3) | (2,3) | (3,3) |
|  12   |  13   |  14   |  15   |
+-------+-------+-------+-------+

To convert from (x,y) to n, for width of grid w:
n = (w*(y+1)) - (w-x)

To convert from n to (x,y), for width of grid w:
y = RoundDown(n / w)
x = n - (w * y)

I tested these functions on a variety of grid sizes and couldn’t find anything wrong with them. Does anyone see a problem?

Also, if there is a better way to do this, I’m open to suggestions :slight_smile:

TIA!

–FCOD

2

Dammit! That second sentence should read, “The grid is stored in a numbered array, and therefore each cell has an index (everything is zero-based).”

–FCOD

3

To convert from (x,y) to n, I’d use:

n=x+(w*(y+1))

4

Oops, rather:
n=w*y+x

or redundantly bracketed n=w*(y+x) if your compiler applies BODMAS

5

Gah, I even got that wrong. Start again:

n=(w*y)+x

If your compiler applies BODMAS, or even just consistently performs the operations in stated sequence, the brackets are unnecessary.

6

Well, that’s right, but if you simplify it:
n = (w*(y+1)) - (w-x)
= wy + w - w + x
= wx + x

That looks right. Or you can use the modulus function, if your language has one:
x = n mod w

Some languages have a function that does intiger division and returns both the quotient and remainder. If so, you can just do n/w, and the quotient is y and the remainder is x.

7

(x, y) to n:

n = w*y + x

n to (x, y):

y = n % w
x = (n - y)/w

8

I tested some of the equations

This works just fine.

This should be x = n % w

This doesn’t seem to work. For (1,3) n=13 (see my example grid): x = (13-3)/4 = 10 / 4 = 2.5

–FCOD

9

Just curious. Why not just use a 2D array and avoid doing any maths?

10

I think he/she meant y=(n-x)/w.

11

Ah. Yes that’s it.

Thank you everyone!

–FCOD

12

If you use x + (x + y) * (x + y + 1) / 2, you get an index that isn’t dependent on the width of the array. Could be useful if you need to resize the array, or for storing sparse arrays.

13

Some Performance Reasons:

  1. In Java (not sure what language the OP is in) 2D arrays are much slower than 1D.
  2. At times, in the past, I have used 1D instead of 2D for drawing lines in graphics because calculating the next pixel can be accomplished with 1 add or sub instead of adjusting the X and Y and then re-calculating the pixel index.
14

But how do you convert back?

15

um… I’ve been wondering that myself.

Let d = trunc((1 + n * 8)^0.5 - 1) / 2)
Then …
x = n - d * (d + 1) / 2
y = d - x

That works mathematically, but you might get into trouble with round off errors. You could change the first line to d = trunc((1 + n * 8 + 0.1)^0.5 - 1) / 2) or do some other fudge I suppose.

After the first post, I thought of another way to do this that’s easier to invert, but you still end up taking a square root and truncation.