java - 在某个 epsilon 内检查 Java 对象的唯一性

Question

我正在尝试通过检查顶点的唯一性来修剪 3D 网格。但是因为每个顶点都有某种与之相关的错误，所以两个“相似”的顶点实际上可能是相同的。例如

<1.9999999, 1, 3> 可以是与 <2.000001, 1, 3> 相同的顶点

我需要检查数百万个顶点，因此我打算将所有对象放入一个哈希表并查询它们是否是唯一的。覆盖 isEqual 很简单:取两个坐标之间的差的绝对值并除以 1 的大小。例如:
if (Math.abs((x2-x2)/x1) < 0.0000001) return true;
但是我如何想出一个哈希码，它会为两个有效相等但不完全相等的顶点返回相同的值？

我考虑过对空间进行量化，即将整个集合的地板保留到小数位。但是，在我上面的例子中，我会舍入到 <1.999, 1, 3> 和 <2.000, 1, 3> 例如。

Answer 1

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

简而言之，这是不可能的。

如果 hashcode(x) == hashcode(x + eps)为所有 x , 那么 hashcode(x + eps) == hashcode(x + 2*eps) 也是真的等等。

满足这一点的唯一方法是int hashcode() { return CONSTANT; } ，这是有限的使用...

作为推论，您的 equals()方法也有缺陷。 contract for equals() 要求它是可传递的，即如果 a.equals(b)和 b.equals(c) ，然后 a.equals(c) , 对于 任意 a , b , c .您的定义并非如此。

这将导致各种微妙的 hell ，因为许多标准的 Java 集合等都依赖于此。