1

I would like to be able to map geographic points from WGS84, I believe, formatted for ms sql server, to the set of cells it would touch if the same coordinate pair were to be tessallated into an sql server spatial index with 4 hiearchical grids of 256 cells each.

The sql server 2008 spatial index does not ideally suit our needs because it doesn't support the use of both geographic and non-geographic data within the same index.

If we knew how to perform the translation ourselves it would seem like that would allow us to bypass the above limitation.

this page shows visually how a geography point can be mapped to planar cells which can be individually encoded as a sequence of from 1 and up to 4 positive integers. For an example of numbered cells please refer to the section "Deepest-Cell Rule" within the linked page.

I'm basically looking for pseduo-code on how to do just that.

Any help will be appreciated and if you know the algorithmic details that would be very much appreciated.

Thank you in advance.

JM Hicks
  • 1,282
  • 1
  • 11
  • 22

1 Answers1

1

A simple solution is to interleave x-and y co-ordinate, like in a morton curve a.k.a z curve. You can verify it by calcuting the upper bound using the most significant bit. Bing maps uses a morton curve:http://msdn.microsoft.com/en-us/library/bb259689.aspx but a hilbert curve is much more complicated but also better in most cases. In hilbert curve it's using a gray code for the co-ordinate. Here is some code example:Mapping N-dimensional value to a point on Hilbert curve.

Community
  • 1
  • 1
Micromega
  • 12,486
  • 7
  • 35
  • 72
  • Please re-check the OP. The OP asks for something that produces the exact same tesselations, not something analogous, as sql server 2008's spatial index produces. OP aside, maybe this post might help someone else. For whatever it's worth, I did eventually come up with a similar solution on my own that gives me a single btree seek on the combination of latitude and longitude followed by partial scan of rows, within the surface-of-interest, pre-ordered by paging requirements, with no trig, div, or fp operations. It's not posted here though as it doesn't really answer the OP. – JM Hicks May 19 '14 at 12:43
  • @JMHicks:Hilbert curve is using a gray code. Isn't that what you need? Also, in the link it's code about the morton curve:http://msdn.microsoft.com/en-us/library/bb259689.aspx. If my answer is helpful please consider to vote! – Micromega May 19 '14 at 15:06