Нахождение списка уникальных объектов с допуском - PullRequest
Новая
       39

Нахождение списка уникальных объектов с допуском

3 голосов
/ 05 августа 2020

У меня есть список точек, из которых я хочу извлечь только уникальные элементы. Класс точки выглядит следующим образом 

class Point
{
   double X;
   double Y;
   double Z;
}

теперь две точки, например, p1 (1,2,3) и p2 (1.01,2,3.01), должны рассматриваться как одна и та же точка. это некоторая терпимость. Теперь из-за допуска я не могу использовать метод c# independent () или любую из функций, использующих hascode. Есть ли какой-либо способ, с помощью которого я могу получить уникальный список без использования метода Bruteforce и который будет идентифицировать p1 и p2 как одну и ту же точку и сохранит только один из них в уникальном списке

1 Ответ

3 голосов
/ 05 августа 2020

Увы, а невозможно даже в простейшем 1d случае (пусть Y и Z будут равны по всем пунктам). Мы можем доказать это от противного; пусть e будет положительным допуском , что означает, что 

 p1 ~ p2

каждый раз, когда 

 |p1.X - p2.X| <= e

Каждое отношение равенства должно соответствовать трем свойствам:

  1. Reflexive: A ~ A
  2. Symmetri c: if A ~ B then B ~ A
  3. Transitive: if A ~ B and B ~ C then A ~ C

Нет проблем с 1-м и 2-м свойствами, но мы не можем удовлетворить 3-й: пример счетчика - это три точки A, B, C такие, что 

B.X = A.X + e
C.X = B.X + e = A.X + 2 * e

Итак, у нас есть 

|A.X - B.X| = e <= e, so A ~ B
|B.X - C.X| = e <= e, so B ~ C

Однако 

|A.X - C.X| = 2 * e > e, so A !~ C

Изменить: Вы можете попробовать масштабирование как частичное решение. Очки равны, если они находятся в одном (гипер -) кубе e * e * ... * e где масштабный коэффициент e - это своего рода «допуск». Итак, для 

class Point
{
    double X;
    double Y;
    double Z;
}

мы можем реализовать компаратор равенства следующим образом: 

public class PointEqualityComparer : IEqualityComparer<Point> {
  private double m_Scale;

  private long Scale(double value) => (long)Math.Round(value / m_Scale);

  public PointEqualityComparer(double scale) {
    m_Scale = scale > 0
      ? scale
      : throw new ArgumentOutOfRangeException(nameof(scale));
  }

  public bool Equals(Point left, Point right) {
    if (ReferenceEquals(left, right))
      return true;
    else if (null == left || null == right)
      return false;

    return Scale(left.X) == Scale(right.X) &&
           Scale(left.Y) == Scale(right.Y) &&
           Scale(left.Z) == Scale(right.Z);
  }

  public int GetHashCode(Point obj) => obj == null
    ? 0
    : Scale(obj.X).GetHashCode() ^ 
      Scale(obj.Y).GetHashCode() ^ 
      Scale(obj.Z).GetHashCode();
}

Использование 

List<Point> original = ...

List<Point> unique = original
  .Distinct(new PointEqualityComparer(1e-3))
  .ToList();

Другой популярный подход - кластеризация - может быть, но когда-либо, очень сложно реализовать. Сначала вы группируете точки в кластеры (которые могут быть огромными , разной формы и c.), Затем берете «типичных представителей» из каждого кластера (скажем, все точки, которые находятся на границе их кластер).

...