v3
This patch is getting serious!
To reduce the number of short arcs that are being generated at tile
boundaries, this now clips the ways before the short arc removal is
done. However, it isn't a perfect solution because some map data is
very hard to deal with:
a - If a way crosses a tile boundary right in the corner such that both
ends are clipped and the resulting sub-way is less than 5m long, it
will fail to fix that. A possible workaround could be to introduce
extra points to elongate the arc.
b - a much more common problem is where a way forks very close to a
tile boundary and more than one of the connected ways cross the
boundary so you end up with several boundary nodes that should be
merged to remove the short arc(s) but they can't be moved as they are
boundary nodes! I believe that this could be fixed by not merging the
forking node but, instead, moving it away from the boundary such that
the ways connected to it that do cross the boundary are not less than
5m long! Alternatively, adding extra points to elongate the
forking arcs could be done.
With this patch, I processed a 14 tile map of the Netherlands and it
produced 21 of these short arc errors (all due to forks close to the
tile boundaries). I then tested the routing at 5 of these positions
(using mapsource) and only 1 of the 5 showed any sign of breakage, the
other 4 all routed happily in all directions. The one that was broken
was a junction of three ways and one pair of the ways had no
connectivity but the others were ok.
On the upside, the patch removed 147 short arcs introduced by the
clipping.
So more work is required here to fix the corner cases (ha ha) but please
test this patch anyway as I expect it to have problems due to the big
change it has introduced.
As usual, all feedback is appreciated.
----------------
v2 of this patch not only enables remove-short-arcs by default when
routing is in use (as previously discussed on ML) but it also fixes some
problems in the way splitting code.
I would be grateful if people could test this patch because it could
possibly cure some routing failures.
Cheers,
Mark
diff --git a/resources/help/en/options b/resources/help/en/options
index 9bbfad7..ceb1921 100644
--- a/resources/help/en/options
+++ b/resources/help/en/options
@@ -182,11 +182,15 @@ Miscellaneous options:
in which they appear in the OSM input. Without this option,
the order in which the elements are processed is not defined.
---remove-short-arcs[=MinLength]
- Merge nodes to remove short arcs that can cause routing
- problems. If MinLength is specified (in metres), arcs shorter
- than that length will be removed. If a length is not
- specified, only zero-length arcs will be removed.
+--remove-short-arcs (a)
+--remove-short-arcs=MinLength (b)
+--remove-short-arcs=no (c)
+ If routing is enabled, arcs shorter than 5m will be removed
+ to avoid routing problems. This behaviour can be modified with
+ this option. It has three variants:
+ (a) turn on short arc removal even if routing is not enabled.
+ (b) explicitly specify the minimum arc length (no 'm' suffix).
+ (c) completely disable short arc removal.
--road-name-pois[=GarminCode]
Generate a POI for each named road. By default, the POIs'
diff --git a/src/uk/me/parabola/imgfmt/app/Coord.java b/src/uk/me/parabola/imgfmt/app/Coord.java
index 5462602..3e47df7 100644
--- a/src/uk/me/parabola/imgfmt/app/Coord.java
+++ b/src/uk/me/parabola/imgfmt/app/Coord.java
@@ -20,6 +20,7 @@ import java.util.Formatter;
import java.util.Locale;
import uk.me.parabola.imgfmt.Utils;
+import uk.me.parabola.imgfmt.app.net.RouteArc;
/**
* A point coordinate in unshifted map-units.
@@ -101,6 +102,11 @@ public class Coord implements Comparable<Coord> {
return latitude == other.latitude && longitude == other.longitude;
}
+ public boolean tooCloseTo(Coord other) {
+ return ((latitude == other.latitude && longitude == other.longitude) ||
+ !RouteArc.goodArcLength(quickDistance(other)));
+ }
+
/**
* Distance to other point in meters.
*/
diff --git a/src/uk/me/parabola/imgfmt/app/net/RouteArc.java b/src/uk/me/parabola/imgfmt/app/net/RouteArc.java
index 1a0968d..ae2bf8b 100644
--- a/src/uk/me/parabola/imgfmt/app/net/RouteArc.java
+++ b/src/uk/me/parabola/imgfmt/app/net/RouteArc.java
@@ -193,6 +193,12 @@ public class RouteArc {
return (int) (l * factor);
}
+
+ public static boolean goodArcLength(double len) {
+ int l = convertMeters(len);
+ return l > 0 && l < (1 << 14);
+ }
+
public void write(ImgFileWriter writer) {
offset = writer.position();
if(log.isDebugEnabled())
diff --git a/src/uk/me/parabola/mkgmap/general/RoadNetwork.java b/src/uk/me/parabola/mkgmap/general/RoadNetwork.java
index 0c45d68..f76b4b1 100644
--- a/src/uk/me/parabola/mkgmap/general/RoadNetwork.java
+++ b/src/uk/me/parabola/mkgmap/general/RoadNetwork.java
@@ -105,8 +105,8 @@ public class RoadNetwork {
log.error("Road " + road.getRoadDef().getName() + " (OSM id " + road.getRoadDef().getId() + ") contains consecutive identical nodes - routing will be broken");
log.error(" " + co.toOSMURL());
}
- else if(arcLength == 0) {
- log.error("Road " + road.getRoadDef().getName() + " (OSM id " + road.getRoadDef().getId() + ") contains zero length arc");
+ else if(!RouteArc.goodArcLength(arcLength)) {
+ log.error("Road " + road.getRoadDef().getName() + " (OSM id " + road.getRoadDef().getId() + ") contains a bad arc of length " + String.format("%.2f", arcLength) + "m");
log.error(" " + co.toOSMURL());
}
diff --git a/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java b/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
index 2a549f8..60cbfde 100644
--- a/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
+++ b/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
@@ -33,7 +33,6 @@ import uk.me.parabola.log.Logger;
import uk.me.parabola.mkgmap.general.AreaClipper;
import uk.me.parabola.mkgmap.general.Clipper;
import uk.me.parabola.mkgmap.general.LineAdder;
-import uk.me.parabola.mkgmap.general.LineClipper;
import uk.me.parabola.mkgmap.general.MapCollector;
import uk.me.parabola.mkgmap.general.MapElement;
import uk.me.parabola.mkgmap.general.MapExitPoint;
@@ -468,9 +467,9 @@ public class StyledConverter implements OsmConverter {
// now split the way at the next point to
// limit the region that has restricted
// access
- if(!p.equals(p1) &&
+ if(!p.tooCloseTo(p1) &&
((i + 2) == points.size() ||
- !p1.equals(points.get(i + 2)))) {
+ !p1.tooCloseTo(points.get(i + 2)))) {
Way tail = splitWayAt(way, i + 1);
// recursively process tail of way
addRoad(tail, gt);
@@ -531,8 +530,8 @@ public class StyledConverter implements OsmConverter {
// first point in the way
if(p1 instanceof CoordPOI &&
i > 0 &&
- !p.equals(points.get(i - 1)) &&
- !p.equals(p1)) {
+ !p.tooCloseTo(points.get(i - 1)) &&
+ !p.tooCloseTo(p1)) {
Way tail = splitWayAt(way, i);
// recursively process tail of road
addRoad(tail, gt);
@@ -543,59 +542,12 @@ public class StyledConverter implements OsmConverter {
}
}
- // if there is a bounding box, clip the way with it
-
- List<Way> clippedWays = null;
-
- if(bbox != null) {
- List<List<Coord>> lineSegs = LineClipper.clip(bbox, way.getPoints());
-
- if (lineSegs != null) {
-
- clippedWays = new ArrayList<Way>();
-
- for (List<Coord> lco : lineSegs) {
- Way nWay = new Way(way.getId());
- nWay.setName(way.getName());
- nWay.copyTags(way);
- for(Coord co : lco) {
- nWay.addPoint(co);
- if(co.getOnBoundary()) {
- // this point lies on a boundary
- // make sure it becomes a node
- co.incHighwayCount();
- }
- }
- clippedWays.add(nWay);
- // associate the original Way
- // to the new Way
- Way origWay = originalWay.get(way);
- if(origWay == null)
- origWay = way;
- originalWay.put(nWay, origWay);
- }
- }
- }
-
- if(clippedWays != null) {
- for(Way cw : clippedWays) {
- while(cw.getPoints().size() > MAX_POINTS_IN_WAY) {
- Way tail = splitWayAt(cw, MAX_POINTS_IN_WAY - 1);
- addRoadAfterSplittingLoops(cw, gt);
- cw = tail;
- }
- addRoadAfterSplittingLoops(cw, gt);
- }
- }
- else {
- // no bounding box or way was not clipped
- while(way.getPoints().size() > MAX_POINTS_IN_WAY) {
- Way tail = splitWayAt(way, MAX_POINTS_IN_WAY - 1);
- addRoadAfterSplittingLoops(way, gt);
- way = tail;
- }
+ while(way.getPoints().size() > MAX_POINTS_IN_WAY) {
+ Way tail = splitWayAt(way, MAX_POINTS_IN_WAY - 1);
addRoadAfterSplittingLoops(way, gt);
+ way = tail;
}
+ addRoadAfterSplittingLoops(way, gt);
}
void addRoadAfterSplittingLoops(Way way, GType gt) {
@@ -622,7 +574,7 @@ public class StyledConverter implements OsmConverter {
// start at point before intersection point
// check that splitting there will not produce
- // a zero length arc - if it does try the
+ // a short arc - if it does try the
// previous point(s)
int splitI = p2I - 1;
while(splitI > p1I &&
@@ -632,7 +584,7 @@ public class StyledConverter implements OsmConverter {
}
if(splitI == p1I) {
- log.warn("Splitting looped way " + getDebugName(way) + " would make a zero length arc, so it will have to be pruned");
+ log.warn("Splitting looped way " + getDebugName(way) + " would make a short arc, so it will have to be pruned");
do {
log.warn(" Pruning point[" + p2I + "]");
wayPoints.remove(p2I);
@@ -647,7 +599,7 @@ public class StyledConverter implements OsmConverter {
// loop back and prune it
} while(p2I > p1I &&
(p2I + 1) == numPointsInWay &&
- p1.equals(wayPoints.get(p2I)));
+ p1.tooCloseTo(wayPoints.get(p2I)));
}
else {
// split the way before the second point
@@ -686,7 +638,7 @@ public class StyledConverter implements OsmConverter {
Coord p = points.get(i);
if(p.getHighwayCount() > 1) {
// point is going to be a node
- if(candidate.equals(p))
+ if(candidate.tooCloseTo(p))
return false;
// no need to test further
break;
@@ -697,7 +649,7 @@ public class StyledConverter implements OsmConverter {
Coord p = points.get(i);
if(p.getHighwayCount() > 1) {
// point is going to be a node
- if(candidate.equals(p))
+ if(candidate.tooCloseTo(p))
return false;
// no need to test further
break;
diff --git a/src/uk/me/parabola/mkgmap/reader/osm/Element.java b/src/uk/me/parabola/mkgmap/reader/osm/Element.java
index a49e7c7..d2ebc69 100644
--- a/src/uk/me/parabola/mkgmap/reader/osm/Element.java
+++ b/src/uk/me/parabola/mkgmap/reader/osm/Element.java
@@ -86,7 +86,8 @@ public abstract class Element implements Iterable<String> {
* element.
*/
public void copyTags(Element other) {
- tags = other.tags.copy();
+ if(other.tags != null)
+ tags = other.tags.copy();
}
public String getName() {
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 e350483..869b62c 100644
--- a/src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java
+++ b/src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java
@@ -27,6 +27,7 @@ import uk.me.parabola.imgfmt.app.Area;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.imgfmt.app.Exit;
import uk.me.parabola.log.Logger;
+import uk.me.parabola.mkgmap.general.LineClipper;
import uk.me.parabola.mkgmap.general.MapDetails;
import uk.me.parabola.mkgmap.general.RoadNetwork;
import uk.me.parabola.mkgmap.reader.osm.CoordPOI;
@@ -73,6 +74,7 @@ class Osm5XmlHandler extends DefaultHandler {
private static final int MODE_BOUNDS = 5;
private static final long CYCLEWAY_ID_OFFSET = 0x10000000;
+ private static final long CLIPPED_WAYS_ID_OFFSET = 0x20000000;
private Node currentNode;
private Way currentWay;
@@ -107,8 +109,13 @@ class Osm5XmlHandler extends DefaultHandler {
ignoreBounds = props.getProperty("ignore-osm-bounds", false);
routing = props.containsKey("route");
String rsa = props.getProperty("remove-short-arcs", null);
- if(rsa != null)
- minimumArcLength = (rsa.length() > 0)? Double.parseDouble(rsa) : 0.0;
+ final double MIN_ALLOWED_ARC_LENGTH = 5.0;
+ if("no".equals(rsa))
+ minimumArcLength = null;
+ else if(rsa != null)
+ minimumArcLength = (rsa.length() > 0)? Double.parseDouble(rsa) : MIN_ALLOWED_ARC_LENGTH;
+ else if(routing)
+ minimumArcLength = MIN_ALLOWED_ARC_LENGTH;
else
minimumArcLength = null;
frigRoundabouts = props.getProperty("frig-roundabouts");
@@ -454,6 +461,9 @@ class Osm5XmlHandler extends DefaultHandler {
nodeMap = null;
+ if(bbox != null)
+ clipWays();
+
if(minimumArcLength != null)
removeShortArcsByMergingNodes(minimumArcLength);
@@ -488,6 +498,59 @@ class Osm5XmlHandler extends DefaultHandler {
endTask.run();
}
+ private void clipWays() {
+ log.info("Clipping ways");
+ List<Way> allClippedWays = new ArrayList<Way>();
+ List<Way> deletedWays = new ArrayList<Way>();
+ // clip the ways
+ for(Way way : wayMap.values()) {
+ List<Way> clippedWays = clipWay(way);
+ if(clippedWays != null) {
+ deletedWays.add(way);
+ allClippedWays.addAll(clippedWays);
+ }
+ }
+ // now for each way that was clipped, remove the original
+ // way from wayMap and add the clipped sub-ways
+ for(Way way : deletedWays)
+ wayMap.remove(way.getId());
+
+ long clippedWayId = CLIPPED_WAYS_ID_OFFSET;
+ for(Way cw : allClippedWays)
+ wayMap.put(clippedWayId++, cw);
+
+ log.info("Clipping ways - " + deletedWays.size() + " ways clipped");
+ }
+
+ private List<Way> clipWay(Way way) {
+
+ List<Way> clippedWays = null;
+
+ List<List<Coord>> lineSegs = LineClipper.clip(bbox, way.getPoints());
+
+ if (lineSegs != null) {
+
+ clippedWays = new ArrayList<Way>();
+
+ for (List<Coord> lco : lineSegs) {
+ Way nWay = new Way(way.getId());
+ nWay.setName(way.getName());
+ nWay.copyTags(way);
+ for(Coord co : lco) {
+ nWay.addPoint(co);
+ if(co.getOnBoundary()) {
+ // this point lies on a boundary
+ // make sure it becomes a node
+ co.incHighwayCount();
+ }
+ }
+ clippedWays.add(nWay);
+ }
+ }
+
+ return clippedWays;
+ }
+
private final void incArcCount(Map<Coord, Integer> map, Coord p, int inc) {
Integer i = map.get(p);
if(i != null)
@@ -500,6 +563,7 @@ class Osm5XmlHandler extends DefaultHandler {
Map<Coord, Integer> arcCounts = new IdentityHashMap<Coord, Integer>();
int numWaysDeleted = 0;
int numNodesMerged = 0;
+ log.info("Removing short arcs (min arc length = " + minArcLength + "m)");
log.info("Removing short arcs - counting arcs");
for(Way w : wayMap.values()) {
List<Coord> points = w.getPoints();
@@ -520,6 +584,7 @@ class Osm5XmlHandler extends DefaultHandler {
// replacements maps those nodes that have been replaced to
// the node that replaces them
Map<Coord, Coord> replacements = new IdentityHashMap<Coord, Coord>();
+ Map<Way, Way> complainedAbout = new IdentityHashMap<Way, Way>();
boolean anotherPassRequired = true;
int pass = 0;
while(anotherPassRequired && pass < 10) {
@@ -537,6 +602,7 @@ class Osm5XmlHandler extends DefaultHandler {
}
int previousNodeIndex = 0; // first point will be a node
Coord previousPoint = points.get(0);
+ double arcLength = 0;
for(int i = 0; i < points.size(); ++i) {
Coord p = points.get(i);
// check if this point is to be replaced because
@@ -547,7 +613,9 @@ class Osm5XmlHandler extends DefaultHandler {
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));
+ assert !p.getOnBoundary() : "Boundary node replaced";
+ String replacementId = (replacement.getOnBoundary())? "'boundary node'" : "" + nodeIdMap.get(replacement);
+ log.info(" Way " + way.getTag("name") + " (OSM id " + way.getId() + ") has node " + nodeIdMap.get(p) + " replaced with node " + replacementId);
p = replacement;
// replace point in way
points.set(i, p);
@@ -558,13 +626,14 @@ class Osm5XmlHandler extends DefaultHandler {
if(i > 0) {
// this is not the first point in the way
if(p == previousPoint) {
- log.info(" Way " + way.getTag("name") + " (OSM id " + way.getId() + ") has consecutive identical nodes (" + nodeIdMap.get(p) + ") - deleting the second node");
+ log.info(" Way " + way.getTag("name") + " (OSM id " + way.getId() + ") has consecutive identical points (" + nodeIdMap.get(p) + ") - deleting the second point");
points.remove(i);
// hack alert! rewind the loop index
--i;
anotherPassRequired = true;
continue;
}
+ arcLength += p.distance(previousPoint);
previousPoint = p;
Coord previousNode = points.get(previousNodeIndex);
// this point is a node if it has an arc count
@@ -578,31 +647,71 @@ class Osm5XmlHandler extends DefaultHandler {
if(p != previousNode &&
(p.equals(previousNode) ||
(minArcLength > 0 &&
- minArcLength > p.distance(previousNode)))) {
+ minArcLength > arcLength))) {
+ if(previousNode.getOnBoundary() && p.getOnBoundary()) {
+ // both the previous node and this node
+ // are on the boundary
+ if(complainedAbout.get(way) == null) {
+ log.warn(" Way " + way.getTag("name") + " (OSM id " + way.getId() + ") has short arc (" + String.format("%.2f", arcLength) + "m) - but it can't be removed because both ends of the arc are boundary nodes!");
+ complainedAbout.put(way, way);
+ }
+ break; // give up with this way
+ }
+ String thisNodeId = (p.getOnBoundary())? "'boundary node'" : "" + nodeIdMap.get(p);
+ String previousNodeId = (previousNode.getOnBoundary())? "'boundary node'" : "" + nodeIdMap.get(previousNode);
+
if(p.equals(previousNode))
- log.info(" Way " + way.getTag("name") + " (OSM id " + way.getId() + ") has zero length arc - removing it by merging node " + nodeIdMap.get(p) + " into " + nodeIdMap.get(previousNode));
+ log.info(" Way " + way.getTag("name") + " (OSM id " + way.getId() + ") has zero length arc - removing it by merging node " + thisNodeId + " into " + previousNodeId);
else
- log.info(" Way " + way.getTag("name") + " (OSM id " + way.getId() + ") has short arc (" + ((int)(100 * p.distance(previousNode)))/100.0 + "m) - removing it by merging node " + nodeIdMap.get(p) + " into " + nodeIdMap.get(previousNode));
- ++numNodesMerged;
- replacements.put(p, previousNode);
- // add this node's arc count to the node
- // that is replacing it
- incArcCount(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);
+ log.info(" Way " + way.getTag("name") + " (OSM id " + way.getId() + ") has short arc (" + String.format("%.2f", arcLength) + "m) - removing it by merging node " + thisNodeId + " into " + previousNodeId);
+ if(p.getOnBoundary()) {
+ // current point is a boundary node so
+ // we need to merge the previous node into
+ // this node
+ ++numNodesMerged;
+ replacements.put(previousNode, p);
+ // add the previous node's arc
+ // count to this node
+ incArcCount(arcCounts, p, arcCounts.get(previousNode) - 1);
+ // remove the preceding point(s)
+ // back to and including the
+ // previous node
+ for(int j = i - 1; j >= previousNodeIndex; --j) {
+ points.remove(j);
+ }
+ // hack alert! rewind the loop index
+ i = previousNodeIndex;
+ anotherPassRequired = true;
+ }
+ else {
+ // current point is not on a boundary so
+ // merge this node into the previous one
+ ++numNodesMerged;
+ replacements.put(p, previousNode);
+ // add this node's arc count to the node
+ // that is replacing it
+ incArcCount(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;
}
- // 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 arc length
+ arcLength = 0;
}
}
}
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
