# How can I index 2 dimensional points, starting at the origin and going outwards?

Is there any way that I can mathematically determine a unique index number for 2D points that increases the further away I get from the origin? I do not know how far out that this coordinate system extends to.

I am working on a system where I need random access to data indexed by a 2D point.

In other words, I need a function that will always return a unique integer given the same two integers, but not conflict with other sets of numbers. Think of it like a hash. However, I need the indices generated to increase as the distance from the origin increases - this is so that my index growth remains constant as I add more data.

EDIT:

Here is some procedurally generated data that would work as a solution. I simply need a function that I can execute in constant time that produces something to the effect of:

   0,   0 = 0
-1,   0 = 1
0,  -1 = 2
0,   1 = 3
1,   0 = 4
-1,  -1 = 5
-1,   1 = 6
1,  -1 = 7
1,   1 = 8
-2,   0 = 9
0,  -2 = 10
0,   2 = 11
2,   0 = 12
-2,  -1 = 13
-2,   1 = 14
-1,  -2 = 15
-1,   2 = 16
1,  -2 = 17
1,   2 = 18
2,  -1 = 19
2,   1 = 20
-2,  -2 = 21
-2,   2 = 22
2,  -2 = 23
2,   2 = 24
-3,   0 = 25
0,  -3 = 26
-3,  -1 = 27
-3,   1 = 28
-1,  -3 = 29
1,  -3 = 30
-3,  -2 = 31
-3,   2 = 32
-2,  -3 = 33
2,  -3 = 34
-3,  -3 = 35

• Two answers are posted, both generally increasing with distance from the origin, but neither monotonic. Is that a requirement? It makes the problem much harder. You would need a solution to the Gauss circle problem: see en.wikipedia.org/wiki/Gauss_circle_problem Jun 3, 2011 at 5:10

First suppose the coordinates are non-negative. You can define $$f(x,y) = \binom{x+y+1}{2} + x.$$ Here $\binom{z}{2} = z(z-1)/2$.

In order to handle arbitrary integers, define $$g(x) = \begin{cases} 0 & x = 0, \\ 2x - 1 & x > 0, \\ -2x & x < 0. \end{cases}$$ Then the function you want is $$h(x,y) = f(g(x),g(y)).$$

• I implemented this and it seems very promising. I'm going to be doing some more testing tomorrow on this, but I am pretty sure this is what I need. I would upvote you if I could... Thanks!
– user11686
Jun 3, 2011 at 6:05
• After some testing, this is indeed what I was looking for. Thanks!
– user11686
Jun 3, 2011 at 21:14

If you're using points with integer coordinates, then try a spiral like this one: http://upload.wikimedia.org/wikipedia/commons/1/1d/Ulam_spiral_howto_all_numbers.svg.

• This is very very close to what I am looking for. However, I need a function that I can use to calculate one of those values given a point - in constant time.
– user11686
Jun 3, 2011 at 5:17
• @NelsonLaQuet, finding a formula is a nice exercise. Note that the square number appear diagonally down to right. If you still need help, please ask.
– lhf
Jun 3, 2011 at 12:55

It is believed (but not proved) that $f(x,y)=x^5+y^5$ never takes on the same value twice except, of course, for $f(x,y)=f(y,x)$. It certainly never takes on the same value twice for as far as anyone has been able to compute - call it "an industrial grade theorem." Like the other suggestions, it increases, but not monotonely, with increasing distance from the origin.

If the coordinates of the points can have any real value, then I don't think such a function is possible because you are looking for an injective function from $\mathbb{R}^2$ to $\mathbb{R}$.

EDIT: The examples came up after I posted this. If you're just using integers, then such a function is possible.

• $\mathbb{R}^2$ and $\mathbb{R}$ have the same cardinality, and therefore are in bijection. See here. Jun 3, 2011 at 6:17
• @Zev Well dang.
– Tauf
Jun 4, 2011 at 5:01