Cómo implementar IEqualityComparer Con Tolerancia

Question

Esta pregunta es similar a la de aquí .

Todos sabemos lo que PointF es decir, ¿no es así? Esta es la estructura de datos:

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

Cómo implementar IEqualityComparer<PointF> con la tolerancia? Digamos que mi código Equals es como esto

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

Pregunta: ¿Cómo aplicar la GetHashCode correcta de manera que para un diccionario de PointF, voy a acceder correctamente el elemento

Me trueno cabeza un par de días, pero todavía no puede encontrar una solución satisfactoria.

Answer 1

En lugar de definir la tolerancia por la distancia, puede colocar los puntos en una cuadrícula.
Si dos puntos están en la misma celda, que están consideradas iguales y tienen el mismo código hash.

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
}

---

Tesis:. No hay ninguna aplicación de Equals y GetHashCode que satisfaga sus requerimientos

Prueba: Considere los siguientes tres puntos, A, B, y C:

Según sus requisitos,

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)

Sin embargo, a partir de (iv) y (v) de la siguiente manera

GetHashCode(A) == GetHashCode(C)

y de ese modo

Equals(A, C) == true

lo que contradice (iii) y (vi).

Desde Equals y GetHashCode no puede devolver valores diferentes para los mismos argumentos, no hay ninguna aplicación que se adapte a sus necesidades. q.e.d.

Answer 2

No creo que sea posible, ya que podría tener una secuencia infinita de valores que son iguales (dentro de la tolerancia) al valor anterior y siguiente en la secuencia pero no cualquier otro valor y GetHashCode tendría que devolver un valor idéntico para todos ellos.

Answer 3

Bueno, la respuesta sobre la base de las redes es bueno, pero a veces es necesario agrupar los puntos cercanos de todos modos, incluso si no están en la misma celda de la cuadrícula. Mi enfoque es implementar esto con una agrupación: dos puntos están en el mismo grupo, si bien están cerca o hay una secuencia de puntos cercanos de conectarlos. Esta semántica no se puede hacer con un IEqualityComparer adecuada, porque necesita saber todos los elementos de antelación antes de producir los grupos. Así que he hecho un simple operador GroupByCluster estilo de LINQ, que básicamente se logra esto.

El código está aquí: http://ideone.com/8l0LH . Se compila en mi VS 2010, pero falla al compilar en Mono porque HashSet<> no puede ser implícita convierte en IEnumerable<> (¿por qué?).

El enfoque es genérico y por lo tanto no es muy eficiente: esto es cuadrática en el tamaño de la entrada. Para los tipos de hormigón que puede ser más eficiente: por ejemplo, para T = doble que acabamos puede ordenar la matriz de entrada y han O(n log n) rendimiento. El truco similar, aunque más complicado es aplicable para 2D puntos también.

---

Nota al margen:. Su propuesta inicial es imposible de implementar con IEqualityComparer, ya que su "igualdad aproximada" no es transitiva (pero la igualdad en IEqualityComparer tiene que ser así)