Hash/key creation function for latitude longitude?

Question

Hello,

I have blocks of data associated with latitude/longitude values. I'd like to create a lookup key/hash value from the latitude/longitude value so it can be used as a lookup into a map or something similar.

I'm using negative values for West and South... therefore 5W, 10S is represented as -5, -10 in the program.

I'd like to be able to get the latitude/longitude values back from the key value if possible.

The derived value MUST be some sort of integer value.

I'm using C/C++ :)

Thanks, I'll be happy to answer any questions!

Answer 1

You are not really looking for a Hash (Hashes normally scatter the underlying keys, and also they allow for colisions).

Instead a simple formula like the following would do the trick, I think, and it is reversible.

[pseudo code]
Precision = 100       // lat and long precsion, boost to 1000 if need be
LatOffset = 1000      // Anithing above 180 would do

Key = ((int)(Lat * Precision) * LatOffset) + (int)(Long * Precision)

To reverse

Long = (Key Modulo (LatOffset * Precision)) Div Precision
Lat  = (Key Div (LatOffset * Precision)) Div Precision )

Edit: Oops, I didn't notice this was in C. Indeed, use jheddings' solution (or a variation thereof (with the requirement that the "hash" key be an integer).

Answer 2

Trivial solution: make a hash key out of the lat/long pair, and hash that. Then if you have the key, by definition you have the coordinates. Hash keys are fairly compact, e.g. eight bytes if each coordinate value is a 32-bit integer.

Non-trivial solution: use spatial hashing.

Answer 3

As mjv pointed out, a hash will typically obfuscate the original input data. Instead, it sounds like you are just looking to combine the values.

To keep it easy, you can just define a new type for your "hash":

typedef struct {
    float lat;
    float lon;
} latlon;

You can treat this as a 64-bit number. And use it as such:

float lat = -5.432;
float lon = 10.3423;
latlon pair = {
    .lat = lat,
    .lon = lon,
};

Answer 4

Are you 100% sure hashing is appropriate here? Hash lookups only work if you know the exact value of the key you are looking for, and (AFAIK) latitude/longitude values are not always known precisely.

For example, say you have a record stored under key (-5.432, 10.3423) and someone else wants to know what records are stored within in a 1.0 radius of (-5.0, +10.0). Or perhaps they want to look up the record, but due to floating point roundoff in their calculations, they have (-5.431999, 10.3423001) as their key value. Hashing can't help you in those cases. To do that sort of spatial/inexact lookup, you'd probably be better off with a more specialized data structure like octrees (or their two-dimensional equivalent).

Answer 5

You could also encode it in nicely into a 64-bit integer using some bit manipulation

longitude ranges from -180 to 180 so needs a minimum of 9 bits. lattitude rangs from -90 to +90 so needs a minimum of 8 bits. minutes go from 0 to 60 so require 6 bits. same for seconds.

9+12 = 21 bits for longitude and 20 bits for lattitude.

For subsecond precision you can then use 11 bit fixed point. this gives you accuracy down to a 2048th of a second.

SO to store a longitude or lattitude you could use a struct as follows

struct ALatLong
{
    int angle:9;
    int minutes:6;
    int seconds:6;
    int subSeconds:11;
};

struct LatAndLong
{
    ALatLong longitude;
    ALatLong lattitude;
};