Changeset 18379 in osm for applications/editors/josm/plugins/validator

Timestamp:

2009-10-30T23:53:08+01:00 (15 years ago)

Author:

dhansen

Message:

This uses the new quadbuckets code for the UnconnectedWays test,
as well as a few other optimizations.

Using a large (~18MB) data set, the test took 187.827 seconds in
one instance. After applying this patch, the same test takes
1.631 seconds.

File:

• applications/editors/josm/plugins/validator/src/org/openstreetmap/josm/plugins/validator/tests/UnconnectedWays.java (modified) (10 diffs)

applications/editors/josm/plugins/validator/src/org/openstreetmap/josm/plugins/validator/tests/UnconnectedWays.java

@@ -5 +5 @@
 import java.awt.geom.Area;
 import java.awt.geom.Line2D;
+import java.awt.geom.Point2D;
+import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
 import java.util.HashMap;
 import java.util.HashSet;
@@ -12 +17 @@
 
 import org.openstreetmap.josm.Main;
+import org.openstreetmap.josm.data.coor.LatLon;
+import org.openstreetmap.josm.data.coor.EastNorth;
 import org.openstreetmap.josm.data.osm.Node;
 import org.openstreetmap.josm.data.osm.OsmUtils;
 import org.openstreetmap.josm.data.osm.Way;
 import org.openstreetmap.josm.gui.progress.ProgressMonitor;
+import org.openstreetmap.josm.data.osm.DataSet;
+import org.openstreetmap.josm.data.osm.QuadBuckets;
 import org.openstreetmap.josm.plugins.validator.PreferenceEditor;
 import org.openstreetmap.josm.plugins.validator.Severity;
@@ -36 +45 @@
     Set<Node> middlenodes; // nodes in middle of way
     Set<Node> othernodes; // nodes appearing at least twice
+    //NodeSearchCache nodecache;
+    QuadBuckets<Node> nodecache;
+    Area ds_area;
+    DataSet ds;
 
     double mindist;
@@ -59 +72 @@
         mindist = Main.pref.getDouble(PREFIX + ".node_way_distance", 10.0)/6378135.0;
         minmiddledist = Main.pref.getDouble(PREFIX + ".way_way_distance", 0.0)/6378135.0;
+        this.ds = Main.main.getCurrentDataSet();
+        this.ds_area = ds.getDataSourceArea();
     }
 
