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}