Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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?

share|improve this question
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 '13 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. –  lynxlynxlynx Mar 16 '13 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 '13 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)
share|improve this answer
    
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 '13 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 '13 at 8:38

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

http://svn.osgeo.org/grass/grass-addons/grass7/general/g.compare.md5/g.compare.md5.html

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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