So implementieren IEqualityComparer Mit Toleranz

Question

Diese Frage ist ähnlich dem hier .

Wir wissen alle, was PointF ist, nicht wahr? Dies ist die Datenstruktur:

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

Wie IEqualityComparer<PointF> mit Toleranz implementieren? Sagen wir, mein Equals Code wie dieser

ist

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

Frage: Wie der richtigen GetHashCode implementieren, so dass für ein Wörterbuch von PointF, werde ich das Element zugreifen richtig

ich den Kopf ein paar Tage knacken, aber noch keine zufriedenstellende Lösung finden.

Answer 1

Statt die Definition der Toleranz durch den Abstand, könnten Sie die Punkte in einem Raster platzieren.
Wenn zwei Punkte in der gleichen Zelle sind, sind sie als gleich betrachtet und haben den gleichen 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
}

---

Arbeit:. Es gibt keine Implementierung von Equals und GetHashCode die Ihren Anforderungen entspricht

Beweis: Beachten Sie die folgenden drei Punkte A, B, und C:

Wie pro Ihre Anforderungen,

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)

Aber aus (iv) und (v) folgt

GetHashCode(A) == GetHashCode(C)

und damit

Equals(A, C) == true

welche widerspricht (iii) und (vi).

Da Equals und GetHashCode können keine unterschiedlichen Werte für die gleichen Argumente zurückgeben, gibt es keine Implementierung, die Ihren Anforderungen entspricht. q.e.d.

Answer 2

Ich glaube nicht, es möglich ist, weil Sie eine unendliche Folge von Werten aufweisen könnten, die (innerhalb der Toleranz) gleich zum vorherigen und nächsten Wert in der Folge aber nicht jeder anderer Wert und GetHashCode müßten einen identischen Wert zurück für alle von ihnen.

Answer 3

Nun, die Antwort basierend auf Gittern ist gut, aber manchmal müssen Sie Gruppe die engen Punkte trotzdem, auch wenn sie nicht in der gleichen Rasterzelle sind. Mein Ansatz ist dies mit einer Gruppierung zu implementieren: zwei Punkte in der gleichen Gruppe sind, wenn entweder sie in der Nähe sind, oder es ist eine Folge der engen Punkte verbindet sie. Diese Semantik kann nicht mit einem richtigen IEqualityComparer getan werden, weil es alle Elemente im Voraus wissen muss, bevor die Gruppen zu erzeugen. Also ich habe einen einfachen LINQ-Stil Operator GroupByCluster getan, was diese im Grunde erreicht.

Der Code ist hier: http://ideone.com/8l0LH . Es kompiliert auf meinem VS 2010, aber nicht auf Mono kompilieren, weil HashSet<> nicht implizit in IEnumerable<> umgewandelt werden (warum?).

Der Ansatz ist generisch und damit nicht sehr effizient: es ist quadratisch auf Eingabegröße. beispielsweise für T = verdoppeln können wir einfach irgendwie das Eingabearray und O(n log n) Leistung haben: Für die konkreten Typen kann es effizienter gemacht werden. Die analoge obwohl komplizierter Trick ist für 2D-Punkte als auch.

---

Hinweis zur Seite. Ihre ursprüngliche Aussage nicht möglich ist, mit IEqualityComparer zu implementieren, da Ihre „ungefähre Gleichheit“ nicht transitiv ist (aber die Gleichheit in IEqualityComparer muss so sein)