Hashcode für 3D-ganzzahligen Koordinaten mit hohen räumlichen Kohärenz

Question

dies ist meine erste Frage auf diesen Foren:)

Ich bin für ein räumliches Octree Voxel-System einer Koordinaten Klasse in Java zu schreiben. Diese Koordinaten sind keine Gleitpunktkoordinaten, sie sind 4D-Ganzzahlindizes in den Octree (3 normale Dimensionen X, Y, Z und ein viertes für die Tiefe in den Baum). Die ersten 3 Werte sind alle Kurzschlüsse, die letzte Dimension ist ein Byte. In der aktuellen Verwendung werden nur die ersten 11 Bits der Kurzschlüsse und nur 3 Bits des Bytes verwendet, aber dies könnte sich ändern.

Jetzt versuche ich eine 'gute' Hash-Funktion für diese Klasse zu schreiben. Das Problem, mit dem ich mich wehre, ist, dass die Koordinaten oft in räumlich hochgradig kohärenten Situationen verwendet werden (hoffe, ich verwende dort die richtige Terminologie). Was ich meine ist, dass oft eine Koordinate zusammen mit ihren unmittelbar benachbarten Nachbarn und anderen nahegelegenen Koordinaten gehashed wird.

Gibt es eine effektive Praxis, diese "nahe beieinander" -Koordinaten zu veranlassen, signifikant unterschiedliche Hashcodes zu erzeugen?

Answer 1

"Signifikant anders" hängt wirklich davon ab, was Sie hinterher mit dem Hashcode machen. In einigen Fällen wird es dann einem Round-Robin-Bucket-Pick unterzogen, indem Sie die hash % size nehmen, wobei size beispielsweise die Größe der verwendeten Hash-Map ist. Natürlich wird sich das mit der Zeit ändern. Ich würde in der Regel so etwas wie verwenden:

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

(. Das von Effective Java abgeschaut ist, im Grunde) Offensichtlich bedeutet dies, dass (x1, y1, z1) und (x1 + 1, y1 - 31, z1) würden den gleichen Hash-Code haben, aber wenn Sie hauptsächlich besorgt über sehr nahe Nachbarn sollte es kein Problem sein.

EDIT: mikera's Antwort wird wahrscheinlich besser funktionieren, aber komplizierter zu codieren sein. Ich würde persönlich versuchen diese sehr einfache Vorgehensweise zuerst, und sehen, ob es gut genug ist für Ihre tatsächlichen Anwendungsfälle. Verwenden Sie schrittweise effektivere, aber komplizierte Ansätze, bis Sie einen finden, der gut genug ist.

Answer 2

Sie haben Glück: Es gibt eine Möglichkeit, anständige Koordinatenkodierungen mit hoher räumlicher Kohärenz zu erhalten, indem man etwas verwendet, das Z-order curve genannt wird.

Der Trick besteht darin, die Bits der verschiedenen Koordinatenkomponenten zu verschachteln. Also, wenn Sie drei 8-Bit-Koordinaten wie:

[XXXXXXXX, YYYYYYYY, ZZZZZZZZ] 

Dann wird die z-Kurve codierten Wert würde ein einzelner 24-Bit-Wert sein:

XYZXYZXYZXYZXYZXYZXYZXYZ 

Sie auf größere Zahlen erweitern können Bits oder Koordinaten wie erforderlich.

Diese Codierung funktioniert, weil Koordinaten, die im Raum dicht sind, Unterschiede hauptsächlich in den Bits niedrigerer Ordnung aufweisen. Indem Sie die Koordinaten verschachteln, erhalten Sie die Unterschiede in den niederwertigen Bits des kodierten Wertes.

Eine weitere interessante Eigenschaft ist, dass die unteren Bits Koordinaten innerhalb von Raumwürfeln beschreiben. Also die niedrigste 3-Bit-Adressposition mit 2x2x2 Würfeln, die niedrigste 6-Bit-Adressposition innerhalb von 4 * 4 * 4 Würfeln, die niedrigste 9-Bit-Position innerhalb von 8 * 8 * 8 Würfeln usw. Das ist also eigentlich ein ideales System zur Adressierung von Co -Ordinaten in einem Octree.