Latitude/Longitude storage and compression in C

Question

Does anyone know the most efficient representation for lat/long coordinates? Accuracy level should be enough for consumer GPS devices.

Most implementations seem to use double for each unit, but I'm suspicious that a float or fixed point format should be sufficient. I'd be curious to hear from anyone who has tried to compress and or store large arrays of these values.

EDIT:

In other words, whats the minimum accuracy required to represent lat/long for a consumer level device?

Answer 1

Personally I would use a 32 bit decimal fixed point representation, dividing by 1,000,000 as per Evan's answer and my comments.

However, if space is truly at a premium, here are some additional ideas:

• You could use a 26 bit fixed point representation on the wire. This will require marshalling and unmarshalling the latitude and longitude into a large array of bytes, but will save you 12 bits for each location over the 32 bit value representation - almost a 19% saving, so it might well be worthwhile.

• You could take advantage of the fact that longitude values need less precision as you get closer to the poles - they only need 26 bits worth at the equator. So you could write a scheme where the number of bits used to encode the longitude depends on the value of the latitude.

• If your data has other compressible attributes - say, all the points are usually quite close together - you could take specific advantage of those, like using a delta coding scheme (where each point other than the first can be encoded as a delta from the last point).

Answer 2

EDIT: added some points from comments, 32-bit values should be capable of offering enough precision.

I would use a 32-bit fixed point representation. If the values are:

42.915512,-99.521654 I would store the values * 100000 in int32_t's (they can be negative).

int32_t lat = 42915512; int32_t lon = -99521654; 

This is a good compromise between simple and accurate (5 decimal points is usually good enough, you could always bump it up to 1000000 to get 6 if needed).

To display to the user, do what caf suggests:

... to display to the user - use integer divide and modulo, eg printf("Lat = %d.%06d\n", lat / 1000000, abs(lat) % 1000000)

These will also be comparable/sortable in an efficient way since the relative ordering will be preserved.

EDIT: an additional benefit is that it can sent over a network or stored to disk in a binary format in a portable way.