Introduction

This article compares two methods for encoding a point within a grid. One uses the target grid’s metadata (anchor point, cell size, rotation angle), the other the SQL Server STContains operator.

A lot of what this article covers is covered in other places where discussion occurs about space curves (Morton, Hilbert) or where one needs to encode a latitude longitude point to its Google Maps/Microsoft Bing grid reference.

This article covers the generation and use of user defined grids. In particular it describes the encoding of a point to the cell it falls within.

A grid is defined as being a collection of grid cells, created by a tiling process, that are organised in a rectilinear way. The grid cells have extension in both the X (col) and Y (row) dimensions. Each cell must have the same dimensions as all other cells. That dimension is defined by X and Y distance (normally in meters) but they can be different e.g, X of 100m and Y of 5m. There can also be a different number of rows compared to columns. Grids can be created at any rotation angle.

The following functions enable the creation by the customer of a grid over a defined area or geometry.

• STTileByNumGrids — Covers supplied geometry object with a mesh of a specific number of times in X and Y.
• STTileGeogByPoint — Creates grid of tiles in geographic space anchored to a supplied origin.
• STTileGeomByPoint — Creates mesh of tiles in geometric space anchored to a supplied origin.
• STTileGeom — Covers envelope of supplied geometry with a mesh of tiles of size TileX and TileY.
• STTileXY — Covers supplied envelope (LL/UR) with a mesh of tiles of size TileX and TileY.
• STTiler — Covers supplied envelope (LL/UR) with a mesh of tiles of size TileX and TileY, and writes them to a new table created with the supplied name.

Problem

Grids are predominantly used to “index” spatial objects. For example, in an archaeological dig, the location of a found object is defined by the grid cell in which it is found (unless one uses very high precision GPS to generate a very precise coordinate).

In this situation, the grid is over water, and is used to record ships passing in and out of cells over time.

Now, as the ship is moving, a grid cell reference must be calculated and stored against the ship’s point object.

Later on, analysis of ship traffic can be carried out using the grid cell as an aggregation shape: potentially a big data problem.

Now, the problem is how to geocode the ship with its grid cell.

Now, I hear you say, that this is trivial: just use a spatial contains operator (in SQL Server Spatial this is STContains). This is indeed true but the volume of data is such that a potential performance issue arises.

STContains is insufficient to encode all ship points: let me show you why.

Why?

The following example shows how STContains works for points that have an inside relationship with a grid cell polygon (points and boundaries have insides), but fails when it falls on a boundary (a boundary with an adjacent cell or on the corner of four cells): while the polygon has a boundary, points do not, so there is no relationship.

Now, let’s test some pretend ship positions against a small grid of cells to show these issues.

Firstly, let us first start with a simple grid.

Grid Definition or Metadata

The metadata that defines our simple grid is (see INPUTS):

****f* TILING/STTileXY (2008)
 *  NAME
 *    STTileXY -- Covers supplied envelope (LL/UR) with a mesh of tiles of size TileX and TileY.
 *  SYNOPSIS
 *    Function STTileXY (
 *               @p_ll_x   float,
 *               @p_ll_y   float,
 *               @p_ur_x   float,
 *               @p_ur_y    float,
 *               @p_TileX  float,
 *               @p_TileY  float,
 *               @p_rx     float,
 *               @p_ry     float,
 *               @p_rangle float,
 *               @p_srid   int = 0
 *             )
 *     Returns @table table
 *    (
 *      col  Int,
 *      row  Int,
 *      geom geometry
 *    )
 *  INPUTS
 *    @p_ll_x  (float) - Spatial Extent's lower left X ordinate.
 *    @p_ll_y  (float) - Spatial Extent's lower left Y ordinate.
 *    @p_ur_x  (float) - Spatial Extent's upper right X ordinate.
 *    @p_ur_y  (float) - Spatial Extent's upper right Y ordinate.
 *    @p_TileX (float) - Size of a Tile's X dimension in real world units.
 *    @p_TileY (float) - Size of a Tile's Y dimension in real world units.
 *    @p_rX    (float) - X ordinate of rotation point.
 *    @p_rY    (float) - Y ordinate of rotation point.
 *    @p_rangle (float) - Rotation angle expressed in decimal degrees between 0 and 360.
 *    @p_srid    (int) - Geometric SRID.

The generation code is shown in the following SQL.

select CAST(t.col as varchar(3)) + ',' + CAST(t.row as varchar(3)) as cell_reference,
       t.geom as cell
  from dbo.STTileXY(
             /* @p_ll_x   */ 0.0,
             /* @p_ll_y   */ 0.0,
             /* @p_ur_x   */ 4.0,
             /* @p_ur_y   */ 4.0,
             /* @p_TileX  */ 1.0,
             /* @p_TileY  */ 1.0,
             /* @p_rx     */ 0.0,
             /* @p_ry     */ 0.0,
             /* @p_rangle */ 0.0,
             /* @p_srid   */ 0
       ) as t
Go

Point Positions And Grid

Now let us generate three points which lie in specific positions in the grid:

• inside a cell, or
• On the boundary between two cells, or
• On the corner of four cells.

We will now test those three points against the grid.

with points as (
  select 'Inside a Cell' as point_type, geometry::Point(2.5,2.5,0) as geom
  union all
  select 'Corner 4 Cells' as test, geometry::Point(1,1,0) as geom
  union all
  select '2 Cells' as test, geometry::Point(2,1.5,0) as geom
)
select test, t.geom.STAsText() as geom from points as t
union all
select NULL, t.geom.STAsText() as Geom  /* For Visualisation Only */
  from dbo.STTileXY(
             /* @p_ll_x   */ 0.0,
             /* @p_ll_y   */ 0.0,
             /* @p_ur_x   */ 4.0,
             /* @p_ur_y   */ 4.0,
             /* @p_TileX  */ 1.0,
             /* @p_TileY  */ 1.0,
             /* @p_rx     */ 0.0,
             /* @p_ry     */ 0.0,
             /* @p_rangle */ 0.0,
             /* @p_srid   */ 0
       ) as t
Go

(Grid Cells in original data – removed for blog article purposes.)

This is visualised as follows.