Index: trunk/src/org/openstreetmap/josm/data/coor/QuadTiling.java =================================================================== --- trunk/src/org/openstreetmap/josm/data/coor/QuadTiling.java (revision 11236) +++ trunk/src/org/openstreetmap/josm/data/coor/QuadTiling.java (revision 11237) @@ -75,9 +75,9 @@ * @since 6171 */ - public static int index(final double lat, final double lon, final int level) { + public static byte index(final double lat, final double lon, final int level) { long x = lon2x(lon); long y = lat2y(lat); int shift = NR_LEVELS-level-1; - return (int) ((x >> shift & 1) * 2 + (y >> shift & 1)); + return (byte) ((x >> shift & 1) * 2 + (y >> shift & 1)); } } Index: trunk/src/org/openstreetmap/josm/data/osm/BBox.java =================================================================== --- trunk/src/org/openstreetmap/josm/data/osm/BBox.java (revision 11236) +++ trunk/src/org/openstreetmap/josm/data/osm/BBox.java (revision 11237) @@ -12,8 +12,14 @@ public class BBox { - private double xmin = Double.POSITIVE_INFINITY; - private double xmax = Double.NEGATIVE_INFINITY; - private double ymin = Double.POSITIVE_INFINITY; - private double ymax = Double.NEGATIVE_INFINITY; + protected double xmin = Double.POSITIVE_INFINITY; + protected double xmax = Double.NEGATIVE_INFINITY; + protected double ymin = Double.POSITIVE_INFINITY; + protected double ymax = Double.NEGATIVE_INFINITY; + + /** + * Constructs a new (invalid) BBox + */ + protected BBox() { } + /** @@ -242,17 +248,17 @@ } - int getIndex(final int level) { - - int idx1 = QuadTiling.index(ymin, xmin, level); - - final int idx2 = QuadTiling.index(ymin, xmax, level); + byte getIndex(final int level) { + + byte idx1 = QuadTiling.index(ymin, xmin, level); + + final byte idx2 = QuadTiling.index(ymin, xmax, level); if (idx1 == -1) idx1 = idx2; else if (idx1 != idx2) return -1; - final int idx3 = QuadTiling.index(ymax, xmin, level); + final byte idx3 = QuadTiling.index(ymax, xmin, level); if (idx1 == -1) idx1 = idx3; else if (idx1 != idx3) return -1; - final int idx4 = QuadTiling.index(ymax, xmax, level); + final byte idx4 = QuadTiling.index(ymax, xmax, level); if (idx1 == -1) idx1 = idx4; else if (idx1 != idx4) return -1; Index: trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java =================================================================== --- trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java (revision 11236) +++ trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java (revision 11237) @@ -15,5 +15,5 @@ /** * Note: bbox of primitives added to QuadBuckets has to stay the same. In case of coordinate change, primitive must - * be removed and readded. + * be removed and re-added. * * This class is (no longer) thread safe. @@ -23,8 +23,8 @@ public class QuadBuckets implements Collection { private static final boolean consistency_testing = false; - private static final int NW_INDEX = 1; - private static final int NE_INDEX = 3; - private static final int SE_INDEX = 2; - private static final int SW_INDEX = 0; + private static final byte NW_INDEX = 1; + private static final byte NE_INDEX = 3; + private static final byte SE_INDEX = 2; + private static final byte SW_INDEX = 0; static void abort(String s) { @@ -32,10 +32,9 @@ } - public static final int MAX_OBJECTS_PER_LEVEL = 16; - - static class QBLevel { - private final int level; - private final int index; - private final BBox bbox; + private static final int MAX_OBJECTS_PER_NODE = 48; + + static class QBLevel extends BBox { + private final byte level; + private final byte index; private final long quad; private final QBLevel parent; @@ -46,26 +45,24 @@ private QBLevel nw, ne, sw, se; - private final QuadBuckets buckets; - - private QBLevel getChild(int index) { + private QBLevel getChild(byte index) { switch (index) { case NE_INDEX: if (ne == null) { - ne = new QBLevel<>(this, index, buckets); + ne = new QBLevel<>(this, index); } return ne; case NW_INDEX: if (nw == null) { - nw = new QBLevel<>(this, index, buckets); + nw = new QBLevel<>(this, index); } return nw; case SE_INDEX: if (se == null) { - se = new QBLevel<>(this, index, buckets); + se = new QBLevel<>(this, index); } return se; case SW_INDEX: if (sw == null) { - sw = new QBLevel<>(this, index, buckets); + sw = new QBLevel<>(this, index); } return sw; @@ -82,43 +79,31 @@ @Override public String toString() { - return super.toString() + '[' + level + "]: " + bbox(); + return super.toString() + '[' + level + "]: "; } /** * Constructor for root node - * @param buckets quadbuckets */ - QBLevel(final QuadBuckets buckets) { + QBLevel() { + super(-180, 90, 180, -90); level = 0; index = 0; quad = 0; parent = null; - bbox = new BBox(-180, 90, 180, -90); - this.buckets = buckets; - } - - QBLevel(QBLevel parent, int parentIndex, final QuadBuckets buckets) { + } + + QBLevel(QBLevel parent, byte index) { this.parent = parent; - this.level = parent.level + 1; - this.index = parentIndex; - this.buckets = buckets; + this.level = (byte) (parent.level + 1); + this.index = index; int shift = (QuadTiling.NR_LEVELS - level) * 2; - long mult = 1; - // Java blows the big one. It seems to wrap when you shift by > 31 - if (shift >= 30) { - shift -= 30; - mult = 1 << 30; - } - long quadpart = mult * (parentIndex << shift); + long quadpart = (long) index << shift; this.quad = parent.quad | quadpart; - this.bbox = calculateBBox(); // calculateBBox reference quad - } - - private BBox calculateBBox() { - LatLon bottomLeft = this.coor(); - double lat = bottomLeft.lat() + parent.height() / 2; - double lon = bottomLeft.lon() + parent.width() / 2; - return new BBox(bottomLeft.lon(), bottomLeft.lat(), lon, lat); + LatLon bottomLeft = QuadTiling.tile2LatLon(this.quad); + xmin = bottomLeft.lon(); + ymin = bottomLeft.lat(); + xmax = xmin + parent.width() / 2; + ymax = ymin + parent.height() / 2; } @@ -127,5 +112,5 @@ return this; else { - int idx = bbox.getIndex(level); + byte idx = bbox.getIndex(level); if (idx == -1) return this; @@ -163,5 +148,5 @@ for (T o : tmpcontent) { - int idx = o.getBBox().getIndex(level); + byte idx = o.getBBox().getIndex(level); if (idx == -1) { doAddContent(o); @@ -283,12 +268,12 @@ void doAdd(T o) { if (consistency_testing) { - if (!matches(o, this.bbox())) { + if (o instanceof Node && !matches(o, this)) { o.getBBox().getIndex(level); o.getBBox().getIndex(level - 1); - abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + this.bbox()); + abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + super.toString()); } } doAddContent(o); - if (isLeaf() && content.size() > MAX_OBJECTS_PER_LEVEL && level < QuadTiling.NR_LEVELS) { + if (isLeaf() && content.size() > MAX_OBJECTS_PER_NODE && level < QuadTiling.NR_LEVELS) { doSplit(); } @@ -299,8 +284,8 @@ } - private void search(BBox searchBbox, List result) { - if (!this.bbox().intersects(searchBbox)) + private void search(QuadBuckets buckets, BBox searchBbox, List result) { + if (!this.intersects(searchBbox)) return; - else if (bbox().bounds(searchBbox)) { + else if (this.bounds(searchBbox)) { buckets.searchCache = this; } @@ -313,14 +298,14 @@ if (nw != null) { - nw.search(searchBbox, result); + nw.search(buckets, searchBbox, result); } if (ne != null) { - ne.search(searchBbox, result); + ne.search(buckets, searchBbox, result); } if (se != null) { - se.search(searchBbox, result); + se.search(buckets, searchBbox, result); } if (sw != null) { - sw.search(searchBbox, result); + sw.search(buckets, searchBbox, result); } } @@ -337,24 +322,4 @@ } return -1; - } - - double width() { - return bbox.width(); - } - - double height() { - return bbox.height(); - } - - public BBox bbox() { - return bbox; - } - - /* - * This gives the coordinate of the bottom-left - * corner of the box - */ - final LatLon coor() { - return QuadTiling.tile2LatLon(this.quad); } @@ -404,5 +369,5 @@ @Override public final void clear() { - root = new QBLevel<>(this); + root = new QBLevel<>(); searchCache = null; size = 0; @@ -583,4 +548,9 @@ } + /** + * Search the tree for objects in the bbox (or crossing the bbox if they are ways) + * @param searchBbox the bbox + * @return List of primitives within the bbox (or crossing the bbox if they are ways). Can be empty, but not null. + */ public List search(BBox searchBbox) { List ret = new ArrayList<>(); @@ -590,5 +560,5 @@ } // Walk back up the tree when the last search spot can not cover the current search - while (searchCache != null && !searchCache.bbox().bounds(searchBbox)) { + while (searchCache != null && !searchCache.bounds(searchBbox)) { searchCache = searchCache.parent; } @@ -602,5 +572,5 @@ QBLevel tmp = searchCache.parent; - searchCache.search(searchBbox, ret); + searchCache.search(this, searchBbox, ret); // A way that spans this bucket may be stored in one