Changeset 11269 in josm for trunk/src/org/openstreetmap

Timestamp:

2016-11-17T19:58:39+01:00 (7 years ago)

Author:

michael2402

Message:

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

Patch by Gerd Petermann

Location:

trunk/src/org/openstreetmap/josm/data/osm

Files:

• BBox.java (modified) (6 diffs)
• DataSet.java (modified) (2 diffs)
• Node.java (modified) (1 diff)
• OsmPrimitive.java (modified) (1 diff)
• QuadBuckets.java (modified) (12 diffs)
• Relation.java (modified) (2 diffs)
• Way.java (modified) (1 diff)

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

@@ -20 +20 @@
      * Constructs a new (invalid) BBox
      */
-    protected BBox() { }
-
+    public BBox() { }
 
     /**
@@ -31 +30 @@
      */
     public BBox(final double x, final double y) {
-        xmax = xmin = x;
-        ymax = ymin = y;
-        sanity();
+        if (!Double.isNaN(x) && !Double.isNaN(y)) {
+            xmin = x;
+            ymin = y;
+            xmax = x;
+            ymax = y;
+        }
     }
 
     /**
      * Constructs a new {@code BBox} defined by points <code>a</code> and <code>b</code>.
-     * Result is minimal BBox containing both points.
+     * Result is minimal BBox containing both points if they are both valid, else undefined
      *
      * @param a first point
@@ -59 +61 @@
     }
 
+    /**
+     * Create minimal  BBox so that {@code this.bounds(ax,ay)} and {@code this.bounds(bx,by)} will both return true
+     * @param ax left or right X value (-180 .. 180)
+     * @param ay top or bottom Y value (-90 .. 90)
+     * @param bx left or right X value (-180 .. 180)
+     * @param by top or bottom Y value (-90 .. 90)
+     */
     public BBox(double ax, double ay, double bx, double by) {
+        if (Double.isNaN(ax) || Double.isNaN(ay) || Double.isNaN(bx) || Double.isNaN(by)) {
+            return; // use default which is an invalid BBox
+        }
 
         if (ax > bx) {
@@ -76 +88 @@
             ymin = ay;
         }
-
-        sanity();
-    }
-
+    }
+
+    /**
+     * Create BBox for all nodes of the way with known coordinates.
+     * If no node has a known coordinate, an invalid BBox is returned.
+     * @param w the way
+     */
     public BBox(Way w) {
-        for (Node n : w.getNodes()) {
-            LatLon coor = n.getCoor();
-            if (coor == null) {
-                continue;
-            }
-            add(coor);
-        }
-    }
-
+        w.getNodes().forEach((n) -> add(n.getCoor()));
+    }
+
+    /**
+     * Create BBox for a node. An invalid BBox is returned if the coordinates are not known.
+     * @param n the node
+     */
     public BBox(Node n) {
-        LatLon coor = n.getCoor();
-        if (coor == null) {
-            xmin = xmax = ymin = ymax = 0;
-        } else {
-            xmin = xmax = coor.lon();
-            ymin = ymax = coor.lat();
-        }
-    }
-
-    private void sanity() {
-        if (xmin < -180.0) {
-            xmin = -180.0;
-        }
-        if (xmax > 180.0) {
-            xmax = 180.0;
-        }
-        if (ymin < -90.0) {
-            ymin = -90.0;
-        }
-        if (ymax > 90.0) {
-            ymax = 90.0;
-        }
-    }
-
+        if (n.isLatLonKnown())
+            add(n.getCoor());
+    }
+
+    /**
+     * Add a point to an existing BBox. Extends this bbox if necessary so that this.bounds(c) will return true
+     * if c is a valid LatLon instance.
+     * @param c a LatLon point
+     */
     public final void add(LatLon c) {
-        add(c.lon(), c.lat());
+        if (c != null && c.isValid())
+            add(c.lon(), c.lat());
     }
 
