001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.coor;
003
004import org.openstreetmap.josm.tools.Utils;
005
006/**
007 * This class helps in tiling the world into multiple quad tiles.
008 */
009public final class QuadTiling {
010
011    private QuadTiling() {
012        // Hide default constructor for utils classes
013    }
014
015    /**
016     * The maximum number of levels to split the quads
017     */
018    public static final int NR_LEVELS = 24;
019    /**
020     * The number of parts the world is split into in each direction
021     */
022    public static final double WORLD_PARTS = 1 << NR_LEVELS;
023
024    /**
025     * The log(2) of how many tiles there are per level
026     */
027    public static final int TILES_PER_LEVEL_SHIFT = 2; // Has to be 2. Other parts of QuadBuckets code rely on it
028    /**
029     * How many tiles there are per level
030     */
031    public static final int TILES_PER_LEVEL = 1 << TILES_PER_LEVEL_SHIFT;
032    /**
033     * The size of the world in X direction
034     */
035    public static final int X_PARTS = 360;
036    /**
037     * The offset of the world in x direction
038     */
039    public static final int X_BIAS = -180;
040
041    /**
042     * The size of the world in y direction
043     */
044    public static final int Y_PARTS = 180;
045    /**
046     * The offset of the world in y direction
047     */
048    public static final int Y_BIAS = -90;
049
050    /**
051     * Converts a tile index to a lat/lon position
052     * @param quad The tile to convert
053     * @return The lat/lon position of that tile
054     */
055    public static LatLon tile2LatLon(long quad) {
056        // The world is divided up into X_PARTS,Y_PARTS.
057        // The question is how far we move for each bit being set.
058        // In the case of the top level, we move half of the world.
059        double xUnit = X_PARTS/2d;
060        double yUnit = Y_PARTS/2d;
061        long shift = (NR_LEVELS*2L)-2L;
062
063        double x = 0;
064        double y = 0;
065        for (int i = 0; i < NR_LEVELS; i++) {
066            long bits = (quad >> shift) & 0x3;
067            // remember x is the MSB
068            if ((bits & 0x2) != 0) {
069                x += xUnit;
070            }
071            if ((bits & 0x1) != 0) {
072                y += yUnit;
073            }
074            xUnit /= 2;
075            yUnit /= 2;
076            shift -= 2;
077        }
078        x += X_BIAS;
079        y += Y_BIAS;
080        return new LatLon(y, x);
081    }
082
083    static long lon2x(double lon) {
084        long ret = (long) ((lon + 180.0) * WORLD_PARTS / 360.0);
085        if (Utils.equalsEpsilon(ret, WORLD_PARTS)) {
086            ret--;
087        }
088        return ret;
089    }
090
091    static long lat2y(double lat) {
092        long ret = (long) ((lat + 90.0) * WORLD_PARTS / 180.0);
093        if (Utils.equalsEpsilon(ret, WORLD_PARTS)) {
094            ret--;
095        }
096        return ret;
097    }
098
099    /**
100     * Returns quad tiling index for given coordinates and level.
101     *
102     * @param lat latitude
103     * @param lon longitude
104     * @param level level
105     *
106     * @return quad tiling index for given coordinates and level.
107     * @since 6171
108     */
109    public static byte index(final double lat, final double lon, final int level) {
110        long x = lon2x(lon);
111        long y = lat2y(lat);
112        int shift = NR_LEVELS-level-1;
113        return (byte) ((x >> shift & 1) * 2 + (y >> shift & 1));
114    }
115}