如何使用公差实现IEqualityComparer<PointF>

Question

如何使用公差实现IEqualityComparer<PointF>

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 字典，我能够正确地访问元素？

我已经思考了几天，但仍然没有找到一个令人满意的解决方案。

- Graviton

1

你想要的是：对于每个点P，Q，其中P =~ Q，则Hash（P）== Hash（Q）。对吧？（=〜表示具有容差相等）我猜这真的很难做到。你甚至可以尝试在MathOverflow上找到一个具有该属性的函数。 - Vinko Vrsalovic

@Vinko，是的，这就是我想要的。 - Graviton

3个回答

1

我认为这是不可能的，因为你可能有一个无限序列的值，它们在容差范围内等于序列中的前一个和后一个值，但没有其他值，而GetHashCode需要为它们所有返回相同的值。

- Pent Ploompuu

我从未想过那个。尽管我怀疑在低容差的稀疏数据集中不可能存在无限序列，但仍希望能找到解决容差问题的方法。 - Mateen Ulhaq

0

嗯，基于网格的答案很好，但有时您仍然需要将接近的点分组，即使它们不在同一个网格单元中。我的方法是使用分组来实现：如果两个点接近或存在连接它们的一系列接近点，则它们属于同一组。这种语义不能使用适当的IEqualityComparer完成，因为它需要在生成组之前知道所有项目。因此，我使用了一个简单的类似于LINQ的运算符GroupByCluster，基本上可以实现这一点。

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

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

注意：您的初始提议无法使用IEqualityComparer实现，因为您的“近似相等”不是传递性的（但在IEqualityComparer中的相等必须是传递性的）。

- Vlad

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dtb · Accepted Answer

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

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和hashCode不能为相同的参数返回不同的值，因此没有符合您要求的实现。证毕。