QuadTile infrastructure.

diff --git a/db/functions/Makefile b/db/functions/Makefile
new file mode 100644 (file)
index 0000000..6544db1
--- /dev/null
+++ b/db/functions/Makefile
@@ -0,0 +1,4 @@
+QTDIR=../../lib/quad_tile
+
+libquadtile.so: quadtile.c ${QTDIR}/quad_tile.h
+       cc `mysql_config --include` -I${QTDIR} -fPIC -O3 -shared -o libquadtile.so quadtile.c

diff --git a/db/functions/quadtile.c b/db/functions/quadtile.c
new file mode 100644 (file)
index 0000000..7d17f6f
--- /dev/null
+++ b/db/functions/quadtile.c
@@ -0,0 +1,31 @@
+#include <my_global.h>
+#include <my_sys.h>
+#include <m_string.h>
+#include <mysql.h>
+#include <quad_tile.h>
+
+my_bool tile_for_point_init(UDF_INIT *initid, UDF_ARGS *args, char *message)
+{
+   if ( args->arg_count != 2 ||
+        args->arg_type[0] != INT_RESULT ||
+        args->arg_type[1] != INT_RESULT )
+   {
+      strcpy( message, "Your tile_for_point arguments are bogus!" );
+      return 1;
+   }
+
+   return 0;
+}
+
+void tile_for_point_deinit(UDF_INIT *initid)
+{
+   return;
+}
+
+long long tile_for_point(UDF_INIT *initid, UDF_ARGS *args, char *is_null, char *error)
+{
+   long long lon = *(long long *)args->args[0];
+   long long lat = *(long long *)args->args[1];
+
+   return xy2tile(lon2x(lon / 1000000.0), lat2y(lat / 1000000.0));
+}

diff --git a/lib/osm.rb b/lib/osm.rb
index aab3e1335bf9828bcddae6fe760945d78d44558c..e5d3c7fbb6b653172cf804bbe744be8021b39e52 100644 (file)
--- a/lib/osm.rb
+++ b/lib/osm.rb
@@ -410,4 +410,15 @@ module OSM
     return Digest::MD5.hexdigest(password) if salt.nil?
     return Digest::MD5.hexdigest(salt + password)
   end
+
+  # Return an SQL fragment to select a given area of the globe
+  def self.sql_for_area(minlat, minlon, maxlat, maxlon)
+    tilesql = QuadTile.sql_for_area(minlat, minlon, maxlat, maxlon)
+    minlat = (minlat * 1000000).round
+    minlon = (minlon * 1000000).round
+    maxlat = (maxlat * 1000000).round
+    maxlon = (maxlon * 1000000).round
+
+    return "#{tilesql} AND latitude BETWEEN #{minlat} AND #{maxlat} AND longitude BETWEEN #{minlon} AND #{maxlon}"
+  end
 end

diff --git a/lib/quad_tile.rb b/lib/quad_tile.rb
new file mode 100644 (file)
index 0000000..cb1b5a0
--- /dev/null
+++ b/lib/quad_tile.rb
@@ -0,0 +1,81 @@
+module QuadTile
+  begin
+    require "quad_tile/quad_tile_so"
+  rescue MissingSourceFile
+    def self.tile_for_point(lat, lon)
+      x = ((lon + 180) * 65535 / 360).round
+      y = ((lat + 90) * 65535 / 180).round
+
+      return tile_for_xy(x, y)
+    end
+
+    def self.tiles_for_area(minlat, minlon, maxlat, maxlon)
+      minx = ((minlon + 180) * 65535 / 360).round
+      maxx = ((maxlon + 180) * 65535 / 360).round
+      miny = ((minlat + 90) * 65535 / 180).round
+      maxy = ((maxlat + 90) * 65535 / 180).round
+      tiles = []
+
+      minx.upto(maxx) do |x|
+        miny.upto(maxy) do |y|
+          tiles << tile_for_xy(x, y)
+        end
+      end
+
+      return tiles
+    end
+
+    def self.tile_for_xy(x, y)
+      t = 0
+
+      16.times do
+        t = t << 1
+        t = t | 1 unless (x & 0x8000).zero?
+        x <<= 1
+        t = t << 1
+        t = t | 1 unless (y & 0x8000).zero?
+        y <<= 1
+      end
+
+      return t
+    end
+  end
+
+  def self.sql_for_area(minlat, minlon, maxlat, maxlon)
+    sql = Array.new
+    single = Array.new
+
+    iterate_tiles_for_area(minlat, minlon, maxlat, maxlon) do |first,last|
+      if first == last
+        single.push(first)
+      else
+        sql.push("tile BETWEEN #{first} AND #{last}")
+      end
+    end
+
+    sql.push("tile IN (#{single.join(',')})") if single.size > 0
+
+    return "( " + sql.join(" OR ") + " )"
+  end
+
+  def self.iterate_tiles_for_area(minlat, minlon, maxlat, maxlon)
+    tiles = tiles_for_area(minlat, minlon, maxlat, maxlon)
+    first = last = nil
+
+    tiles.sort.each do |tile|
+      if last.nil?
+        first = last = tile
+      elsif tile == last + 1
+        last = tile
+      else
+        yield first, last
+
+        first = last = tile
+      end
+    end
+
+    yield first, last unless last.nil?
+  end
+
+  private_class_method :tile_for_xy, :iterate_tiles_for_area
+end

