1 | // License: GPL. For details, see LICENSE file. |
---|
2 | package org.openstreetmap.josm.tools; |
---|
3 | |
---|
4 | import org.openstreetmap.josm.data.coor.LatLon; |
---|
5 | import org.openstreetmap.josm.data.osm.BBox; |
---|
6 | |
---|
7 | /** |
---|
8 | * Fast index to look up properties of the earth surface. |
---|
9 | * |
---|
10 | * It is expected that there is a relatively slow method to look up the property |
---|
11 | * for a certain coordinate and that there are larger areas with a uniform |
---|
12 | * property. |
---|
13 | * |
---|
14 | * This index tries to find rectangles with uniform property and caches them. |
---|
15 | * Rectangles are subdivided, if there are different properties within. |
---|
16 | * (Up to a maximum level, when the slow method is used again.) |
---|
17 | * |
---|
18 | * @param <T> the property (like land/water or nation) |
---|
19 | */ |
---|
20 | public class GeoPropertyIndex<T> { |
---|
21 | |
---|
22 | private final int maxLevel; |
---|
23 | private final GeoProperty<T> geoProp; |
---|
24 | private final GPLevel<T> root; |
---|
25 | private GPLevel<T> lastLevelUsed; |
---|
26 | |
---|
27 | private static final boolean DEBUG = false; |
---|
28 | |
---|
29 | /** |
---|
30 | * Create new GeoPropertyIndex. |
---|
31 | * @param geoProp the input property that should be made faster by this index |
---|
32 | * @param maxLevel max level |
---|
33 | */ |
---|
34 | public GeoPropertyIndex(GeoProperty<T> geoProp, int maxLevel) { |
---|
35 | this.geoProp = geoProp; |
---|
36 | this.maxLevel = maxLevel; |
---|
37 | this.root = new GPLevel<>(0, new BBox(-180, -90, 180, 90), null, this); |
---|
38 | this.lastLevelUsed = root; |
---|
39 | } |
---|
40 | |
---|
41 | /** |
---|
42 | * Look up the property for a certain point. |
---|
43 | * This gives the same result as {@link GeoProperty#get(LatLon)}, but |
---|
44 | * should be faster. |
---|
45 | * @param ll the point coordinates |
---|
46 | * @return property value at that point |
---|
47 | */ |
---|
48 | public T get(LatLon ll) { |
---|
49 | return lastLevelUsed.get(ll); |
---|
50 | } |
---|
51 | |
---|
52 | /** |
---|
53 | * Gets the index of the given coordinate. Only used internally |
---|
54 | * @param ll The lat/lon coordinate |
---|
55 | * @param level The scale level |
---|
56 | * @return The index for that position |
---|
57 | */ |
---|
58 | public static int index(LatLon ll, int level) { |
---|
59 | long noParts = 1L << level; |
---|
60 | long x = ((long) ((ll.lon() + 180.0) * noParts / 360.0)) & 1; |
---|
61 | long y = ((long) ((ll.lat() + 90.0) * noParts / 180.0)) & 1; |
---|
62 | return (int) (2 * x + y); |
---|
63 | } |
---|
64 | |
---|
65 | protected static class GPLevel<T> { |
---|
66 | private final T val; |
---|
67 | private final int level; |
---|
68 | private final BBox bbox; |
---|
69 | private final GPLevel<T> parent; |
---|
70 | private final GeoPropertyIndex<T> owner; |
---|
71 | |
---|
72 | // child order by index is sw, nw, se, ne |
---|
73 | private GPLevel<T>[] children; |
---|
74 | |
---|
75 | public GPLevel(int level, BBox bbox, GPLevel<T> parent, GeoPropertyIndex<T> owner) { |
---|
76 | this.level = level; |
---|
77 | this.bbox = bbox; |
---|
78 | this.parent = parent; |
---|
79 | this.owner = owner; |
---|
80 | this.val = owner.geoProp.get(bbox); |
---|
81 | } |
---|
82 | |
---|
83 | public T get(LatLon ll) { |
---|
84 | if (isInside(ll)) |
---|
85 | return getBounded(ll); |
---|
86 | if (DEBUG) System.err.print("up["+level+"]"); |
---|
87 | return parent.get(ll); |
---|
88 | } |
---|
89 | |
---|
90 | private T getBounded(LatLon ll) { |
---|
91 | if (DEBUG) System.err.print("GPLevel["+level+"]"+bbox+" "); |
---|
92 | if (!isInside(ll)) { |
---|
93 | throw new AssertionError("Point "+ll+" should be inside "+bbox); |
---|
94 | } |
---|
95 | if (val != null) { |
---|
96 | if (DEBUG) System.err.println(" hit! "+val); |
---|
97 | owner.lastLevelUsed = this; |
---|
98 | return val; |
---|
99 | } |
---|
100 | if (level >= owner.maxLevel) { |
---|
101 | if (DEBUG) System.err.println(" max level reached !"); |
---|
102 | return owner.geoProp.get(ll); |
---|
103 | } |
---|
104 | |
---|
105 | if (children == null) { |
---|
106 | @SuppressWarnings("unchecked") |
---|
107 | GPLevel<T>[] tmp = new GPLevel[4]; |
---|
108 | this.children = tmp; |
---|
109 | } |
---|
110 | |
---|
111 | int idx = index(ll, level+1); |
---|
112 | if (children[idx] == null) { |
---|
113 | double lon1, lat1; |
---|
114 | switch (idx) { |
---|
115 | case 0: |
---|
116 | lon1 = bbox.getTopLeftLon(); |
---|
117 | lat1 = bbox.getBottomRightLat(); |
---|
118 | break; |
---|
119 | case 1: |
---|
120 | lon1 = bbox.getTopLeftLon(); |
---|
121 | lat1 = bbox.getTopLeftLat(); |
---|
122 | break; |
---|
123 | case 2: |
---|
124 | lon1 = bbox.getBottomRightLon(); |
---|
125 | lat1 = bbox.getBottomRightLat(); |
---|
126 | break; |
---|
127 | case 3: |
---|
128 | lon1 = bbox.getBottomRightLon(); |
---|
129 | lat1 = bbox.getTopLeftLat(); |
---|
130 | break; |
---|
131 | default: |
---|
132 | throw new AssertionError(); |
---|
133 | } |
---|
134 | if (DEBUG) System.err.println(" - new with idx "+idx); |
---|
135 | LatLon center = bbox.getCenter(); |
---|
136 | BBox b = new BBox(lon1, lat1, center.lon(), center.lat()); |
---|
137 | children[idx] = new GPLevel<>(level + 1, b, this, owner); |
---|
138 | } |
---|
139 | return children[idx].getBounded(ll); |
---|
140 | } |
---|
141 | |
---|
142 | /** |
---|
143 | * Checks, if a point is inside this tile. |
---|
144 | * Makes sure, that neighboring tiles do not overlap, i.e. a point exactly |
---|
145 | * on the border of two tiles must be inside exactly one of the tiles. |
---|
146 | * @param ll the coordinates of the point |
---|
147 | * @return true, if it is inside of the box |
---|
148 | */ |
---|
149 | boolean isInside(LatLon ll) { |
---|
150 | return bbox.getTopLeftLon() <= ll.lon() && |
---|
151 | (ll.lon() < bbox.getBottomRightLon() || (ll.lon() == 180.0 && bbox.getBottomRightLon() == 180.0)) && |
---|
152 | bbox.getBottomRightLat() <= ll.lat() && |
---|
153 | (ll.lat() < bbox.getTopLeftLat() || (ll.lat() == 90.0 && bbox.getTopLeftLat() == 90.0)); |
---|
154 | } |
---|
155 | |
---|
156 | @Override |
---|
157 | public String toString() { |
---|
158 | return "GPLevel [val=" + val + ", level=" + level + ", bbox=" + bbox + ']'; |
---|
159 | } |
---|
160 | } |
---|
161 | |
---|
162 | @Override |
---|
163 | public String toString() { |
---|
164 | return "GeoPropertyIndex [maxLevel=" + maxLevel + ", geoProp=" + geoProp + ", root=" + root + ", lastLevelUsed=" |
---|
165 | + lastLevelUsed + ']'; |
---|
166 | } |
---|
167 | } |
---|