I would like to take geometries from a vector dataset and reduce them to a hash. This hash would then be used to verify the integrity of that data and also identify identical geometries.

Do any appropriate algorithms exist that could be used? What pitfalls could I encounter?

  • 4
    You might be interested in my article on vector steganography (in Directions Magazine) for an overview of just a few of the issues involved in a closely related application, that of hiding messages in vector data.
    – whuber
    Mar 16, 2013 at 21:37
  • What everything do geometries need to satisfy to be considered equal? If there is no rotation involved, you could start by looking at WKB and extending it so you can compare translated geometries. Mar 16, 2013 at 23:07
  • "simplest thing that could possibly work" would be to use a standard hash (e.g. CRC32 or MD4 if you don't need any security properties, or a SHA256 if you need one or more security properties). As lynxlynxlynx pointed out though, geometries are floating point data, so you need to be careful about comparison for "equality".
    – BradHards
    Mar 17, 2013 at 5:44

2 Answers 2


and also identify identical geometries.

You cannot rely on hashcodes for identification. In the case of a hash collision you could get the same hashcode for different objects, so you'll always need a more expensive comparison method as post-processing. But of course, you could tune your hashing method in order to reduce hash collisions.

If you want to make it simple just use MD5 or whatever hash, but you could reduce the probability of a hash-collision more. If you don't have translated or rotated geometries and you want an integer hashcode your method could look like:

int hash = numberOfPoints * 37;
hash += geometryType * 37;
for(point : points) {
     hash = hash XOR geohash(point.lat, point.lon)

For the geohash method also have a look into a spatial key ('binary geohash') which is more memory efficient and more precise if the area boundaries are smaller than world boundaries. You can also take a look into my Java implementation.

You could even further reduce the probability of a hash collision if you are using the differences of the points and calculate some center point:

int hash = numberOfPoints;
hash += 37 * geometryType;
hash = hash XOR geohash(someCenterPoint.lat, someCenterPoint.lon);
for(point : points) {
   hash += 37 * latToInteger(previousPoint.lat - point.lat);
   hash += 37 * lonToInteger(previousPoint.lon - point.lon);

To convert e.g. the latitude into an integer you could do:

latAsInt = latitudeFloatValue * (Integer.MAX / 90)

Or for the longitude:

lonAsInt = longitudeFloatValue * (Integer.MAX / 180)
  • I'll admit I'm not an expert on hashes, but in practice, people commonly rely on hashes for identification - in part because the probability of obtaining a collision is so low. A more expensive method of identification would give better results, but I think you could also use a hashing algorithm with a larger results space (SHA1, SHA256) to aid that as well. Whether or not the more complex comparison becomes fast enough vs. hashing at that point, I don't know.
    – nicksan
    Mar 20, 2013 at 3:09
  • I'm not an hash-expert myself :) ! and you'r indeed right that collisions for SHA-1 (and even MD5) are rahter rare. But one advantage of my specific hash calculations could be (not tested it though!) that they are faster to calculate. BTW: the int hash value can be increased to a long or even byte array
    – Karussell
    Mar 20, 2013 at 8:38

In the GRASS GIS software, we use MD5 to check if two maps are identical:


In your case the attached DB (attributes) also needs to be checked.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.