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}