v5
in case people are still using this patch, i have reissued it without
the stuff that is now in commit 1152.
if you are using this patch and think it should also be committed -
please say - it didn't seem conclusive that is was useful when we last
discussed it
-----------------
v4
I have gone back to the original ordering of doing short arc removal
before clipping as the previous version of this patch badly broke
polygons
As for arcs whose length is less 5m, I am not convinced they are
actually a problem as far as routing is concerned as my tests show that
mapsource can happily route through zero length arcs that occur at tile
boundaries.
It would be good if people who have been obliged to use a minimum arc
length of > 0 would provide examples of where the routing is broken.
i.e. without using this patch, find an example which doesn't route when
--remove-short-arcs is specified but will route when
--remove-short-arcs=5 is specified.
What is still an issue and was discussed a while ago is the problem
where routing will fail (or produce a big diversion) when routing out
of one tile into another and then back to a destination in the first
tile. That never seems to work, short arcs or not.
--------------------
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 caa2d3e..b99d74b 100644
--- a/resources/help/en/options
+++ b/resources/help/en/options
@@ -187,11 +187,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 3930beb..6518b8c 100644
--- a/src/uk/me/parabola/imgfmt/app/net/RouteArc.java
+++ b/src/uk/me/parabola/imgfmt/app/net/RouteArc.java
@@ -72,14 +72,20 @@ public class RouteArc {
* @param nextCoord The heading coordinate.
*/
public RouteArc(RoadDef roadDef, RouteNode source, RouteNode dest,
- Coord nextCoord, double length) {
+ Coord nextCoord, double lengthInMetres) {
this.roadDef = roadDef;
this.source = source;
this.dest = dest;
- this.length = convertMeters(length);
+ length = convertMeters(lengthInMetres);
+ /*
+ if(length == 0) {
+ log.info("Forcing arc length to be non-zero at " + source.getCoord().toOSMURL());
+ length = 1;
+ }
+ */
if(log.isDebugEnabled())
- log.debug("set length", this.length);
+ log.debug("set length", length);
// if nextCoord is so close to the source node that the
// coordinates are equal, it won't be possible to determine
// the heading angle so use the dest node instead
@@ -207,6 +213,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 8506381..1e21590 100644
--- a/src/uk/me/parabola/mkgmap/general/RoadNetwork.java
+++ b/src/uk/me/parabola/mkgmap/general/RoadNetwork.java
@@ -105,10 +105,12 @@ 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());
}
+ */
// Create forward arc from node1 to node2
Coord bearing = coordList.get(lastIndex + 1);
diff --git a/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java b/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
index c45f2d9..0df58ac 100644
--- a/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
+++ b/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
@@ -575,9 +575,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);
@@ -638,8 +638,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);
@@ -729,7 +729,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 &&
@@ -739,7 +739,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);
@@ -754,7 +754,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
@@ -793,7 +793,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;
@@ -804,7 +804,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/xml/Osm5XmlHandler.java b/src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java
index e350483..28a037f 100644
--- a/src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java
+++ b/src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java
@@ -107,8 +107,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");
@@ -500,6 +505,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();
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
