001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.data.coor; 003 004public final class QuadTiling { 005 006 private QuadTiling() { 007 // Hide default constructor for utils classes 008 } 009 010 public static final int NR_LEVELS = 24; 011 public static final double WORLD_PARTS = (1 << NR_LEVELS); 012 013 public static final int TILES_PER_LEVEL_SHIFT = 2; // Has to be 2. Other parts of QuadBuckets code rely on it 014 public static final int TILES_PER_LEVEL = 1<<TILES_PER_LEVEL_SHIFT; 015 public static final int X_PARTS = 360; 016 public static final int X_BIAS = -180; 017 018 public static final int Y_PARTS = 180; 019 public static final int Y_BIAS = -90; 020 021 public static LatLon tile2LatLon(long quad) { 022 // The world is divided up into X_PARTS,Y_PARTS. 023 // The question is how far we move for each bit 024 // being set. In the case of the top level, we 025 // move half of the world. 026 double x_unit = X_PARTS/2; 027 double y_unit = Y_PARTS/2; 028 long shift = (NR_LEVELS*2)-2; 029 030 double x = 0; 031 double y = 0; 032 for (int i = 0; i < NR_LEVELS; i++) { 033 long bits = (quad >> shift) & 0x3; 034 // remember x is the MSB 035 if ((bits & 0x2) != 0) { 036 x += x_unit; 037 } 038 if ((bits & 0x1) != 0) { 039 y += y_unit; 040 } 041 x_unit /= 2; 042 y_unit /= 2; 043 shift -= 2; 044 } 045 x += X_BIAS; 046 y += Y_BIAS; 047 return new LatLon(y, x); 048 } 049 050 static long xy2tile(long x, long y) { 051 long tile = 0; 052 int i; 053 for (i = NR_LEVELS-1; i >= 0; i--) 054 { 055 long xbit = ((x >> i) & 1); 056 long ybit = ((y >> i) & 1); 057 tile <<= 2; 058 // Note that x is the MSB 059 tile |= (xbit<<1) | ybit; 060 } 061 return tile; 062 } 063 064 static long coorToTile(LatLon coor) { 065 return quadTile(coor); 066 } 067 068 static long lon2x(double lon) { 069 long ret = (long)((lon + 180.0) * WORLD_PARTS / 360.0); 070 if (ret == WORLD_PARTS) { 071 ret--; 072 } 073 return ret; 074 } 075 076 static long lat2y(double lat) { 077 long ret = (long)((lat + 90.0) * WORLD_PARTS / 180.0); 078 if (ret == WORLD_PARTS) { 079 ret--; 080 } 081 return ret; 082 } 083 084 public static long quadTile(LatLon coor) { 085 return xy2tile(lon2x(coor.lon()), lat2y(coor.lat())); 086 } 087 088 public static int index(int level, long quad) { 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 094 /** 095 * Returns quad tiling index for given coordinates and level. 096 * 097 * @param coor coordinates 098 * @param level level 099 * 100 * @return quad tiling index for given coordinates and level. 101 * @since 2263 102 */ 103 public static int index(LatLon coor, int level) { 104 // The nodes that don't return coordinates will all get stuck in a single tile. 105 // Hopefully there are not too many of them 106 if (coor == null) 107 return 0; 108 109 return index(coor.lat(), coor.lon(), level); 110 } 111 112 /** 113 * Returns quad tiling index for given coordinates and level. 114 * 115 * @param lat latitude 116 * @param lon longitude 117 * @param level level 118 * 119 * @return quad tiling index for given coordinates and level. 120 * @since 6171 121 */ 122 public static int index(final double lat, final double lon, final int level) { 123 long x = lon2x(lon); 124 long y = lat2y(lat); 125 int shift = NR_LEVELS-level-1; 126 return (int)((x >> shift & 1) * 2 + (y >> shift & 1)); 127 } 128}