Hashcode for geometries that differ only on their orientation

Question

I have a collection that contains geometries (usually (Poly)Lines). Now I want to implement a HashCode for these geometries in order to put them into the collection. To do so I have three members within every geometry that will not change and thus are suitable for a HashCode: the geometry-type (which is PolyLine for all geometries, the from- and the to-point)

So I wrote this code

int hash = 17;

// this hascode-implementation uses the geometry-type and the from- and toPoints of the geometry

hash = hash * 31 + this.Geometry.GeometryType.GetHashCode();
hash = hash * 31 + this.Geometry.FromPoint.X.GetHashCode();
hash = hash * 31 + this.Geometry.FromPoint.Y.GetHashCode();
hash = hash * 31 + this.Geometry.ToPoint.X.GetHashCode();
hash = hash * 31 + this.Geometry.ToPoint.Y.GetHashCode();

Now we have another prerequisite within our application which makes it impossible to me to write a hash-function: two geometries are also considered equal when they are contrary. Since every actual equal object MUST have the same hashCode I have to change the implementation so it allows diagonal collisions.

This means the following:

when fromPoint of geometry 1 equals toPoint from geometry 2 (and vice versa) also their hashCodes must be equal.

Which of the factors do I have to change in my implementation to enable diagonal collisions or am I totally whrong with my implementation /is there a better way to do this)?

Answer 1

For the swapped points to yield the same result, you need a mathematical operation where A op B == B op A and you need to apply it to both coordinates before adding the result to the hash.

I would try this:

hash = hash * 31 + (
       this.Geometry.FromPoint.X.GetHashCode()
       + this.Geometry.ToPoint.X.GetHashCode
);

This line returns the same result, no matter in which order you pass the X coordinate.

Note: If you add/remove lines of the polygon or move end points, then the hash code changes. So you must make sure that the geometry doesn't change as long as such an object is stored in a hash map/set.

If you need to change the geometry, you first have to remove the object from the hash map/set, change the geometry and add it again.

PS: The X in the last line of your code should be Y.

Answer 2

I haven't really understood the geometrical aspects of the problem you are describing, but here are a few thoughts:

• how many objects do you have? If it's something that fits into not too many, it might be acceptable to not worry too much about the hashcode implementation, just make it constant

• if the equals operation of any two geometries is non-trivial, what about wrapping them into an object where you have less problems talking about equality? e.g. new MyGeometry("an Id", aGeometry)? Implementing hashCode / equals should be trivial then.