¿Cómo puedo indexar puntos bidimensionales, empezando en el origen y yendo hacia fuera?

Question

¿Hay alguna forma de determinar matemáticamente un número de índice único para puntos 2D que aumente cuanto más me aleje del origen? No sé hasta dónde se extiende este sistema de coordenadas.

Estoy trabajando en un sistema en el que necesito acceso aleatorio a datos indexados por un punto 2D.

En otras palabras, necesito una función que siempre devuelva un único número entero dados los mismos dos números enteros, pero que no entre en conflicto con otros conjuntos de números. Piénsalo como un hash. Sin embargo, necesito que los índices generados aumenten a medida que aumenta la distancia desde el origen - esto es para que el crecimiento de mi índice se mantenga constante a medida que añado más datos.

EDITAR:

Aquí hay algunos datos generados procedimentalmente que funcionarían como solución. Simplemente necesito una función que puedo ejecutar en tiempo constante que produce algo al efecto de:

   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

Answer 1

En primer lugar, supongamos que las coordenadas son no negativas. Se puede definir $$f(x,y) = \binom{x+y+1}{2} + x.$$ Aquí $\binom{z}{2} = z(z-1)/2$ .

Para manejar números enteros arbitrarios, defina $$g(x) = \begin{cases} 0 & x = 0, \\ 2x - 1 & x > 0, \\ -2x & x < 0. \end{cases}$$ Entonces la función que quieres es $$h(x,y) = f(g(x),g(y)).$$

Answer 2

Si utilizas puntos con coordenadas enteras, prueba con una espiral como ésta: http://upload.wikimedia.org/wikipedia/commons/1/1d/Ulam_spiral_howto_all_numbers.svg .

Answer 3

Se cree (pero no se ha demostrado) que $f(x,y)=x^5+y^5$ nunca toma el mismo valor dos veces excepto, por supuesto, para $f(x,y)=f(y,x)$ . Desde luego, nunca toma el mismo valor dos veces por lo que nadie ha sido capaz de calcular - llámalo "un teorema de grado industrial". Al igual que las otras sugerencias, aumenta, pero no monótonamente, con el aumento de la distancia al origen.

Answer 4

Si las coordenadas de los puntos pueden tener cualquier valor real, entonces no creo que tal función sea posible porque estás buscando una función inyectiva de $\mathbb{R}^2$ a $\mathbb{R}$ .

EDIT: Los ejemplos aparecieron después de publicar esto. Si sólo está utilizando números enteros, a continuación, una función de este tipo es posible.