Como implementar o iEqualityComparer com tolerância

Question

Esta questão é semelhante a aquele aqui.

Todos nós sabemos o que Pointf É, não é? Esta é a estrutura de dados:

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

Como implementar IEqualityComparer<PointF> com tolerância? Vamos dizer meu Equals Código é assim

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

Pergunta: Como implementar o correto GetHashCode de modo que para um dicionário de PointF, Vou acessar o elemento corretamente?

Eu quebro minha cabeça alguns dias, mas ainda não consigo encontrar uma solução satisfatória.

Answer 1

Em vez de definir a tolerância à distância, você pode colocar os pontos em uma grade.
Se dois pontos estiverem na mesma célula, eles são considerados iguais e têm o mesmo código de 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
}

---

Tese: Não há implementação de Equals e GetHashCode Isso atende às suas necessidades.

Prova: Considere os três pontos a seguir, A, B e C:

Conforme seus 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)

Mas de (iv) e (v) segue

GetHashCode(A) == GetHashCode(C)

e assim

Equals(A, C) == true

que contradiz (iii) e (vi).

Desde Equals e GetHashCode Não pode retornar valores diferentes para os mesmos argumentos, não há implementação que atenda aos seus requisitos.QED

Answer 2

Eu não acho que seja possível, porque você pode ter uma sequência infinita de valores que são iguais (dentro da tolerância) ao valor anterior e próximo na sequência, mas não em qualquer outro valor e GetHashCode precisaria devolver um valor idêntico a todos eles.

Answer 3

Bem, a resposta baseada em grades é boa, mas às vezes você precisa agrupar os pontos de fechamento de qualquer maneira, mesmo que não estejam na mesma célula da grade. Minha abordagem é implementar isso com um agrupamento: dois pontos estão no mesmo grupo se estiverem próximos ou houver uma sequência de pontos próximos que os conectam. Esta semântica não pode ser feita com um adequado IEqualityComparer, porque precisa conhecer todos os itens com antecedência antes de produzir os grupos. Então eu fiz um operador simples no estilo LINQ GroupByCluster, que basicamente consegue isso.

O código está aqui: http://ideone.com/8l0lh. Ele compila no meu VS 2010, mas não consegue compilar em mono porque HashSet<> não pode ser implicitamente convertido para IEnumerable<> (Por quê?).

A abordagem é genérica e, portanto, não é muito eficiente: é quadrática no tamanho da entrada. Para os tipos de concreto, pode ser mais eficiente: por exemplo, para t = dobrar, podemos apenas classificar a matriz de entrada e ter O(n log n) atuação. O truque análogo, embora mais complicado, também é aplicável a pontos 2D.

---

Nota de lado: sua proposição inicial é impossível de implementar com IEqualityComparer, uma vez que sua "igualdade aproximada" não é transitiva (mas a igualdade em IEqualityComparer tem que ser assim).