Finding list of unique objects with a tolerance

user_10422354 0
Viewed 194

I have a list of points from which I want to extract only the unique elements. The point class is as follows

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

now two points for example p1(1,2,3) and p2(1.01,2,3.01) should be considered as same point. that is some tolerance is there. Now because of the tolerance I am not able to use c# distinct() method or any of the functions that use hascode. Is there any possible way by which I can get the the unique list with out having to use Bruteforce method and which will identify p1 and p2 as same point and will only keep one of them in the unique list

distinct c#
1 Answers

Alas, it's not possible even in the simplest 1d case (let Y and Z be equal for all the points). We can prove it by contradiction; let e be a positive tolerance, which means that

 p1 ~ p2

whenever

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

Every equality relation must meet three properties:

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

There are no problems with 1st and 2nd properties, but we can't meet the 3d one: counter example is three points A, B, C such that

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

So we have

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

However

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

Edit: You can try scaling as a partial solution. Points are equal if they are in the same (hyper-)cube e * e * ... * e where scale factor e is some kind of "tolerance". So, for

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

We can implement an equality comparer like this:

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

Usage

List<Point> original = ...

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

Another popular approach - clustering - can be, howw=ever, much difficult to implement. First, you group points into clusters (which can be huge, of different shapes etc.) then take "typical representatives" from each cluster (say, all all point which are on the border of their cluster).

user_23194070
Related