@@ -125 +124 @@
      */
     public final void add(double x, double y) {
+        if (Double.isNaN(x) || Double.isNaN(y))
+            return;
         xmin = Math.min(xmin, x);
         xmax = Math.max(xmax, x);
         ymin = Math.min(ymin, y);
         ymax = Math.max(ymax, y);
-        sanity();
-    }
-
-    public final void add(BBox box) {
-        xmin = Math.min(xmin, box.xmin);
-        xmax = Math.max(xmax, box.xmax);
-        ymin = Math.min(ymin, box.ymin);
-        ymax = Math.max(ymax, box.ymax);
-        sanity();
-    }
-
+    }
+
+    /**
+     * Extends this bbox to include the bbox other. Does nothing if other is not valid.
+     * @param other a bbox
+     */
+    public final void add(BBox other) {
+        if (other.isValid()) {
+            xmin = Math.min(xmin, other.xmin);
+            xmax = Math.max(xmax, other.xmax);
+            ymin = Math.min(ymin, other.ymin);
+            ymax = Math.max(ymax, other.ymax);
+        }
+    }
+
+    /**
+     * Extends this bbox to include the bbox of the primitive extended by extraSpace.
+     * @param primitive an OSM primitive
+     * @param extraSpace the value to extend the primitives bbox. Unit is in LatLon degrees.
+     */
     public void addPrimitive(OsmPrimitive primitive, double extraSpace) {
         BBox primBbox = primitive.getBBox();
@@ -285 +295 @@
     }
 
+    /**
+     * @return true if the bbox covers a part of the planets surface
+     * Height and width must be non-negative, but may (both) be 0.
+     */
+    public boolean isValid() {
+        return (xmin <= xmax && ymin <= ymax);
+    }
+
+    /**
+     * @return true if the bbox covers a part of the planets surface
+     */
+    public boolean isInWorld() {
+        return !(xmin < -180.0 || xmax > 180.0 || ymin < -90.0 || ymax > 90.0);
+    }
+
     @Override
     public String toString() {

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

@@ -504 +504 @@
                         tr("Unable to add primitive {0} to the dataset because it is already included", primitive.toString()));
 
-            primitive.updatePosition(); // Set cached bbox for way and relation (required for reindexWay and reinexRelation to work properly)
+            allPrimitives.add(primitive);
+            primitive.setDataset(this);
+            primitive.updatePosition(); // Set cached bbox for way and relation (required for reindexWay and reindexRelation to work properly)
             boolean success = false;
             if (primitive instanceof Node) {
@@ -515 +517 @@
             if (!success)
                 throw new RuntimeException("failed to add primitive: "+primitive);
-            allPrimitives.add(primitive);
-            primitive.setDataset(this);
             firePrimitivesAdded(Collections.singletonList(primitive), false);
         } finally {

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

@@ -330 +330 @@
     @Override
     public BBox getBBox() {
-        return new BBox(this);
+        return new BBox(lon, lat);
+    }
+
+    @Override
+    protected void addToBBox(BBox box, Set<PrimitiveId> visited) {
+        box.add(lon, lat);
     }
 

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

@@ -1417 +1417 @@
         return false;
     }
+
+    /**
+     * If necessary, extend the bbox to contain this primitive
+     * @param box a bbox instance
+     * @param visited a set of visited members  or null
+     */
+    protected abstract void addToBBox(BBox box, Set<PrimitiveId> visited);
 }

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

@@ -6 +6 @@
 import java.util.Collection;
 import java.util.Iterator;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.NoSuchElementException;
@@ -167 +168 @@
 
         boolean matches(final T o, final BBox searchBbox) {
-            if (o instanceof Node) {
-                final LatLon latLon = ((Node) o).getCoor();
-                // node without coords -> bbox[0,0,0,0]
-                return searchBbox.bounds(latLon != null ? latLon : LatLon.ZERO);
-            }
             return o.getBBox().intersects(searchBbox);
         }
@@ -359 +355 @@
     private QBLevel<T> searchCache;
     private int size;
