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<T>(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}