## Top 5 Recent Articles

##### ARTICLES CATEGORIES

- Algorithms (15)
- All (399)
- Biography (1)
- Blog (44)
- Business Requirements (1)
- Commentary (1)
- Customers (2)
- Data Models (1)
- Education (2)
- GeoRaptor (13)
- Image Processing (2)
- Import Export (8)
- Licensing (2)
- Linear Referencing (4)
- Manifold GIS (3)
- Mapping (1)
- MySQL Spatial (7)
- Networking and Routing (including Optimization) (3)
- Open Source (18)
- Oracle Spatial and Locator (192)
- PostGIS (34)
- Published Articles (1)
- qGIS (1)
- Recommendations (1)
- Services (1)
- Software Change Log (1)
- Source Code (35)
- Space Curves (9)
- Spatial Database Functions (107)
- Spatial DB comparison (1)
- Spatial XML Processing (10)
- SQL Server Spatial (85)
- Standards (2)
- Stored Procedure (15)
- Tessellation or Gridding (10)
- Tools (2)
- Topological Relationships (1)
- Training (2)
- Triangulation (2)

# 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;

row | col | morton |
---|---|---|

0 | 0 | 0 |

1 | 0 | 2 |

2 | 0 | 8 |

3 | 0 | 10 |

0 | 1 | 1 |

1 | 1 | 3 |

2 | 1 | 9 |

3 | 1 | 11 |

0 | 2 | 4 |

1 | 2 | 6 |

2 | 2 | 12 |

3 | 2 | 14 |

0 | 3 | 5 |

1 | 3 | 7 |

2 | 3 | 13 |

3 | 3 | 15 |

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.

## Documentation

- MySQL Spatial General Function Documentation
- Oracle LRS Object Documentation
- Oracle Spatial Exporter Package Documentation
- Oracle Spatial Object Function Documentation
- Oracle Spatial Object Function Documentation (Multi Page Version)
- PostGIS pl/pgSQL Function Documentation
- SC4O Oracle Java Topology Suite (Stored Procedures) Package Documentation
- SQL Server Spatial General TSQL Function Documentation
- SQL Server Spatial LRS TSQL Function Documentation