HashCode per intero coordinate 3D ad alta coerenza spaziale

Question

questa è la mia prima domanda su questi forum:)

Sto scrivendo una classe di coordinate in Java per un sistema octree voxel spaziale. Queste coordinate non sono coordinate in virgola mobile, sono indici interi 4D nell'occhiello (3 dimensioni normali X, Y, Z e una avanti per profondità nell'albero). I primi 3 valori sono tutti in cortocircuito, l'ultima dimensione è un byte. In questo momento vengono utilizzati solo i primi 11 bit dei cortocircuiti e solo 3 bit del byte, ma ciò potrebbe essere soggetto a modifiche.

Ora sto cercando di scrivere una funzione di hash "buona" per questa classe. Il problema con cui sto lottando è che le coordinate saranno spesso utilizzate in situazioni coerenti altamente spaziali (spero che io stia usando la terminologia giusta lì). Quello che intendo è che spesso le coordinate di una coordinata vengono troncate insieme ai suoi vicini immediatamente adiacenti e altre coordinate vicine.

Esiste una pratica efficace per far sì che queste coordinate "vicine l'una all'altra" producano codici hash significativamente differenti?

Answer 1

"Significativamente diverso" dipende in realtà da ciò che si sta facendo con il codice hash in seguito. In alcuni casi sarà quindi soggetto a una scelta di bucket round robin prendendo lo hash % size dove size è la dimensione della mappa di hash che stai utilizzando, ad esempio. Ovviamente questo cambierà nel tempo. Mi piacerebbe di solito uso qualcosa di simile:

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

(. Questo è cribbed da Effective Java, in fondo) Ovviamente significa che (x1, y1, z1) e (x1 + 1, y1 - 31, z1) avrebbe lo stesso codice hash, ma se siete preoccupati per lo più molto vicino ai vicini non dovrebbe essere un problema.

MODIFICA: la risposta di mikera è probabile che funzioni meglio ma essere più complicato da codificare. Vorrei provare personalmente questo approccio molto semplice, e vedere se è abbastanza buono per i tuoi casi d'uso reali. Usa approcci progressivamente più efficaci ma complicati finché non trovi quello che è abbastanza buono.

Answer 2

Sei fortunato: c'è un modo per ottenere codifiche di coordinate decenti con alta coerenza spaziale usando qualcosa chiamato Z-order curve.

Il trucco è di interlacciare i bit dei diversi componenti di coordinate. Quindi, se si dispone di 3 coordinate 8-bit come:

[XXXXXXXX, YYYYYYYY, ZZZZZZZZ] 

Quindi il valore codificato z-curva sarebbe un singolo valore a 24 bit:

XYZXYZXYZXYZXYZXYZXYZXYZ 

è possibile estendere a un maggior numero di bit o coordinate come richiesto.

Questa codifica funziona perché le coordinate che sono vicine nello spazio avranno differenze principalmente nei bit di ordine inferiore. Quindi, interlacciando le coordinate, si ottengono le differenze focalizzate nei bit di ordine inferiore del valore codificato.

Una proprietà molto interessante è che i bit inferiori descrivono le coordinate all'interno dei cubi dello spazio. Quindi la posizione dell'indirizzo a 3 bit più bassa con i cubi 2x2x2, la posizione dell'indirizzo a 6 bit più bassa all'interno dei cubi 4 * 4 * 4, la posizione a 9 bit più bassa all'interno dei cubi 8 * 8 * 8 ecc. Quindi questo è in realtà un sistema piuttosto ideale per indirizzare co -ordinati in un ottetto