1 | // License: GPL. Copyright 2009 by Dave Hansen, others
|
---|
2 | package org.openstreetmap.josm.data.coor;
|
---|
3 |
|
---|
4 | import org.openstreetmap.josm.data.osm.Node;
|
---|
5 |
|
---|
6 | import org.openstreetmap.josm.Main;
|
---|
7 | import org.openstreetmap.josm.data.projection.Projection;
|
---|
8 |
|
---|
9 | public class QuadTiling
|
---|
10 | {
|
---|
11 | public static int NR_LEVELS = 24;
|
---|
12 | public static double WORLD_PARTS = (1 << NR_LEVELS);
|
---|
13 |
|
---|
14 | public static int MAX_OBJECTS_PER_LEVEL = 16;
|
---|
15 | // has to be a power of 2
|
---|
16 | public static int TILES_PER_LEVEL_SHIFT = 2;
|
---|
17 | public static int TILES_PER_LEVEL = 1<<TILES_PER_LEVEL_SHIFT;
|
---|
18 | static public int X_PARTS = 360;
|
---|
19 | static public int X_BIAS = -180;
|
---|
20 |
|
---|
21 | static public int Y_PARTS = 180;
|
---|
22 | static public int Y_BIAS = -90;
|
---|
23 |
|
---|
24 | public static LatLon tile2LatLon(long quad)
|
---|
25 | {
|
---|
26 | // The world is divided up into X_PARTS,Y_PARTS.
|
---|
27 | // The question is how far we move for each bit
|
---|
28 | // being set. In the case of the top level, we
|
---|
29 | // move half of the world.
|
---|
30 | double x_unit = X_PARTS/2;
|
---|
31 | double y_unit = Y_PARTS/2;
|
---|
32 | long shift = (NR_LEVELS*2)-2;
|
---|
33 |
|
---|
34 | //if (debug)
|
---|
35 | // out("tile2xy(0x"+Long.toHexString(quad)+")");
|
---|
36 | double x = 0;
|
---|
37 | double y = 0;
|
---|
38 | for (int i = 0; i < NR_LEVELS; i++) {
|
---|
39 | long bits = (quad >> shift) & 0x3;
|
---|
40 | //if (debug)
|
---|
41 | // out("shift: " + shift + " bits: " + bits);
|
---|
42 | // remember x is the MSB
|
---|
43 | if ((bits & 0x2) != 0)
|
---|
44 | x += x_unit;
|
---|
45 | if ((bits & 0x1) != 0)
|
---|
46 | y += y_unit;
|
---|
47 | x_unit /= 2;
|
---|
48 | y_unit /= 2;
|
---|
49 | shift -= 2;
|
---|
50 | }
|
---|
51 | x += X_BIAS;
|
---|
52 | y += Y_BIAS;
|
---|
53 | return new LatLon(y, x);
|
---|
54 | }
|
---|
55 | static long xy2tile(long x, long y)
|
---|
56 | {
|
---|
57 | long tile = 0;
|
---|
58 | int i;
|
---|
59 | for (i = NR_LEVELS-1; i >= 0; i--)
|
---|
60 | {
|
---|
61 | long xbit = ((x >> i) & 1);
|
---|
62 | long ybit = ((y >> i) & 1);
|
---|
63 | tile <<= 2;
|
---|
64 | // Note that x is the MSB
|
---|
65 | tile |= (xbit<<1) | ybit;
|
---|
66 | }
|
---|
67 | return tile;
|
---|
68 | }
|
---|
69 | static long coorToTile(LatLon coor)
|
---|
70 | {
|
---|
71 | return quadTile(coor);
|
---|
72 | }
|
---|
73 | static long lon2x(double lon)
|
---|
74 | {
|
---|
75 | //return Math.round((lon + 180.0) * QuadBuckets.WORLD_PARTS / 360.0)-1;
|
---|
76 | long ret = (long)Math.floor((lon + 180.0) * WORLD_PARTS / 360.0);
|
---|
77 | if (ret == WORLD_PARTS)
|
---|
78 | ret--;
|
---|
79 | return ret;
|
---|
80 | }
|
---|
81 | static long lat2y(double lat)
|
---|
82 | {
|
---|
83 | //return Math.round((lat + 90.0) * QuadBuckets.WORLD_PARTS / 180.0)-1;
|
---|
84 | long ret = (long)Math.floor((lat + 90.0) * WORLD_PARTS / 180.0);
|
---|
85 | if (ret == WORLD_PARTS)
|
---|
86 | ret--;
|
---|
87 | return ret;
|
---|
88 | }
|
---|
89 | static public long quadTile(LatLon coor)
|
---|
90 | {
|
---|
91 | return xy2tile(lon2x(coor.lon()),
|
---|
92 | lat2y(coor.lat()));
|
---|
93 | }
|
---|
94 | static public int index(int level, long quad)
|
---|
95 | {
|
---|
96 | long mask = 0x00000003;
|
---|
97 | int total_shift = TILES_PER_LEVEL_SHIFT*(NR_LEVELS-level-1);
|
---|
98 | return (int)(mask & (quad >> total_shift));
|
---|
99 | }
|
---|
100 | static public int index(LatLon coor, int level)
|
---|
101 | {
|
---|
102 | // The nodes that don't return coordinates will all get
|
---|
103 | // stuck in a single tile. Hopefully there are not too
|
---|
104 | // many of them
|
---|
105 | if (coor == null)
|
---|
106 | return 0;
|
---|
107 | long quad = coorToTile(coor);
|
---|
108 | return index(level, quad);
|
---|
109 | }
|
---|
110 | }
|
---|