Morton key function for PostgreSQL/PostGIS

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:

 CREATE OR REPLACE FUNCTION st_morton (p_col int8, p_row int8)
  RETURNS int8
 AS
 $$
 /*  this procedure calculates the Morton number of a cell
     at the given row and col[umn]
     Written:  D.M. Mark, Jan 1984;
     Converted to Vax/VMS: July 1985
     Converted to PostgreSQL, Simon Greener, 2010
 */
 DECLARE
    v_row          int8 := 0;
    v_col          int8 := 0;
    v_key          int8;
    v_level        int8;
    v_left_bit     int8;
    v_right_bit    int8;
    v_quadrant     int8;
 BEGIN
    v_row   := p_row;
    v_col   := p_col;
    v_key   := 0;
    v_level := 0;
    WHILE ((v_row>0) OR (v_col>0)) LOOP
      /* Split off the row (left_bit) and column (right_bit) bits and
      then combine them to form a bit-pair representing the quadrant */
      v_left_bit  := v_row % 2;
      v_right_bit := v_col % 2;
      v_quadrant  := v_right_bit + 2*v_left_bit;
      v_key       := v_key + ( v_quadrant << (2*v_level) );
      /* row, column, and level are then modified before the loop continues */
      v_row := v_row / 2;
      v_col := v_col / 2;
      v_level := v_level + 1;
    END LOOP;
    RETURN (v_key);
 END;
 $$
   LANGUAGE 'plpgsql' IMMUTABLE;

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

 SELECT *
   FROM (SELECT a.gcol,
                b.grow,
                st_morton( a.gcol, b.grow ) AS MortonKey,
                ST_MakeBox2D(ST_MakePoint(a.gcol, b.grow)::geometry,
                             ST_MakePoint(a.gcol+100, b.grow+100)::geometry)::geometry AS geometry           FROM (SELECT 0 + g AS gcol FROM generate_series(0,7,1) AS g) AS a,
                (SELECT 0 + g AS grow FROM generate_series(0,7,1) AS g) AS b
         ) AS foo
  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.