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 | /**
|
---|
23 | * A method to look up a property of the earth surface.
|
---|
24 | * (User input for the index.)
|
---|
25 | * @param <T> the property
|
---|
26 | */
|
---|
27 | public interface GeoProperty<T> {
|
---|
28 | /**
|
---|
29 | * Look up the property for a point.
|
---|
30 | * @param ll the point coordinates
|
---|
31 | * @return property value at that point. Must not be null.
|
---|
32 | */
|
---|
33 | T get(LatLon ll);
|
---|
34 | /**
|
---|
35 | * Look up the property for a coordinate rectangle.
|
---|
36 | * @param box the rectangle
|
---|
37 | * @return the property, if it is the same in the entire rectangle;
|
---|
38 | * null otherwise
|
---|
39 | */
|
---|
40 | T get(BBox box);
|
---|
41 | }
|
---|
42 |
|
---|
43 | private final int maxLevel;
|
---|
44 | private final GeoProperty<T> geoProp;
|
---|
45 | private final GPLevel<T> root;
|
---|
46 | private GPLevel<T> lastLevelUsed;
|
---|
47 |
|
---|
48 | private static final boolean DEBUG = false;
|
---|
49 |
|
---|
50 | /**
|
---|
51 | * Create new GeoPropertyIndex.
|
---|
52 | * @param geoProp the input property that should be made faster by this index
|
---|
53 | * @param maxLevel
|
---|
54 | */
|
---|
55 | public GeoPropertyIndex(GeoProperty<T> geoProp, int maxLevel) {
|
---|
56 | this.geoProp = geoProp;
|
---|
57 | this.maxLevel = maxLevel;
|
---|
58 | this.root = new GPLevel<T>(0, new BBox(-180, -90, 180, 90), null, this);
|
---|
59 | this.lastLevelUsed = root;
|
---|
60 | }
|
---|
61 |
|
---|
62 | /**
|
---|
63 | * Look up the property for a certain point.
|
---|
64 | * This gives the same result as {@link #geoProp#get(LatLon)}, but
|
---|
65 | * should be faster.
|
---|
66 | * @param ll the point coordinates
|
---|
67 | * @return property value at that point
|
---|
68 | */
|
---|
69 | public T get(LatLon ll) {
|
---|
70 | return lastLevelUsed.get(ll);
|
---|
71 | }
|
---|
72 |
|
---|
73 | public static int index(LatLon ll, int level) {
|
---|
74 | long noParts = 1 << level;
|
---|
75 | long x = ((long)((ll.lon() + 180.0) * noParts / 360.0)) & 1;
|
---|
76 | long y = ((long)((ll.lat() + 90.0) * noParts / 180.0)) & 1;
|
---|
77 | return (int) (2 * x + y);
|
---|
78 | }
|
---|
79 |
|
---|
80 | protected static class GPLevel<T> {
|
---|
81 | private final T val;
|
---|
82 | private final int level;
|
---|
83 | private final BBox bbox;
|
---|
84 | private final GPLevel<T> parent;
|
---|
85 | private final GeoPropertyIndex<T> owner;
|
---|
86 |
|
---|
87 | // child order by index is sw, nw, se, ne
|
---|
88 | private GPLevel<T>[] children;
|
---|
89 |
|
---|
90 | public GPLevel(int level, BBox bbox, GPLevel<T> parent, GeoPropertyIndex<T> owner) {
|
---|
91 | this.level = level;
|
---|
92 | this.bbox = bbox;
|
---|
93 | this.parent = parent;
|
---|
94 | this.owner = owner;
|
---|
95 | this.val = owner.geoProp.get(bbox);
|
---|
96 | }
|
---|
97 |
|
---|
98 | public T get(LatLon ll) {
|
---|
99 | if (bbox.bounds(ll))
|
---|
100 | return getBounded(ll);
|
---|
101 | if (DEBUG) System.err.print("up["+level+"]");
|
---|
102 | return parent.get(ll);
|
---|
103 | }
|
---|
104 |
|
---|
105 | private T getBounded(LatLon ll) {
|
---|
106 | if (DEBUG) System.err.print("GPLevel["+level+"]"+bbox+" ");
|
---|
107 | if (!bbox.bounds(ll)) {
|
---|
108 | throw new AssertionError("Point "+ll+" should be inside "+bbox);
|
---|
109 | }
|
---|
110 | if (val != null) {
|
---|
111 | if (DEBUG) System.err.println(" hit! "+val);
|
---|
112 | owner.lastLevelUsed = this;
|
---|
113 | return val;
|
---|
114 | }
|
---|
115 | if (level >= owner.maxLevel) {
|
---|
116 | if (DEBUG) System.err.println(" max level reached !");
|
---|
117 | return owner.geoProp.get(ll);
|
---|
118 | }
|
---|
119 |
|
---|
120 | if (children == null) {
|
---|
121 | @SuppressWarnings("unchecked")
|
---|
122 | GPLevel<T>[] tmp = (GPLevel<T>[]) new GPLevel[4];
|
---|
123 | this.children = tmp;
|
---|
124 | }
|
---|
125 |
|
---|
126 | int idx = index(ll, level+1);
|
---|
127 | if (children[idx] == null) {
|
---|
128 | double lon1, lat1;
|
---|
129 | switch (idx) {
|
---|
130 | case 0:
|
---|
131 | lon1 = bbox.getTopLeftLon();
|
---|
132 | lat1 = bbox.getBottomRightLat();
|
---|
133 | break;
|
---|
134 | case 1:
|
---|
135 | lon1 = bbox.getTopLeftLon();
|
---|
136 | lat1 = bbox.getTopLeftLat();
|
---|
137 | break;
|
---|
138 | case 2:
|
---|
139 | lon1 = bbox.getBottomRightLon();
|
---|
140 | lat1 = bbox.getBottomRightLat();
|
---|
141 | break;
|
---|
142 | case 3:
|
---|
143 | lon1 = bbox.getBottomRightLon();
|
---|
144 | lat1 = bbox.getTopLeftLat();
|
---|
145 | break;
|
---|
146 | default:
|
---|
147 | throw new AssertionError();
|
---|
148 | }
|
---|
149 | if (DEBUG) System.err.println(" - new with idx "+idx);
|
---|
150 | LatLon center = bbox.getCenter();
|
---|
151 | BBox b = new BBox(lon1,lat1, center.lon(), center.lat());
|
---|
152 | children[idx] = new GPLevel<>(level + 1, b, this, owner);
|
---|
153 | }
|
---|
154 | return children[idx].getBounded(ll);
|
---|
155 | }
|
---|
156 |
|
---|
157 | }
|
---|
158 | }
|
---|