[7193] | 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.
|
---|
[7509] | 9 | *
|
---|
[7193] | 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.
|
---|
[7509] | 13 | *
|
---|
[7193] | 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.)
|
---|
[7509] | 17 | *
|
---|
[7193] | 18 | * @param <T> the property (like land/water or nation)
|
---|
| 19 | */
|
---|
| 20 | public class GeoPropertyIndex<T> {
|
---|
[7509] | 21 |
|
---|
[7193] | 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);
|
---|
[9059] | 34 |
|
---|
[7193] | 35 | /**
|
---|
| 36 | * Look up the property for a coordinate rectangle.
|
---|
| 37 | * @param box the rectangle
|
---|
| 38 | * @return the property, if it is the same in the entire rectangle;
|
---|
| 39 | * null otherwise
|
---|
| 40 | */
|
---|
| 41 | T get(BBox box);
|
---|
| 42 | }
|
---|
| 43 |
|
---|
| 44 | private final int maxLevel;
|
---|
| 45 | private final GeoProperty<T> geoProp;
|
---|
| 46 | private final GPLevel<T> root;
|
---|
| 47 | private GPLevel<T> lastLevelUsed;
|
---|
[7509] | 48 |
|
---|
[7193] | 49 | private static final boolean DEBUG = false;
|
---|
| 50 |
|
---|
| 51 | /**
|
---|
| 52 | * Create new GeoPropertyIndex.
|
---|
| 53 | * @param geoProp the input property that should be made faster by this index
|
---|
[8470] | 54 | * @param maxLevel max level
|
---|
[7193] | 55 | */
|
---|
| 56 | public GeoPropertyIndex(GeoProperty<T> geoProp, int maxLevel) {
|
---|
| 57 | this.geoProp = geoProp;
|
---|
| 58 | this.maxLevel = maxLevel;
|
---|
[9070] | 59 | this.root = new GPLevel<>(0, new BBox(-180, -90, 180, 90), null, this);
|
---|
[7193] | 60 | this.lastLevelUsed = root;
|
---|
| 61 | }
|
---|
[7509] | 62 |
|
---|
[7193] | 63 | /**
|
---|
| 64 | * Look up the property for a certain point.
|
---|
[7592] | 65 | * This gives the same result as {@link GeoProperty#get(LatLon)}, but
|
---|
[7193] | 66 | * should be faster.
|
---|
| 67 | * @param ll the point coordinates
|
---|
| 68 | * @return property value at that point
|
---|
| 69 | */
|
---|
| 70 | public T get(LatLon ll) {
|
---|
| 71 | return lastLevelUsed.get(ll);
|
---|
| 72 | }
|
---|
[7509] | 73 |
|
---|
[7193] | 74 | public static int index(LatLon ll, int level) {
|
---|
| 75 | long noParts = 1 << level;
|
---|
[8510] | 76 | long x = ((long) ((ll.lon() + 180.0) * noParts / 360.0)) & 1;
|
---|
| 77 | long y = ((long) ((ll.lat() + 90.0) * noParts / 180.0)) & 1;
|
---|
[7193] | 78 | return (int) (2 * x + y);
|
---|
| 79 | }
|
---|
| 80 |
|
---|
| 81 | protected static class GPLevel<T> {
|
---|
| 82 | private final T val;
|
---|
| 83 | private final int level;
|
---|
| 84 | private final BBox bbox;
|
---|
| 85 | private final GPLevel<T> parent;
|
---|
| 86 | private final GeoPropertyIndex<T> owner;
|
---|
| 87 |
|
---|
| 88 | // child order by index is sw, nw, se, ne
|
---|
| 89 | private GPLevel<T>[] children;
|
---|
| 90 |
|
---|
| 91 | public GPLevel(int level, BBox bbox, GPLevel<T> parent, GeoPropertyIndex<T> owner) {
|
---|
| 92 | this.level = level;
|
---|
| 93 | this.bbox = bbox;
|
---|
| 94 | this.parent = parent;
|
---|
| 95 | this.owner = owner;
|
---|
| 96 | this.val = owner.geoProp.get(bbox);
|
---|
| 97 | }
|
---|
| 98 |
|
---|
| 99 | public T get(LatLon ll) {
|
---|
[7353] | 100 | if (isInside(ll))
|
---|
[7193] | 101 | return getBounded(ll);
|
---|
| 102 | if (DEBUG) System.err.print("up["+level+"]");
|
---|
| 103 | return parent.get(ll);
|
---|
| 104 | }
|
---|
[7509] | 105 |
|
---|
[7193] | 106 | private T getBounded(LatLon ll) {
|
---|
| 107 | if (DEBUG) System.err.print("GPLevel["+level+"]"+bbox+" ");
|
---|
[7353] | 108 | if (!isInside(ll)) {
|
---|
[7193] | 109 | throw new AssertionError("Point "+ll+" should be inside "+bbox);
|
---|
| 110 | }
|
---|
| 111 | if (val != null) {
|
---|
| 112 | if (DEBUG) System.err.println(" hit! "+val);
|
---|
| 113 | owner.lastLevelUsed = this;
|
---|
| 114 | return val;
|
---|
| 115 | }
|
---|
| 116 | if (level >= owner.maxLevel) {
|
---|
| 117 | if (DEBUG) System.err.println(" max level reached !");
|
---|
| 118 | return owner.geoProp.get(ll);
|
---|
| 119 | }
|
---|
[7509] | 120 |
|
---|
[7193] | 121 | if (children == null) {
|
---|
| 122 | @SuppressWarnings("unchecked")
|
---|
[7596] | 123 | GPLevel<T>[] tmp = new GPLevel[4];
|
---|
[7193] | 124 | this.children = tmp;
|
---|
| 125 | }
|
---|
[7509] | 126 |
|
---|
[7193] | 127 | int idx = index(ll, level+1);
|
---|
| 128 | if (children[idx] == null) {
|
---|
| 129 | double lon1, lat1;
|
---|
| 130 | switch (idx) {
|
---|
[7509] | 131 | case 0:
|
---|
[7193] | 132 | lon1 = bbox.getTopLeftLon();
|
---|
| 133 | lat1 = bbox.getBottomRightLat();
|
---|
| 134 | break;
|
---|
| 135 | case 1:
|
---|
| 136 | lon1 = bbox.getTopLeftLon();
|
---|
| 137 | lat1 = bbox.getTopLeftLat();
|
---|
| 138 | break;
|
---|
[7509] | 139 | case 2:
|
---|
[7193] | 140 | lon1 = bbox.getBottomRightLon();
|
---|
| 141 | lat1 = bbox.getBottomRightLat();
|
---|
| 142 | break;
|
---|
[7509] | 143 | case 3:
|
---|
[7193] | 144 | lon1 = bbox.getBottomRightLon();
|
---|
| 145 | lat1 = bbox.getTopLeftLat();
|
---|
| 146 | break;
|
---|
| 147 | default:
|
---|
| 148 | throw new AssertionError();
|
---|
| 149 | }
|
---|
| 150 | if (DEBUG) System.err.println(" - new with idx "+idx);
|
---|
| 151 | LatLon center = bbox.getCenter();
|
---|
[8510] | 152 | BBox b = new BBox(lon1, lat1, center.lon(), center.lat());
|
---|
[7193] | 153 | children[idx] = new GPLevel<>(level + 1, b, this, owner);
|
---|
| 154 | }
|
---|
| 155 | return children[idx].getBounded(ll);
|
---|
| 156 | }
|
---|
[7509] | 157 |
|
---|
[7353] | 158 | /**
|
---|
| 159 | * Checks, if a point is inside this tile.
|
---|
| 160 | * Makes sure, that neighboring tiles do not overlap, i.e. a point exactly
|
---|
| 161 | * on the border of two tiles must be inside exactly one of the tiles.
|
---|
| 162 | * @param ll the coordinates of the point
|
---|
| 163 | * @return true, if it is inside of the box
|
---|
| 164 | */
|
---|
| 165 | boolean isInside(LatLon ll) {
|
---|
[7509] | 166 | return bbox.getTopLeftLon() <= ll.lon() &&
|
---|
[8416] | 167 | (ll.lon() < bbox.getBottomRightLon() || (ll.lon() == 180.0 && bbox.getBottomRightLon() == 180.0)) &&
|
---|
[7509] | 168 | bbox.getBottomRightLat() <= ll.lat() &&
|
---|
[8416] | 169 | (ll.lat() < bbox.getTopLeftLat() || (ll.lat() == 90.0 && bbox.getTopLeftLat() == 90.0));
|
---|
[7353] | 170 | }
|
---|
[7193] | 171 |
|
---|
| 172 | }
|
---|
| 173 | }
|
---|