@@ -64 +79 @@
     public void endTest()
     {
-        Area a = Main.main.getCurrentDataSet().getDataSourceArea();
+        //Area a = Main.ds.getDataSourceArea();
         Map<Node, Way> map = new HashMap<Node, Way>();
-        for(Node en : endnodes_highway)
-        {
-            Boolean isexit = OsmUtils.getOsmBoolean(en.get("noexit"));
-            if("turning_circle".equals(en.get("highway")) ||
-            (isexit != null && isexit) || en.get("barrier") != null)
-                continue;
-            for(MyWaySegment s : ways)
-            {
-                if(!s.isBoundary && !s.isAbandoned && s.highway && s.nearby(en, mindist) && (a == null || a.contains(en.getCoor())))
+        long last = -1;
+        for (int iter = 0; iter < 1; iter++) {
+        last = System.currentTimeMillis();
+        long last_print = -1;
+        int nr = 0;
+        Collection<MyWaySegment> tmp_ways = ways;
+        for(MyWaySegment s : tmp_ways) {
+            nr++;
+            long now = System.currentTimeMillis();
+            if (now - last_print > 200) {
+                System.err.println("processing segment nr: " + nr + " of " + ways.size());
+                last_print = now;
+            }
+            for(Node en : s.nearbyNodes(mindist)) {
+                if (en == null)
+                    continue;
+                //if("turning_circle".equals(en.get("highway")) ||
+                //        (isexit != null && isexit) || en.get("barrier") != null)
+                //    c4++;
+                if(!s.highway)
+                    continue;
+                if (!endnodes_highway.contains(en))
+                    continue;
+                Boolean isexit = OsmUtils.getOsmBoolean(en.get("noexit"));
+                if("turning_circle".equals(en.get("highway")) ||
+                  (isexit != null && isexit) || en.get("barrier") != null)
+                    continue;
+                // There's a small false-positive here.  Imagine an intersection
+                // like a 't'.  If the top part of the 't' is short enough, it
+                // will trigger the node at the very top of the 't' to be unconnected
+                // to the way that "crosses" the 't'.  We should probably check that
+                // the ways to which 'en' belongs are not connected to 's.w'.
+                map.put(en, s.w);
+            }
+        }
+        System.out.println("p1 elapesd: " + (System.currentTimeMillis()-last));
+        last = System.currentTimeMillis();
+        }
+        for(Map.Entry<Node, Way> error : map.entrySet())
+        {
+            errors.add(new TestError(this, Severity.WARNING,
+            tr("Way end node near other highway"), UNCONNECTED_WAYS,
+            Arrays.asList(error.getKey(), error.getValue())));
+        }
+        map.clear();
+        for(MyWaySegment s : ways)
+        {
+            for(Node en : s.nearbyNodes(mindist))
+            {
+                if (endnodes_highway.contains(en) && !s.highway && !s.isArea()) {
                     map.put(en, s.w);
-            }
-        }
-        if(map.size() > 0)
-        {
-            for(Map.Entry<Node, Way> error : map.entrySet())
-            {
-                errors.add(new TestError(this, Severity.WARNING,
-                tr("Way end node near other highway"), UNCONNECTED_WAYS,
-                Arrays.asList(error.getKey(), error.getValue())));
-            }
-        }
-        map.clear();
-        for(Node en : endnodes_highway)
-        {
-            for(MyWaySegment s : ways)
-            {
-                if(!s.isBoundary && !s.isAbandoned && !s.highway && s.nearby(en, mindist) && !s.isArea() && (a == null || a.contains(en.getCoor())))
+                } else if (endnodes.contains(en) && !s.isArea()) {
                     map.put(en, s.w);
-            }
-        }
-        for(Node en : endnodes)
-        {
-            for(MyWaySegment s : ways)
-            {
-                if(!s.isBoundary && !s.isAbandoned && s.nearby(en, mindist) && !s.isArea() && (a == null || a.contains(en.getCoor())))
-                    map.put(en, s.w);
-            }
-        }
-        if(map.size() > 0)
-        {
-            for(Map.Entry<Node, Way> error : map.entrySet())
-            {
-                errors.add(new TestError(this, Severity.WARNING,
-                tr("Way end node near other way"), UNCONNECTED_WAYS,
-                Arrays.asList(error.getKey(), error.getValue())));
-            }
+                }
+            }
+        }
+        System.out.println("p2 elapesd: " + (System.currentTimeMillis()-last));
+        last = System.currentTimeMillis();
+        for(Map.Entry<Node, Way> error : map.entrySet())
+        {
+            errors.add(new TestError(this, Severity.WARNING,
+            tr("Way end node near other way"), UNCONNECTED_WAYS,
+            Arrays.asList(error.getKey(), error.getValue())));
         }
         /* the following two use a shorter distance */
@@ -117 +149 @@
         {
             map.clear();
-            for(Node en : middlenodes)
-            {
-                for(MyWaySegment s : ways)
+            for(MyWaySegment s : ways)
+            {
+                for(Node en : s.nearbyNodes(minmiddledist))
                 {
-                    if(!s.isBoundary && !s.isAbandoned && s.nearby(en, minmiddledist) && (a == null || a.contains(en.getCoor())))
-                        map.put(en, s.w);
+                    if (!middlenodes.contains(en))
+                        continue;
+                    map.put(en, s.w);
                 }
             }
-            if(map.size() > 0)
-            {
-                for(Map.Entry<Node, Way> error : map.entrySet())
+            System.out.println("p3 elapesd: " + (System.currentTimeMillis()-last));
+            last = System.currentTimeMillis();
+            for(Map.Entry<Node, Way> error : map.entrySet())
+            {
+                errors.add(new TestError(this, Severity.OTHER,
+                tr("Way node near other way"), UNCONNECTED_WAYS,
+                Arrays.asList(error.getKey(), error.getValue())));
+            }
+            map.clear();
+            for(MyWaySegment s : ways)
+            {
+                for(Node en : s.nearbyNodes(minmiddledist))
                 {
-                    errors.add(new TestError(this, Severity.OTHER,
-                    tr("Way node near other way"), UNCONNECTED_WAYS,
-                    Arrays.asList(error.getKey(), error.getValue())));
+                    if (!othernodes.contains(en))
+                        continue;
+                    map.put(en, s.w);
                 }
             }
-            map.clear();
-            for(Node en : othernodes)
-            {
-                for(MyWaySegment s : ways)
-                {
-                    if(!s.isBoundary && !s.isAbandoned && s.nearby(en, minmiddledist) && (a == null || a.contains(en.getCoor())))
-                        map.put(en, s.w);
-                }
-            }
-            if(map.size() > 0)
-            {
-                for(Map.Entry<Node, Way> error : map.entrySet())
-                {
-                    errors.add(new TestError(this, Severity.OTHER,
-                    tr("Connected way end node near other way"), UNCONNECTED_WAYS,
-                    Arrays.asList(error.getKey(), error.getValue())));
-                }
+            System.out.println("p4 elapesd: " + (System.currentTimeMillis()-last));
+            last = System.currentTimeMillis();
+            for(Map.Entry<Node, Way> error : map.entrySet())
+            {
+                errors.add(new TestError(this, Severity.OTHER,
+                tr("Connected way end node near other way"), UNCONNECTED_WAYS,
+                Arrays.asList(error.getKey(), error.getValue())));
             }
         }
@@ -156 +188 @@
         endnodes = null;
         super.endTest();
+        System.out.println("p99 elapesd: " + (System.currentTimeMillis()-last));
+        last = System.currentTimeMillis();
     }
 
@@ -165 +199 @@
         public boolean isBoundary = false;
         public boolean highway;
+        private double len;
+        private Set<Node> nearbyNodeCache;
+        double nearbyNodeCacheDist = -1.0;
+        Node n1;
+        Node n2;
 
         public MyWaySegment(Way w, Node n1, Node n2)
@@ -175 +214 @@
             this.isBoundary = !this.highway && "administrative".equals(w.get("boundary"));
             line = new Line2D.Double(n1.getEastNorth().east(), n1.getEastNorth().north(),
-            n2.getEastNorth().east(), n2.getEastNorth().north());
+                                     n2.getEastNorth().east(), n2.getEastNorth().north());
+            len = line.getP1().distance(line.getP2());
+            this.n1 = n1;
+            this.n2 = n2;
         }
 
         public boolean nearby(Node n, double dist)
         {
-            return !w.containsNode(n)
-            && line.ptSegDist(n.getEastNorth().east(), n.getEastNorth().north()) < dist;
+//            return !w.containsNode(n)
+//            && line.ptSegDist(n.getEastNorth().east(), n.getEastNorth().north()) < dist;
+            if (w == null)
+                Main.debug("way null");
+            if (w.containsNode(n))
+                return false;
+            EastNorth coord = n.getEastNorth();
+            if (coord == null)
+                return false;
+            Point2D p = new Point2D.Double(coord.east(), coord.north());
+            if (line.getP1().distance(p) > len+dist)
+                return false;
+            if (line.getP2().distance(p) > len+dist)
+                return false;
+            return line.ptSegDist(p) < dist;
+        }
+        public List<LatLon> getBounds(double fudge)
+        {
+            double x1 = n1.getCoor().lon();
+            double x2 = n2.getCoor().lon();
+            if (x1 > x2) {
+                double tmpx = x1;
+                x1 = x2;
+                x2 = tmpx;
+            }
+            double y1 = n1.getCoor().lat();
+            double y2 = n2.getCoor().lat();
+            if (y1 > y2) {
+                double tmpy = y1;
+                y1 = y2;
+                y2 = tmpy;
+            }
+            LatLon topLeft  = new LatLon(y2+fudge, x1-fudge);
+            LatLon botRight = new LatLon(y1-fudge, x2+fudge);
+            List<LatLon> ret = new ArrayList<LatLon>();
+            ret.add(topLeft);
+            ret.add(botRight);
+            return ret;
+        }
+
+        public Collection<Node> nearbyNodes(double dist)
+        {
+            // If you're looking for nodes that are farther
+            // away that we looked for last time, the cached
+            // result is no good
+            if (dist > nearbyNodeCacheDist) {
+                //if (nearbyNodeCacheDist != -1)
+                //    System.out.println("destroyed MyWaySegment nearby node cache:" + dist + " > " +  nearbyNodeCacheDist);
+                nearbyNodeCache = null;
+            }
+            if (nearbyNodeCache != null) {
+                // If we've cached an aread greater than the
+                // one now being asked for...
+                if (nearbyNodeCacheDist > dist) {
+                    System.out.println("had to trim MyWaySegment nearby node cache.");
+                    // Used the cached result and trim out
+                    // the nodes that are not in the smaller
+                    // area, but keep the old larger cache.
+                    Set<Node> trimmed = new HashSet<Node>(nearbyNodeCache);
+                    for (Node n : new HashSet<Node>(nearbyNodeCache)) {
+                        if (!nearby(n, dist))
+                            trimmed.remove(n);
+                    }
+                    return trimmed;
+                }
+                return nearbyNodeCache;
+            }
+            /*
+             * We know that any point near the line must be at
+             * least as close as the other end of the line, plus
+             * a little fudge for the distance away ('dist').
+             */
+
+            // This needs to be a hash set because the searches
+            // overlap a bit and can return duplicate nodes.
+            nearbyNodeCache = null;
+            nodecache = ds.nodes;
+            List<LatLon> bounds = this.getBounds(dist);
+            List<Node> found_nodes = nodecache.search(bounds.get(0), bounds.get(1));
+            if (found_nodes == null)
+                return Collections.emptySet();
+
+            for (Node n : found_nodes) {
+                if (!nearby(n, dist) ||
+                     (ds_area != null && !ds_area.contains(n.getCoor())))
+                    continue;
+                // It is actually very rare for us to find a node
+                // so defer as much of the work as possible, like
+                // allocating the hash set
+                if (nearbyNodeCache == null)
+                    nearbyNodeCache = new HashSet<Node>();
+                nearbyNodeCache.add(n);
+            }
+            nearbyNodeCacheDist = dist;
+            if (nearbyNodeCache == null)
+                nearbyNodeCache = Collections.emptySet();
+            return nearbyNodeCache;
         }
 
@@ -191 +328 @@
     }
 
-    @Override
-    public void visit(Way w)
-    {
+    List<MyWaySegment> getWaySegments(Way w)
+    {
+        List<MyWaySegment> ret = new ArrayList<MyWaySegment>();
         if (!w.isUsable()
             || w.get("barrier") != null
             || "cliff".equals(w.get("natural")))
-            return;
+            return ret;
 
         int size = w.getNodesCount();
         if(size < 2)
-            return;
+            return ret;
         for(int i = 1; i < size; ++i)
         {
             if(i < size-1)
                 addNode(w.getNode(i), middlenodes);
-            ways.add(new MyWaySegment(w, w.getNode(i-1), w.getNode(i)));
-        }
+            MyWaySegment ws = new MyWaySegment(w, w.getNode(i-1), w.getNode(i));
+            if (ws.isBoundary || ws.isAbandoned)
+                continue;
+            ret.add(ws);
+        }
+        return ret;
+    }
+
+    @Override
+    public void visit(Way w)
+    {
+        ways.addAll(getWaySegments(w));
         Set<Node> set = endnodes;
         if(w.get("highway") != null || w.get("railway") != null)
             set = endnodes_highway;
-        addNode(w.getNode(0), set);
-        addNode(w.getNode(size-1), set);
+        addNode(w.firstNode(), set);
+        addNode(w.lastNode(), set);
+    }
+    @Override
+    public void visit(Node n)
+    {
     }
     private void addNode(Node n, Set<Node> s)