Go to content Go to navigation and search

Home

Current SQL Server Blog Articles

    SQL Server Spatial: Converting a LineString to COGO XML
    SQL Server Spatial: Creating (Multi)LineStrings geometries from COGO XML instructions
    New Version of Package of TSQL Spatial Functions
    Vectorize/Segmentize SQL Server 2012
    Coordinate Editing Functions for SQL Server Spatial
    Function to Scale a geometry object for SQL Server Spatial
    TSQL String Tokenizer Function for SQL Server
    geography/geometry to MBR helper functions
    generate_series for SQL Server 2008
    Extract Polygons from result of STIntersection in SQL Server Spatial
    Function to round ordinates of a SQL Server Spatial geometry object
    Extract elements of SQL Server Spatial geometry object
    Counting number of polygon rings SQL Server Spatial
    Filtering Polygon Rings in SQL Server Spatial
    Function to Move a geometry object in SQL Server Spatial
    Alternate Centroid Functions for SQL Server Spatial
    Function to Rotate geometry objects in SQL Server Spatial
    A GetVertices wrapper for DumpPoints in SQL Server 2008 Spatial
    Creating a Morton number Space Key generator for SQL Server
    Gridding a geometry or geography object (SQL Server Denali)
    On hinting spatial indexes
    Random Search Procedure (SQL Server 2008 Spatial)
    COGO: Converting (Google Earth) Formatted Longitude/Latitude points to decimal degrees (SQL Server)
    COGO: Convert Degrees, Minutes and Seconds values to Decimal Degrees
    COGO: DD2DMS Formatting a latitude/longitude decimal degree value
    COGO: Create point from bearing and distance
    COGO: Compute number of vertices required to stroke circle or circular arc
    COGO: Calculating the bearing between two points (SQL Server 2008 Spatial)
    COGO: Compute arc length subtended by angle centre of circle
    COGO: Compute chord length of segment of a circle (arc)
    COGO: Computing Arc To Chord (Arc2Chord) Separation
    COGO: Creating a stroked polygon from a circle's centre x,y and radius
    COGO: Finding centre and radius of a curve defined by three points: FindCircle function
    Identifying Tight Radius Curves sections within LineString geometry data
    Generating random point data for SQL Server 2008 Spatial
    New Presentation on Active (Searchable) Spatial Metadata for SQL Server 2008 Spatial and FreeText
    Checking is a column in a table or a view is of type geometry or geography
    Extracting geometry type string values from geometry/geography objects in SQL Server 2008 Spatial
    Vectorising geometry objects in SQL Server 2008
    MBR to geography/geometry helper functions
    Extracting geometry types from geometry/geography objects in SQL Server 2008
    Getting the number of coordinate dimensions of a geometry/geography object in SQL Server 2008
    A Dump Points Function for SQL Server 2008 Spatial
    toGeography and toGeography Conversion Functions for SQL Server 2008 Spatial
    Write text file with spatial data from SQL Server 2008
    Loading Shapefiles into Geography type column in SQL Server 2008
    Tip #6: Correcting invalid geometries
    Tip #5: Where or where has my little column gone
    Tip #4: What Coordinate System is that?
    Tip #3: What object is that?
    Tip #2: Spatial Indexing and Primary Keys
    Tip #1: SQL Server 2008 "Katmai" - Setting SRIDs

Search

    Browse

RSS / Atom

Email me

textpattern

Creative Commons License
All Blog Articles, Data Models and Free Source Code by Simon Greener, The SpatialDB Advisor is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

Creating a Morton number Space Key generator for SQL Server

Tuesday December 27 2011 at 23:46

Keywordsspace curve key morton number
Summary

This article shows how to construct a Morton Number space key value for a nominated cell in a grid.

