Finding distinct Points in a list (using 2 predicates)

Question

Lets say that I have a List of a custom "Point" class (I know there is one in System.Drawing, but lets say I need a custom one). Now this list can sometimes have the same points, so for example, say it is set up like this:

List<customPoint> myPoints = new List<customPoint>();
myPoints.Add(new customPoint(1,5));
myPoints.Add(new customPoint(1,5));
myPoints.Add(new customPoint(2,3));
myPoints.Add(new customPoint(4,9));
myPoints.Add(new customPoint(8,7));
myPoints.Add(new customPoint(2,3));

And later I need to do some calculation, but I do not need duplicates. What would be a more elegant way to make a new list of unique points than this:

List<customPoint> uniquePoints = new List<customPoint>();

for(int i; i < myPoints.Count; i++)
{
    Boolean foundDuplicate = false;    

    int tempX = myPoints[i].X;
    int tempY = myPoints[i].Y;        

    for(int j=0; j < uniquePoints.Count; j++)
    {
        if((tempX == uniquePoints[0].X) && (tempY == uniquePoints[0].Y))
        {
            foundDuplicate = true;
            break;
        }            
    }
    if(!foundDuplicate)
    {
        uniquePoints.Add(myPoints[i]);
    }        
}

I know it is messy, but that is why I am asking if there is a more elegant way. I looked at the Linq "Distinct" command, but it does not appear to work, I guess there's something in their object instantiation that is still unique.

Does your `customPoint` class (which should be `CustomPoint` to follow naming conventions) override `Equals` and `GetHashCode` appropriately? — Jon Skeet, Apr 26 '13 at 18:57
Here's a link [Distinct](http://stackoverflow.com/questions/998066/linq-distinct-values) to a previous discussion along with a link to the msdn doc on distinct — user1376713, Apr 26 '13 at 18:57

score 1 · Answer 1 · answered Apr 26 '13 at 18:54

1

What did you try using LINQ that didn't work? The code below should do it:

var uniquePoints = myPoints.Distinct();

answered Apr 26 '13 at 18:54

Abe Miessler

82,532
99
305
486

1

I suspect the OP called `myPoints.Distinct()` and ignored the return value. – Jon Skeet Apr 26 '13 at 18:57
Or that he hasn't overridden Equals/GetHashCode properly, of course :) – Jon Skeet Apr 26 '13 at 19:01
@JonSkeet That was indeed the case, at least on the GetHashCode, I was not aware I could override that until I asked this question. I did do what Abe Miessler suggested, and without overriding those it did not work. How would you generate a hash such that it would be unlikely to get different points would have unique codes, especially if I was comparing (2,1) to (1,2)? – Xantham Apr 26 '13 at 19:55

I4V · Accepted Answer · 2013-04-26T19:19:43.130

1) After adding these methods to your customPoint

public override int GetHashCode()
{
    return X.GetHashCode() * 19 + Y.GetHashCode();
}

public override bool Equals(object obj)
{
    var other = obj as customPoint;
    return this.X == other.X && this.Y == other.Y;
}

You can use Linq's Distinct method.

var distinctPoints = myPoints.Distinct().ToList();

2) You can use the Anonymous type comparison trick without overriding any method.

var distinctPoints = myPoints.GroupBy(m => new { m.X, m.Y })
                             .Select(x => x.First())
                             .ToList();

3) You can also do it by writing a custom IEqualityComparer

public class MyEqualityComparer : IEqualityComparer<customPoint>
{
    public bool Equals(customPoint a, customPoint b)
    {
        return a.X == b.X && a.Y == b.Y;
    }

    public int GetHashCode(customPoint other)
    {
        return other.X.GetHashCode() * 19 + other.Y.GetHashCode();
    }
}

var distinctPoints = myPoints.Distinct(new MyEqualityComparer()).ToList();

I had done the Equals (but using the IEquatable), but not the hash code. I had also looked into GroupBy, but was having a bit of trouble understanding the syntax of other questions that used it in a similar fashion. I am a bit new to hashcodes, so I am curious, why is the X multiplied by 19 in this case? — Xantham, Apr 26 '13 at 19:51
@Xantham it is a random prime number, it would even work if you wrote `return 0;`. A good hashing algorithm may improve the performance that's all. All you have to ensure is that if two objects are equal then their hash codes must be the same.(But Not Necessarily the Other Way Around ) — I4V, Apr 26 '13 at 20:20

score 0 · Answer 3 · answered Apr 26 '13 at 18:58

The Distinct method would be a good way to go, but in order to use it as you'd like, you must either implement Equals and GetHashCode on your object, or create an IEqualityComparer<customPoint> and pass that into the Distinct method. For your case, it would probably make sense to implement those methods on your object. From the documentation:

The default equality comparer, Default, is used to compare values of the types that implement the IEquatable<T> generic interface. To compare a custom data type, you need to implement this interface and provide your own GetHashCode and Equals methods for the type.

score 0 · Answer 4 · answered Apr 26 '13 at 19:05

I did this in LinqPad, so excuse the Dump()...but here's a way to implement your customPoint class:

void Main()
{
    var myPoints = new List<customPoint>();
    myPoints.Add(new customPoint(1,5));
    myPoints.Add(new customPoint(1,5));
    myPoints.Add(new customPoint(2,3));
    myPoints.Add(new customPoint(4,9));
    myPoints.Add(new customPoint(8,7));
    myPoints.Add(new customPoint(2,3));

    myPoints.Distinct().Dump();
}


public class customPoint {
    public int X;
    public int Y;

    public customPoint(int x, int y){
        X = x;
        Y = y;
    }

    public override Boolean Equals(Object rhs) {
        var theObj = rhs as customPoint;

        if(theObj==null) {
            return false;
        } else {
            return theObj.X == this.X && theObj.Y == this.Y;
        }
    }

    public override int GetHashCode() {
        return X ^ Y;
    }
}

Finding distinct Points in a list (using 2 predicates)

4 Answers4