001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.tools; 003 004import org.openstreetmap.josm.data.coor.LatLon; 005import org.openstreetmap.josm.data.osm.BBox; 006 007/** 008 * Fast index to look up properties of the earth surface. 009 * 010 * It is expected that there is a relatively slow method to look up the property 011 * for a certain coordinate and that there are larger areas with a uniform 012 * property. 013 * 014 * This index tries to find rectangles with uniform property and caches them. 015 * Rectangles are subdivided, if there are different properties within. 016 * (Up to a maximum level, when the slow method is used again.) 017 * 018 * @param <T> the property (like land/water or nation) 019 */ 020public class GeoPropertyIndex<T> { 021 022 private final int maxLevel; 023 private final GeoProperty<T> geoProp; 024 private final GPLevel<T> root; 025 private GPLevel<T> lastLevelUsed; 026 027 private static final boolean DEBUG = false; 028 029 /** 030 * Create new GeoPropertyIndex. 031 * @param geoProp the input property that should be made faster by this index 032 * @param maxLevel max level 033 */ 034 public GeoPropertyIndex(GeoProperty<T> geoProp, int maxLevel) { 035 this.geoProp = geoProp; 036 this.maxLevel = maxLevel; 037 this.root = new GPLevel<>(0, new BBox(-180, -90, 180, 90), null, this); 038 this.lastLevelUsed = root; 039 } 040 041 /** 042 * Look up the property for a certain point. 043 * This gives the same result as {@link GeoProperty#get(LatLon)}, but 044 * should be faster. 045 * @param ll the point coordinates 046 * @return property value at that point 047 */ 048 public T get(LatLon ll) { 049 return lastLevelUsed.get(ll); 050 } 051 052 /** 053 * Returns the geo property. 054 * @return the geo property 055 * @since 14484 056 */ 057 public final GeoProperty<T> getGeoProperty() { 058 return geoProp; 059 } 060 061 protected static class GPLevel<T> { 062 private final T val; 063 private final int level; 064 private final BBox bbox; 065 private final GPLevel<T> parent; 066 private final GeoPropertyIndex<T> owner; 067 068 // child order by index is sw, nw, se, ne 069 private GPLevel<T>[] children; 070 071 public GPLevel(int level, BBox bbox, GPLevel<T> parent, GeoPropertyIndex<T> owner) { 072 this.level = level; 073 this.bbox = bbox; 074 this.parent = parent; 075 this.owner = owner; 076 this.val = owner.geoProp.get(bbox); 077 } 078 079 public T get(LatLon ll) { 080 if (isInside(ll)) 081 return getBounded(ll); 082 if (DEBUG) System.err.print("up["+level+"]"); 083 return parent != null ? parent.get(ll) : null; 084 } 085 086 private T getBounded(LatLon ll) { 087 if (DEBUG) System.err.print("GPLevel["+level+"]"+bbox+" "); 088 if (!isInside(ll)) { 089 throw new AssertionError("Point "+ll+" should be inside "+bbox); 090 } 091 if (val != null) { 092 if (DEBUG) System.err.println(" hit! "+val); 093 owner.lastLevelUsed = this; 094 return val; 095 } 096 if (level >= owner.maxLevel) { 097 if (DEBUG) System.err.println(" max level reached !"); 098 return owner.geoProp.get(ll); 099 } 100 101 if (children == null) { 102 @SuppressWarnings("unchecked") 103 GPLevel<T>[] tmp = new GPLevel[4]; 104 this.children = tmp; 105 } 106 107 LatLon center = bbox.getCenter(); 108 for (int idx = 0; idx < 4; idx++) { 109 BBox testBBox = null; 110 if (children[idx] != null) 111 testBBox = children[idx].bbox; 112 113 if (testBBox == null) { 114 double lon1, lat1; 115 switch (idx) { 116 case 0: 117 lon1 = bbox.getTopLeftLon(); 118 lat1 = bbox.getBottomRightLat(); 119 break; 120 case 1: 121 lon1 = bbox.getTopLeftLon(); 122 lat1 = bbox.getTopLeftLat(); 123 break; 124 case 2: 125 lon1 = bbox.getBottomRightLon(); 126 lat1 = bbox.getBottomRightLat(); 127 break; 128 case 3: 129 lon1 = bbox.getBottomRightLon(); 130 lat1 = bbox.getTopLeftLat(); 131 break; 132 default: 133 throw new AssertionError(); 134 } 135 testBBox = new BBox(lon1, lat1, center.lon(), center.lat()); 136 } 137 if (isInside(testBBox, ll)) { 138 if (children[idx] == null) { 139 if (DEBUG) System.err.println(" - new with idx "+idx); 140 children[idx] = new GPLevel<>(level + 1, testBBox, this, owner); 141 } 142 return children[idx].getBounded(ll); 143 } 144 } 145 throw new AssertionError("Point "+ll+" should be inside one of the children of "+bbox); 146 } 147 148 /** 149 * Checks, if a point is inside this tile. 150 * Makes sure, that neighboring tiles do not overlap, i.e. a point exactly 151 * on the border of two tiles must be inside exactly one of the tiles. 152 * @param ll the coordinates of the point 153 * @return true, if it is inside of the box 154 */ 155 boolean isInside(LatLon ll) { 156 return isInside(bbox, ll); 157 } 158 159 /** 160 * Checks, if a point is inside this tile. 161 * Makes sure, that neighboring tiles do not overlap, i.e. a point exactly 162 * on the border of two tiles must be inside exactly one of the tiles. 163 * @param bbox the tile 164 * @param ll the coordinates of the point 165 * @return true, if it is inside of the box 166 */ 167 boolean isInside(BBox bbox, LatLon ll) { 168 return bbox.getTopLeftLon() <= ll.lon() && 169 (ll.lon() < bbox.getBottomRightLon() || (ll.lon() == 180.0 && bbox.getBottomRightLon() == 180.0)) && 170 bbox.getBottomRightLat() <= ll.lat() && 171 (ll.lat() < bbox.getTopLeftLat() || (ll.lat() == 90.0 && bbox.getTopLeftLat() == 90.0)); 172 } 173 174 @Override 175 public String toString() { 176 return "GPLevel [val=" + val + ", level=" + level + ", bbox=" + bbox + ']'; 177 } 178 } 179 180 @Override 181 public String toString() { 182 return "GeoPropertyIndex [maxLevel=" + maxLevel + ", geoProp=" + geoProp + ", root=" + root + ", lastLevelUsed=" 183 + lastLevelUsed + ']'; 184 } 185}