Hashing 2D, 3D and nD vectors
Solution 1
There's a spatial hash function described in Optimized Spatial Hashing for Collision Detection of Deformable Objects. They use the hash function
hash(x,y,z) = ( x p1 xor y p2 xor z p3) mod n
where p1, p2, p3 are large prime numbers, in our case 73856093, 19349663, 83492791, respectively. The value n is the hash table size.
In the paper, x, y, and z are the discretized coordinates; you could probably also use the binary values of your floats.
Solution 2
I have two suggestions.
- Assume a grid cell of size l and quantize the x, y and z co-ordinates by computing ix = floor(x/l), iy = floor(y/l), and iz = floor(z/l), where ix, iy and iz are integers. Now use the hash function defined in Optimized Spatial Hashing for Collision Detection of Deformable Objects
If you don't do the quantization, it wont be sensitive to closeness(locality).
- Locality Sensitive Hashing has been mentioned for hashing higher dimensional vectors. Why not use them for 3d or 2d vectors as well? A variant of LSH using adapted for Eucledian distance metric (which is what we need for 2d and 3d vectors) is called Locality Sensitive Hashing using p-stable distributions. A very readable tutorial is here.
Comments
-
Christian Rau about 2 years
What are good hashing functions (fast, good distribution, few collisions) for hashing 2d and 3d vectors composed of IEEE 32bit floats. I assume general 3d vectors, but algorithms assuming normals (always in [-1,1]) are also welcome. I also do not fear bit-manipulation as IEEE floats are alsways IEEE floats.
Another more general problem is hashing an Nd float-vector, where N is quite small (3-12) and constant but not known at compile time. At the moment I just take these floats as uints and XOR them together, which is probably not the best solution.
-
sehe almost 11 yearsNote that 19349663 isn't prime (it's the product of 41 and 471943)
-
axel22 over 8 yearsI found that using the prime numbers p1 and p3 for the two-dimensional case results in very good distributions.
-
emlai about 8 yearsWhen they wrote
x p1 xor y p2 xor z p3
, did they mean(x*p1) xor (y*p2) xor (z*p3)
orx * (p1 xor y) * (p2 xor z) * p3
? -
celion about 8 years@tuple_cat I believe it's
(x*p1) xor (y*p2) xor (z*p3)
-
tuned about 7 yearsVery interesting! Is there any implementation around? I am trying to implement this with scipy/numpy. Thanks.
-
kenyee over 5 yearsBy "discretized coordinates", do you mean integers? I have coordinates in floating point meters.
-
John T almost 3 yearsHmm. These results seem wrong jsfiddle.net/uwg0ehs6
-
John T almost 3 yearsOr jsfiddle.net/spowz758/2 , very not correct
-
John T almost 3 years
n is hash table size
. MM. What table? The one I will fill with these keys?