Choosing a type to store location coordinates in iOS
Intro to location coordinates
I am building offline maps engine for iOS based on OpenStreetMap data. I use raw data, stored in XML. Each node in it has latitude and longitude written in degrees, which means ranges from −180.0° to +180.0° for longitude and from −90.0° to +90.0° for latitude.
App implements Mercator map projection, so, spheric angular coordinates are converted into Euclidian coordinates for 2D space which both (for lat and lon) result in a range from −π to +π.
These formulas are used to convert coordinate values from degrees into Euclidian map projection coordinates:
latEuclidian = −log2( tan( π / 4 + 0.5 × latDeg × π / 180 ) )
lonEuclidian = lonDeg × π / 180
It is important to notice, that latitude is processed for range of −85.0° to +85.0° only, because values more close to 90.0° produce super high intermediate values which aim to eternity and at the same time these coordinates are not important for maps because they relate to areas not attended by people usually.
I have implemented tiled map rendering (for productivity considerations) and it means, that map on each discrete zoom level will have different number of tiles to be rendered and at the same time the whole map will have different size in pixels. For example, map for zoom level
z = 0 will have just one tile for the whole world, and map for zoom level
z = 3 will have
8×8 = 64 tiles totally. In brief, map side has length of
2^z tiles at each zoom level, to render the whole world.
In order to have the same address for every pixel on the map for each zoom level and to have clear and simple computation routines, coordinates are processed into normalized values. It means, that the whole world has size of 1.0×1.0 square at any zoom level, and each coordinate in it (lat and lon) is inside the range from 0.0 to 1.0. So, it never matters, what is the size of the world: you can address every certain point in it by the same normalized value.
Formulas to convert Euclidian coordinates into normalized:
latNormalized = (latEuclidian + π) / (2 × π)
lonNormalized = (lonEuclidian + π) / (2 × π)
Working with normalized coordinates made obvious (in the beginning) to use Double type to store and process coordinates. World is extremely large and we need good precision to address rendered pixels properly.
What is Double? It uses 64 bits to store data: 1 bit for sign, 11 bits for exponent and 52 bits for fraction. This data type offers possibility to store floating-point number of about 15 significant decimal digits. It is highly precise and it seems to be great to operate with highly accurate geo data. I could not take Float type, because it offers storage just for 6 decimal digits, and it is not enough for me.
Double seemed to be working fine until I’ve come across some strange issues, which turned to be the consequences of choosing this data type.
Accuracy problems with transmitting data to GPU
I am using Metal engine to render data by GPU, and it offers several types of data transmitting, but for floating point format there is no Double: it offers Float type only. Float is used inside Metal to process pixel coordinates. Metal handles screen as a surface of normalized coordinates: it does not address pixels, it addresses normalized location on the screen from −1.0 to 1.0.
At first I’ve just converted Double to Float (a bit stupid :) for me) and sent it to the buffer.
It seemed to work for middle zoom values mainly (up to 17-th zoom level), but soon I’ve noticed, that for some reason at higher zoom levels (20–21) objects become messy: their geometry distorts. At first I thought, that there was a computation error, but soon I’ve come to conclusion, that problem is related to the data accuracy.
Float is OK for the GPU screen model itself, because it handles screen resolution only and precision of 6 decimal digits is more, than enough. But if we are talking about the whole world resolution, 6 decimal digits are not enough at all.
Accuracy problems for coordinates comparison
Double values are stored as fraction, multiplied by exponent, but the main difference with integer types is that decimal digits are generated not by multiplication (2^i) logic, but by division (2^−i) logic. The problem with division, is that it does not produce that accurate results to be precisely transformed into integers or floating-point numbers, rounded to the certain digit. Division produces numbers, which have certain precision. It might be very small, but still it is not zero.
I had some routines in geometry processing, which used coordinate comparison, and it came to the point, that 0.4 was never more equal to the other 0.4. It happened, because coordinate, which was 0.4 at the beginning, turned out to be 0.40000000000000002 or 0.39999999999999998 at last, which is not equal to 0.4 surely. So, my logic failed.
The solution turned out to be not so obvious: I’ve found out that both problems can be solved by switching to Integer type, stored in 32 bits (Int32 or UInt32).
I’ve decided to implement up to 21 zoom levels in my map. At first I’ve taken this value, because it is just the same, as Apple Maps have. But then I saw that it is absolutely enough to render most accurate OpenStreetMap data. If we use tiles of 128 points each, then 21 zoom levels result in 6 points of the screen per 1 physical meter. Pretty enough for current maps accuracy.
World side in tiles for zoom
z = 21 will be 2²¹ tiles. For device resolution of 3 pixels per point (highest resolution for today: screen of iPhone 7 Plus) the side of the world in pixels for zoom
z = 21 will be:
2²¹ × 128 pt × 3 px / pt = 805 306 368 pixels.
So, the most accurate coordinate for our map at highest resolution requires just 9 decimal digits to store data or 30 binary digits (30 bits). This data can be completely stored in Int32 or UInt32 data types which propose 32 bits.
To convert normalized coordinate from Double to UInt32 I just use multiplier of 1`000`000`000 in this manner:
latUInt32 = UInt32( latDouble × 1`000`000`000 )
Sending UInt32 coordinate data to GPU
In order to get accurate coordinates transformations on screen after scale and rotation I had to carefully convert data from integer to floating point (shrink 9 decimals to 6) without losing data precision. Too early or too late conversion will result in poor data precision.
For lower zoom levels (i.e.
z = 8) world has rather small pixel dimensions, so, upper digits are mainly used. But for highest zoom levels (i.e.
z = 21) we need lower digits, while upper ones does not really matter (because in every single moment just a small part of the world is displayed). The problem of correct precision conversion for higher zoom levels is solved by subtracting coordinates of screen center from coordinates of each rendered vertex on the screen.
So, the algorithm is:
Step 0: store data in UInt32
Step 1: write data to buffer
Step 2: fetch data from buffer in GPU in int format
Step 3: subtract coordinates of screen center
Step 4: convert type to float and make all further computations.
UInt32 makes all comparison operations absolutely accurate: 0.4 value is converted to 400`000`000 and it has precision of 0 (zero). So, comparison always succeeds.
On the other hand it results in another problem: coordinates, which earlier seemed to be different (because they had difference somewhere in 12-th digit, for example) now become the same (because they are rounded to the 9-th digit). So, you have to design your logics accurately to process correctly equal coordinates for different nodes.
Other Int32 benefits
Int32 and UInt32 require less digits to be stored, so, coordinates, stored in integer value, occupy less space, than the same data, given in Double precision. We pay by less accuracy, but it is still enough for our purposes.
Int32 and UInt32 use 32 bits of memory while Double uses 64 bits of memory, so Integer values are expected to be processed faster (I did not notice it yet, but anyway).
Download the app with my maps engine: