v4 - added --remove-bogus-nodes option to turn on this feature.
Even though the reduction in nodes is fairly modest (typically 5-10%), I
believe that this could be useful for those routable ways that share
many points with non-routable lines or areas. A lot of roads do
share points with neighbouring areas and in those cases, this option
should remove a lot of bogus nodes. Whether that translates into
improved routing in that region is yet to be proven.
----------
v3 - now duplicates ways so that any structural changes to the way made
while processing a line/road will not affect the original way and so
each map object generated from the original way will see the full set
of points in the way.
Duplicating the ways appeared to have no noticeable effect on the run
time when processing the GB map.
--------
v2 - avoid assertion when more than one routable way is generated from
the same OSM way
-------
With the recent reversion of the Table A breakage, it's now useful
to post this patch for wider testing as it no longer causes my Nuvi to
barf.
What it does is remove routing nodes from ways that should never have
been put there in the first place. Without this patch, a routable way
will have a node for each of its points that are shared by any other
way (whether the other ways are routable or not). For example, at the
moment, if a way shares its points with a boundary line or shape, each
of those points will become nodes. From the routing point of view,
that's (essentially) harmless but having extra nodes does take up space
and must slow down the routing calculation.
It therefore makes sense to remove the bogus nodes.
What this patch does is defer the processing of all of the
points/lines/shapes until after their types have been computed. Having
computed the ways' types we know what's routable and what isn't so
nodes only need to be created where routable ways meet.
That's the theory, in practice, it produces slightly smaller maps.
Whether it actually improves the routing quality is yet to be
determined.
Obviously, the gain you will see depends on how many bogus nodes are in
your maps.
All feedback welcome.
Mark
diff --git a/resources/help/en/options b/resources/help/en/options
index 6dc6a7f..4c77030 100644
--- a/resources/help/en/options
+++ b/resources/help/en/options
@@ -240,6 +240,10 @@ 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-bogus-nodes
+ Removes routing nodes that are only used in a single way.
+ Such nodes are harmless but they inflate the routing data.
+
--remove-short-arcs[=MinLength]
Merge nodes to remove short arcs that can cause routing
problems. If MinLength is specified (in metres), arcs shorter
diff --git a/src/uk/me/parabola/imgfmt/app/Coord.java b/src/uk/me/parabola/imgfmt/app/Coord.java
index 6a15fce..186ea86 100644
--- a/src/uk/me/parabola/imgfmt/app/Coord.java
+++ b/src/uk/me/parabola/imgfmt/app/Coord.java
@@ -77,10 +77,15 @@ public class Coord implements Comparable<Coord> {
return highwayCount;
}
- public void incHighwayCount() {
+ public Coord incHighwayCount() {
// don't let it wrap
if(highwayCount < Byte.MAX_VALUE)
++highwayCount;
+ return this;
+ }
+
+ public void zeroHighwayCount() {
+ highwayCount = 0;
}
public boolean getOnBoundary() {
diff --git a/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java b/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
index 6c665e0..7398f08 100644
--- a/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
+++ b/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
@@ -95,14 +95,19 @@ public class StyledConverter implements OsmConverter {
private final int MAX_POINTS_IN_ARC = MAX_POINTS_IN_WAY;
- private final int MAX_NODES_IN_WAY = 64; // possibly could be increased
+ private final int MAX_NODES_IN_WAY = MAX_POINTS_IN_WAY;
private final double MIN_DISTANCE_BETWEEN_NODES = 5.5;
// nodeIdMap maps a Coord into a nodeId
private final Map<Coord, Integer> nodeIdMap = new IdentityHashMap<Coord, Integer>();
private int nextNodeId = 1;
-
+
+ private List<Way> routableWays = new ArrayList<Way>(10000);
+ private List<Way> allWays = new ArrayList<Way>(10000);
+ private List<GType> allTypes = new ArrayList<GType>(10000);
+ private int[] nodeCounts = new int[MAX_NODES_IN_WAY + 1];
+
private final Rule wayRules;
private final Rule nodeRules;
private final Rule relationRules;
@@ -111,6 +116,7 @@ public class StyledConverter implements OsmConverter {
private boolean driveOnLeft;
private boolean driveOnRight;
private boolean checkRoundabouts;
+ private boolean removeBogusNodes;
class AccessMapping {
private final String type;
@@ -156,6 +162,7 @@ public class StyledConverter implements OsmConverter {
NODHeader.setDriveOnLeft(driveOnLeft);
driveOnRight = props.getProperty("drive-on-right") != null;
checkRoundabouts = props.getProperty("check-roundabouts") != null;
+ removeBogusNodes = props.getProperty("remove-bogus-nodes") != null;
LineAdder overlayAdder = style.getOverlays(lineAdder);
if (overlayAdder != null)
@@ -253,25 +260,84 @@ public class StyledConverter implements OsmConverter {
* @param way The OSM way.
*/
public void convertWay(Way way) {
+
+ // way being null signals that all ways have now been passed
+ if(way == null) {
+ if(removeBogusNodes) {
+ // to minimise the number of routing nodes created, we
+ // need to recalculate the highway counts as some will
+ // be too large due to the fact that a routable way
+ // has shared points with some non-routable feature
+ // (line or shape)
+ log.info("Zeroing highway counts in " + routableWays.size() + " routable ways");
+ int nodesThen = 0;
+ int nodesNow = 0;
+ for(Way w : routableWays) {
+ for(Coord p : w.getPoints()) {
+ if(p.getHighwayCount() > 1)
+ ++nodesThen;
+ p.zeroHighwayCount();
+ }
+ }
+
+ log.info("Updating highway counts");
+ for(Way w : routableWays) {
+ if(!w.isBoolTag("mkgmap:synthesised")) {
+ for(Coord p : w.getPoints()) {
+ p.incHighwayCount();
+ if(p.getHighwayCount() == 2)
+ ++nodesNow;
+ }
+ }
+ }
+ log.info("" + (nodesThen - nodesNow) + " bogus nodes removed, " + nodesNow + " nodes remain");
+ }
+ log.info("Processing ways");
+ for(int i = 0; i < allWays.size(); ++i) {
+ Way wi = allWays.get(i);
+ GType ti = allTypes.get(i);
+ if (ti.getFeatureKind() == GType.POLYLINE) {
+ if(ti.isRoad() &&
+ !MapElement.hasExtendedType(ti.getType())) {
+ addRoad(wi, ti);
+ }
+ else
+ addLine(wi, ti);
+ }
+ else
+ addShape(wi, ti);
+ }
+
+ log.info("Node statistics - " + routableWays.size() + " routable ways");
+ for(int i = 0; i <= MAX_NODES_IN_WAY; ++i) {
+ int nc = nodeCounts[i];
+ if(nc > 0)
+ log.info("" + nc + " way(s) have " + i + " nodes");
+ }
+
+ routableWays = null;
+ allWays = null;
+ allTypes = null;
+
+ return;
+ }
+
if (way.getPoints().size() < 2)
return;
GType foundType = null;
if(way.getTag("mkgmap:gtype") != null) {
-
foundType = makeGTypeFromTags(way);
if(foundType == null)
return;
-
- if (foundType.getFeatureKind() == GType.POLYLINE) {
- if(foundType.isRoad() &&
- !MapElement.hasExtendedType(foundType.getType()))
- addRoad(way, foundType);
- else
- addLine(way, foundType);
- }
- else
- addShape(way, foundType);
+ Way dupWay = way.duplicate();
+ // remember way and foundType so it can be processed later
+ // after the highway counts have been recalculated
+ allWays.add(dupWay);
+ allTypes.add(foundType);
+ if (foundType.isRoad() &&
+ !MapElement.hasExtendedType(foundType.getType()))
+ routableWays.add(dupWay);
}
else {
preConvertRules(way);
@@ -284,14 +350,13 @@ public class StyledConverter implements OsmConverter {
postConvertRules(dupWay, foundType);
- if (foundType.getFeatureKind() == GType.POLYLINE) {
- if(foundType.isRoad())
- addRoad(dupWay, foundType);
- else
- addLine(dupWay, foundType);
- }
- else
- addShape(dupWay, foundType);
+ // remember way and foundType so it can be processed later
+ // after the highway counts have been recalculated
+ allWays.add(dupWay);
+ allTypes.add(foundType);
+ if (foundType.isRoad() &&
+ !MapElement.hasExtendedType(foundType.getType()))
+ routableWays.add(dupWay);
} while (!foundType.isFinal());
}
}
@@ -586,6 +651,8 @@ public class StyledConverter implements OsmConverter {
void addRoad(Way way, GType gt) {
+ log.info("Adding road " + way.toBrowseURL() + " with type 0x" + Integer.toHexString(gt.getType()));
+
String oneWay = way.getTag("oneway");
if("-1".equals(oneWay) || "reverse".equals(oneWay)) {
// it's a oneway street in the reverse direction
@@ -790,6 +857,7 @@ public class StyledConverter implements OsmConverter {
// insert a new point after the POI to
// make a short stub segment
p1 = p.makeBetweenPoint(p1, stubSegmentLength / dist);
+ p1.incHighwayCount();
points.add(i + 1, p1);
}
@@ -848,6 +916,7 @@ public class StyledConverter implements OsmConverter {
// insert a new point to make a short
// stub segment
p1 = p1.makeBetweenPoint(p, stubSegmentLength / dist);
+ p1.incHighwayCount();
points.add(i + 1, p1);
// as p1 is now no longer a CoordPOI,
// the split below will be deferred
@@ -888,6 +957,15 @@ public class StyledConverter implements OsmConverter {
nWay.copyTags(way);
for(Coord co : lco) {
nWay.addPoint(co);
+ if(co.getHighwayCount() == 0) {
+ // either the point is in a synthesised
+ // way or it was added by the clipper
+ // (which should not happen if the ways
+ // were "soft clipped" earlier).
+ if(false && !way.isBoolTag("mkgmap:synthesised"))
+ log.warn("Clipper added point at " + co.toOSMURL());
+ co.incHighwayCount();
+ }
if(co.getOnBoundary()) {
// this point lies on a boundary
// make sure it becomes a node
@@ -1059,7 +1137,7 @@ public class StyledConverter implements OsmConverter {
name = "";
else
name += " ";
- return name + "(OSM id " + way.getId() + ")";
+ return name + "(" + way.toBrowseURL() + ")";
}
void addRoadWithoutLoops(Way way, GType gt) {
@@ -1223,6 +1301,8 @@ public class StyledConverter implements OsmConverter {
}
}
+ assert p.getHighwayCount() > 0 : "Point " + i + " in way " + debugWayName + " has zero highway count at " + p.toOSMURL() + " (way has " + points.size() + " points)";
+
if(p.getHighwayCount() > 1) {
// this point is a node connecting highways
Integer nodeId = nodeIdMap.get(p);
@@ -1419,6 +1499,14 @@ public class StyledConverter implements OsmConverter {
int numNodes = nodeIndices.size();
road.setNumNodes(numNodes);
+ ++nodeCounts[numNodes];
+
+ if(numNodes > 0.9 * points.size()) {
+ String message = "Way " + debugWayName + " has " + points.size() + " points and " + (100 * numNodes / points.size()) + "% of those are nodes, perhaps it overlaps another way?";
+ if(points.size() > 10)
+ log.info(message);
+ }
+
if(numNodes > 0) {
// replace Coords that are nodes with CoordNodes
boolean hasInternalNodes = false;
@@ -1437,7 +1525,12 @@ public class StyledConverter implements OsmConverter {
}
CoordNode thisCoordNode = new CoordNode(coord.getLatitude(), coord.getLongitude(), nodeId, boundary);
+ thisCoordNode.incHighwayCount();
points.set(n, thisCoordNode);
+ // put an entry in nodeIdMap for the CoordNode so that
+ // it will get matched if this way is used to generate
+ // more than one routable way
+ nodeIdMap.put(thisCoordNode, nodeId);
// see if this node plays a role in any turn
// restrictions
diff --git a/src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java b/src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
index e2f3c64..95882ca 100644
--- a/src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
+++ b/src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
@@ -136,12 +136,12 @@ public class MultiPolygonRelation extends Relation {
int iLon = inList.get(in).getLongitude();
if (Math.abs(oLat - iLat) > Math.abs(oLon - iLon)) {
int delta = (oLon > iLon)? -1 : 1;
- outList.add(index++, new Coord(iLat + delta, iLon));
- outList.add(index, new Coord(oLat + delta, oLon));
+ outList.add(index++, new Coord(iLat + delta, iLon).incHighwayCount());
+ outList.add(index, new Coord(oLat + delta, oLon).incHighwayCount());
} else{
int delta = (oLat > iLat)? 1 : -1;
- outList.add(index++, new Coord(iLat, iLon + delta));
- outList.add(index, new Coord(oLat, oLon + delta));
+ outList.add(index++, new Coord(iLat, iLon + delta).incHighwayCount());
+ outList.add(index, new Coord(oLat, oLon + delta).incHighwayCount());
}
}
}
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 57a6ae1..0f5466d 100644
--- a/src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java
+++ b/src/uk/me/parabola/mkgmap/reader/osm/xml/Osm5XmlHandler.java
@@ -559,6 +559,9 @@ class Osm5XmlHandler extends DefaultHandler {
for (Way w: wayMap.values())
converter.convertWay(w);
+ // signal converter that all ways have been passed
+ converter.convertWay(null);
+
wayMap = null;
RoadNetwork roadNetwork = mapper.getRoadNetwork();
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
