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