Geocoding Points Against a Grid of Cells/Tiles With/out Spatial Operators

Space Key/Curve

One problem with using column and row references of a grid is that simply that there are two of them!

Wouldn’t it be would be better if we could use a single reference?

We can, and the way to do it is via use of a Space Key/Curve.

What is a Space Key/Curve?

I’ve written about Space Keys/Curves before and it is now good to see them appearing in things like Bing Maps and for ORDER BY sorting by PostGIS.

Space Key values are generally created from the column/row references that index a grid and its cells. There are many Space Keys (thanks to Wikipedia); here are three:

• Hilbert Curve — First described by the German mathematician David Hilbert in 1891, as a variant of the space-filling Peano curves
• Peano Curve — Similar to Morton by Italian Mathematician Giuseppe Peano (1858 – 1932)
• Morton Curve— Named after Guy Macdonald Morton, who first applied the order to file sequencing in 1966

There is an implementation of Morton Curve in the SQL Server Spatial TSQL tools.

Here’s an example of how to use it.

with data as (
   select 0.0 as rAngle,
          10.0 as tileX,
          10.0 as tileY,
          4 as numTiles,
          geometry::Point(0.5,0.5,0) as origin
), tiles as (
   select col, row, [dbo].[STMorton](col, row) as morton, geom
     from data as a
          cross apply
           [dbo].[STTileGeomByPoint] (
            a.origin,
            'LL',
            /*@p_numTileX*/ a.numTiles,
            /*@p_numTileY*/ a.numTiles, /* 4 x 4 cells */
            /*@p_TileX   */ a.tileX,
            /*@p_TileY   */ a.tileY,
            /*@p_rAngle  */ a.rAngle,
            /*@p_AsPoint*/  0
           ) as t
)
select * from tiles;

Which looks like this:

Let’s add to this image the space curve (or line) that traverses these grid cells. The space curve can be computed as follows.

use devdb
go
With data as (
  select x.IntValue as x, y.IntValue as y
    from dbo.generate_series(0,3,1) as x,
         dbo.generate_series(0,3,1) as y
)
select geometry::STGeomFromText(
        'LINESTRING(' + STRING_AGG(dbo.STPointGeomAsText(point,12,12,12),',') WITHIN GROUP (order by hkey)+ ')',
        0).STBuffer(0.0075) as line
  from (select geometry::Point(d.x,d.y,0) as point, 
               dbo.STMorton(d.x,d.y) as hKey
         from data as d
        ) as f
union all
select geom
  from [dbo].[STTileGeomByPoint] (
          geometry::Point(-0.5,-0.5,0) ,
          'LL',
          /*@p_numTileX*/ 4,
          /*@p_numTileY*/ 4,
          /*@p_TileX   */ 1.0,
          /*@p_TileY   */ 1.0,
          /*@p_rAngle  */ -90.0,
          /*@p_AsPoint*/  0
           ) as t
go

Let’s now overlay this on the grid we generated above.

Terminology

The space key is the index, the space curve is a line created by walking through the cells in space key order.

Now let’s apply the space key concept to the grid we will now create.