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.