Hashcode de número entero coordenadas 3D con alta coherencia espacial

Question

esta es mi primera pregunta en estos foros:)

estoy escribiendo una clase de coordenadas en Java para un sistema octree voxel espacial. Estas coordenadas no son coordenadas de coma flotante, son índices enteros 4D en el octárbol (3 dimensiones normales X, Y, Z y a cuarta para profundizar en el árbol). Los primeros 3 valores son todos cortos, la última dimensión es un byte. En uso real en este momento, solo se usan los primeros 11 bits de los cortos y solo 3 bits del byte, pero esto podría estar sujeto a cambios.

Ahora estoy tratando de escribir una función de hash "buena" para esta clase. El problema con el que estoy luchando es que las coordenadas a menudo se usarán en situaciones coherentes altamente espaciales (espero estar usando la terminología correcta allí). Lo que quiero decir es que muchas veces una coordenada será hashed junto con sus vecinos inmediatamente adyacentes y otras coordenadas cercanas.

¿Existe una práctica efectiva para provocar que estas coordenadas "cercanas entre sí" produzcan códigos hash significativamente diferentes?

Answer 1

"Significativamente diferente" realmente depende de lo que esté haciendo con el código hash después. En algunos casos, estará sujeto a una selección de cubeta circular tomando el hash % size donde size tiene el tamaño del mapa hash que está utilizando, por ejemplo. Obviamente eso cambiará con el tiempo. Por lo general usaría algo como:

int hash = 23; 
hash = hash * 31 + x; 
hash = hash * 31 + y; 
hash = hash * 31 + z; 
hash = hash * 31 + depth; 
return hash; 

(. Esto se cribbed de Effective Java, básicamente) Obviamente esto significa que (x1, y1, z1) y (x1 + 1, y1 - 31, z1) tendría el mismo código hash, pero si usted está preocupado por su mayoría muy cerca de los vecinos no debería ser un problema.

EDITAR: la respuesta de mikera probablemente funcione mejor pero será más complicado de codificar. Yo personalmente probaría este enfoque muy simple primero, y ver si es suficientemente bueno para sus casos de uso reales. Use enfoques progresivamente más efectivos pero complicados hasta que encuentre uno que sea lo suficientemente bueno.

Answer 2

Estás de enhorabuena: hay una forma de obtener codificaciones de coordenadas decentes con una alta coherencia espacial usando algo llamado Z-order curve.

El truco es intercalar los bits de los diferentes componentes de coordenadas. Así que si usted tiene 3 8 bits coordenadas como:

[XXXXXXXX, YYYYYYYY, ZZZZZZZZ] 

A continuación, el valor codificado Z-curva sería un valor único de 24 bits:

XYZXYZXYZXYZXYZXYZXYZXYZ 

Se puede extender a un mayor número de bits o coordenadas según sea necesario.

Esta codificación funciona porque las coordenadas que están cerca en el espacio tendrán diferencias principalmente en los bits de orden inferior. Entonces al intercalar las coordenadas, obtienes las diferencias enfocadas en los bits de orden inferior del valor codificado.

Una propiedad extra interesante es que los bits inferiores describen coordenadas dentro de cubos de espacio. Así que la posición de dirección más baja de 3 bits con cubos 2x2x2, la posición más baja de dirección de 6 bits dentro de 4 * 4 * 4 cubos, la posición más baja de 9 bits dentro de 8 * 8 * 8 cubos, etc. Así que este es un sistema bastante ideal para direccionar -ordina dentro de un octree.