Top 5 Recent Articles
- Algorithms (13)
- All (407)
- Biography (1)
- Blog (44)
- Business Requirements (1)
- Commentary (1)
- Customers (2)
- Data Models (1)
- Education (2)
- GeoRaptor (5)
- Image Processing (2)
- Import Export (5)
- Licensing (2)
- Linear Referencing (3)
- Manifold GIS (3)
- Mapping (1)
- MySQL Spatial (7)
- Networking and Routing (including Optimization) (3)
- Open Source (16)
- Oracle Spatial and Locator (178)
- PostGIS (33)
- Published Articles (1)
- Recommendations (1)
- Services (1)
- Software Change Log (1)
- Source Code (35)
- Space Curves (9)
- Spatial Database Functions (101)
- Spatial DB comparison (1)
- Spatial XML Processing (10)
- SQL Server Spatial (General) (83)
- SQL Server Spatial (LRS) (38)
- Standards (1)
- Stored Procedure (15)
- Tessellation or Gridding (9)
- Tools (2)
- Training (2)
Geocoding Points Against a Grid of Cells/Tiles With/out Spatial Operators
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.
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.