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}