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