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?
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.
Floats would be way more than sufficient for storing GPS coordinates, even if consumer-level GPS devices had anywhere near the accuracy claimed for them. If you don't believe this is true, try these two simple experiments:
I've been writing applications for GPS-enabled PDAs for years, and I've verified this for dubious customers over and over again (I've even won bets this way). There are higher-quality GPS devices out there that do achieve better accuracy than this, but the better accuracy is achieved with more expensive chipsets, and the devices are left in one spot for days or even weeks, with the readings averaged over time.
A four-byte float is far more accurate than the devices themselves. It would of course not hurt you at all to use a double instead, as long as the 2X factor isn't a problem for you.
The circumference of the Earth is approx. 40.000 km or 24900 miles.
You need one-meter accuracy (3ft) to be able to out-resolve gps precision by an order of magnitude.
Therefore you need precisiton to store 40.000.000 different values. That's at minimum 26 bits of information. A 32 bit float or int will do well.
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).
I am suprised that no one has posted the fact that long/lat is a terrible way to store data on a sphere (someone did mention that longitude requires less precision near the poles).
Basically you can store data position as X and Y co-ords in meters. Imagine a cube around the earth that exactally fits (haha ok almost fits it). You only need store X and Y position, not all 3 co-ords, because the 3-rd co-ord can come from the redius of the earth, r = square root[x^2 + y^2 + z^2].
So convert your lat/long to x/y in meters. You will only need a total of 12756200m per co-ord (thats the diameters of the earth). So your total value will only have to span 0 to 25,512,400 (someone else claimed 40,000,000 because they were using long/lat) to be accurate to +/- 0.5m.
That will result in just 25 bits per position. If I were you I would just do accuracy to within 2m and use 24 bits per position, as that is a tidy 3 bytes.
Also if you are storing way-point information on a path, you can store each way-point as an offset from the last waypoint. Like start with a 24bit x/y co-ord. And then have a 16bit 'update' that adjusts the position by adding/subtracting x/y meters. 16bit would allow a waypoint update to be over 400m away. So if you know the device is not meant for planes and updates every so often, this might be acceptable too.
23 bits of precision at 179 degrees of longitude gives under 10-meter accuracy, which is the best that ordinary GPS devices give. At the equator:
% gps distance "0.0, 179.0" "0.0, $((179 * (1 + 2**-23)))"
From 0.0, 179.0 to 0.0, 179.00002133846283 is 7.79 feet E
From 0.0, 179.0 to 0.0, 179.00002133846283 is 2.38 meters E
So an IEEE 754 single-precision floating-point number, known to your C compiler as float, wil be just adequate for representation. Beware of using floats for extended computations! Rounding error may eat your lunch. Consult a numerical analyst.
You can pack both the latitude and longitude values in a single 32-bit integer with a resolution of at worst ~2.4 meters/pixel (at the equator) if you use a recursive tiling system. Using two bits per level, you can store 16 levels in 32 bits. You can get an idea of how that would work looking at this article about Virtual Earth's tiling system. This uses Mercator, so it would give you problems for the poles. You could instead use a different projection and still get very similar results.
This can also be used for a rough filter to find any points within a given parent tile since the first N bits will be the same (and so search becomes bit masking).
In Garmin's IMG map format they store coordinates inside bounding boxes using floats to set the edges of the boxes. Coords within the boxes are defined using a variable number of bits that are are just linear between min and max values depending on the precision needed.
For example: minlat=49.0, maxlat=50.0, minlon=122.0, maxlon=123.0, number of bits=16
So a value of:
32768,32768 would be converted to 49.5, 122.5
16384,0 would be 49.25, 122.0
If you need less precision, the same output could be generated with a number of bits=4
8,8 would be converted to 49.5, 122.5
4,0 would be 49.25, 122.0