Changeset 11269 in josm


Ignore:
Timestamp:
2016-11-17T19:58:39+01:00 (8 years ago)
Author:
michael2402
Message:

Fix #13361: Use a more consistent invalid bbox for primitives.

Patch by Gerd Petermann

Location:
trunk
Files:
11 edited

Legend:

Unmodified
Added
Removed

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

    r11237 r11269  
    2020     * Constructs a new (invalid) BBox
    2121     */
    22     protected BBox() { }
    23 
     22    public BBox() { }
    2423
    2524    /**
    … …  
    3130     */
    3231    public BBox(final double x, final double y) {
    33         xmax = xmin = x;
    34         ymax = ymin = y;
    35         sanity();
     32        if (!Double.isNaN(x) && !Double.isNaN(y)) {
     33            xmin = x;
     34            ymin = y;
     35            xmax = x;
     36            ymax = y;
     37        }
    3638    }
    3739
    3840    /**
    3941     * Constructs a new {@code BBox} defined by points <code>a</code> and <code>b</code>.
    40      * Result is minimal BBox containing both points.
     42     * Result is minimal BBox containing both points if they are both valid, else undefined
    4143     *
    4244     * @param a first point
    … …  
    5961    }
    6062
     63    /**
     64     * Create minimal  BBox so that {@code this.bounds(ax,ay)} and {@code this.bounds(bx,by)} will both return true
     65     * @param ax left or right X value (-180 .. 180)
     66     * @param ay top or bottom Y value (-90 .. 90)
     67     * @param bx left or right X value (-180 .. 180)
     68     * @param by top or bottom Y value (-90 .. 90)
     69     */
    6170    public BBox(double ax, double ay, double bx, double by) {
     71        if (Double.isNaN(ax) || Double.isNaN(ay) || Double.isNaN(bx) || Double.isNaN(by)) {
     72            return; // use default which is an invalid BBox
     73        }
    6274
    6375        if (ax > bx) {
    … …  
    7688            ymin = ay;
    7789        }
    78 
    79         sanity();
    80     }
    81 
     90    }
     91
     92    /**
     93     * Create BBox for all nodes of the way with known coordinates.
     94     * If no node has a known coordinate, an invalid BBox is returned.
     95     * @param w the way
     96     */
    8297    public BBox(Way w) {
    83         for (Node n : w.getNodes()) {
    84             LatLon coor = n.getCoor();
    85             if (coor == null) {
    86                 continue;
    87             }
    88             add(coor);
    89         }
    90     }
    91 
     98        w.getNodes().forEach((n) -> add(n.getCoor()));
     99    }
     100
     101    /**
     102     * Create BBox for a node. An invalid BBox is returned if the coordinates are not known.
     103     * @param n the node
     104     */
    92105    public BBox(Node n) {
    93         LatLon coor = n.getCoor();
    94         if (coor == null) {
    95             xmin = xmax = ymin = ymax = 0;
    96         } else {
    97             xmin = xmax = coor.lon();
    98             ymin = ymax = coor.lat();
    99         }
    100     }
    101 
    102     private void sanity() {
    103         if (xmin < -180.0) {
    104             xmin = -180.0;
    105         }
    106         if (xmax > 180.0) {
    107             xmax = 180.0;
    108         }
    109         if (ymin < -90.0) {
    110             ymin = -90.0;
    111         }
    112         if (ymax > 90.0) {
    113             ymax = 90.0;
    114         }
    115     }
    116 
     106        if (n.isLatLonKnown())
     107            add(n.getCoor());
     108    }
     109
     110    /**
     111     * Add a point to an existing BBox. Extends this bbox if necessary so that this.bounds(c) will return true
     112     * if c is a valid LatLon instance.
     113     * @param c a LatLon point
     114     */
    117115    public final void add(LatLon c) {
    118         add(c.lon(), c.lat());
     116        if (c != null && c.isValid())
     117            add(c.lon(), c.lat());
    119118    }
    120119
    … …  
    125124     */
    126125    public final void add(double x, double y) {
     126        if (Double.isNaN(x) || Double.isNaN(y))
     127            return;
    127128        xmin = Math.min(xmin, x);
    128129        xmax = Math.max(xmax, x);
    129130        ymin = Math.min(ymin, y);
    130131        ymax = Math.max(ymax, y);
    131         sanity();
    132     }
    133 
    134     public final void add(BBox box) {
    135         xmin = Math.min(xmin, box.xmin);
    136         xmax = Math.max(xmax, box.xmax);
    137         ymin = Math.min(ymin, box.ymin);
    138         ymax = Math.max(ymax, box.ymax);
    139         sanity();
    140     }
    141 
     132    }
     133
     134    /**
     135     * Extends this bbox to include the bbox other. Does nothing if other is not valid.
     136     * @param other a bbox
     137     */
     138    public final void add(BBox other) {
     139        if (other.isValid()) {
     140            xmin = Math.min(xmin, other.xmin);
     141            xmax = Math.max(xmax, other.xmax);
     142            ymin = Math.min(ymin, other.ymin);
     143            ymax = Math.max(ymax, other.ymax);
     144        }
     145    }
     146
     147    /**
     148     * Extends this bbox to include the bbox of the primitive extended by extraSpace.
     149     * @param primitive an OSM primitive
     150     * @param extraSpace the value to extend the primitives bbox. Unit is in LatLon degrees.
     151     */
    142152    public void addPrimitive(OsmPrimitive primitive, double extraSpace) {
    143153        BBox primBbox = primitive.getBBox();
    … …  
    285295    }
    286296
     297    /**
     298     * @return true if the bbox covers a part of the planets surface
     299     * Height and width must be non-negative, but may (both) be 0.
     300     */
     301    public boolean isValid() {
     302        return (xmin <= xmax && ymin <= ymax);
     303    }
     304
     305    /**
     306     * @return true if the bbox covers a part of the planets surface
     307     */
     308    public boolean isInWorld() {
     309        return !(xmin < -180.0 || xmax > 180.0 || ymin < -90.0 || ymax > 90.0);
     310    }
     311
    287312    @Override
    288313    public String toString() {

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

    r11115 r11269  
    504504                        tr("Unable to add primitive {0} to the dataset because it is already included", primitive.toString()));
    505505
    506             primitive.updatePosition(); // Set cached bbox for way and relation (required for reindexWay and reinexRelation to work properly)
     506            allPrimitives.add(primitive);
     507            primitive.setDataset(this);
     508            primitive.updatePosition(); // Set cached bbox for way and relation (required for reindexWay and reindexRelation to work properly)
    507509            boolean success = false;
    508510            if (primitive instanceof Node) {
    … …  
    515517            if (!success)
    516518                throw new RuntimeException("failed to add primitive: "+primitive);
    517             allPrimitives.add(primitive);
    518             primitive.setDataset(this);
    519519            firePrimitivesAdded(Collections.singletonList(primitive), false);
    520520        } finally {

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

    r10919 r11269  
    330330    @Override
    331331    public BBox getBBox() {
    332         return new BBox(this);
     332        return new BBox(lon, lat);
     333    }
     334
     335    @Override
     336    protected void addToBBox(BBox box, Set<PrimitiveId> visited) {
     337        box.add(lon, lat);
    333338    }
    334339

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

    r11079 r11269  
    14171417        return false;
    14181418    }
     1419
     1420    /**
     1421     * If necessary, extend the bbox to contain this primitive
     1422     * @param box a bbox instance
     1423     * @param visited a set of visited members  or null
     1424     */
     1425    protected abstract void addToBBox(BBox box, Set<PrimitiveId> visited);
    14191426}

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

    r11237 r11269  
    66import java.util.Collection;
    77import java.util.Iterator;
     8import java.util.LinkedHashSet;
    89import java.util.List;
    910import java.util.NoSuchElementException;
    … …  
    167168
    168169        boolean matches(final T o, final BBox searchBbox) {
    169             if (o instanceof Node) {
    170                 final LatLon latLon = ((Node) o).getCoor();
    171                 // node without coords -> bbox[0,0,0,0]
    172                 return searchBbox.bounds(latLon != null ? latLon : LatLon.ZERO);
    173             }
    174170            return o.getBBox().intersects(searchBbox);
    175171        }
    … …  
    359355    private QBLevel<T> searchCache;
    360356    private int size;
     357    private Collection<T> invalidBBoxPrimitives;
    361358
    362359    /**
    … …  
    370367    public final void clear() {
    371368        root = new QBLevel<>();
     369        invalidBBoxPrimitives = new LinkedHashSet<>();
    372370        searchCache = null;
    373371        size = 0;
    … …  
    376374    @Override
    377375    public boolean add(T n) {
    378         root.add(n);
     376        if (n.getBBox().isValid())
     377            root.add(n);
     378        else
     379            invalidBBoxPrimitives.add(n);
    379380        size++;
    380381        return true;
    … …  
    426427        searchCache = null; // Search cache might point to one of removed buckets
    427428        QBLevel<T> bucket = root.findBucket(t.getBBox());
    428         if (bucket.removeContent(t)) {
     429        boolean removed = bucket.removeContent(t);
     430        if (!removed)
     431            removed = invalidBBoxPrimitives.remove(o);
     432        if (removed)
    429433            size--;
    430             return true;
    431         } else
    432             return false;
     434        return removed;
    433435    }
    434436
    … …  
    437439        @SuppressWarnings("unchecked")
    438440        T t = (T) o;
     441        if (!t.getBBox().isValid())
     442            return invalidBBoxPrimitives.contains(o);
    439443        QBLevel<T> bucket = root.findBucket(t.getBBox());
    440444        return bucket != null && bucket.content != null && bucket.content.contains(t);
    … …  
    466470        private QBLevel<T> currentNode;
    467471        private int contentIndex;
     472        private Iterator<T> invalidBBoxIterator = invalidBBoxPrimitives.iterator();
     473        boolean fromInvalidBBoxPrimitives;
    468474        QuadBuckets<T> qb;
    469475
    … …  
    491497        @Override
    492498        public boolean hasNext() {
    493             if (this.peek() == null)
    494                 return false;
     499            if (this.peek() == null) {
     500                fromInvalidBBoxPrimitives = true;
     501                return invalidBBoxIterator.hasNext();
     502            }
    495503            return true;
    496504        }
    … …  
    513521        @Override
    514522        public T next() {
     523            if (fromInvalidBBoxPrimitives)
     524                return invalidBBoxIterator.next();
    515525            T ret = peek();
    516526            if (ret == null)
    … …  
    522532        @Override
    523533        public void remove() {
    524             // two uses
    525             // 1. Back up to the thing we just returned
    526             // 2. move the index back since we removed
    527             //    an element
    528             contentIndex--;
    529             T object = peek();
    530             if (currentNode.removeContent(object))
     534            if (fromInvalidBBoxPrimitives) {
     535                invalidBBoxIterator.remove();
    531536                qb.size--;
     537            } else {
     538                // two uses
     539                // 1. Back up to the thing we just returned
     540                // 2. move the index back since we removed
     541                //    an element
     542                contentIndex--;
     543                T object = peek();
     544                if (currentNode.removeContent(object))
     545                    qb.size--;
     546
     547            }
    532548        }
    533549    }
    … …  
    555571    public List<T> search(BBox searchBbox) {
    556572        List<T> ret = new ArrayList<>();
     573        if (!searchBbox.isValid()) {
     574            return ret;
     575        }
     576
    557577        // Doing this cuts down search cost on a real-life data set by about 25%
    558578        if (searchCache == null) {

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

    r11038 r11269  
    447447    @Override
    448448    public BBox getBBox() {
    449         RelationMember[] members = this.members;
    450 
    451         if (members.length == 0)
    452             return new BBox(0, 0, 0, 0);
    453         if (getDataSet() == null)
    454             return calculateBBox(new HashSet<PrimitiveId>());
    455         else {
    456             if (bbox == null) {
    457                 bbox = calculateBBox(new HashSet<PrimitiveId>());
    458             }
    459             if (bbox == null)
    460                 return new BBox(0, 0, 0, 0); // No real members
    461             else
    462                 return new BBox(bbox);
    463         }
    464     }
    465 
    466     private BBox calculateBBox(Set<PrimitiveId> visitedRelations) {
    467         if (visitedRelations.contains(this))
    468             return null;
    469         visitedRelations.add(this);
    470 
    471         RelationMember[] members = this.members;
    472         if (members.length == 0)
    473             return null;
    474         else {
    475             BBox result = null;
    476             for (RelationMember rm:members) {
    477                 BBox box = rm.isRelation() ? rm.getRelation().calculateBBox(visitedRelations) : rm.getMember().getBBox();
    478                 if (box != null) {
    479                     if (result == null) {
    480                         result = box;
    481                     } else {
    482                         result.add(box);
    483                     }
    484                 }
    485             }
    486             return result;
     449        if (getDataSet() != null && bbox != null)
     450            return new BBox(bbox); // use cached value
     451
     452        BBox box = new BBox();
     453        addToBBox(box, new HashSet<PrimitiveId>());
     454        if (getDataSet() != null)
     455            bbox = box; // set cache
     456        return new BBox(box);
     457    }
     458
     459    @Override
     460    protected void addToBBox(BBox box, Set<PrimitiveId> visited) {
     461        for (RelationMember rm : members) {
     462            if (visited.add(rm.getMember()))
     463                rm.getMember().addToBBox(box, visited);
    487464        }
    488465    }
    … …  
    490467    @Override
    491468    public void updatePosition() {
    492         bbox = calculateBBox(new HashSet<PrimitiveId>());
     469        bbox = null; // make sure that it is recalculated
     470        bbox = getBBox();
    493471    }
    494472

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

    r10662 r11269  
    631631        }
    632632        return new BBox(bbox);
     633    }
     634
     635    @Override
     636    protected void addToBBox(BBox box, Set<PrimitiveId> visited) {
     637        box.add(getBBox());
    633638    }
    634639

  • trunk/test/unit/org/openstreetmap/josm/data/osm/BBoxTest.java

    r10945 r11269  
    22package org.openstreetmap.josm.data.osm;
    33
     4import static org.junit.Assert.assertFalse;
     5import static org.junit.Assert.assertTrue;
     6
    47import org.junit.Rule;
    58import org.junit.Test;
     9import org.openstreetmap.josm.data.coor.LatLon;
    610import org.openstreetmap.josm.testutils.JOSMTestRules;
    711
    … …  
    3135            .verify();
    3236    }
     37
     38    /**
     39     * Test LatLon constructor which might result in invalid bbox
     40     */
     41    @Test
     42    public void testLatLonConstructor() {
     43        LatLon latLon1 = new LatLon(10, 20);
     44        LatLon latLon2 = new LatLon(20, 10);
     45        BBox b1 = new BBox(latLon1, latLon2);
     46        BBox b2 = new BBox(latLon2, latLon1);
     47        assertTrue(b1.bounds(latLon1));
     48        assertTrue(b2.bounds(latLon1));
     49        assertTrue(b1.bounds(latLon2));
     50        assertTrue(b2.bounds(latLon2));
     51        assertTrue(b2.bounds(b1));
     52        assertTrue(b1.bounds(b2));
     53
     54        // invalid latlon values
     55        LatLon invalid1 = new LatLon(-190, 340);
     56        BBox b3 = new BBox(invalid1, latLon1);
     57        BBox b4 = new BBox(latLon1, invalid1);
     58        BBox b5 = new BBox(invalid1, invalid1);
     59        // what should be the result?
     60        assertTrue(b3.isValid());
     61        assertTrue(b4.isValid());
     62        assertTrue(b3.bounds(latLon1));
     63        assertTrue(b4.bounds(latLon1));
     64        assertTrue(b5.isValid());
     65        assertFalse(b5.isInWorld());
     66    }
     67
    3368}

  • trunk/test/unit/org/openstreetmap/josm/data/osm/NodeTest.java

    r10945 r11269  
    22package org.openstreetmap.josm.data.osm;
    33
     4import static org.junit.Assert.assertEquals;
    45import static org.junit.Assert.assertFalse;
    56import static org.junit.Assert.assertNotNull;
    67import static org.junit.Assert.assertNull;
     8import static org.junit.Assert.assertTrue;
    79
    810import org.junit.Rule;
    … …  
    4345        assertFalse(n.isOutsideDownloadArea());
    4446    }
     47
     48    /**
     49     * Test BBox calculation with Node
     50     */
     51    @Test
     52    public void testBBox() {
     53        DataSet ds = new DataSet();
     54        Node n1 = new Node(1);
     55        Node n2 = new Node(2);
     56        Node n3 = new Node(3);
     57        Node n4 = new Node(4);
     58        n1.setIncomplete(true);
     59        n2.setCoor(new LatLon(10, 10));
     60        n3.setCoor(new LatLon(20, 20));
     61        n4.setCoor(new LatLon(90, 180));
     62        ds.addPrimitive(n1);
     63        ds.addPrimitive(n2);
     64        ds.addPrimitive(n3);
     65        ds.addPrimitive(n4);
     66
     67        assertFalse(n1.getBBox().isValid());
     68        assertTrue(n2.getBBox().isValid());
     69        assertTrue(n3.getBBox().isValid());
     70        assertTrue(n4.getBBox().isValid());
     71        BBox box1 = n1.getBBox();
     72        box1.add(n2.getCoor());
     73        assertTrue(box1.isValid());
     74        BBox box2 = n2.getBBox();
     75        box2.add(n1.getCoor());
     76        assertTrue(box2.isValid());
     77        assertEquals(box1, box2);
     78        box1.add(n3.getCoor());
     79        assertTrue(box1.isValid());
     80        assertEquals(box1.getCenter(), new LatLon(15, 15));
     81    }
    4582}

  • trunk/test/unit/org/openstreetmap/josm/data/osm/QuadBucketsTest.java

    r10945 r11269  
    99import java.util.Iterator;
    1010import java.util.List;
     11import java.util.Random;
    1112
    1213import org.fest.reflect.core.Reflection;
    … …  
    175176        }
    176177        Assert.assertEquals(0, qbWays.size());
     178
     179    }
     180
     181    /**
     182     *  Add more data so that quad buckets tree has a few leaves
     183     */
     184    @Test
     185    public void testSplitsWithIncompleteData() {
     186        DataSet ds = new DataSet();
     187        long nodeId = 1;
     188        long wayId = 1;
     189        final int NUM_COMPLETE_WAYS = 300;
     190        final int NUM_INCOMPLETE_WAYS = 10;
     191        final int NUM_NODES_PER_WAY = 20;
     192        final int NUM_INCOMPLETE_NODES = 10;
     193
     194        // force splits in quad buckets
     195        Random random = new Random(31);
     196        for (int i = 0; i < NUM_COMPLETE_WAYS; i++) {
     197            Way w = new Way(wayId++);
     198            List<Node> nodes = new ArrayList<>();
     199            double center = random.nextDouble() * 10;
     200            for (int j = 0; j < NUM_NODES_PER_WAY; j++) {
     201                Node n = new Node(nodeId++);
     202                double lat = random.nextDouble() * 0.001;
     203                double lon = random.nextDouble() * 0.001;
     204                n.setCoor(new LatLon(center + lat, center + lon));
     205                nodes.add(n);
     206                ds.addPrimitive(n);
     207            }
     208            w.setNodes(nodes);
     209            ds.addPrimitive(w);
     210        }
     211        Assert.assertEquals(NUM_COMPLETE_WAYS, ds.getWays().size());
     212        Assert.assertEquals(NUM_COMPLETE_WAYS * NUM_NODES_PER_WAY, ds.getNodes().size());
     213
     214        // add some incomplete nodes
     215        List<Node> incompleteNodes = new ArrayList<>();
     216        for (int i = 0; i < NUM_INCOMPLETE_NODES; i++) {
     217            Node n = new Node(nodeId++);
     218            incompleteNodes.add(n);
     219            n.setIncomplete(true);
     220            ds.addPrimitive(n);
     221        }
     222        Assert.assertEquals(NUM_COMPLETE_WAYS * NUM_NODES_PER_WAY + NUM_INCOMPLETE_NODES, ds.getNodes().size());
     223        // add some incomplete ways
     224        List<Way> incompleteWays = new ArrayList<>();
     225        for (int i = 0; i < NUM_INCOMPLETE_WAYS; i++) {
     226            Way w = new Way(wayId++);
     227            incompleteWays.add(w);
     228            w.setIncomplete(true);
     229            ds.addPrimitive(w);
     230        }
     231        Assert.assertEquals(NUM_COMPLETE_WAYS + NUM_INCOMPLETE_WAYS, ds.getWays().size());
     232
     233        BBox planet = new BBox(-180, -90, 180, 90);
     234        // incomplete ways should not be found with search
     235        Assert.assertEquals(NUM_COMPLETE_WAYS, ds.searchWays(planet).size());
     236        // incomplete ways are only retrieved via iterator or object reference
     237        for (Way w : incompleteWays) {
     238            Assert.assertTrue(ds.getWays().contains(w));
     239        }
     240
     241        QuadBuckets<Way> qb = new QuadBuckets<>();
     242        qb.addAll(ds.getWays());
     243        int count = qb.size();
     244        Assert.assertEquals(count, ds.getWays().size());
     245        Iterator<Way> iter = qb.iterator();
     246        while (iter.hasNext()) {
     247            iter.next();
     248            iter.remove();
     249            count--;
     250            Assert.assertEquals(count, qb.size());
     251        }
     252        Assert.assertEquals(0, qb.size());
    177253    }
    178254}

  • trunk/test/unit/org/openstreetmap/josm/data/osm/RelationTest.java

    r10945 r11269  
    7676        Assert.assertEquals(w1.getBBox(), r1.getBBox());
    7777        Assert.assertEquals(w1.getBBox(), r2.getBBox());
     78
     79        // create incomplete node and add it to the relation, this must not change the bbox
     80        BBox oldBBox = r2.getBBox();
     81        Node n4 = new Node();
     82        n4.setIncomplete(true);
     83        ds.addPrimitive(n4);
     84        r2.addMember(new RelationMember("", n4));
     85
     86        Assert.assertEquals(oldBBox, r2.getBBox());
    7887    }
    7988
Note: See TracChangeset for help on using the changeset viewer.