From: Tom Hughes Date: Tue, 11 Sep 2007 23:55:25 +0000 (+0000) Subject: QuadTile infrastructure. X-Git-Tag: live~8157 X-Git-Url: https://git.openstreetmap.org/rails.git/commitdiff_plain/33a65a90c9d0e2ab121e1da9c3efedaf9e6a9789 QuadTile infrastructure. --- diff --git a/db/functions/Makefile b/db/functions/Makefile new file mode 100644 index 000000000..6544db1ff --- /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 index 000000000..7d17f6f76 --- /dev/null +++ b/db/functions/quadtile.c @@ -0,0 +1,31 @@ +#include +#include +#include +#include +#include + +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 aab3e1335..e5d3c7fbb 100644 --- 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 index 000000000..cb1b5a06e --- /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 index 000000000..c7fc1b899 --- /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 index 000000000..137963bd0 --- /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 index 000000000..f868ff515 --- /dev/null +++ b/lib/quad_tile/quad_tile.h @@ -0,0 +1,25 @@ +#include + +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); +}