How to Implement IEqualityComparer<PointF> With Tolerance

Question

This question is similar to the one here.

We all know what PointF is, don't we? This is the data structure:

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

How to implement IEqualityComparer<PointF> with tolerance? Let's say my Equals code is like this

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;
}

Question: How to implement the correct GetHashCode so that for a dictionary of PointF, I will access the element correctly?

I crack my head a few days but still can't find a satisfactory solution.

Answer 1

Instead of defining the tolerance by the distance, you could place the points in a grid.
If two points are in the same cell, they're considered equal and have the same hash code.

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
}

---

Thesis: There is no implementation of Equals and GetHashCode that meets your requirements.

Proof: Consider the following three points, A, B, and C:

As per your requirements,

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)

But from (iv) and (v) follows

GetHashCode(A) == GetHashCode(C)

and thereby

Equals(A, C) == true

which contradicts (iii) and (vi).

Since Equals and GetHashCode cannot return different values for the same arguments, there is no implementation that meets your requirements. q.e.d.

Answer 2

I don't think it's possible because you could have an infinite sequence of values that are equal (within tolerance) to the previous and next value in the sequence but not any other value and GetHashCode would need to return an identical value for all of them.

Answer 3

Well, the answer based on grids is good, but sometimes you need to group the close points anyway, even if they are not in the same grid cell. My approach is to implement this with a grouping: two points are in the same group if either they are close or there is a sequence of close points connecting them. This semantics cannot be done with a proper IEqualityComparer, because it needs to know all the items in advance before producing the groups. So I've done a simple LINQ-style operator GroupByCluster, which basically achieves this.

The code is here: http://ideone.com/8l0LH. It compiles on my VS 2010, but fails to compile on Mono because HashSet<> cannot be implicitly converted to IEnumerable<> (why?).

The approach is generic and thus not very efficient: it's quadratic on input size. For the concrete types it can be made more efficient: for example, for T = double we can just sort the input array and have O(n log n) performance. The analogous though more complicated trick is applicable for 2D points as well.

---

Note aside: your initial proposition is impossible to implement with IEqualityComparer, since your "approximate equality" is not transitive (but the equality in IEqualityComparer has to be so).