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 11: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 morton (p_col int4, p_row int4)
  2.  RETURNS int4
  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          int4 := 0;
  13.    v_col          int4 := 0;
  14.    v_key          int4;
  15.    v_level        int4;
  16.    v_left_bit     int4;
  17.    v_right_bit    int4;
  18.    v_quadrant     int4;
  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 gcol, grow, MortonKey, geometry
  2.   FROM (SELECT a.gcol,
  3.                b.grow,
  4.                gis.morton( a.gcol, b.grow ) AS MortonKey,
  5.                ST_MakeEnvelope(a.gcol, b.grow, a.gcol+1, b.grow+1, 0) AS geometry
  6.           FROM (SELECT 0 + g AS gcol FROM generate_series(0,7,1) AS g) AS a,
  7.                (SELECT 0 + g AS grow FROM generate_series(0,7,1) AS g) AS b
  8.         ) AS foo
  9.  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

Article Navigation:   Previous