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?

Relativity

What are you trying to do? Are you storing paths? – Radiograph

Store and transmit GPS data on consumer devices. – Relativity

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).

Lunge

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.

Cosec

Maybe be a bit more careful to not obliterate the meaning of the difference between -77.521654 and 77.521654 – Jabalpur

I would suggest using a power-of-two multiplier rather than 10,000. Using 10,000 might be human-readable if you find that you have to hard-code numbers, but is fairly useless otherwise. Also, if you do use this method, ALWAYS use macros/inline functions to convert to/from double to ints. – Kay

unsigned isn't much chop since they can be negative. Also, .0001 degrees can be as much as 22 metres, and consumer GPS can be more accurate than that. So use signed ints, and multiply by at least 1000000 (the maximum value will still easily fit into signed 32 bits). – Lunge

Thanks, good points, I forgot to account for negative values, I've adjusted my answer. – Cosec

Oh, and don't cast to double and divide to display to the user - use integer divide and modulo, eg printf("Lat = %d.%06d\n", lat / 1000000, lat % 1000000) – Lunge

Good god, just use a float. It's more readable, for one thing, if you're storing the values in a database. – Chesser

In another post's comment, he indicated that it may be sent over the network. In which case, a fixed point representation may be simpler in the long run. – Cosec

Don't use that printf statement! The C modulus operator isn't really a modulus, it's a remainder operator, and gives negative results for negative inputs. For example, if lat=-1234567, then the code will print "-1.-234567". – Hazelhazelnut

Ahh, very good point. Throw an abs() around that, or labs() if you need to use longs (and adjust the format specifiers appropriately). – Lunge

Is there a typo? Should the 100000 (100,000) be 1000000 (1,000,000) – Scheller

@TalPressman I tried 2^24 and could not get the decimal part to come back out the same. EG 42.915512 was 42.15359742; using 10^6 however got out 42.915512. perl -E'$by=1_000_000; @c=(42.915512, -99.521654); say join ",", @c; sub to{ int($_[0]*$by)} sub fr{sprintf "%d.%d", int($_[0]/$by), abs($_[0])%$by} for(@c){ say(to($_)); say(fr(to($_))); }' works while changing $by=(1<<24) does not. – Richter

@TalPressman - IMHO, don't underestimate the value of human readable - nor of maintaining a multiple of 10. Its a nice sanity check to see values that are still in degrees (just missing the decimal point). And it round-trips to/from a nice display format with zero inaccuracy - so never have to worry about whether you've messed up rounding. – Mothball

Answer 3

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.

Gin

No, you need to store 40,075,020 different values to have one metre resolution, which requires 26 bits. – Lunge

Actually, a 32-bit IEEE float has 23 explicit bits of fraction (and an assumed 1) for 24 effective bits of significand. That is only capable of distinguishing 16 million unique values, of the 40 million required. Looked at another way, it can represent position to within 2.4 meter at the equator, which may still be close enough. – Balduin

I'd lean towards a fixed point representation since floats don't have advantages for this kind of application, and a signed 32-bit value has plenty of bits available to pick a convenient scale. – Balduin

@Balduin Don't forget the sign, that gives you another bit, since the default representation is ±180° for latitude and longitude. Since the accuracy is better if you are close to zero 32 bit floats gives you 1m accuracy except for ca 1/5 of the globe near the date line. – Radiograph

Depends on the application. WP suggests that "civilian GPS fixes under a clear view of the sky are on average accurate to about 5 meters", but with "specially equipped receivers" (e.g., in surveying) the "error might be as low as 2 millimeters". So pick your precision, and realize that next year a $5 cell phone will probably be able to beat it. :-) – Gainful

@Ken: no way in hell are civilian GPS devices accurate on average to 5 meters (in any event, accuracies are usually measured in a statistical sense with variances and standard deviations and so forth - a single number can't possibly reflect the accuracy). What they mean is: once in a while the device measures a position within 5 meters of the true position - kind of like how a broken clock is right twice a day. – Chesser

Answer 4

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:

1. Take two or more GPS devices out into one spot on a field somewhere, and jot down the coordinates measured by each device. Go back inside and plot the points from each device on a map (I think Google has something that does this for you). You'll be suprised at how far apart the points are (even though they're all supposed to be measuring the exact same spot).
2. Take your (allegedly) most accurate device, and place it somewhere where it can get a satellite fix but won't get rained on, and record a series of measurements taken over a couple of days. Plot all of the readings (as in #1). Again, you'll be surprised by how the points (which should all be the same or nearly the same) wander all over the map, sometimes by as much as a couple hundred feet.

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.

