das ist meine erste Frage in diesen Foren:)
Ich schreibe eine Koordinatenklasse in Java für ein räumliches Octree-Voxel-System. 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. Im aktuellen Gebrauch 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 nahen Koordinaten gehashed wird.
Gibt es eine effektive Vorgehensweise, um diese "nahe beieinander liegenden" Koordinaten dazu zu bringen, signifikant unterschiedliche Hashcodes zu erzeugen?
Sie haben Glück: Es gibt eine Möglichkeit, anständige Koordinatencodierungen mit hoher räumlicher Kohärenz zu erhalten, indem Sie ein so genanntes Z verwenden -Korrekturkurve .
Der Trick besteht darin, die Bits der verschiedenen Koordinatenkomponenten zu verschachteln. Also, wenn Sie 3 8-Bit-Koordinaten haben wie:
%Vor%Dann wäre der z-Kurven-codierte Wert ein einzelner 24-Bit-Wert:
%Vor%Sie können nach Bedarf auf eine größere Anzahl von Bits oder Koordinaten erweitern.
Diese Codierung funktioniert, weil Koordinaten, die im Raum dicht sind, hauptsächlich in den Bits niedrigerer Ordnung Unterschiede aufweisen. Indem Sie die Koordinaten verschachteln, erhalten Sie die Unterschiede in den niederwertigen Bits des kodierten Wertes.
Eine besonders 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 -Ordnung in einem Octree.
"Signifyly different" hängt davon ab, was Sie hinterher mit dem Hashcode machen. In einigen Fällen wird es dann einem Round-Robin-Bucket-Pick unterzogen, indem es das hash % size übernimmt, wobei size beispielsweise die Größe der verwendeten Hash-Map ist. Natürlich wird sich das mit der Zeit ändern. Normalerweise verwende ich etwas wie:
(Dies wird im Grunde von Effektivem Java abgekürzt.) Offensichtlich bedeutet das (x1, y1, z1) und (x1 + 1, y1 - 31, z1) würde denselben Hash-Code haben, aber wenn Sie sich hauptsächlich Sorgen um sehr Nachbarn machen, sollte das kein Problem sein.
BEARBEITEN: mikers Antwort wird wahrscheinlich besser funktionieren, aber komplizierter zu codieren sein. Ich würde persönlich diese sehr einfache Methode zuerst ausprobieren und sehen, ob es für Ihre tatsächlichen Anwendungsfälle gut genug ist. Verwenden Sie schrittweise effektivere, aber komplizierte Ansätze, bis Sie eine finden, die gut genug ist.
Tags und Links java hash coordinates