Implementing equality for 2d lines

Question

I have simple class defining 2d line:

public class Line {
    public double X1 { get; set; }
    public double Y1 { get; set; }
    public double X2 { get; set; }
    public double Y2 { get; set; }
}

My primary goal is to get different lines from List using .Distinct(). In my case two lines are equal if theirs coordinates are equal regardless direction (line 1,2 -> 3,4 equals to 3,4 -> 1,2). I going to implement Equals like:

public override bool Equals(object obj) {
    if (obj as Line == null) { return false; }
    var second = (Line)obj;
    if (this.X1 != second.X1 && this.X1 != second.X2) { return false; }
    if (this.Y1 != second.Y1 && this.Y1 != second.Y2) { return false; }
    if (this.X2 != second.X2 && this.X2 != second.X1) { return false; }
    if (this.Y2 != second.Y2 && this.Y2 != second.Y1) { return false; }
    return true;
}

but I have no idea how to implement GetHashCode (as I understand it's necessary to make it in case of using Distinct())

Maybe you can use an IEqualityComparer? http://stackoverflow.com/questions/13331985/how-do-i-use-a-custom-comparer-with-the-linq-distinct-method — Gusman, Mar 12 '16 at 10:15
Possible duplicate of [GetHashCode Guidelines in C#](http://stackoverflow.com/questions/462451/gethashcode-guidelines-in-c-sharp) — Red, Mar 12 '16 at 10:15
if you make it `return 0` all the time it will work but performance would be problem. the time complexity would be equal to `O(n)`. you can make hashcode to pass parametesr through some formula and return the result. it will greatly improve the performance. for example `return X1 + X2 + Y1 + Y2`. or you can consider the orders too like `X1 + X2 << 1 + Y1 << 2 + Y2 << 3`. note that if you make formula to have less hash collisions ,performance would be better. hash collision means if two different object return same hash code. btw the algorithm generating the hashcode also affects performance — M.kazem Akhgary, Mar 12 '16 at 10:26

spender · Accepted Answer · 2016-03-12T11:04:15.587

This becomes a bit easier if you first define a Point, then define your Line in terms of 2 Points.

Now, to calculate a reliable (but unaffected by direction) hash of a Line, make sure you order your points consistently when calculating the hash.

Putting this all together into a complete implementation (which also covers operator == and !=):

public class Point
{
    public double X { get; set; }
    public double Y { get; set; }

    protected bool Equals(Point other)
    {
        return X.Equals(other.X) && Y.Equals(other.Y);
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;
        if (obj.GetType() != this.GetType()) return false;
        return Equals((Point) obj);
    }

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

    public static bool operator ==(Point left, Point right)
    {
        return Equals(left, right);
    }

    public static bool operator !=(Point left, Point right)
    {
        return !Equals(left, right);
    }
}

public class Line
{
    public Point Point1 { get; set; }
    public Point Point2 { get; set; }

    protected bool Equals(Line other)
    {
        return Equals(Point1, other.Point1) && Equals(Point2, other.Point2) 
             || Equals(Point1, other.Point2) && Equals(Point2, other.Point1);
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;
        if (obj.GetType() != this.GetType()) return false;
        return Equals((Line) obj);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            var orderedPoints =
                new[] {Point1, Point2}.OrderBy(p => p != null ? p.X : 0)
                                      .ThenBy(p => p != null ? p.Y : 0).ToList();
            var p1 = orderedPoints[0];
            var p2 = orderedPoints[1];
            return ((p1 != null ? p1.GetHashCode() : 0)*397) 
                   + (p2 != null ? p2.GetHashCode() : 0);
        }
    }

    public static bool operator ==(Line left, Line right)
    {
        return Equals(left, right);
    }

    public static bool operator !=(Line left, Line right)
    {
        return !Equals(left, right);
    }
}

I changed a detail of the GetHashCode implementation to use `+` instead of `*`, otherwise 0 coordinates would mess up the calculation. — spender, Mar 12 '16 at 11:04

Implementing equality for 2d lines

1 Answers1