Chesser

Good point - I guess the question could be rephrased as "Whats the minimum accuracy required for consumer gps devices?" – Relativity

the the heck downvoted all the answers?! Personally I think both yours and mine were valid answers. – Cosec

I've had people in the real world get particularly angry with me for puncturing the GPS accuracy myth (and then I take their money). And I've encountered people on StackOverflow who feel that 32-bit floats belong in the same category as vacuum tubes. So this question is the perfect storm, in a sense. :) – Chesser

Answer 5

Assuming the earth is a perfect sphere (it is not, but close enough) with a radius ‘R’ of 3959 miles (or ×5280 ft/mi = 20903520 ft), the circumference is 131340690 feet (using 2×PI×R).

360 degrees of longitude covers 131340690 feet. 180 degrees of latitude covers 65670345 feet.

If you want to store lat/lng down to an accuracy of 3 feet, you need to be able to store 43780230 (131340690/3) longitude value and 21890115 (65670345/3) latitude values. 43780230 requires 25.38 bits (log(43780230)/log(2)) to store and 21890115 requires 24.38 bits (log(21890115)/log(2)) to store – or just under 50 bits (or 6.25 bytes).

So the obvious question becomes, if you want to store latitude and longitude in just 6 bytes, what will the accuracy be? Well, 6 bytes is 48 bits. That means 23.5 bits for latitude and 24.5 bits for longitude (longitude has twice as many values, which is just one bit and 24.5-23.5=1 bit). So 23.5 bits allows you to represent a number from 0 to 11863282 (11863283 values). And 65670345 feet divided by 11863283 values is 5.53 feet (and the same accuracy value for longitude).

THE BOTTOM LINE: So, if you can live with 5.5 feet of accuracy for both latitude and longitude, you can pack both values into just six bytes.

*A SIDE NOTE: Regarding comments that latitude and longitude are horrible for storing the positional information around a sphere (because there is less information to store at the poles) – well, those comments don’t hold up to the math! Let’s figure it out. Let’s say we want to design a new perfect system that can record and place a stake in the ground in the center of every square foot of earth. The surface area of earth (with a R of 3959 miles; formula for surface area of a sphere) is 5490965469267303 SQ FT – that many stakes requires 52.29 bits to represent. Now the existing latitude and longitude system uses a rectangular system. The width of the rectangle is the circumference of the earth and height of the rectangle is 1/2 the circumference) – which is 131340690 * 65670345 (see far above), or 8625188424838050 SQ FT – which requires 52.94 bits to represent (this system places ‘too many’ stakes in the ground around the poles). So, the shocking answer is that both the new perfect system, and the old lat/lng system, would BOTH require 53 actual bits to store a single location on earth, down to 1 foot accuracy!

Ewaewald

Answer 6

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

Sandhi

Answer 7

If you are storing large arrays of these values, there are a few simple tricks if you do a delta compression, and store deltas, you can greatly reduce the size of a data stream. You can do deltas from a "key point"

K D D D D D D D D D D K D D D D ...

k + d get you to any d point

The deltas all reference the previous K, so to reconstruct any point, you need a K and a D

or you can do incrimental deltas

K I I I I I I I I I I K

This may take multiple sums to get to the desired position. but the data is smaller overall. SO to reconsturct

k+i+i+i to get to the 4th point

Finally you can combine both

K D I I I D I I I D I I I K

This is like mpeg-2 with IPB frames, but this way you are never more than 4 sums to any position, and you get the some of the benefit of Delta and Incrimental Compression.

Selfanalysis

Answer 8

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.

Newberry

Answer 9

Because I needed it here's the python code for Jerry Jongerius's answer that represents Lat/Lon values with 6 Bytes and an accuracy of around 1.7m near the equator using 23.5 and 24.5 bits:

import struct

NBYTES=6
LATVALS=int(2**(NBYTES*4-0.5))
LONVALS=int(2**(NBYTES*4+0.5))

