v2
now reports OSM ids of merged/replaced nodes (at the cost of using more
memory while the XML is being converted).
only does this stuff if route option enabled.
----------
The attached patch is a first stab at a solution for this problem.
Please test.
It is implemented in an iterative fashion and it should terminate after
a few passes. If 10 passes are executed it will give up, please report
if you see it doing that.
It would be nice if the diagnostics reported the OSM id of the nodes
rather than their coordinates but I haven't worked out the best way of
achieving that yet.
Cheers,
Mark
diff --git a/src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java b/src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java
index b7a0ee0..af7e676 100644
--- a/src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java
+++ b/src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java
@@ -18,6 +18,7 @@ package uk.me.parabola.mkgmap.reader.osm.xml;
import java.util.ArrayList;
import java.util.HashMap;
+import java.util.IdentityHashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
@@ -55,6 +56,7 @@ class Osm5XmlHandler extends DefaultHandler {
private int mode;
private Map<Long, Coord> coordMap = new HashMap<Long, Coord>(50000);
+ private Map<Coord, Long> nodeIdMap = new IdentityHashMap<Coord, Long>();
private Map<Long, Node> nodeMap;
private Map<Long, Way> wayMap;
private Map<Long, Relation> relationMap;
@@ -365,6 +367,11 @@ class Osm5XmlHandler extends DefaultHandler {
nodeMap = null;
+ if(routing)
+ removeShortArcs();
+
+ nodeIdMap = null;
+
for (Way w: wayMap.values())
converter.convertWay(w);
@@ -394,6 +401,127 @@ class Osm5XmlHandler extends DefaultHandler {
endTask.run();
}
+ private final void countArcs(Map<Coord, Integer> map, Coord p, int n) {
+ Integer i = map.get(p);
+ if(i != null)
+ map.put(p, i + n);
+ else
+ map.put(p, n);
+ }
+
+ private void removeShortArcs() {
+ final double MIN_ARC_LENGTH = 3.5;
+ // keep track of how many arcs reach a given point
+ Map<Coord, Integer> arcCounts = new IdentityHashMap<Coord, Integer>();
+ log.info("Removing short arcs - counting arcs");
+ for(Way w : wayMap.values()) {
+ List<Coord> points = w.getPoints();
+ int numPoints = points.size();
+ if(numPoints >= 2) {
+ // all end points have 1 arc
+ countArcs(arcCounts, points.get(0), 1);
+ countArcs(arcCounts, points.get(numPoints - 1), 1);
+ // non-end points have 2 arcs but ignore points that
+ // are only in a single way
+ for(int i = numPoints - 2; i >= 1; --i) {
+ Coord p = points.get(i);
+ if(p.getHighwayCount() > 1)
+ countArcs(arcCounts, p, 2);
+ }
+ }
+ }
+ // replacements maps those nodes that have been replaced to
+ // the node that replaces them
+ Map<Coord, Coord> replacements = new IdentityHashMap<Coord, Coord>();
+ boolean anotherPassRequired = true;
+ int pass = 0;
+ while(anotherPassRequired && pass < 10) {
+ anotherPassRequired = false;
+ log.info("Removing short arcs - PASS " + ++pass);
+ Way[] ways = wayMap.values().toArray(new Way[wayMap.size()]);
+ for(int w = 0; w < ways.length; ++w) {
+ Way way = ways[w];
+ List<Coord> points = way.getPoints();
+ if(points.size() < 2) {
+ log.info(" Way " + way.getTag("name") + " (OSM id " + way.getId() + ") has less than 2 points - deleting it");
+ wayMap.remove(way.getId());
+ continue;
+ }
+ int arcLength = 0;
+ int previousNodeIndex = 0; // first point will be a node
+ Coord previousPoint = points.get(0);
+ for(int i = 0; i < points.size(); ++i) {
+ Coord p = points.get(i);
+ // check if this point is to be replaced because
+ // it was previously merged into another point
+ Coord replacement = null;
+ Coord r = p;
+ while((r = replacements.get(r)) != null) {
+ replacement = r;
+ }
+ if(replacement != null) {
+ log.info(" Way " + way.getTag("name") + " (OSM id " + way.getId() + ") has node " + nodeIdMap.get(p) + " replaced with node " + nodeIdMap.get(replacement));
+ p = replacement;
+ // replace point in way
+ points.set(i, p);
+ if(i == 0)
+ previousPoint = p;
+ anotherPassRequired = true;
+ }
+ if(i > 0) {
+ // this is not the first point in the way
+ double d = previousPoint.distance(p);
+ previousPoint = p;
+ arcLength += d;
+ Coord previousNode = points.get(previousNodeIndex);
+ // this point is a node if it has an arc count
+ Integer arcCount = arcCounts.get(p);
+ if(arcCount != null) {
+ // merge this node to previous node in way
+ // if the arc length is zero or is small
+ // and it has more than 2 arcs connected
+ // to it and the previous node has more
+ // than 2 arcs connected to it
+ if(arcLength == 0 ||
+ (arcLength < MIN_ARC_LENGTH &&
+ arcCount > 2 &&
+ arcCounts.get(previousNode) > 2)) {
+ log.info(" Way " + way.getTag("name") + " (OSM id " + way.getId() + ") has evil short arc (" + arcLength + "m) - merging node " + nodeIdMap.get(p) + " into " + nodeIdMap.get(previousNode));
+ if(p != previousNode) {
+ replacements.put(p, previousNode);
+ // add this node's arc count to the node
+ // that is replacing it
+ countArcs(arcCounts, previousNode, arcCount - 1);
+ }
+ // reset previous point to be the previous node
+ previousPoint = previousNode;
+ // remove the point(s) back to the previous node
+ for(int j = i; j > previousNodeIndex; --j) {
+ points.remove(j);
+ }
+ // hack alert! rewind the loop index
+ i = previousNodeIndex;
+ anotherPassRequired = true;
+ }
+ else {
+ // the node did not need to be merged so
+ // it now becomes the new previous node
+ previousNodeIndex = i;
+ }
+ // reset arcLength at we pass each node
+ arcLength = 0;
+ }
+ }
+ }
+ }
+ }
+
+ if(anotherPassRequired)
+ log.error("Removing short arcs - didn't finish in " + pass + " passes, giving up (moved " + replacements.size() + " nodes)");
+ else
+ log.info("Removing short arcs - finished in " + pass + " passes (moved " + replacements.size() + " nodes)");
+ }
+
private void setupBBoxFromBounds(Attributes xmlattr) {
try {
setBBox(Double.parseDouble(xmlattr.getValue("minlat")),
@@ -462,8 +590,11 @@ class Osm5XmlHandler extends DefaultHandler {
private void addNodeToWay(long id) {
Coord co = coordMap.get(id);
//co.incCount();
- if (co != null)
+ if (co != null) {
currentWay.addPoint(co);
+ if(routing)
+ nodeIdMap.put(co, id);
+ }
}
public void setConverter(OsmConverter converter) {
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
