Changeset 11237 in josm for trunk/src/org


Ignore:
Timestamp:
2016-11-11T17:43:17+01:00 (8 years ago)
Author:
bastiK
Message:

applied #13933 - Simplify QuadBuckets and improve memory footprint (patch by Gerd Petermann, minor modifications)

Location:
trunk/src/org/openstreetmap/josm/data
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/org/openstreetmap/josm/data/coor/QuadTiling.java

    r11143 r11237  
    7575     * @since 6171
    7676     */
    77     public static int index(final double lat, final double lon, final int level) {
     77    public static byte index(final double lat, final double lon, final int level) {
    7878        long x = lon2x(lon);
    7979        long y = lat2y(lat);
    8080        int shift = NR_LEVELS-level-1;
    81         return (int) ((x >> shift & 1) * 2 + (y >> shift & 1));
     81        return (byte) ((x >> shift & 1) * 2 + (y >> shift & 1));
    8282    }
    8383}

  • trunk/src/org/openstreetmap/josm/data/osm/BBox.java

    r10378 r11237  
    1212public class BBox {
    1313
    14     private double xmin = Double.POSITIVE_INFINITY;
    15     private double xmax = Double.NEGATIVE_INFINITY;
    16     private double ymin = Double.POSITIVE_INFINITY;
    17     private double ymax = Double.NEGATIVE_INFINITY;
     14    protected double xmin = Double.POSITIVE_INFINITY;
     15    protected double xmax = Double.NEGATIVE_INFINITY;
     16    protected double ymin = Double.POSITIVE_INFINITY;
     17    protected double ymax = Double.NEGATIVE_INFINITY;
     18
     19    /**
     20     * Constructs a new (invalid) BBox
     21     */
     22    protected BBox() { }
     23
    1824
    1925    /**
    … …  
    242248    }
    243249
    244     int getIndex(final int level) {
    245 
    246         int idx1 = QuadTiling.index(ymin, xmin, level);
    247 
    248         final int idx2 = QuadTiling.index(ymin, xmax, level);
     250    byte getIndex(final int level) {
     251
     252        byte idx1 = QuadTiling.index(ymin, xmin, level);
     253
     254        final byte idx2 = QuadTiling.index(ymin, xmax, level);
    249255        if (idx1 == -1) idx1 = idx2;
    250256        else if (idx1 != idx2) return -1;
    251257
    252         final int idx3 = QuadTiling.index(ymax, xmin, level);
     258        final byte idx3 = QuadTiling.index(ymax, xmin, level);
    253259        if (idx1 == -1) idx1 = idx3;
    254260        else if (idx1 != idx3) return -1;
    255261
    256         final int idx4 = QuadTiling.index(ymax, xmax, level);
     262        final byte idx4 = QuadTiling.index(ymax, xmax, level);
    257263        if (idx1 == -1) idx1 = idx4;
    258264        else if (idx1 != idx4) return -1;

  • trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java

    r11143 r11237  
    1515/**
    1616 * Note: bbox of primitives added to QuadBuckets has to stay the same. In case of coordinate change, primitive must
    17  * be removed and readded.
     17 * be removed and re-added.
    1818 *
    1919 * This class is (no longer) thread safe.
    … …  
    2323public class QuadBuckets<T extends OsmPrimitive> implements Collection<T> {
    2424    private static final boolean consistency_testing = false;
    25     private static final int NW_INDEX = 1;
    26     private static final int NE_INDEX = 3;
    27     private static final int SE_INDEX = 2;
    28     private static final int SW_INDEX = 0;
     25    private static final byte NW_INDEX = 1;
     26    private static final byte NE_INDEX = 3;
     27    private static final byte SE_INDEX = 2;
     28    private static final byte SW_INDEX = 0;
    2929
    3030    static void abort(String s) {
    … …  
    3232    }
    3333
    34     public static final int MAX_OBJECTS_PER_LEVEL = 16;
    35 
    36     static class QBLevel<T extends OsmPrimitive> {
    37         private final int level;
    38         private final int index;
    39         private final BBox bbox;
     34    private static final int MAX_OBJECTS_PER_NODE = 48;
     35
     36    static class QBLevel<T extends OsmPrimitive> extends BBox {
     37        private final byte level;
     38        private final byte index;
    4039        private final long quad;
    4140        private final QBLevel<T> parent;
    … …  
    4645        private QBLevel<T> nw, ne, sw, se;
    4746
    48         private final QuadBuckets<T> buckets;
    49 
    50         private QBLevel<T> getChild(int index) {
     47        private QBLevel<T> getChild(byte index) {
    5148            switch (index) {
    5249            case NE_INDEX:
    5350                if (ne == null) {
    54                     ne = new QBLevel<>(this, index, buckets);
     51                    ne = new QBLevel<>(this, index);
    5552                }
    5653                return ne;
    5754            case NW_INDEX:
    5855                if (nw == null) {
    59                     nw = new QBLevel<>(this, index, buckets);
     56                    nw = new QBLevel<>(this, index);
    6057                }
    6158                return nw;
    6259            case SE_INDEX:
    6360                if (se == null) {
    64                     se = new QBLevel<>(this, index, buckets);
     61                    se = new QBLevel<>(this, index);
    6562                }
    6663                return se;
    6764            case SW_INDEX:
    6865                if (sw == null) {
    69                     sw = new QBLevel<>(this, index, buckets);
     66                    sw = new QBLevel<>(this, index);
    7067                }
    7168                return sw;
    … …  
    8279        @Override
    8380        public String toString() {
    84             return super.toString() + '[' + level + "]: " + bbox();
     81            return super.toString() + '[' + level + "]: ";
    8582        }
    8683
    8784        /**
    8885         * Constructor for root node
    89          * @param buckets quadbuckets
    9086         */
    91         QBLevel(final QuadBuckets<T> buckets) {
     87        QBLevel() {
     88            super(-180, 90, 180, -90);
    9289            level = 0;
    9390            index = 0;
    9491            quad = 0;
    9592            parent = null;
    96             bbox = new BBox(-180, 90, 180, -90);
    97             this.buckets = buckets;
    98         }
    99 
    100         QBLevel(QBLevel<T> parent, int parentIndex, final QuadBuckets<T> buckets) {
     93        }
     94
     95        QBLevel(QBLevel<T> parent, byte index) {
    10196            this.parent = parent;
    102             this.level = parent.level + 1;
    103             this.index = parentIndex;
    104             this.buckets = buckets;
     97            this.level = (byte) (parent.level + 1);
     98            this.index = index;
    10599
    106100            int shift = (QuadTiling.NR_LEVELS - level) * 2;
    107             long mult = 1;
    108             // Java blows the big one. It seems to wrap when you shift by > 31
    109             if (shift >= 30) {
    110                 shift -= 30;
    111                 mult = 1 << 30;
    112             }
    113             long quadpart = mult * (parentIndex << shift);
     101            long quadpart = (long) index << shift;
    114102            this.quad = parent.quad | quadpart;
    115             this.bbox = calculateBBox(); // calculateBBox reference quad
    116         }
    117 
    118         private BBox calculateBBox() {
    119             LatLon bottomLeft = this.coor();
    120             double lat = bottomLeft.lat() + parent.height() / 2;
    121             double lon = bottomLeft.lon() + parent.width() / 2;
    122             return new BBox(bottomLeft.lon(), bottomLeft.lat(), lon, lat);
     103            LatLon bottomLeft = QuadTiling.tile2LatLon(this.quad);
     104            xmin = bottomLeft.lon();
     105            ymin = bottomLeft.lat();
     106            xmax = xmin + parent.width() / 2;
     107            ymax = ymin + parent.height() / 2;
    123108        }
    124109
    … …  
    127112                return this;
    128113            else {
    129                 int idx = bbox.getIndex(level);
     114                byte idx = bbox.getIndex(level);
    130115                if (idx == -1)
    131116                    return this;
    … …  
    163148
    164149            for (T o : tmpcontent) {
    165                 int idx = o.getBBox().getIndex(level);
     150                byte idx = o.getBBox().getIndex(level);
    166151                if (idx == -1) {
    167152                    doAddContent(o);
    … …  
    283268        void doAdd(T o) {
    284269            if (consistency_testing) {
    285                 if (!matches(o, this.bbox())) {
     270                if (o instanceof Node && !matches(o, this)) {
    286271                    o.getBBox().getIndex(level);
    287272                    o.getBBox().getIndex(level - 1);
    288                     abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + this.bbox());
     273                    abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + super.toString());
    289274                }
    290275            }
    291276            doAddContent(o);
    292             if (isLeaf() && content.size() > MAX_OBJECTS_PER_LEVEL && level < QuadTiling.NR_LEVELS) {
     277            if (isLeaf() && content.size() > MAX_OBJECTS_PER_NODE && level < QuadTiling.NR_LEVELS) {
    293278                doSplit();
    294279            }
    … …  
    299284        }
    300285
    301         private void search(BBox searchBbox, List<T> result) {
    302             if (!this.bbox().intersects(searchBbox))
     286        private void search(QuadBuckets<T> buckets, BBox searchBbox, List<T> result) {
     287            if (!this.intersects(searchBbox))
    303288                return;
    304             else if (bbox().bounds(searchBbox)) {
     289            else if (this.bounds(searchBbox)) {
    305290                buckets.searchCache = this;
    306291            }
    … …  
    313298
    314299            if (nw != null) {
    315                 nw.search(searchBbox, result);
     300                nw.search(buckets, searchBbox, result);
    316301            }
    317302            if (ne != null) {
    318                 ne.search(searchBbox, result);
     303                ne.search(buckets, searchBbox, result);
    319304            }
    320305            if (se != null) {
    321                 se.search(searchBbox, result);
     306                se.search(buckets, searchBbox, result);
    322307            }
    323308            if (sw != null) {
    324                 sw.search(searchBbox, result);
     309                sw.search(buckets, searchBbox, result);
    325310            }
    326311        }
    … …  
    337322            }
    338323            return -1;
    339         }
    340 
    341         double width() {
    342             return bbox.width();
    343         }
    344 
    345         double height() {
    346             return bbox.height();
    347         }
    348 
    349         public BBox bbox() {
    350             return bbox;
    351         }
    352 
    353         /*
    354          * This gives the coordinate of the bottom-left
    355          * corner of the box
    356          */
    357         final LatLon coor() {
    358             return QuadTiling.tile2LatLon(this.quad);
    359324        }
    360325
    … …  
    404369    @Override
    405370    public final void clear() {
    406         root = new QBLevel<>(this);
     371        root = new QBLevel<>();
    407372        searchCache = null;
    408373        size = 0;
    … …  
    583548    }
    584549
     550    /**
     551     * Search the tree for objects in the bbox (or crossing the bbox if they are ways)
     552     * @param searchBbox the bbox
     553     * @return List of primitives within the bbox (or crossing the bbox if they are ways). Can be empty, but not null.
     554     */
    585555    public List<T> search(BBox searchBbox) {
    586556        List<T> ret = new ArrayList<>();
    … …  
    590560        }
    591561        // Walk back up the tree when the last search spot can not cover the current search
    592         while (searchCache != null && !searchCache.bbox().bounds(searchBbox)) {
     562        while (searchCache != null && !searchCache.bounds(searchBbox)) {
    593563            searchCache = searchCache.parent;
    594564        }
    … …  
    602572        QBLevel<T> tmp = searchCache.parent;
    603573
    604         searchCache.search(searchBbox, ret);
     574        searchCache.search(this, searchBbox, ret);
    605575
    606576        // A way that spans this bucket may be stored in one
Note: See TracChangeset for help on using the changeset viewer.