Comment mettre en œuvre IEqualityComparer Avec la tolérance

Question

Cette question est similaire à celui .

Nous savons tous ce que PointF est, ne pas nous? Ceci est la structure de données:

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

Comment mettre en œuvre IEqualityComparer<PointF> avec la tolérance? Disons que mon code Equals est comme ceci

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: Comment mettre en œuvre la GetHashCode correcte de sorte que pour un dictionnaire de PointF, j'accéder correctement l'élément

Je craque ma tête quelques jours mais ne peut pas trouver une solution satisfaisante.

Answer 1

Au lieu de définir la tolérance par la distance, vous pouvez placer les points dans une grille.
Si deux points sont dans la même cellule, ils sont considérés comme égaux et ont le même code de hachage.

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
}

---

Thèse:. Il n'y a pas de mise en œuvre et Equals GetHashCode qui répond à vos besoins

Preuve: Considérons les trois points suivants, A, B et C:

Selon vos besoins,

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)

Mais à partir de (iv) et (v) suivante

GetHashCode(A) == GetHashCode(C)

et ainsi

Equals(A, C) == true

ce qui contredit (iii) et (vi).

Depuis Equals et GetHashCode ne peut pas renvoyer des valeurs différentes pour les mêmes arguments, il n'y a pas mise en œuvre qui répond à vos besoins. q.e.d.

Answer 2

Je ne pense pas qu'il est possible parce que vous pourriez avoir une suite infinie de valeurs égales (dans les tolérances) à la valeur précédente et suivante dans la séquence mais pas une autre valeur et GetHashCode devrez retourner une valeur identique pour tous.

Answer 3

Eh bien, la réponse basée sur des grilles est bonne, mais parfois vous avez besoin de regrouper les points proches de toute façon, même si elles ne sont pas dans la même cellule de la grille. Mon approche consiste à mettre en œuvre ce avec un groupement: deux points sont dans le même groupe soit si elles sont proches ou il y a une séquence de points proches qui les relie. Cette sémantique ne peut se faire avec un bon IEqualityComparer, parce qu'il a besoin de connaître tous les éléments à l'avance avant de produire les groupes. Donc, je l'ai fait d'un simple opérateur de style LINQ GroupByCluster, qui réalise essentiellement cela.

Le code est ici: http://ideone.com/8l0LH . Il compile sur mon VS 2010, mais ne parvient pas à compiler sur Mono parce HashSet<> ne peut pas être converti implicitement IEnumerable<> (pourquoi?).

L'approche est générique et donc pas très efficace: il est du second degré de la taille d'entrée. Pour les types de béton, il peut être plus efficace: par exemple, pour T = deux, nous pouvons simplement trier le tableau d'entrée et ont des performances O(n log n). L'astuce analogue bien plus complexe est applicable pour les points 2D ainsi.

---

Notez de côté:. Votre proposition initiale est impossible de mettre en œuvre avec IEqualityComparer, puisque votre « égalité approximative » n'est pas transitif (mais l'égalité dans IEqualityComparer doit être)