Ok, I think I know what's been going wrong with some people's maps
where the routing goes zig-zaggy when the way is longish. However, it's
not the number of points in the way or even the length of the way that's
wrong.
It's because the bounding box becomes sufficiently large that it causes
the line to be split by the LineSizeSplitterFilter. This ancient
bit of code splits the line so that it doesn't have a bigger bounding
box than it thinks is acceptable. Well, that may be OK for plain lines
but for routable stuff like roads, it's bad news because there's no node
between the two parts of the split line. If, by chance, the point at
where the way was split was actually a node anyway, it probably worked
OK but for other points, anything could happen!
So the attached patch checks the way's bounding box earlier on when
it's doing all that boring way size/arc size/node count checking and if
the BB gets too large it snips the way in the accustomed fashion.
Anyway, please try the attached patch and see if it works OK - (no new
bad routing, no assertions, etc.)
Bloody hell, another long evening spent hacking mkgmap...
diff --git a/src/uk/me/parabola/mkgmap/filters/LineSizeSplitterFilter.java b/src/uk/me/parabola/mkgmap/filters/LineSizeSplitterFilter.java
index 19d2654..89d1f65 100644
--- a/src/uk/me/parabola/mkgmap/filters/LineSizeSplitterFilter.java
+++ b/src/uk/me/parabola/mkgmap/filters/LineSizeSplitterFilter.java
@@ -23,6 +23,7 @@ import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.log.Logger;
import uk.me.parabola.mkgmap.general.MapElement;
import uk.me.parabola.mkgmap.general.MapLine;
+import uk.me.parabola.mkgmap.general.MapRoad;
import uk.me.parabola.mkgmap.general.MapShape;
/**
@@ -41,6 +42,13 @@ public class LineSizeSplitterFilter implements MapFilter {
public void init(FilterConfig config) {
}
+ // return the greater of the absolute values of HEIGHT and WIDTH
+ // divided by the maximum allowed size - so if the height and
+ // width are not too large, the result will be <= 1.0
+ public static double testDims(int height, int width) {
+ return (double)Math.max(Math.abs(height), Math.abs(width)) / MAX_SIZE;
+ }
+
/**
* Keep track of the max dimentions of a line and split when they get too
* big.
@@ -59,6 +67,11 @@ public class LineSizeSplitterFilter implements MapFilter {
return;
}
+ if(line instanceof MapRoad) {
+ MapRoad road = ((MapRoad)line);
+ log.error("Way " + road.getRoadDef() + " has a max dimension of " + line.getBounds().getMaxDimention() + " and is about to be split (routing will be broken)");
+ }
+
List<Coord> points = line.getPoints();
log.debug("line too big, splitting");
@@ -130,10 +143,11 @@ public class LineSizeSplitterFilter implements MapFilter {
dim.reset();
coords = new ArrayList<Coord>();
coords.add(co);
+ dim.addToBounds(co);
}
}
- if (!coords.isEmpty()) {
+ if (coords.size() > 1) {
log.debug("bigness saving a final part");
l.setPoints(coords);
next.addElement(l);
diff --git a/src/uk/me/parabola/mkgmap/filters/LineSplitterFilter.java b/src/uk/me/parabola/mkgmap/filters/LineSplitterFilter.java
index 921d9d4..341e7c2 100644
--- a/src/uk/me/parabola/mkgmap/filters/LineSplitterFilter.java
+++ b/src/uk/me/parabola/mkgmap/filters/LineSplitterFilter.java
@@ -56,7 +56,7 @@ public class LineSplitterFilter implements MapFilter {
List<Coord> points = line.getPoints();
int npoints = points.size();
- if (npoints < MAX_POINTS_IN_LINE) {
+ if (npoints <= MAX_POINTS_IN_LINE) {
next.doFilter(element);
return;
}
diff --git a/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java b/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
index aefcf80..d1dcfab 100644
--- a/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
+++ b/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
@@ -31,6 +31,8 @@ import uk.me.parabola.imgfmt.app.Exit;
import uk.me.parabola.imgfmt.app.net.NODHeader;
import uk.me.parabola.imgfmt.app.trergn.ExtTypeAttributes;
import uk.me.parabola.log.Logger;
+import uk.me.parabola.mkgmap.filters.LineSizeSplitterFilter;
+import uk.me.parabola.mkgmap.filters.LineSplitterFilter;
import uk.me.parabola.mkgmap.general.AreaClipper;
import uk.me.parabola.mkgmap.general.Clipper;
import uk.me.parabola.mkgmap.general.LineAdder;
@@ -84,11 +86,11 @@ public class StyledConverter implements OsmConverter {
// limit arc lengths to what can be handled by RouteArc
private final int MAX_ARC_LENGTH = 75000;
- private final int MAX_POINTS_IN_WAY = 200;
+ private final int MAX_POINTS_IN_WAY = LineSplitterFilter.MAX_POINTS_IN_LINE;
- private final int MAX_POINTS_IN_ARC = 50;
+ private final int MAX_POINTS_IN_ARC = MAX_POINTS_IN_WAY;
- private final int MAX_NODES_IN_WAY = 16;
+ private final int MAX_NODES_IN_WAY = 64; // possibly could be increased
private final double MIN_DISTANCE_BETWEEN_NODES = 5.5;
@@ -1009,36 +1011,89 @@ public class StyledConverter implements OsmConverter {
// inter-node arc length becomes excessive
double arcLength = 0;
int numPointsInArc = 0;
+ // track the dimensions of the way's bbox so that we can
+ // detect if it would be split by the LineSizeSplitterFilter
+ class WayBBox {
+ int minLat = Integer.MAX_VALUE;
+ int maxLat = Integer.MIN_VALUE;
+ int minLon = Integer.MAX_VALUE;
+ int maxLon = Integer.MIN_VALUE;
+
+ void addPoint(Coord co) {
+ int lat = co.getLatitude();
+ if(lat < minLat)
+ minLat = lat;
+ if(lat > maxLat)
+ maxLat = lat;
+ int lon = co.getLongitude();
+ if(lon < minLon)
+ minLon = lon;
+ if(lon > maxLon)
+ maxLon = lon;
+ }
+
+ boolean tooBig() {
+ return LineSizeSplitterFilter.testDims(maxLat - minLat,
+ maxLon - minLon) > 1.0;
+ }
+ }
+
+ WayBBox wayBBox = new WayBBox();
+
for(int i = 0; i < points.size(); ++i) {
Coord p = points.get(i);
+ wayBBox.addPoint(p);
+
// check if we should split the way at this point to limit
// the arc length between nodes
if((i + 1) < points.size()) {
- double d = p.distance(points.get(i + 1));
- if(d > MAX_ARC_LENGTH) {
- double fraction = 0.99 * MAX_ARC_LENGTH / d;
- Coord extrap = p.makeBetweenPoint(points.get(i + 1), fraction);
- extrap.incHighwayCount();
- points.add(i + 1, extrap);
- double newD = p.distance(extrap);
- log.info("Way " + debugWayName + " contains a segment that is " + (int)d + "m long so I am adding a point to reduce its length to " + (int)newD + "m");
+ Coord nextP = points.get(i + 1);
+ double d = p.distance(nextP);
+ // get arc size as a proportion of the max allowed - a
+ // value greater than 1.0 indicate that the bbox is
+ // too large in at least one dimension
+ double arcProp = LineSizeSplitterFilter.testDims(nextP.getLatitude() -
+ p.getLatitude(),
+ nextP.getLongitude() -
+ p.getLongitude());
+ if(arcProp > 1.0 || d > MAX_ARC_LENGTH) {
+ if(arcProp > 1.0)
+ nextP = p.makeBetweenPoint(nextP, 0.95 / arcProp);
+ else
+ nextP = p.makeBetweenPoint(nextP, 0.95 * MAX_ARC_LENGTH / d);
+ nextP.incHighwayCount();
+ points.add(i + 1, nextP);
+ double newD = p.distance(nextP);
+ log.info("Way " + debugWayName + " contains a segment that is " + (int)d + "m long but I am adding a new point to reduce its length to " + (int)newD + "m");
d = newD;
}
+ wayBBox.addPoint(nextP);
+
if((arcLength + d) > MAX_ARC_LENGTH) {
assert i > 0;
+ assert trailingWay == null;
trailingWay = splitWayAt(way, i);
// this will have truncated the current Way's
// points so the loop will now terminate
log.info("Splitting way " + debugWayName + " at " + points.get(i).toOSMURL() + " to limit arc length to " + (long)arcLength + "m");
}
+ else if(wayBBox.tooBig()) {
+ assert i > 0;
+ assert trailingWay == null;
+ trailingWay = splitWayAt(way, i);
+ // this will have truncated the current Way's
+ // points so the loop will now terminate
+ log.info("Splitting way " + debugWayName + " at " + points.get(i).toOSMURL() + " to limit the size of its bounding box");
+ }
else if(numPointsInArc >= (MAX_POINTS_IN_ARC / 2) &&
points.size() > MAX_POINTS_IN_ARC &&
p.getHighwayCount() > 1) {
// this point is already a node so it's a good place
// to split the way
log.info("Splitting way " + debugWayName + " at " + points.get(i).toOSMURL() + " (using an existing node) to limit number of points in this arc to " + numPointsInArc + ", way has " + (points.size() - i) + " more points");
+ assert trailingWay == null;
trailingWay = splitWayAt(way, i);
// this will have truncated the current Way's
// points so the loop will now terminate
@@ -1047,6 +1102,7 @@ public class StyledConverter implements OsmConverter {
safeToSplitWay(points, i, i - numPointsInArc, points.size() - 1)) {
// we have to split the way here
log.info("Splitting way " + debugWayName + " at " + points.get(i).toOSMURL() + " (making a new node) to limit number of points in this arc to " + numPointsInArc + ", way has " + (points.size() - i) + " more points");
+ assert trailingWay == null;
trailingWay = splitWayAt(way, i);
// this will have truncated the current Way's
// points so the loop will now terminate
@@ -1077,6 +1133,7 @@ public class StyledConverter implements OsmConverter {
// this isn't the last point in the way so split
// it here to avoid exceeding the max nodes in way
// limit
+ assert trailingWay == null;
trailingWay = splitWayAt(way, i);
// this will have truncated the current Way's
// points so the loop will now terminate
@@ -1138,7 +1195,7 @@ public class StyledConverter implements OsmConverter {
int rs = getSpeedIdx(maxSpeed);
if(rs >= 0)
roadSpeed = rs;
- log.info(debugWayName + " maxspeed=" + maxSpeed + ", speedIndex=" + roadSpeed);
+ log.debug(debugWayName + " maxspeed=" + maxSpeed + ", speedIndex=" + roadSpeed);
}
}
val = way.getTag("mkgmap:road-speed");
@@ -1198,7 +1255,7 @@ public class StyledConverter implements OsmConverter {
// access
noAccess[index] = true;
}
- log.info(type + " is not allowed in " + highwayType + " " + debugWayName);
+ log.debug(type + " is not allowed in " + highwayType + " " + debugWayName);
} else if (accessExplicitlyAllowed(accessTagValue)) {
if (index == RoadNetwork.NO_MAX) {
// everything is allowed access
@@ -1209,7 +1266,7 @@ public class StyledConverter implements OsmConverter {
// access
noAccess[index] = false;
}
- log.info(type + " is allowed in " + highwayType + " " + debugWayName);
+ log.debug(type + " is allowed in " + highwayType + " " + debugWayName);
}
else if (accessTagValue.equalsIgnoreCase("destination")) {
if (type.equals("motorcar") ||
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