+    private Collection<T> invalidBBoxPrimitives;
 
     /**
@@ -370 +367 @@
     public final void clear() {
         root = new QBLevel<>();
+        invalidBBoxPrimitives = new LinkedHashSet<>();
         searchCache = null;
         size = 0;
@@ -376 +374 @@
     @Override
     public boolean add(T n) {
-        root.add(n);
+        if (n.getBBox().isValid())
+            root.add(n);
+        else
+            invalidBBoxPrimitives.add(n);
         size++;
         return true;
@@ -426 +427 @@
         searchCache = null; // Search cache might point to one of removed buckets
         QBLevel<T> bucket = root.findBucket(t.getBBox());
-        if (bucket.removeContent(t)) {
+        boolean removed = bucket.removeContent(t);
+        if (!removed)
+            removed = invalidBBoxPrimitives.remove(o);
+        if (removed)
             size--;
-            return true;
-        } else
-            return false;
+        return removed;
     }
 
@@ -437 +439 @@
         @SuppressWarnings("unchecked")
         T t = (T) o;
+        if (!t.getBBox().isValid())
+            return invalidBBoxPrimitives.contains(o);
         QBLevel<T> bucket = root.findBucket(t.getBBox());
         return bucket != null && bucket.content != null && bucket.content.contains(t);
@@ -466 +470 @@
         private QBLevel<T> currentNode;
         private int contentIndex;
+        private Iterator<T> invalidBBoxIterator = invalidBBoxPrimitives.iterator();
+        boolean fromInvalidBBoxPrimitives;
         QuadBuckets<T> qb;
 
@@ -491 +497 @@
         @Override
         public boolean hasNext() {
-            if (this.peek() == null)
-                return false;
+            if (this.peek() == null) {
+                fromInvalidBBoxPrimitives = true;
+                return invalidBBoxIterator.hasNext();
+            }
             return true;
         }
@@ -513 +521 @@
         @Override
         public T next() {
+            if (fromInvalidBBoxPrimitives)
+                return invalidBBoxIterator.next();
             T ret = peek();
             if (ret == null)
@@ -522 +532 @@
         @Override
         public void remove() {
-            // two uses
-            // 1. Back up to the thing we just returned
-            // 2. move the index back since we removed
-            //    an element
-            contentIndex--;
-            T object = peek();
-            if (currentNode.removeContent(object))
+            if (fromInvalidBBoxPrimitives) {
+                invalidBBoxIterator.remove();
                 qb.size--;
+            } else {
+                // two uses
+                // 1. Back up to the thing we just returned
+                // 2. move the index back since we removed
+                //    an element
+                contentIndex--;
+                T object = peek();
+                if (currentNode.removeContent(object))
+                    qb.size--;
+
+            }
         }
     }
@@ -555 +571 @@
     public List<T> search(BBox searchBbox) {
         List<T> ret = new ArrayList<>();
+        if (!searchBbox.isValid()) {
+            return ret;
+        }
+
         // Doing this cuts down search cost on a real-life data set by about 25%
         if (searchCache == null) {

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

@@ -447 +447 @@
     @Override
     public BBox getBBox() {
-        RelationMember[] members = this.members;
-
-        if (members.length == 0)
-            return new BBox(0, 0, 0, 0);
-        if (getDataSet() == null)
-            return calculateBBox(new HashSet<PrimitiveId>());
-        else {
-            if (bbox == null) {
-                bbox = calculateBBox(new HashSet<PrimitiveId>());
-            }
-            if (bbox == null)
-                return new BBox(0, 0, 0, 0); // No real members
-            else
-                return new BBox(bbox);
-        }
-    }
-
-    private BBox calculateBBox(Set<PrimitiveId> visitedRelations) {
-        if (visitedRelations.contains(this))
-            return null;
-        visitedRelations.add(this);
-
-        RelationMember[] members = this.members;
-        if (members.length == 0)
-            return null;
-        else {
-            BBox result = null;
-            for (RelationMember rm:members) {
-                BBox box = rm.isRelation() ? rm.getRelation().calculateBBox(visitedRelations) : rm.getMember().getBBox();
-                if (box != null) {
-                    if (result == null) {
-                        result = box;
-                    } else {
-                        result.add(box);
-                    }
-                }
-            }
-            return result;
+        if (getDataSet() != null && bbox != null)
+            return new BBox(bbox); // use cached value
+
+        BBox box = new BBox();
+        addToBBox(box, new HashSet<PrimitiveId>());
+        if (getDataSet() != null)
+            bbox = box; // set cache
+        return new BBox(box);
+    }
+
+    @Override
+    protected void addToBBox(BBox box, Set<PrimitiveId> visited) {
+        for (RelationMember rm : members) {
+            if (visited.add(rm.getMember()))
+                rm.getMember().addToBBox(box, visited);
         }
     }
@@ -490 +467 @@
     @Override
     public void updatePosition() {
-        bbox = calculateBBox(new HashSet<PrimitiveId>());
+        bbox = null; // make sure that it is recalculated
+        bbox = getBBox();
     }
 

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

@@ -631 +631 @@
         }
         return new BBox(bbox);
+    }
+
+    @Override
+    protected void addToBBox(BBox box, Set<PrimitiveId> visited) {
+        box.add(getBBox());
     }