On Sun, 24 Mar 2013 17:57:35 -0700, Alexander Gräf wrote: > I'm currently trying to uncover how a certain kind of spatial index is mapped to latitude and longitude -- I hope I selected the right group because it intersects mathematic, geometry and programming. > I sampled a significant amount of data (500+ data points) consisting of a key and longitude/latitude data in decimal. Here are some samples:
You refer to "a certain kind of spatial index". Does the kind of index have a name? Or do you merely mean the 64-bit binary or hex values before the "->" in the data? Where did the data come from? Is there any reason to believe that the keys are not just cryptographic hash values? If they are just hash values, trying to convert them back to original form is a lost cause.
> Binary = Hex -> LatHex,LongHex (Lat,Long (factor 1,000,000)) > 001000000000000000001011011110001010000000000000000000000000000 = 100005bc50000000 -> 000186a0,0001fbce (0.10,0.13) [snip 9 such lines] > 001000000000000000011101111101100110000000000000000000000000000 = 10000efb30000000 -> 00018c20,0002fe7a (0.10,0.20) > > I tried converting to base-4 and using them as quadkeys, tried Z-curve and Hilbert curves and other techniques. My first approach was to use lat/long to recreate the keys. As this clearly requires knowledge about the grid used, I tried the inverse way, and rebuilt the lat/long positions with the mentioned algorithms, and try to match the pattern of the resulting points to the already known lat/long. > Here is an image of the sample points, connected in increasing spatial index: > http://i.imgur.com/vyUHWLL.png > > As can be seen, no clear pattern of the above mentioned algorithms is visible. A pattern is visible on larger scale, but not persistent: > http://imgur.com/0SL7S2c > > I'm open for all kinds of suggestions. A full dump of the data can be found here, if anyone is interested in giving this a shot: > http://pastebin.com/CTQKcpY6