CODEWITHSUNDEEP
c#hashgeometryequalshashcode
NMO
NMO

Reputation: 766

Equals and hashcode for vertices

I have a couple of vertices which I want to put into a Hashtable. Vertices which are really close to each other are considered as the same vertex. My C# vertex class looks like this:

public class Vertex3D
{
    protected double _x, _y, _z;
    public static readonly double EPSILON = 1e-10;

    public virtual double x 
    {
        get { return _x;}
        set { _x = value; }
    }

    public virtual double y
    {
        get { return _y; }
        set { _y = value; }
    }

    public virtual double z
    {
        get { return _z; }
        set { _z = value; }
    }

    public Vertex3D(double p1, double p2, double p3)
    {
        this._x = p1;
        this._y = p2;
        this._z = p3;
    }

    public override bool Equals(object obj)
    {
        var other = obj as Vertex3D;

        if (other == null)
        {
            return false;
        }
        double diffx = this.x - other.x;
        double diffy = this.y - other.y;
        double diffz = this.z - other.z;
        bool eqx = diffx > -EPSILON && diffx < EPSILON;
        bool eqy = diffy > -EPSILON && diffy < EPSILON;
        bool eqz = diffz > -EPSILON && diffz < EPSILON;
        return eqx && eqy && eqz;
    }

    public override int GetHashCode()
    {
        return this.x.GetHashCode() ^ this.y.GetHashCode() ^ this.z.GetHashCode();
    }

    public override string ToString()
    {
        return "Vertex:" + " " + x + " " + y + " " + z;
    }

Now lets say I put the following two vertices into a dictionary (a dictionary is a hashtable which doesn't allow null keys):

    Dictionary<Vertex3D, Vertex3D> vertexList = new Dictionary<Vertex3D, Vertex3D>();
    Vertex3D v0 = new Vertex3D(0.000000000000000037842417475065449, -1,   0.00000000000000011646698526992202));
    Vertex3D v1 = new Vertex3D(0, -1, 0));
    vertexList.Add(v0, v0);
    vertexList.Add(v1, v1);

The problem is that my implementation of equals and hashcode is faulty. The above two vertices are considered as equal because the distance to each other is smaller than EPSILON. BUT they don't return the same hashcode.

How do I implement equals and hashcode correctly?

Upvotes: 1

Views: 398

Answers (2)

Ben Voigt
Ben Voigt

Reputation: 283733

Hashtables require equivalence classes, but your Equals() is not transitive. Therefore you cannot use a hashtable for this purpose. (If, for example, you allowed nearby objects to compare equal by rounding to lattice points, you would have transitivity and equivalence classes. But then there still would be arbitrarily close points, down to the precision of your representation, which fell on opposite sides of a threshold and thus in different equivalence classes)

There are other data structures, such as octtrees, which are designed to accelerate finding nearby points. I suggest you use one of those.

Upvotes: 1

supercat
supercat

Reputation: 81217

Generally, mutable-thing references should only be considered equivalent if they both refer to the same object. Only references to immutable things should use any other definition of equality. It would be helpful if Object included virtual functions to test for equivalence in the scenario where two references are held by separate objects, neither of which will expose its reference to anything that might mutate it. Unfortunately, even though the effectively-immutable-instance-of-mutable-type pattern is very common (nearly all immutable collections, for example, use one or more mutable-type objects such as arrays to hold their data) there's no standard pattern for equivalence testing with it.

If you want to store vertices in a dictionary using Object.Equals for equality testing, it should be an immutable type. Alternatively, you could define a custom IEqualityComparer<T> for use with the dictionary, but you should be aware that Dictionary should only be used to find perfect matches. If you want to be able to find any point that's within EPSILON of a given point, you should use a which maps rounded values to lists of precise values (values should be rounded to a power of two that's at least twice as great as epsilon). If adding or subtracting EPSILON from some or all of the coordinates in a point would cause it to be rounded differently, the point should be included in the dictionary, rounded every such possible way.

Upvotes: 1

Related Questions