Как реализовать IEqualityComparer<PointF> с допуском

StackOverflow https://stackoverflow.com/questions/2055422

  •  20-09-2019
  •  | 
  •  

Вопрос

Этот вопрос похож на тот, что здесь.

Мы все знаем, что ТочкаF это, не так ли?Это структура данных:

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

Как реализовать IEqualityComparer<PointF> с толерантностью?скажем, мой Equals код такой

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

Вопрос:Как правильно реализовать GetHashCode так что для словаря PointF, я правильно получу доступ к элементу?

Я ломаю голову несколько дней, но до сих пор не могу найти удовлетворительного решения.

Это было полезно?

Решение

Вместо определения допуска по расстоянию вы можете разместить точки в сетке.
Если две точки находятся в одной ячейке, они считаются равными и имеют одинаковый хеш-код.

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
}

Тезис: Нет реализации Equals и GetHashCode который соответствует вашим требованиям.

Доказательство: Рассмотрим следующие три точки: A, B и C:

Illustration

Согласно вашим требованиям,

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)

Но из (iv) и (v) следует

GetHashCode(A) == GetHashCode(C)

и таким образом

Equals(A, C) == true

что противоречит (iii) и (vi).

С Equals и GetHashCode не может возвращать разные значения для одних и тех же аргументов, не существует реализации, отвечающей вашим требованиям.q.e.d.

Другие советы

Я не думаю, что это возможно, потому что у вас может быть бесконечная последовательность значений, равных (в пределах допуска) предыдущему и следующему значению в последовательности, но не любому другому значению и GetHashCode нужно будет вернуть одинаковое значение для всех из них.

Что ж, ответ на основе сеток — это хорошо, но иногда вам все равно нужно сгруппировать близкие точки, даже если они не находятся в одной ячейке сетки.Мой подход заключается в реализации этого с помощью группировки:две точки находятся в одной группе, если они либо близки, либо существует последовательность близких точек, соединяющая их.Эту семантику невозможно реализовать с помощью надлежащего IEqualityComparer, поскольку ему необходимо заранее знать все элементы, прежде чем создавать группы.Итак, я создал простой оператор в стиле LINQ. GroupByCluster, что в основном и достигает этого.

Код здесь: http://ideone.com/8l0LH.Он компилируется на моем VS 2010, но не компилируется на Mono, потому что HashSet<> не может быть неявно преобразовано в IEnumerable<> (почему?).

Подход является универсальным и поэтому не очень эффективным:он квадратичен по размеру ввода.Для конкретных типов это можно сделать более эффективным:например, для T = double мы можем просто отсортировать входной массив и получить O(n log n) производительность.Аналогичный, но более сложный прием применим и для 2D-точек.

Обратите внимание:ваше первоначальное предложение невозможно реализовать с помощью IEqualityComparer, поскольку ваше «приблизительное равенство» не транзитивно (но равенство в IEqualityComparer должно быть так).

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top