TimeHorse wrote:Update: I think I have the equation for converting between the Map Data Grid, X and Y and longitude and latitude and rather than making anyone else suffer, let me spell it out here for all to see. This information wasn't meant to be proprietary, it was meant to be free as in speech, but in this case also free as in beer!

The Grid Data collectively stores a 25-bit number for the longitude (x) and a 25-bit number for the latitude (y). The North American Nissan LEAF maps only distend over a range from 172W to 52W Longitude and from 0N to 80N in Latitude. The North Pole is not part of the map, and neither is Iceland or Europe or the Prime Meridian. Thus one third of the Earth by Longitude (120 degrees or 432,000 arc-seconds) and almost half by Latitude (80 degrees or 288,000 arc-seconds). The mapping between x, y and Longitude, Latitude is a linear function mapping the 25-bit values to their degree, minute, second mapping, respectively, as follows:

Code: Select all

`x = (longitude + 172)*65,536 + 15,728,640`

y = latitude*98,304 + 16,777,216

longitude = (x - 15,728,640)/65,536 - 172

latitude = (y - 16,777,216)/98,304

This is clearer if hexadecimal is used:

Code: Select all

`x = (longitude + 172)*0x10000 + 0x0f00000`

y = latitude*0x18000 + 0x1000000

longitude = (x - 0x0f00000)/0x10000 - 172

latitude = (y - 0x1000000)/0x18000

Of course, that assumes you have x and y as the properly formatted, unsigned, 25-bit values. To get those you have to do quite a bit of jiggery-pokery. Specifically, the Data Grid is a negative, 32-bit value. I find it easier treat the grid data as an unsigned 32-bit value in my calculations so for instance -2,147,452,928 (-0x7fff8800) becomes 2,147,514,368 (0x80007800), specifically:

Code: Select all

`u = (grid_data & 0x7FFFFFFF) + 0x80000000`

grid_data = -(-u & 0x7FFFFFFF)

It has to be done this way to preserve the sign, otherwise the grid_data will lose the upper bits.

That resolved, I've observed that, starting from 0x80000000 as bit zero and 0x00000001 as bit 31, bits 1, 12, 13, 28 and 29 are never used. In other words, 0x400C000C is a mask for all the bits never used in the grid data. Likewise, 0 and 18 are always set (bit 0 means the number is always negative), in other words 0x80002000 is a mask for the always-on bits. Ignoring bits 0, 1 and 18 for the moment, what's clear with bits 12, 13, 28 and 29 is that they don't enter into the calculation of position. What you effectively have when you ignore those bits is:

for the format of the upper register of the x and y components, xh and yh, where each letter represents a bit in u starting with bit 0. The conversion is thus:

Code: Select all

`xh = ((u & 0xFFF0) >> 2) | (u & 0x0003)`

yh = (((u >> 16) & 0xFFF0) >> 2) | ((u >> 16) & 0x3

u = ((yh & 0x3FFC) << 18) | ((yh & 0x0003) << 16) | ((xh & 0x3FFC) << 2) | (xh & 0x0003)

where

**<<** means

*bitwise shift left*,

**>>** means

*bitwise shift right*,

**&** means bitwise

*and* and

**|** means bitwise

*or*.

Finally we have the Map Data X and Y components, which are each 11-bit, unsigned values, meaning they go from 0 to 2047; at 2048 the increment the high portion and go back to 0. We'll call these map X and Y points xl and yl respectively.Therefore:

Code: Select all

`x = (xh << 11) | xl`

y = (yh << 11) | yl

xh = x >> 11

xl = x & 0x7FF

yh = y >> 11

yl = y & 0x7FF

And from x and y you can now compute longitude and latitude as a floating-point number similar to the way its stored in the NavTech app. I've found this calculation to be accurate within 1 arc-second, the resolution of the longitude and latitude floating-point values, which represents about 30m (100 ft) of accuracy in latitude and less in longitude (by a factor of the cosine of the latitude). Ideally, this should be within a half a degree which would be within rounding error. Currently, the error represents as much as one arc-second difference between the Grid Data Longitude and Latitude and the stored Longitude and Latitude.

Anyway, that's the total skinny you've been waiting for. Hope this helps any would-be developer.

**Edit**: Fixed equation for u in terms of xh and yh thanks to kcarmich.