001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.tools; 003 004import java.util.Collection; 005 006import org.openstreetmap.josm.data.coor.ILatLon; 007import org.openstreetmap.josm.data.coor.LatLon; 008import org.openstreetmap.josm.data.osm.BBox; 009 010/** 011 * Fast index to look up properties of the earth surface. 012 * <p> 013 * It is expected that there is a relatively slow method to look up the property 014 * for a certain coordinate and that there are larger areas with a uniform 015 * property. 016 * <p> 017 * This index tries to find rectangles with uniform property and caches them. 018 * Rectangles are subdivided, if there are different properties within. 019 * (Up to a maximum level, when the slow method is used again.) 020 * 021 * @param <T> the property (like land/water or nation) 022 */ 023public class GeoPropertyIndex<T> { 024 025 private final int maxLevel; 026 private final GeoProperty<T> geoProp; 027 private final GPLevel<T> root; 028 private GPLevel<T> lastLevelUsed; 029 030 private static final boolean DEBUG = false; 031 032 /** 033 * Create new GeoPropertyIndex. 034 * @param geoProp the input property that should be made faster by this index 035 * @param maxLevel max level 036 */ 037 public GeoPropertyIndex(GeoProperty<T> geoProp, int maxLevel) { 038 this.geoProp = geoProp; 039 this.maxLevel = maxLevel; 040 this.root = new GPLevel<>(0, new BBox(-180, -90, 180, 90), null, this); 041 this.lastLevelUsed = root; 042 } 043 044 /** 045 * Look up the property for a certain point. 046 * This gives the same result as {@link GeoProperty#get(LatLon)}, but 047 * should be faster. 048 * @param ll the point coordinates 049 * @return property value at that point 050 */ 051 public T get(LatLon ll) { 052 return lastLevelUsed.get(ll); 053 } 054 055 /** 056 * Returns the geo property. 057 * @return the geo property 058 * @since 14484 059 */ 060 public final GeoProperty<T> getGeoProperty() { 061 return geoProp; 062 } 063 064 protected static class GPLevel<T> { 065 private final T val; 066 private final int level; 067 private final BBox bbox; 068 private final GPLevel<T> parent; 069 private final GeoPropertyIndex<T> owner; 070 071 // child order by index is sw, nw, se, ne 072 private GPLevel<T>[] children; 073 074 public GPLevel(int level, BBox bbox, GPLevel<T> parent, GeoPropertyIndex<T> owner) { 075 this.level = level; 076 this.bbox = bbox; 077 this.parent = parent; 078 this.owner = owner; 079 this.val = owner.geoProp.get(bbox); 080 } 081 082 public T get(LatLon ll) { 083 if (isInside(ll)) 084 return getBounded(ll); 085 if (DEBUG) Logging.trace("up[{0}]", level); 086 return parent != null ? parent.get(ll) : null; 087 } 088 089 private T getBounded(LatLon ll) { 090 if (DEBUG) Logging.trace("GPLevel[{0}]{1}", level, bbox); 091 if (!isInside(ll)) { 092 throw new AssertionError("Point "+ll+" should be inside "+bbox); 093 } 094 if (val != null) { 095 if (DEBUG) Logging.trace("GPLevel[{0}]{1} hit! {2}", level, bbox, val); 096 owner.lastLevelUsed = this; 097 return val; 098 } 099 if (level >= owner.maxLevel) { 100 if (DEBUG) Logging.trace("GPLevel[{0}]{1} max level reached !", level, bbox); 101 return owner.geoProp.get(ll); 102 } 103 104 GPLevel<T>[] currentChildren = this.getChildren(); 105 106 LatLon center = bbox.getCenter(); 107 for (int idx = 0; idx < 4; idx++) { 108 BBox testBBox = null; 109 if (currentChildren[idx] != null) 110 testBBox = currentChildren[idx].bbox; 111 112 if (testBBox == null) { 113 testBBox = generateTestBBox(idx, center.lon(), center.lat()); 114 } 115 if (isInside(testBBox, ll)) { 116 generateChild(currentChildren, testBBox, idx); 117 return currentChildren[idx].getBounded(ll); 118 } 119 } 120 throw new AssertionError("Point "+ll+" should be inside one of the children of "+bbox); 121 } 122 123 /** 124 * Generate the bbox for the specified index in the {@link #getChildren()} array 125 * @param idx The index in the {@link #getChildren()} array 126 * @param lon2 The longitude of the center of the previous level 127 * @param lat2 The latitude of the center of the previous level 128 * @return The test bbox for the specified index in the {@link #getChildren()} array 129 */ 130 private BBox generateTestBBox(int idx, double lon2, double lat2) { 131 double lon1; 132 double lat1; 133 switch (idx) { 134 case 0: 135 lon1 = bbox.getTopLeftLon(); 136 lat1 = bbox.getBottomRightLat(); 137 break; 138 case 1: 139 lon1 = bbox.getTopLeftLon(); 140 lat1 = bbox.getTopLeftLat(); 141 break; 142 case 2: 143 lon1 = bbox.getBottomRightLon(); 144 lat1 = bbox.getBottomRightLat(); 145 break; 146 case 3: 147 lon1 = bbox.getBottomRightLon(); 148 lat1 = bbox.getTopLeftLat(); 149 break; 150 default: 151 throw new AssertionError(); 152 } 153 return new BBox(lon1, lat1, lon2, lat2); 154 } 155 156 /** 157 * Safely generate the child in a multi-threaded environment 158 * @param currentChildren The children array to check 159 * @param testBBox The current bbox (will be used to create the new {@link GPLevel}) 160 * @param idx The index in the child array 161 */ 162 private synchronized void generateChild(GPLevel<T>[] currentChildren, BBox testBBox, int idx) { 163 if (currentChildren[idx] == null) { 164 if (DEBUG) Logging.trace("GPLevel[{0}]{1} - new with idx {2}", level, bbox, idx); 165 currentChildren[idx] = new GPLevel<>(level + 1, testBBox, this, owner); 166 } 167 } 168 169 /** 170 * Get the children array safely in a multi-threaded environment. 171 * If this ends up being a performance issue, look up the "immutable" double-checked locking idiom. 172 * Just be certain you have a good test when checking the performance differences. 173 * See #23309/#23036. The issue there is that {@link Territories#getRegionalTaginfoUrls(LatLon)} 174 * uses a {@link Collection#parallelStream}. 175 * @return The children array (sw, nw, se, ne) 176 */ 177 private synchronized GPLevel<T>[] getChildren() { 178 GPLevel<T>[] currentChildren = this.children; 179 if (currentChildren == null) { 180 @SuppressWarnings("unchecked") 181 GPLevel<T>[] tmp = new GPLevel[4]; 182 currentChildren = tmp; 183 this.children = currentChildren; 184 } 185 return currentChildren; 186 } 187 188 /** 189 * Checks, if a point is inside this tile. 190 * Makes sure, that neighboring tiles do not overlap, i.e. a point exactly 191 * on the border of two tiles must be inside exactly one of the tiles. 192 * @param ll the coordinates of the point 193 * @return true, if it is inside of the box 194 */ 195 boolean isInside(ILatLon ll) { 196 return isInside(bbox, ll); 197 } 198 199 /** 200 * Checks, if a point is inside this tile. 201 * Makes sure, that neighboring tiles do not overlap, i.e. a point exactly 202 * on the border of two tiles must be inside exactly one of the tiles. 203 * @param bbox the tile 204 * @param ll the coordinates of the point 205 * @return true, if it is inside of the box 206 */ 207 boolean isInside(BBox bbox, ILatLon ll) { 208 return bbox.getTopLeftLon() <= ll.lon() && 209 (ll.lon() < bbox.getBottomRightLon() || (ll.lon() == 180.0 && bbox.getBottomRightLon() == 180.0)) && 210 bbox.getBottomRightLat() <= ll.lat() && 211 (ll.lat() < bbox.getTopLeftLat() || (ll.lat() == 90.0 && bbox.getTopLeftLat() == 90.0)); 212 } 213 214 @Override 215 public String toString() { 216 return "GPLevel [val=" + val + ", level=" + level + ", bbox=" + bbox + ']'; 217 } 218 } 219 220 @Override 221 public String toString() { 222 return "GeoPropertyIndex [maxLevel=" + maxLevel + ", geoProp=" + geoProp + ", root=" + root + ", lastLevelUsed=" 223 + lastLevelUsed + ']'; 224 } 225}