2

Is there a way to represent a 3D Vector as a definite number? I mean that two vectors with different values can't ever have the same hash value. I'm sure there already is a question about this but I haven't found it unfortunately. Thanks for your help.

EDIT:

I know this algorithm for 2D vectors which is pretty good (I think): (x + y) * (x + y + 1) / 2 + y

borchero
  • 5,562
  • 8
  • 46
  • 72
  • Why not just slice the 3D vector XORing the hashes of your slices as you go? – Tripp Kinetics Aug 11 '15 at 20:42
  • In principle what you want to do is map the 3-D Real space R^3 onto the 1-D space R using a reversible transformation, this is not possible. However in practice it is probably possible to do something acceptable in a real programming language to solve a real problem, can you be more specific? – Conor Aug 11 '15 at 20:53
  • @Conor yeah, that's what I need, it doesn't have to be reversible; I don't know how to be more specific, tell me what else you need to know^^ – borchero Aug 11 '15 at 20:57
  • The problem is one of precision and space, how are your vectors represented now, how do you want to represent your hash value, how fast does your hash function have to be? – Conor Aug 11 '15 at 21:08
  • I simply have x, y and z as floating point numbers and want to calculate the hash value as integer (cast in the end) by some simple arithmetic operations in the best case – borchero Aug 11 '15 at 21:13

3 Answers3

1

The best approach to get a hash for a vector of floats is to convert it to a string of bytes or characters and calculate a hash on it. An example of this is given using numpy and python in the following answer: Most efficient property to hash for numpy array.

This will work efficiently for large numbers of vectors, but you cannot guarantee that you will not get collisions due to the simple fact of mapping three floats onto an integer. However there are a number of hashing algorithms available in the python hashlib library to choose from, you might need to experiment. An option in C++ is Boost::Hash.

Community
  • 1
  • 1
Conor
  • 1,028
  • 1
  • 8
  • 15
1

See the pigeon-hole principle - in the same way you can't fit you can't 100 pigeons into 10 holes, you can't uniquely convert 3 values into 1 value (with all values of the same size). There will have to be duplicates.

Now, if you could have a number with 3x as many bits as the vector values, the problem becomes fairly easy:

// convert x, y and z to the range 0-...
x -= minimum possible value
y -= minimum possible value
z -= minimum possible value

mult = maximum possible value + 1
hash = x * mult * mult + y * mult + z

If you're having trouble understanding the above, just take the example of the range of the values being 0-99. We'd multiple x by 100*100 = 10000 and y by 100, so the hash would be a decimal value with (at most) 6 digits with x, y and z all next to each other, guaranteed to not overlap:

x = 12
y = 34
z = 56
hash = 123456

Now this same idea will hold for any maximum value by just changing the base / radix.

If there isn't any overlap in some base, each unique combination of values of x, y and z will result in a unique hash.

This is by far the simplest approach, although it doesn't produce a particularly good hash, so it depends what you want to use it for - there might be a way to uniquely convert this number to another number which will be a good hash.

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
1

Responding to this post a little late, and perhaps this isn't what you're looking for, but I figured I would chime in with another answer.

You could use the function you mentioned, (x + y) * (x + y + 1) / 2 + y , and do it recursively, ex. f( f(x,y) , z).

You can also use other pairing functions as well and use the same method (https://en.wikipedia.org/wiki/Pairing_function).

For my problem, I wanted a function that would order vectors based on their location. The order itself didn't matter, only that a close value means a similar vector. What I ended up doing was:

double get_pairing(double x, double y, double z) {
    double normalizer = 0.0;

    if(x < 0) {
        normalizer += (3.0 * MAX_COORD_VAL);
    } 
    if (y < 0) {
        normalizer += (6.0 * MAX_COORD_VAL); 
    } 
    if (z < 0) {
        normalizer += (9.0 * MAX_COORD_VAL);
    }

    double g = x + y + z - normalizer + (21 * MAX_COORD_VAL);  

    return g;


}

This orders vectors based on whether they have negative coordinate values and whether they have large coordinate values.

This works assuming you have a max coordinate value.

Dyskord
  • 365
  • 5
  • 14