CODEWITHSUNDEEP
javahashtable
Jason
Jason

Reputation: 13956

Check Uniqueness of a Java Object, within some epsilon

I'm trying to prune a 3D mesh by checking vertices for uniqueness. But because each vertex has some sort of error associated with it, two "similar" verts could actually be the same. e.g.

<1.9999999, 1, 3> could be the same vertex as <2.000001, 1, 3>

I have millions of vertices I need to check, so I was going to put all of the objects into a hash table and query to see if they are unique. Overriding isEqual is easy: take the abs of the difference between the two coordinates and divide by the magnitude of one. for example:

if (Math.abs((x2-x2)/x1) < 0.0000001) return true;

But how do I come up with a hashcode that will return the same for two effectively equal, but not exactly equal vertices?

I thought about quantizing the space, i.e. taking the floor to some decimal place for the entire set. But, then in my example above I would round to <1.999, 1, 3> and <2.000, 1, 3> for example.

Upvotes: 1

Views: 90

Answers (1)

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272467

But how do I come up with a hashcode that will return the same for two effectively equal, but not exactly equal vertices?

In short, that's not possible.

If hashcode(x) == hashcode(x + eps) for all x, then it's also true that hashcode(x + eps) == hashcode(x + 2*eps) and so on.

The only way to satisfy this is int hashcode() { return CONSTANT; }, which is of limited use...

As a corollary, your equals() method is flawed too. The contract for equals() requires that it be transitive, i.e. if a.equals(b) and b.equals(c), then a.equals(c), for any a, b, c. That is not the case for your definition.

This is going to lead to all sorts of subtle hell, as many of the standard Java collections, etc. rely on this.

Upvotes: 2

Related Questions