Go to content Go to navigation and search

Home

Current PostGIS Blog Articles


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.

Morton key function for PostgreSQL/PostGIS

Wednesday October 03 2012 at 01:52

Keywordsspace curve morton key postgresql postgis
Summary

This article shows a Morton key function for PostGis and how to use it.

In my article on the creation and use of a space keys for the spatial sorting of spatial data I show how to implement a Morton key for Oracle Locator/Spatial using PL/SQL.

A function in pl/PgSQL for PostgreSQL/PostGIS is as follows:

  1. CREATE OR REPLACE FUNCTION st_morton (p_col int8, p_row int8)
  2.  RETURNS int8
  3. AS
  4. $$
  5. /*  this procedure calculates the Morton number of a cell
  6.     at the given row and col[umn]  
  7.     Written:  D.M. Mark, Jan 1984;
  8.     Converted to Vax/VMS: July 1985
  9.     Converted to PostgreSQL, Simon Greener, 2010
  10. */
  11. DECLARE
  12.    v_row          int8 := 0;
  13.    v_col          int8 := 0;
  14.    v_key          int8;
  15.    v_level        int8;
  16.    v_left_bit     int8;
  17.    v_right_bit    int8;
  18.    v_quadrant     int8;
  19. BEGIN
  20.    v_row   := p_row;
  21.    v_col   := p_col;
  22.    v_key   := 0;
  23.    v_level := 0;
  24.    WHILE ((v_row>0) OR (v_col>0)) LOOP
  25.      /* Split off the row (left_bit) and column (right_bit) bits and
  26.      then combine them to form a bit-pair representing the quadrant */
  27.      v_left_bit  := v_row % 2;
  28.      v_right_bit := v_col % 2;
  29.      v_quadrant  := v_right_bit + 2*v_left_bit;
  30.      v_key       := v_key + ( v_quadrant << (2*v_level) );
  31.      /* row, column, and level are then modified before the loop continues */
  32.      v_row := v_row / 2;
  33.      v_col := v_col / 2;
  34.      v_level := v_level + 1;
  35.    END LOOP;
  36.    RETURN (v_key);
  37. END;
  38. $$
  39.   LANGUAGE 'plpgsql' IMMUTABLE;

Now, let’s test it with some simple SQL:

  1. SELECT *
  2.   FROM (SELECT a.gcol,
  3.                b.grow,
  4.                st_morton( a.gcol, b.grow ) AS MortonKey,
  5.                ST_MakeBox2D(ST_MakePoint(a.gcol, b.grow)::geometry,
  6.                             ST_MakePoint(a.gcol+100, b.grow+100)::geometry)::geometry AS geometry
  7.           FROM (SELECT 0 + g AS gcol FROM generate_series(0,7,1) AS g) AS a,
  8.                (SELECT 0 + g AS grow FROM generate_series(0,7,1) AS g) AS b
  9.         ) AS foo
  10.  ORDER BY mortonkey, gcol;

Results

gcol grow mortonkey wktgeom
integer integer integer text
0 0 0 POLYGON ((0 0,0 0,0 0,0 0,0 0))”
1 0 1 POLYGON ((1 0,1 0,1 0,1 0,1 0))”
0 1 2 POLYGON ((0 1,0 1,0 1,0 1,0 1))”
1 1 3 POLYGON ((1 1,1 1,1 1,1 1,1 1))”
2 0 4 POLYGON ((2 0,2 0,2 0,2 0,2 0))”
3 0 5 POLYGON ((3 0,3 0,3 0,3 0,3 0))”
2 1 6 POLYGON ((2 1,2 1,2 1,2 1,2 1))”
3 1 7 POLYGON ((3 1,3 1,3 1,3 1,3 1))”
0 2 8 POLYGON ((0 2,0 2,0 2,0 2,0 2))”
1 2 9 POLYGON ((1 2,1 2,1 2,1 2,1 2))”
0 3 10 POLYGON ((0 3,0 3,0 3,0 3,0 3))”
1 3 11 POLYGON ((1 3,1 3,1 3,1 3,1 3))”
2 2 12 POLYGON ((2 2,2 2,2 2,2 2,2 2))”
3 2 13 POLYGON ((3 2,3 2,3 2,3 2,3 2))”
2 3 14 POLYGON ((2 3,2 3,2 3,2 3,2 3))”
3 3 15 POLYGON ((3 3,3 3,3 3,3 3,3 3))”
4 0 16 POLYGON ((4 0,4 0,4 0,4 0,4 0))”
5 0 17 POLYGON ((5 0,5 0,5 0,5 0,5 0))”
4 1 18 POLYGON ((4 1,4 1,4 1,4 1,4 1))”

I hope this is of use to someone.

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 for this, Please see my comment at http://evertpot.com/231/ for improvements to this.

— jimmy peter · 9 February 2015, 03:11 · #

Article Navigation:   Previous