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 /** 023 * A method to look up a property of the earth surface. 024 * (User input for the index.) 025 * @param <T> the property 026 */ 027 public interface GeoProperty<T> { 028 /** 029 * Look up the property for a point. 030 * @param ll the point coordinates 031 * @return property value at that point. Must not be null. 032 */ 033 T get(LatLon ll); 034 035 /** 036 * Look up the property for a coordinate rectangle. 037 * @param box the rectangle 038 * @return the property, if it is the same in the entire rectangle; 039 * null otherwise 040 */ 041 T get(BBox box); 042 } 043 044 private final int maxLevel; 045 private final GeoProperty<T> geoProp; 046 private final GPLevel<T> root; 047 private GPLevel<T> lastLevelUsed; 048 049 private static final boolean DEBUG = false; 050 051 /** 052 * Create new GeoPropertyIndex. 053 * @param geoProp the input property that should be made faster by this index 054 * @param maxLevel max level 055 */ 056 public GeoPropertyIndex(GeoProperty<T> geoProp, int maxLevel) { 057 this.geoProp = geoProp; 058 this.maxLevel = maxLevel; 059 this.root = new GPLevel<>(0, new BBox(-180, -90, 180, 90), null, this); 060 this.lastLevelUsed = root; 061 } 062 063 /** 064 * Look up the property for a certain point. 065 * This gives the same result as {@link GeoProperty#get(LatLon)}, but 066 * should be faster. 067 * @param ll the point coordinates 068 * @return property value at that point 069 */ 070 public T get(LatLon ll) { 071 return lastLevelUsed.get(ll); 072 } 073 074 public static int index(LatLon ll, int level) { 075 long noParts = 1 << level; 076 long x = ((long) ((ll.lon() + 180.0) * noParts / 360.0)) & 1; 077 long y = ((long) ((ll.lat() + 90.0) * noParts / 180.0)) & 1; 078 return (int) (2 * x + y); 079 } 080 081 protected static class GPLevel<T> { 082 private final T val; 083 private final int level; 084 private final BBox bbox; 085 private final GPLevel<T> parent; 086 private final GeoPropertyIndex<T> owner; 087 088 // child order by index is sw, nw, se, ne 089 private GPLevel<T>[] children; 090 091 public GPLevel(int level, BBox bbox, GPLevel<T> parent, GeoPropertyIndex<T> owner) { 092 this.level = level; 093 this.bbox = bbox; 094 this.parent = parent; 095 this.owner = owner; 096 this.val = owner.geoProp.get(bbox); 097 } 098 099 public T get(LatLon ll) { 100 if (isInside(ll)) 101 return getBounded(ll); 102 if (DEBUG) System.err.print("up["+level+"]"); 103 return parent.get(ll); 104 } 105 106 private T getBounded(LatLon ll) { 107 if (DEBUG) System.err.print("GPLevel["+level+"]"+bbox+" "); 108 if (!isInside(ll)) { 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 } 120 121 if (children == null) { 122 @SuppressWarnings("unchecked") 123 GPLevel<T>[] tmp = new GPLevel[4]; 124 this.children = tmp; 125 } 126 127 int idx = index(ll, level+1); 128 if (children[idx] == null) { 129 double lon1, lat1; 130 switch (idx) { 131 case 0: 132 lon1 = bbox.getTopLeftLon(); 133 lat1 = bbox.getBottomRightLat(); 134 break; 135 case 1: 136 lon1 = bbox.getTopLeftLon(); 137 lat1 = bbox.getTopLeftLat(); 138 break; 139 case 2: 140 lon1 = bbox.getBottomRightLon(); 141 lat1 = bbox.getBottomRightLat(); 142 break; 143 case 3: 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(); 152 BBox b = new BBox(lon1, lat1, center.lon(), center.lat()); 153 children[idx] = new GPLevel<>(level + 1, b, this, owner); 154 } 155 return children[idx].getBounded(ll); 156 } 157 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) { 166 return bbox.getTopLeftLon() <= ll.lon() && 167 (ll.lon() < bbox.getBottomRightLon() || (ll.lon() == 180.0 && bbox.getBottomRightLon() == 180.0)) && 168 bbox.getBottomRightLat() <= ll.lat() && 169 (ll.lat() < bbox.getTopLeftLat() || (ll.lat() == 90.0 && bbox.getTopLeftLat() == 90.0)); 170 } 171 172 } 173}