# 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 – Ross Millikan Jun 3 '11 at 5:10

## 4 Answers

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! – NelsonLaQuet Jun 3 '11 at 6:05
After some testing, this is indeed what I was looking for. Thanks! – NelsonLaQuet Jun 3 '11 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. – NelsonLaQuet Jun 3 '11 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 '11 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. – Zev Chonoles Jun 3 '11 at 6:17
@Zev Well dang. – Tauf Jun 4 '11 at 5:01