Index: /applications/editors/josm/plugins/validator/src/org/openstreetmap/josm/plugins/validator/tests/UnconnectedWays.java =================================================================== --- /applications/editors/josm/plugins/validator/src/org/openstreetmap/josm/plugins/validator/tests/UnconnectedWays.java (revision 18378) +++ /applications/editors/josm/plugins/validator/src/org/openstreetmap/josm/plugins/validator/tests/UnconnectedWays.java (revision 18379) @@ -5,5 +5,10 @@ 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,8 +17,12 @@ 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,4 +45,8 @@ Set middlenodes; // nodes in middle of way Set othernodes; // nodes appearing at least twice + //NodeSearchCache nodecache; + QuadBuckets nodecache; + Area ds_area; + DataSet ds; double mindist; @@ -59,4 +72,6 @@ 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,52 +79,69 @@ public void endTest() { - Area a = Main.main.getCurrentDataSet().getDataSourceArea(); + //Area a = Main.ds.getDataSourceArea(); Map map = new HashMap(); - 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 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 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 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 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 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,38 +149,38 @@ { 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 error : map.entrySet()) + System.out.println("p3 elapesd: " + (System.currentTimeMillis()-last)); + last = System.currentTimeMillis(); + for(Map.Entry 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 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 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,4 +188,6 @@ endnodes = null; super.endTest(); + System.out.println("p99 elapesd: " + (System.currentTimeMillis()-last)); + last = System.currentTimeMillis(); } @@ -165,4 +199,9 @@ public boolean isBoundary = false; public boolean highway; + private double len; + private Set nearbyNodeCache; + double nearbyNodeCacheDist = -1.0; + Node n1; + Node n2; public MyWaySegment(Way w, Node n1, Node n2) @@ -175,11 +214,109 @@ 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 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 ret = new ArrayList(); + ret.add(topLeft); + ret.add(botRight); + return ret; + } + + public Collection 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 trimmed = new HashSet(nearbyNodeCache); + for (Node n : new HashSet(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 bounds = this.getBounds(dist); + List 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(); + nearbyNodeCache.add(n); + } + nearbyNodeCacheDist = dist; + if (nearbyNodeCache == null) + nearbyNodeCache = Collections.emptySet(); + return nearbyNodeCache; } @@ -191,26 +328,40 @@ } - @Override - public void visit(Way w) - { + List getWaySegments(Way w) + { + List ret = new ArrayList(); 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 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 s)