diff --git a/lib/quad_tile/extconf.rb b/lib/quad_tile/extconf.rb
new file mode 100644 (file)
index 0000000..c7fc1b8
--- /dev/null
+++ b/lib/quad_tile/extconf.rb
@@ -0,0 +1,3 @@
+require "mkmf"
+
+create_makefile("quad_tile_so")

diff --git a/lib/quad_tile/quad_tile.c b/lib/quad_tile/quad_tile.c
new file mode 100644 (file)
index 0000000..137963b
--- /dev/null
+++ b/lib/quad_tile/quad_tile.c
@@ -0,0 +1,47 @@
+#include "ruby.h"
+#include "quad_tile.h"
+
+static VALUE tile_for_point(VALUE self, VALUE lat, VALUE lon)
+{
+   unsigned int x = lon2x(NUM2DBL(lon));
+   unsigned int y = lat2y(NUM2DBL(lat));
+
+   return UINT2NUM(xy2tile(x, y));
+}
+
+static VALUE tiles_for_area(VALUE self, VALUE minlat, VALUE minlon, VALUE maxlat, VALUE maxlon)
+{
+   unsigned int minx = lon2x(NUM2DBL(minlon));
+   unsigned int maxx = lon2x(NUM2DBL(maxlon));
+   unsigned int miny = lat2y(NUM2DBL(minlat));
+   unsigned int maxy = lat2y(NUM2DBL(maxlat));
+   VALUE        tiles = rb_ary_new();
+   unsigned int x;
+   unsigned int y;
+
+   for (x = minx; x <= maxx; x++)
+   {
+      for (y = miny; y <= maxy; y++)
+      {
+         rb_ary_push(tiles, UINT2NUM(xy2tile(x, y)));
+      }
+   }
+
+   return tiles;
+}
+
+static VALUE tile_for_xy(VALUE self, VALUE x, VALUE y)
+{
+   return UINT2NUM(xy2tile(NUM2UINT(x), NUM2UINT(y)));
+}
+
+void Init_quad_tile_so(void)
+{
+   VALUE m = rb_define_module("QuadTile");
+
+   rb_define_module_function(m, "tile_for_point", tile_for_point, 2);
+   rb_define_module_function(m, "tiles_for_area", tiles_for_area, 4);
+   rb_define_module_function(m, "tile_for_xy", tile_for_xy, 2);
+
+   return;
+}

diff --git a/lib/quad_tile/quad_tile.h b/lib/quad_tile/quad_tile.h
new file mode 100644 (file)
index 0000000..f868ff5
--- /dev/null
+++ b/lib/quad_tile/quad_tile.h
@@ -0,0 +1,25 @@
+#include <math.h>
+
+inline unsigned int xy2tile(unsigned int x, unsigned int y)
+{
+   unsigned int tile = 0;
+   int          i;
+
+   for (i = 15; i >= 0; i--)
+   {
+      tile = (tile << 1) | ((x >> i) & 1);
+      tile = (tile << 1) | ((y >> i) & 1);
+   }
+
+   return tile;
+}
+
+inline unsigned int lon2x(double lon)
+{
+   return round((lon + 180.0) * 65535.0 / 360.0);
+}
+
+inline unsigned int lat2y(double lat)
+{
+   return round((lat + 90.0) * 65535.0 / 180.0);
+}