8

这个问题与这里的问题相似。

我们都知道PointF是什么，不是吗？这是数据结构：

public struct PointF
{
  public float X;
  public float Y;
}

如何以IEqualityComparer<PointF>宽容的态度实施？假设我的Equals代码是这样的

public const float Epsilon = 0.01; //say
public bool Equals(PointF pt1, PointF pt2)
{
   return Math.Abs(pt1.X-pt2.X)<Epsilon && Math.Abs(pt1.Y-pt2.Y)<Epsilon;
}

问题：如何实现正确GetHashCode的，以便对于字典PointF，我将正确访问元素？

我绞尽脑汁几天，但仍然找不到令人满意的解决方案。

4

3 回答 3

14

您可以将点放置在网格中，而不是通过距离定义容差。
如果两个点在同一个单元格中，则它们被认为是相等的并且具有相同的哈希码。

public bool Equals(PointF pt1, PointF pt2)
{
   return GetCell(pt1.X) == GetCell(pt2.X)
       && GetCell(pt1.Y) == GetCell(pt2.Y);
}

public int GetHashCode(PointF pt)
{
   return GetCell(pt.X) ^ GetCell(pt.Y);
}

private static int GetCell(float f)
{
    return (int)(f / 10); // cell size is 10 pixels
}

论文：没有满足您的要求Equals的实现。GetHashCode

证明：考虑以下三点，A、B 和 C：

插图

根据您的要求，

Equals(A, B) == true              // (i)
Equals(B, C) == true              // (ii)
Equals(A, C) == false             // (iii)
GetHashCode(A) == GetHashCode(B)  // (iv)
GetHashCode(B) == GetHashCode(C)  // (v)
GetHashCode(A) != GetHashCode(C)  // (vi)

但从 (iv) 和 (v) 得出

GetHashCode(A) == GetHashCode(C)

从而

Equals(A, C) == true

这与 (iii) 和 (vi) 相矛盾。

由于Equals并且GetHashCode不能为相同的参数返回不同的值，因此没有满足您要求的实现。 qed

于 2010-01-13T08:58:47.400 回答
1

我认为这是不可能的，因为您可以拥有无​​限的值序列，这些值等于（在公差范围内）序列中的前一个值和下一个值，但不是任何其他值，并且GetHashCode需要为所有这些值返回相同的值。

于 2010-01-13T09:01:37.657 回答
0

好吧，基于网格的答案很好，但有时您无论如何都需要对关闭点进行分组，即使它们不在同一个网格单元中。我的方法是通过分组来实现这一点：如果两个点很接近或者有一系列接近点连接它们，那么它们就在同一个组中。这种语义不能用适当的 来完成IEqualityComparer，因为它需要在生成组之前提前知道所有项目。所以我做了一个简单的 LINQ 风格的 operator GroupByCluster，基本上实现了这一点。

代码在这里：http: //ideone.com/8l0LH。它在我的 VS 2010 上编译，但无法在 Mono 上编译，因为HashSet<>无法隐式转换为IEnumerable<>（为什么？）。

该方法是通用的，因此不是很有效：它是输入大小的二次方。对于具体类型，它可以变得更高效：例如，对于 T = double 我们可以对输入数组进行排序并具有O(n log n)性能。类似但更复杂的技巧也适用于 2D 点。

另外请注意：您的初始命题不可能用 来实现IEqualityComparer，因为您的“近似相等”不是传递性的（但是 in 的相等性IEqualityComparer必须如此）。

于 2012-09-13T11:05:44.140 回答