代码之家 › 专栏 › 技术社区 › Andy Shellam

为近似相似的数字生成相同的哈希代码

autocad coordinates math c#

Andy Shellam · 技术社区 · 16 年前

我正在C#3.5中创建一个应用程序,它使用AutoCAD API读取二维AutoCAD图形,使用定义的业务逻辑对图形进行更改,然后在AutoCAD中对其进行调整。由于逻辑的性质,必须重新构造图纸的形状-例如,矩形由4条连接直线组成。

我使用AutoCAD中每条线的起点坐标和终点坐标创建这些形状,但有些坐标并不完全匹配。例如,一个点可以位于0.69912839(在一个轴上),但从同一点开始的直线可以是0.69990821。这些单位为毫米,因此距离为分钟(0.00078毫米!)

那很好,工作很出色。现在,我需要检查这些点类的集合以消除所有重复项,因此我在集合上使用LINQ的Distinct()方法。但是,此方法使用GetHashcode(),而不是Equals()来确定实例是否相等。因此,我重写了GetHashcode(),它使用double类的GetHashcode。

但是,上面的示例失败了,因为它们显然是不同的值,因此生成不同的哈希代码。有没有办法让两个相距在0.001以内的数字生成相同的哈希代码(请注意,这些数字彼此并不了解,因为GetHashcode是在不同的类实例上单独调用的。)我尝试了许多方法,这些方法对某些示例有效,但对其他示例无效。

一个例子是将数字截断为3dp(乘以10^3,然后截断),并在结果上创建哈希代码-这适用于上面的例子(699==699.),但这不适用于0.69990821和0.70000120(699!=700.)我尝试过四舍五入,它适用于第二组数字(0.700==0.700),但不适用于第一组数字(0.699!=0.700。)我甚至尝试将数字截断为3dp,然后将其调整为下一个偶数,这对前面的两个示例都有效,但对12.9809和12.9818(12980!=12982.)

7 回复 | 直到 16 年前

MaLio 16 年前

只需删除对Distinct方法的依赖就更容易了。实现System.Collections.IComparer(或通用等效工具),并使用简单的集合,如列表。然后使用比较器确定该项是否在列表中,如果已包含该项,则不要添加该项。

Steck 16 年前

它无法编写正确的哈希代码。让我们证明一下: var a=point1.GetHashCode();

如果是b让我们在点1和点2之间创建点。等等

所以点1和点2的哈希代码应该相等。

因此,我们应该这样做:

public override int GetHashCode()
{
    return 0;
}

heijp06 16 年前

我认为你不应该凌驾于此 Equals() == , != 或 GetHashCode()

如果覆盖其中任何一个,则应确保它们的语义不会更改。在你的例子中,他们是这样做的。

不能传递,因为它是这样的:如果P1距离P2 0.001 mm,P2距离P3 0.001 mm,P1距离P3 0.002 mm,则P1==P2,P2==P3和P1==P3,这不是您想要的。通常,最终所有点都等于所有其他点。

我会坚持使用单独的方法来确定点是否足够接近。

编辑

用你的超控您现在可以编写如下代码:

if(P1 == P2 && P2 == P3 && P1 != P3)
{
    // Code here gets executed
}

fortran 16 年前

我猜如果您总是返回相同的散列(比如0),LinQ将尝试将所有元素与 equals . 毕竟,散列可以用来证明两个元素是不同的,而不是相等的。

但无论如何,我建议您使用更适合这个领域的结构和算法,比如二进制分割分区(BSP)树。

Alexey Romanov 16 年前

这应该是对斯特克和保罗所说的更清楚的解释。

a 和 b ,不管他们之间的距离有多远, a.GetHashCode() == b.GetHashCode() .

证据:假设 a < b . 分道扬镳和分成小于0.001的段。即。 a0 = a , a1 = a0 + 0.0005 , a2 = a1 + 0.0005, 等等,直到你到达

然后 a.GetHashCode() == a1.GetHashCode() == a2.GetHashCode() == ... == b.GetHashCode() .

Darius Bacon 16 年前

我应该放弃相等的,==,!=和GetHashcode重写,并创建我自己的MyPoint.IsEqualTo()和MyPointCollection.Distinct()方法?

对

不过,它不一定是完全不同的数据结构。在检查重复项时,需要检查相邻的哈希代码,例如(x+0.001,y)、(x,y-0.001)的哈希,等等。与通常的重复数据消除查找相比,这只会使速度持续下降,而且并不复杂,因此这可能是一种可行的方法(这是一个显而易见的观点,但我认为这里还没有明确指出。)

为了澄清,让我们看一下问题的一维版本。“点”是单个数字,x。我们认为X1和X2是匹配的。 abs(x1 - x2) < .001 hash(x) = h(floor(1000*x)) 对于一些函数h(),它可以传播信息。为了确定x是否已经在表中,我们计算 hash(x-.001) , hash(x) hash(x+.001) ,然后我们测试x是否与中的任何x_i匹配 三个桶中的任何一个 . 任何匹配的x_i不能在任何其他桶中。

在二维变型中,有9个相邻的铲斗需要检查(计算中间);在3-d中,27。

Andy Shellam 16 年前

这里有一些代码来说明我在做什么。“原始”中的每对数字都应返回相同的值。

int tolerance = 3;
double[] original = new double[] {
0.69912839,
0.69990821,

0.69990821,
0.70000120,

12.980984087,
12.981808908
};
double[] modified = new double[original.Length];

for (int i = 0; i < original.Length; i++)
{
modified[i] = original[i];

/* Begin number adjustment logic */
modified[i] *= Math.Pow(10, tolerance);
modified[i] = Math.Truncate(modified[i]);

if (modified[i] % 2 != 0)
{
modified[i]++;
}
/* End number adjustment logic */

Console.WriteLine(modified[i]);

if (i % 2 != 0)
{
Console.WriteLine(string.Empty);
}
}

上述方法是“截断为3dp,然后调整为最接近的偶数”方法。接下来是truncate方法(替换开始/结束注释之间的代码):

/* Begin number adjustment logic */
modified[i] *= Math.Pow(10, tolerance);
modified[i] = Math.Truncate(modified[i]);
/* End number adjustment logic */

这是四舍五入法:

/* Begin number adjustment logic */
modified[i] = Math.Round(modified[i], tolerance);
/* End number adjustment logic */