Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: Mathematic/geometric/algorithm puzzle
Replies: 1   Last Post: Mar 25, 2013 12:23 PM

 James Waldby Posts: 511 Registered: 1/27/11
Re: Mathematic/geometric/algorithm puzzle
Posted: Mar 25, 2013 12:23 PM

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

--
jiw