Space curves are imaginary lines that systematically cover all tiles in an indexed space. The most well known in GIS is the Morton key. The utility of such a number can be seen though its implementing a form a space autocorrelation such that all geometries in an area are given a Morton number such that, when sorted, they appear next to each other in the sort order. Written to disk, such sorted geometries lie next to each other.

  1. USE [GISDB] -- Change this to your database
  2. GO
  3. SET ANSI_NULLS ON
  4. GO
  5. SET QUOTED_IDENTIFIER ON
  6. GO
  7. -- =============================================
  8. -- Author:    <Author,Simon Greener>
  9. -- Create date: <Create Date, 7th August 2010>
  10. -- Description: <Description, 7th August 2010>
  11. -- =============================================
  12. CREATE FUNCTION [dbo].[Morton] (@p_col INT, @p_row INT)
  13. RETURNS INT
  14. WITH EXECUTE AS CALLER,
  15.      RETURNS NULL ON NULL INPUT
  16. AS
  17. BEGIN
  18.   /* This procedure calculates the Morton number of a cell
  19.      at the given row and col[umn]
  20.      Written:  D.M. Mark, Jan 1984;
  21.      Converted to Vax/VMS: July 1985
  22.      Converted to Java: May 2007 (Simon Greener)
  23.      Converted to PL/SQL: September 2009 (Simon Greener)
  24.      Converted to TSQL: August 2010 (Simon Greener)
  25.   */
  26. BEGIN
  27.   DECLARE
  28.     @ROW       INT = abs(@p_row),
  29.     @col       INT = abs(@p_col),
  30.     @KEY       INT = 0,
  31.     @level     INT = 0,
  32.     @left_bit  INT,
  33.     @right_bit INT,
  34.     @quadrant  INT;
  35.     BEGIN
  36.       While ((@row>0) OR (@col>0))
  37.       BEGIN
  38.        /* Split off the row (left_bit) and column (right_bit) bits and
  39.           then combine them to form a bit-pair representing the
  40.           quadrant
  41.        */
  42.        SET @left_bit  = @ROW % 2;
  43.        SET @right_bit = @col % 2;
  44.        SET @quadrant  = @right_bit + 2*@left_bit;
  45.        SET @KEY       = @KEY + round(@quadrant * POWER(2,2*@level), 0, 1);
  46.        /*   row, column, and level are then modified before the loop
  47.             continues                                                */
  48.        IF ( @ROW = 1 AND @col = 1 )
  49.        BEGIN
  50.          SET @ROW = 0;
  51.          SET @col = 0;
  52.        END
  53.        ELSE
  54.          BEGIN
  55.            SET @ROW = @ROW / 2;
  56.            SET @col = @col / 2;
  57.            SET @level = @level + 1;
  58.          END;
  59.        END;
  60.      END;
  61.      RETURN @KEY;
  62.    END;
  63. END
  64. GO

Now for a simple test. (See MBR2GEOMETRY )

  1. USE [GISDB] -- Change this to your database
  2. GO
  3. SELECT foo.MortonKey, foo.geom
  4.   FROM (SELECT [GISDB].[dbo].Morton( a.gcol, b.grow ) AS MortonKey,
  5.          [GISDB].[dbo].MBR2GEOMETRY(a.gcol,b.grow,10.0,10.0,0) AS geom
  6.           FROM (SELECT 0 + g.IntValue AS gcol FROM generate_series(0,7,1) AS g) AS a
  7.                 CROSS APPLY
  8.                (SELECT 0 + g.IntValue AS grow FROM generate_series(0,7,1) AS g) AS b
  9.        ) foo
  10.  ORDER BY mortonkey;

This is what it looks like:

We can show the actual “curve” as a directed line through the morton numbers as follows. (The required function DumpPoints is described by following the link.)

  1. WITH morton_grid AS (
  2. SELECT foo.MortonKey, foo.geom
  3.   FROM (SELECT [GISDB].[dbo].Morton( a.gcol, b.grow ) AS MortonKey,
  4.          [GISDB].[dbo].MBR2GEOMETRY(a.gcol,b.grow,10.0,10.0,0) AS geom
  5.           FROM (SELECT 0 + g.IntValue AS gcol FROM [GISDB].[dbo].generate_series(0,7,1) AS g) AS a
  6.                 CROSS APPLY
  7.                (SELECT 0 + g.IntValue AS grow FROM [GISDB].[dbo].generate_series(0,7,1) AS g) AS b
  8.        ) foo
  9. )
  10. SELECT geometry::STGeomFromText('LINESTRING(' +
  11.        STUFF((SELECT ',' + a.coord
  12.                  FROM (SELECT m.MortonKey, STR(e.[x],5,1) + ' ' +  STR(e.[y],5,1) AS coord
  13.                  FROM morton_grid m
  14.                 CROSS apply
  15.                 [GISDB].[dbo].DumpPoints(m.geom.STCentroid()) e
  16.                        ) a
  17.                  ORDER BY ',' + STR(a.mortonkey,12,0)
  18.               FOR XML PATH(''), TYPE, ROOT).VALUE('root[1]','nvarchar(max)'),1,1,'')
  19.      + ')',0) AS geom;

Superimposing the curve over the grid of morton keys reveals:

I hope this is of use to someone out there.

Creative Commons License

post this at del.icio.uspost this at Diggpost this at Technoratipost this at Redditpost this at Farkpost this at Yahoo! my webpost this at Windows Livepost this at Google Bookmarkspost this to Twitter

Comment [1]

Thanks alot for your all workings… Included this article some others were very usefull for me….

— Kemal · 10 March 2014, 19:00 · #