def serialize_gps(latlon):
    lat=(int(latlon[0]*LATVALS/180)+LATVALS//2)%LATVALS
    lon=(int(latlon[1]*LONVALS/360)+LONVALS//2)%LONVALS
    return struct.pack("!Q",lat*LONVALS+lon)[8-NBYTES:]

def deserialize_gps(b):
    if len(b)!=NBYTES:
        raise Exception("len(b)!=NBYTES")
    c=struct.unpack("!Q",(b"\x00"*6+b)[-8:])[0]
    lat=(c//LONVALS-LATVALS//2)*180/LATVALS
    lon=(c%LONVALS-LONVALS//2)*360/LONVALS
    return (lat,lon)

s=serialize_gps((47.55754133918577,10.74961245059967))
print(deserialize_gps(s))
#(47.557526866719776, 10.749611216389258)

Alejandraalejandrina

Answer 10

Multiplying latitude and longitude values by 10,000,000 (10^7) is a good approach to achieve a higher precision within the int32_t range. With this scaling factor, you can represent latitude and longitude coordinates with 7 decimal places of precision. Here's how you can do it:

1. For Latitude:

   • Scale your latitude values by multiplying them by 10,000,000 (10^7).
   • This will effectively convert the latitude range from -90.0000000 to +90.0000000 degrees to -900,000,000 to +900,000,000 as integers within the int32_t range.

2. For Longitude:

   • Scale your longitude values by multiplying them by 10,000,000 (10^7).
   • Then, shift the scaled values to ensure they fit within the int32_t range.
   • Map the longitude range from -180.0000000 to +180.0000000 degrees to -1,800,000,000 to +1,800,000,000 within the int32_t range.

Should be correct right?

Adiaphorous

What about using the magic number 11930464.71 when converting (i.e. 2**31/180)? Would give you slightly more precision (but practically no difference) as well as wrapping around nicely for angles outside the supported range – Sucker

Answer 11

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).

Midwife

-1: Apples and oranges: Looking at the table in the article, at level 16, which gives us a resolution of 2.4 meters/px, the map is 16,777,216 pixels wide (2^24), so at zoom level 16, we need 24 bits to store each lat/long value, i.e. 48 bits to store both. – Belay

Answer 12

I agree with Sam Mason. Just use however many bits/bytes you need to get your required angular precision. Latitude and Longitude are angles. Take your total number of bits and interpret them as a signed (or unsigned) fraction of 2*pi (or 360 degrees). It automagically takes care of going around the earth as well.
If you use 32 bits (let's assume signed), the least significant bit represents 1,4629 nanoradians or 527 nanodegrees, which will give you a worst case accuracy in the region of 10mm at the equator. 180 degrees will be the same as -180 degrees (0x80000000) and 360 degrees will be the same as 0 degrees (0x00000000) without any checks or conversions when adding or subracting.

Burtburta

Answer 13

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.

Compensation

Storing X/Y coordinates for a sphere just doesn't work. At all. You lose a lot of precision near the sphere's intersection with the XY plane, and you can't reconstruct the Z coordinate -- you only get a half of a sphere. If you're looking for uniformity, use three dimensional cartesian coordinates. Otherwise, lat/long is a good way of storing it. – Hazelhazelnut

Wow, you should give Garmin a call and explain to them how "terrible" latitude and longitude are for positional information. What were they thinking all these years? – Chesser

UTM uses a similar approach with its Easting and Northing coordinate pairs, so X/Y "coordinates" do work for spheres. It's all a matter of projection. – Midwife

myforwik: your approach still has problems, though. As Dietrich mentions, your version of X/Y is not a good projection. You need flatten to a 2D plane, not to a 3D cube. – Midwife

Programming Pearls (2nd Edition) (ACM Press) (Paperback) is an excellent book which discusses conversion to x,y,z to reduce the number of expensive trig operations which occurred for one particular application of map data. – Lorri

Earth is not a sphere it is a geoid. Its radius is different in different locations. You need x,y,z to know the r at that point. Therefore it is not possible to deduce z by knowing only x and y. – Flagellate

@Szere: I think most of us know the Earth is not a perfect sphere. I was just using Dietrich's wording. Besides, just because the Earth is not a sphere does not mean that it cannot be approximated by a sphere. – Midwife

Actually I didn't just 'make this up'. My gps stores data this way. It has a look up table for radius in its rom. Any error in radius is only going to be a tiny factor anyway. It works out where you are in the hemispheres by simply asking the user what countery/region they are in, or where the sun is in the sky. – Gunpowder