source: josm/trunk/src/org/openstreetmap/josm/tools/GeoPropertyIndex.java @ 14008

Last change on this file since 14008 was 14008, checked in by Don-vip, 5 months ago

fix #16467 - NPE

  • Property svn:eol-style set to native
File size: 6.0 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.tools;
3
4import org.openstreetmap.josm.data.coor.LatLon;
5import org.openstreetmap.josm.data.osm.BBox;
6
7/**
8 * Fast index to look up properties of the earth surface.
9 *
10 * It is expected that there is a relatively slow method to look up the property
11 * for a certain coordinate and that there are larger areas with a uniform
12 * property.
13 *
14 * This index tries to find rectangles with uniform property and caches them.
15 * Rectangles are subdivided, if there are different properties within.
16 * (Up to a maximum level, when the slow method is used again.)
17 *
18 * @param <T> the property (like land/water or nation)
19 */
20public class GeoPropertyIndex<T> {
21
22    private final int maxLevel;
23    private final GeoProperty<T> geoProp;
24    private final GPLevel<T> root;
25    private GPLevel<T> lastLevelUsed;
26
27    private static final boolean DEBUG = false;
28
29    /**
30     * Create new GeoPropertyIndex.
31     * @param geoProp the input property that should be made faster by this index
32     * @param maxLevel max level
33     */
34    public GeoPropertyIndex(GeoProperty<T> geoProp, int maxLevel) {
35        this.geoProp = geoProp;
36        this.maxLevel = maxLevel;
37        this.root = new GPLevel<>(0, new BBox(-180, -90, 180, 90), null, this);
38        this.lastLevelUsed = root;
39    }
40
41    /**
42     * Look up the property for a certain point.
43     * This gives the same result as {@link GeoProperty#get(LatLon)}, but
44     * should be faster.
45     * @param ll the point coordinates
46     * @return property value at that point
47     */
48    public T get(LatLon ll) {
49        return lastLevelUsed.get(ll);
50    }
51
52    /**
53     * Gets the index of the given coordinate. Only used internally
54     * @param ll The lat/lon coordinate
55     * @param level The scale level
56     * @return The index for that position
57     */
58    public static int index(LatLon ll, int level) {
59        long noParts = 1L << level;
60        long x = ((long) ((ll.lon() + 180.0) * noParts / 360.0)) & 1;
61        long y = ((long) ((ll.lat() + 90.0) * noParts / 180.0)) & 1;
62        return (int) (2 * x + y);
63    }
64
65    protected static class GPLevel<T> {
66        private final T val;
67        private final int level;
68        private final BBox bbox;
69        private final GPLevel<T> parent;
70        private final GeoPropertyIndex<T> owner;
71
72        // child order by index is sw, nw, se, ne
73        private GPLevel<T>[] children;
74
75        public GPLevel(int level, BBox bbox, GPLevel<T> parent, GeoPropertyIndex<T> owner) {
76            this.level = level;
77            this.bbox = bbox;
78            this.parent = parent;
79            this.owner = owner;
80            this.val = owner.geoProp.get(bbox);
81        }
82
83        public T get(LatLon ll) {
84            if (isInside(ll))
85                return getBounded(ll);
86            if (DEBUG) System.err.print("up["+level+"]");
87            return parent != null ? parent.get(ll) : null;
88        }
89
90        private T getBounded(LatLon ll) {
91            if (DEBUG) System.err.print("GPLevel["+level+"]"+bbox+" ");
92            if (!isInside(ll)) {
93                throw new AssertionError("Point "+ll+" should be inside "+bbox);
94            }
95            if (val != null) {
96                if (DEBUG) System.err.println(" hit! "+val);
97                owner.lastLevelUsed = this;
98                return val;
99            }
100            if (level >= owner.maxLevel) {
101                if (DEBUG) System.err.println(" max level reached !");
102                return owner.geoProp.get(ll);
103            }
104
105            if (children == null) {
106                @SuppressWarnings("unchecked")
107                GPLevel<T>[] tmp = new GPLevel[4];
108                this.children = tmp;
109            }
110
111            int idx = index(ll, level+1);
112            if (children[idx] == null) {
113            double lon1, lat1;
114                switch (idx) {
115                    case 0:
116                        lon1 = bbox.getTopLeftLon();
117                        lat1 = bbox.getBottomRightLat();
118                        break;
119                    case 1:
120                        lon1 = bbox.getTopLeftLon();
121                        lat1 = bbox.getTopLeftLat();
122                        break;
123                    case 2:
124                        lon1 = bbox.getBottomRightLon();
125                        lat1 = bbox.getBottomRightLat();
126                        break;
127                    case 3:
128                        lon1 = bbox.getBottomRightLon();
129                        lat1 = bbox.getTopLeftLat();
130                        break;
131                    default:
132                        throw new AssertionError();
133                }
134                if (DEBUG) System.err.println(" - new with idx "+idx);
135                LatLon center = bbox.getCenter();
136                BBox b = new BBox(lon1, lat1, center.lon(), center.lat());
137                children[idx] = new GPLevel<>(level + 1, b, this, owner);
138            }
139            return children[idx].getBounded(ll);
140        }
141
142        /**
143         * Checks, if a point is inside this tile.
144         * Makes sure, that neighboring tiles do not overlap, i.e. a point exactly
145         * on the border of two tiles must be inside exactly one of the tiles.
146         * @param ll the coordinates of the point
147         * @return true, if it is inside of the box
148         */
149        boolean isInside(LatLon ll) {
150            return bbox.getTopLeftLon() <= ll.lon() &&
151                    (ll.lon() < bbox.getBottomRightLon() || (ll.lon() == 180.0 && bbox.getBottomRightLon() == 180.0)) &&
152                    bbox.getBottomRightLat() <= ll.lat() &&
153                    (ll.lat() < bbox.getTopLeftLat() || (ll.lat() == 90.0 && bbox.getTopLeftLat() == 90.0));
154        }
155
156        @Override
157        public String toString() {
158            return "GPLevel [val=" + val + ", level=" + level + ", bbox=" + bbox + ']';
159        }
160    }
161
162    @Override
163    public String toString() {
164        return "GeoPropertyIndex [maxLevel=" + maxLevel + ", geoProp=" + geoProp + ", root=" + root + ", lastLevelUsed="
165                + lastLevelUsed + ']';
166    }
167}
Note: See TracBrowser for help on using the repository browser.