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 * Look up the property for a coordinate rectangle. 036 * @param box the rectangle 037 * @return the property, if it is the same in the entire rectangle; 038 * null otherwise 039 */ 040 T get(BBox box); 041 } 042 043 private final int maxLevel; 044 private final GeoProperty<T> geoProp; 045 private final GPLevel<T> root; 046 private GPLevel<T> lastLevelUsed; 047 048 private static final boolean DEBUG = false; 049 050 /** 051 * Create new GeoPropertyIndex. 052 * @param geoProp the input property that should be made faster by this index 053 * @param maxLevel 054 */ 055 public GeoPropertyIndex(GeoProperty<T> geoProp, int maxLevel) { 056 this.geoProp = geoProp; 057 this.maxLevel = maxLevel; 058 this.root = new GPLevel<T>(0, new BBox(-180, -90, 180, 90), null, this); 059 this.lastLevelUsed = root; 060 } 061 062 /** 063 * Look up the property for a certain point. 064 * This gives the same result as {@link #geoProp#get(LatLon)}, but 065 * should be faster. 066 * @param ll the point coordinates 067 * @return property value at that point 068 */ 069 public T get(LatLon ll) { 070 return lastLevelUsed.get(ll); 071 } 072 073 public static int index(LatLon ll, int level) { 074 long noParts = 1 << level; 075 long x = ((long)((ll.lon() + 180.0) * noParts / 360.0)) & 1; 076 long y = ((long)((ll.lat() + 90.0) * noParts / 180.0)) & 1; 077 return (int) (2 * x + y); 078 } 079 080 protected static class GPLevel<T> { 081 private final T val; 082 private final int level; 083 private final BBox bbox; 084 private final GPLevel<T> parent; 085 private final GeoPropertyIndex<T> owner; 086 087 // child order by index is sw, nw, se, ne 088 private GPLevel<T>[] children; 089 090 public GPLevel(int level, BBox bbox, GPLevel<T> parent, GeoPropertyIndex<T> owner) { 091 this.level = level; 092 this.bbox = bbox; 093 this.parent = parent; 094 this.owner = owner; 095 this.val = owner.geoProp.get(bbox); 096 } 097 098 public T get(LatLon ll) { 099 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}