001 // License: GPL. Copyright 2009 by Dave Hansen, others 002 package org.openstreetmap.josm.data.coor; 003 004 public class QuadTiling 005 { 006 public static final int NR_LEVELS = 24; 007 public static final double WORLD_PARTS = (1 << NR_LEVELS); 008 009 public static final int TILES_PER_LEVEL_SHIFT = 2; // Has to be 2. Other parts of QuadBuckets code rely on it 010 public static final int TILES_PER_LEVEL = 1<<TILES_PER_LEVEL_SHIFT; 011 static public final int X_PARTS = 360; 012 static public final int X_BIAS = -180; 013 014 static public final int Y_PARTS = 180; 015 static public final int Y_BIAS = -90; 016 017 public static LatLon tile2LatLon(long quad) 018 { 019 // The world is divided up into X_PARTS,Y_PARTS. 020 // The question is how far we move for each bit 021 // being set. In the case of the top level, we 022 // move half of the world. 023 double x_unit = X_PARTS/2; 024 double y_unit = Y_PARTS/2; 025 long shift = (NR_LEVELS*2)-2; 026 027 double x = 0; 028 double y = 0; 029 for (int i = 0; i < NR_LEVELS; i++) { 030 long bits = (quad >> shift) & 0x3; 031 // remember x is the MSB 032 if ((bits & 0x2) != 0) { 033 x += x_unit; 034 } 035 if ((bits & 0x1) != 0) { 036 y += y_unit; 037 } 038 x_unit /= 2; 039 y_unit /= 2; 040 shift -= 2; 041 } 042 x += X_BIAS; 043 y += Y_BIAS; 044 return new LatLon(y, x); 045 } 046 static long xy2tile(long x, long y) 047 { 048 long tile = 0; 049 int i; 050 for (i = NR_LEVELS-1; i >= 0; i--) 051 { 052 long xbit = ((x >> i) & 1); 053 long ybit = ((y >> i) & 1); 054 tile <<= 2; 055 // Note that x is the MSB 056 tile |= (xbit<<1) | ybit; 057 } 058 return tile; 059 } 060 static long coorToTile(LatLon coor) 061 { 062 return quadTile(coor); 063 } 064 static long lon2x(double lon) 065 { 066 //return Math.round((lon + 180.0) * QuadBuckets.WORLD_PARTS / 360.0)-1; 067 long ret = (long)((lon + 180.0) * WORLD_PARTS / 360.0); 068 if (ret == WORLD_PARTS) { 069 ret--; 070 } 071 return ret; 072 } 073 static long lat2y(double lat) 074 { 075 //return Math.round((lat + 90.0) * QuadBuckets.WORLD_PARTS / 180.0)-1; 076 long ret = (long)((lat + 90.0) * WORLD_PARTS / 180.0); 077 if (ret == WORLD_PARTS) { 078 ret--; 079 } 080 return ret; 081 } 082 static public long quadTile(LatLon coor) 083 { 084 return xy2tile(lon2x(coor.lon()), 085 lat2y(coor.lat())); 086 } 087 static public int index(int level, long quad) 088 { 089 long mask = 0x00000003; 090 int total_shift = TILES_PER_LEVEL_SHIFT*(NR_LEVELS-level-1); 091 return (int)(mask & (quad >> total_shift)); 092 } 093 static public int index(LatLon coor, int level) { 094 // The nodes that don't return coordinates will all get 095 // stuck in a single tile. Hopefully there are not too 096 // many of them 097 if (coor == null) 098 return 0; 099 100 long x = lon2x(coor.lon()); 101 long y = lat2y(coor.lat()); 102 int shift = NR_LEVELS-level-1; 103 return (int)((x >> shift & 1) * 2 + (y >> shift & 1)); 104 } 105 }