Come implementare IEqualityComparer Con Tolleranza

Question

Questa domanda è simile a quello qui .

Sappiamo tutti cosa PointF è, non è vero? Questa è la struttura dei dati:

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

Come implementare IEqualityComparer<PointF> con la tolleranza? Diciamo che il mio codice Equals è come questo

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

Domanda: Come implementare la GetHashCode corretta in modo che per un dizionario di PointF, io accedere correttamente l'elemento

I crack la testa un paio di giorni, ma ancora non riesce a trovare una soluzione soddisfacente.

Answer 1

Invece di definire la tolleranza per la distanza, è possibile inserire i punti in una griglia.
Se due punti sono nella stessa cella, sono considerati uguali e hanno lo stesso codice 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
}

---

Tesi:. Non v'è alcuna implementazione di Equals e GetHashCode che soddisfi le vostre esigenze

Prova: Considerare i seguenti tre punti, A, B, e C:

Come per le vostre esigenze,

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)

Ma da (iv) e (v) segue

GetHashCode(A) == GetHashCode(C)

e quindi

Equals(A, C) == true

che contraddice (iii) e (vi).

Dal Equals e GetHashCode non possono restituire valori diversi per gli stessi argomenti, non v'è alcuna implementazione che soddisfi le vostre esigenze. q.e.d.

Answer 2

Non credo che sia possibile, perché si potrebbe avere una sequenza infinita di valori che sono uguali (in tolleranza) al valore precedente e successivo nella sequenza, ma non qualsiasi altro valore e GetHashCode avrebbe bisogno di restituire un valore identico per tutti loro.

Answer 3

Bene, la risposta in base a griglie è buono, ma a volte è necessario raggruppare i punti vicini in ogni caso, anche se non sono nella stessa cella della griglia. Mio approccio è quello di implementare questo con un gruppo: due punti sono nello stesso gruppo se entrambi sono vicini o v'è una sequenza di punti stretti li collega. Questa semantica non può essere fatto con un adeguato IEqualityComparer, perché ha bisogno di conoscere tutti gli elementi di anticipo prima di produrre i gruppi. Così ho fatto una semplice GroupByCluster operatore di stile LINQ, che realizza fondamentalmente questo.

Il codice è qui: http://ideone.com/8l0LH . Compila il mio VS 2010, ma non riesce a compilare su Mono perché HashSet<> non può essere convertito in modo implicito IEnumerable<> (perché?).

L'approccio è generico e quindi non molto efficiente: è quadratica sulla dimensione di input. Per i tipi di cemento può essere reso più efficiente: per esempio, per T = doppia che può semplicemente ordinare l'array e hanno O(n log n) prestazioni. L'analogo trucco anche se più complicato è applicabile per 2D punti pure.

---

Nota a parte:. La vostra proposta iniziale è impossibile da realizzare con IEqualityComparer, dal momento che il "uguaglianza approssimativa" non è transitiva (ma l'uguaglianza in IEqualityComparer deve essere così)