The attached patch (which also includes the drive-on-left patch because
it's based on that) attempts to improve the quality of routing
instructions so that when a turn off a road that doesn't involve a big
heading change is required, the GPS should say "turn left/right" rather
than "keep left/right". It can also reduce the number of "keep
left/right" instructions you get when you are not leaving the main road
but passing a junction that has a shallow turn (e.g. sometimes happens
on motorways when it tells you to keep left/right even though you are
not leaving the motorway).
I have tested it a little and it appears to work. I expect there are
situations where it does the wrong thing so it would be great if people
could give it a go and see if it behaves OK.
There isn't any option to enable the feature at the moment. If you use
the patch, it will be enabled.
It's currently issuing a warning for each change it makes but later that
can be downgraded to info.
Cheers,
Mark
diff --git a/resources/help/en/options b/resources/help/en/options
index a608abc..bf7a587 100644
--- a/resources/help/en/options
+++ b/resources/help/en/options
@@ -178,6 +178,19 @@ Miscellaneous options:
Experimental: Create maps that support routing. This implies --net
(so that --net need not be given if --route is given).
+--drive-on-left
+--drive-on-right
+ Explicitly specify which side of the road vehicles are
+ expected to drive on. If neither of these options are
+ specified, it is assumed that vehicles drive on the right
+ unless --check-roundabouts is specified and the first
+ roundabout processed is clockwise.
+
+--check-roundabouts
+ Check that roundabouts have the expected direction (clockwise
+ when vehicles drive on the left). Roundabouts that are complete
+ loops and have the wrong direction are reversed.
+
--ignore-maxspeeds
When reading OSM files, ignore any "maxspeed" tags.
diff --git a/src/uk/me/parabola/imgfmt/app/Coord.java b/src/uk/me/parabola/imgfmt/app/Coord.java
index 5462602..335284d 100644
--- a/src/uk/me/parabola/imgfmt/app/Coord.java
+++ b/src/uk/me/parabola/imgfmt/app/Coord.java
@@ -174,6 +174,22 @@ public class Coord implements Comparable<Coord> {
(int)(longitude + (other.longitude - longitude) * fraction));
}
+
+ // returns bearing (in degrees) from current point to another point
+ public double bearingTo(Coord point) {
+ double lat1 = Utils.toRadians(latitude);
+ double lat2 = Utils.toRadians(point.latitude);
+ double lon1 = Utils.toRadians(longitude);
+ double lon2 = Utils.toRadians(point.longitude);
+
+ double dlon = lon2 - lon1;
+
+ double y = Math.sin(dlon) * Math.cos(lat2);
+ double x = Math.cos(lat1)*Math.sin(lat2) -
+ Math.sin(lat1)*Math.cos(lat2)*Math.cos(dlon);
+ return Math.atan2(y, x) * 180 / Math.PI;
+ }
+
/**
* Sort lexicographically by longitude, then latitude.
*
diff --git a/src/uk/me/parabola/imgfmt/app/net/NODHeader.java b/src/uk/me/parabola/imgfmt/app/net/NODHeader.java
index 1623fa7..2a8a709 100644
--- a/src/uk/me/parabola/imgfmt/app/net/NODHeader.java
+++ b/src/uk/me/parabola/imgfmt/app/net/NODHeader.java
@@ -37,6 +37,8 @@ public class NODHeader extends CommonHeader {
private final char align = DEF_ALIGN;
+ private static boolean driveOnLeft;
+
public NODHeader() {
super(HEADER_LEN, "GARMIN NOD");
}
@@ -62,7 +64,10 @@ public class NODHeader extends CommonHeader {
nodes.writeSectionInfo(writer);
// now sets 0x02 (enable turn restrictions?)
- writer.putInt(0x27);
+ int val = 0x27;
+ if(driveOnLeft)
+ val |= 0x0300;
+ writer.putInt(val);
writer.putChar(align);
writer.putChar((char) (align - 1));
@@ -100,4 +105,8 @@ public class NODHeader extends CommonHeader {
public Section getBoundarySection() {
return boundary;
}
+
+ public static void setDriveOnLeft(boolean dol) {
+ driveOnLeft = dol;
+ }
}
diff --git a/src/uk/me/parabola/imgfmt/app/net/RouteArc.java b/src/uk/me/parabola/imgfmt/app/net/RouteArc.java
index f349248..0b80259 100644
--- a/src/uk/me/parabola/imgfmt/app/net/RouteArc.java
+++ b/src/uk/me/parabola/imgfmt/app/net/RouteArc.java
@@ -43,7 +43,7 @@ public class RouteArc {
private int offset;
- private final byte initialHeading;
+ private int initialHeading; // degrees
private byte endDirection;
private final RoadDef roadDef;
@@ -69,10 +69,10 @@ public class RouteArc {
* @param roadDef The road that this arc segment is part of.
* @param source The source node.
* @param dest The destination node.
- * @param nextCoord The heading coordinate.
+ * @param initialHeading The initial heading (signed degrees)
*/
public RouteArc(RoadDef roadDef, RouteNode source, RouteNode dest,
- Coord nextCoord, double length) {
+ int initialHeading, double length) {
this.roadDef = roadDef;
this.source = source;
this.dest = dest;
@@ -80,23 +80,20 @@ public class RouteArc {
this.length = convertMeters(length);
if(log.isDebugEnabled())
log.debug("set length", this.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
- if(source.getCoord().equals(nextCoord)) {
- if(source.getCoord().equals(dest.getCoord())) {
- log.warn("Can't determine arc heading (using 0) at " + source.getCoord().toOSMURL());
- this.initialHeading = (byte)0;
- }
- else {
- log.info("Using destination node to determine arc heading at " + source.getCoord().toOSMURL());
- this.initialHeading = calcAngle(dest.getCoord());
- }
- }
- else
- this.initialHeading = calcAngle(nextCoord);
+ this.initialHeading = initialHeading;
// too early: dest.nodeClass may still increase
//setDestinationClass(dest.getNodeClass());
+
+ source.addArc(this);
+ dest.addIncomingArc(this);
+ }
+
+ public int getInitialHeading() {
+ return initialHeading;
+ }
+
+ public void setInitialHeading(int ih) {
+ initialHeading = ih;
}
public RouteNode getSource() {
@@ -167,36 +164,6 @@ public class RouteArc {
return indexB;
}
- private byte calcAngle(Coord end) {
- Coord start = source.getCoord();
-
- if(log.isDebugEnabled())
- log.debug("start", start.toDegreeString(), ", end", end.toDegreeString());
-
- // Quite possibly too slow... TODO
- double lat1 = Utils.toRadians(start.getLatitude());
- double lat2 = Utils.toRadians(end.getLatitude());
- double lon1 = Utils.toRadians(start.getLongitude());
- double lon2 = Utils.toRadians(end.getLongitude());
-
- //double dlat = lat2 - lat1;
- double dlon = lon2 - lon1;
-
- double y = Math.sin(dlon) * Math.cos(lat2);
- double x = Math.cos(lat1)*Math.sin(lat2) -
- Math.sin(lat1)*Math.cos(lat2)*Math.cos(dlon);
- double angle = Math.atan2(y, x);
-
- // angle is in radians
- if(log.isDebugEnabled())
- log.debug("angle is ", angle, ", deg", angle*57.29);
-
- byte b = (byte) (256 * (angle / (2 * Math.PI)));
- if(log.isDebugEnabled())
- log.debug("deg from ret val", (360 * b) / 256);
-
- return b;
- }
private static int convertMeters(double l) {
// XXX: really a constant factor?
@@ -235,7 +202,7 @@ public class RouteArc {
for (int aLendat : lendat)
writer.put((byte) aLendat);
- writer.put(initialHeading);
+ writer.put((byte)(256 * initialHeading / 360));
if (curve) {
int[] curvedat = encodeCurve();
@@ -327,13 +294,4 @@ public class RouteArc {
log.debug("setting destination class", destinationClass);
flagA |= (destinationClass & MASK_DESTCLASS);
}
-
- public void setEndDirection(double ang) {
- endDirection = angleToByte(ang);
- curve = true;
- }
-
- private static byte angleToByte(double ang) {
- return (byte) (255 * ang / 360);
- }
}
diff --git a/src/uk/me/parabola/imgfmt/app/net/RouteNode.java b/src/uk/me/parabola/imgfmt/app/net/RouteNode.java
index 90a46cd..27fbfce 100644
--- a/src/uk/me/parabola/imgfmt/app/net/RouteNode.java
+++ b/src/uk/me/parabola/imgfmt/app/net/RouteNode.java
@@ -21,6 +21,7 @@ import java.util.List;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.imgfmt.app.CoordNode;
import uk.me.parabola.imgfmt.app.ImgFileWriter;
+import uk.me.parabola.imgfmt.app.Label;
import uk.me.parabola.log.Logger;
/**
@@ -58,7 +59,9 @@ public class RouteNode implements Comparable<RouteNode> {
private final List<RouteArc> arcs = new ArrayList<RouteArc>();
// restrictions at (via) this node
private final List<RouteRestriction> restrictions = new ArrayList<RouteRestriction>();
-
+ // arcs to this node - order must be the same as arcs
+ private final List<RouteArc> incomingArcs = new ArrayList<RouteArc>();
+
private int flags = F_UNK_NEEDED;
private final CoordNode coord;
@@ -107,6 +110,10 @@ public class RouteNode implements Comparable<RouteNode> {
flags |= F_ARCS;
}
+ public void addIncomingArc(RouteArc arc) {
+ incomingArcs.add(arc);
+ }
+
public void addRestriction(RouteRestriction restr) {
restrictions.add(restr);
flags |= F_RESTRICTIONS;
@@ -285,4 +292,142 @@ public class RouteNode implements Comparable<RouteNode> {
public int compareTo(RouteNode otherNode) {
return coord.compareTo(otherNode.getCoord());
}
+
+ private boolean possiblySameRoad(RouteArc raa, RouteArc rab) {
+ if(raa == rab)
+ return true;
+ RoadDef rda = raa.getRoadDef();
+ RoadDef rdb = rab.getRoadDef();
+ if(rda == rdb)
+ return true;
+ Label[] laba = rda.getLabels();
+ Label[] labb = rdb.getLabels();
+ for(int i = 0; i < rda.getNumLabels(); ++i)
+ for(int j = 0; j < rdb.getNumLabels(); ++j)
+ if(laba[i].equals(labb[j]))
+ return true;
+
+ return false;
+ }
+
+ public void tweakArcs() {
+ if(arcs.size() == 3) {
+ final int minHeadingChangeWanted = 45; // min change to be a "turn"
+
+ // detect the "shallow turn" scenario where at a junction
+ // on some road, the side road leaves the original road at
+ // a very shallow angle and the GPS says "keep right/left"
+ // when it would be better if it said "turn right/left"
+
+ // the code tries to detect a pair of arcs (the "incoming"
+ // arc and the "continuing" arc) that are the "main road"
+ // and the remaining arc (called the "other" arc) which is
+ // the "side road"
+
+ // having worked out the roles for the arcs, the heuristic
+ // applied is that if the main road doesn't change its
+ // heading by more than minHeadingChangeWanted, ensure
+ // that the side road heading differs from the continuing
+ // heading by at least minHeadingChangeWanted
+
+ for(int ia = 0; ia < incomingArcs.size(); ++ia) {
+ RouteArc inArc = incomingArcs.get(ia);
+ // determine heading of incoming arc by reversing
+ // heading of matching outgoing arc
+ int inHeading = arcs.get(ia).getInitialHeading() + 180;
+ while(inHeading > 180)
+ inHeading -= 360;
+ while(inHeading < -180)
+ inHeading += 360;
+ // determine the outgoing (continuing) arc that is
+ // likely to be the same road as the incoming arc
+ RouteArc continuingArc = null;
+ int ca = 0;
+ while(ca < arcs.size()) {
+ if(ca != ia) {
+ if(possiblySameRoad(inArc, arcs.get(ca))) {
+ continuingArc = arcs.get(ca);
+ break;
+ }
+ }
+ ++ca;
+ }
+ // if we did not find the continuing arc, give up with
+ // this incoming arc
+ if(continuingArc == null) {
+ // log.warn("Can't continue road " + inArc.getRoadDef().getName() + " at " + coord.toOSMURL());
+ continue;
+ }
+ int continuingHeading = continuingArc.getInitialHeading();
+ int mainHeadingDelta = continuingHeading - inHeading;
+ while(mainHeadingDelta > 180)
+ mainHeadingDelta -= 360;
+ while(mainHeadingDelta < -180)
+ mainHeadingDelta += 360;
+ // log.warn(inArc.getRoadDef().getName() + " continues to " + continuingArc.getRoadDef().getName() + " with a heading change of " + mainHeadingDelta + " at " + coord.toOSMURL());
+
+ // if the continuation road heading change is less
+ // than minHeadingChangeWanted, force the other road's
+ // heading change to be at least minHeadingChangeWanted
+ // from the continuation heading
+ if(Math.abs(mainHeadingDelta) < minHeadingChangeWanted) {
+ int oa = 3 - ia - ca;
+ RouteArc otherArc = arcs.get(oa);
+ if(!possiblySameRoad(inArc, otherArc)) {
+ int outHeading = otherArc.getInitialHeading();
+ int outHeadingDelta = outHeading - continuingHeading;
+ while(outHeadingDelta > 180)
+ outHeadingDelta -= 360;
+ while(outHeadingDelta < -180)
+ outHeadingDelta += 360;
+ // log.warn("Found turn ("+ outHeadingDelta + " deg) from " + inArc.getRoadDef().getName() + " to " + otherArc.getRoadDef().getName() + " at " + coord.toOSMURL());
+ final int veryShallowTurnDelta = 1;
+ if(outHeadingDelta > veryShallowTurnDelta &&
+ outHeadingDelta < minHeadingChangeWanted) {
+ log.warn("Found shallow turn (" + outHeadingDelta + " deg) from " + inArc.getRoadDef().getName() + " to " + otherArc.getRoadDef().getName() + " at " + coord.toOSMURL());
+ int newHeading = continuingHeading + minHeadingChangeWanted;
+ if(newHeading > 180)
+ newHeading -= 360;
+ otherArc.setInitialHeading(newHeading);
+ }
+ /*
+ else if(outHeadingDelta > 0 &&
+ outHeadingDelta <= veryShallowTurnDelta) {
+ log.warn("Found very shallow turn (" + outHeadingDelta + " deg) from " + inArc.getRoadDef().getName() + " to " + otherArc.getRoadDef().getName() + " at " + coord.toOSMURL());
+ int newHeading = continuingHeading + minHeadingChangeWanted/2;
+ if(newHeading > 180)
+ newHeading -= 360;
+ otherArc.setInitialHeading(newHeading);
+ }
+ */
+ else if(outHeadingDelta < -veryShallowTurnDelta &&
+ outHeadingDelta > -minHeadingChangeWanted) {
+ log.warn("Found shallow turn (" + outHeadingDelta + " deg) from " + inArc.getRoadDef().getName() + " to " + otherArc.getRoadDef().getName() + " at " + coord.toOSMURL());
+ int newHeading = continuingHeading - minHeadingChangeWanted;
+ if(newHeading < -180)
+ newHeading += 360;
+ otherArc.setInitialHeading(newHeading);
+ }
+ /*
+ else if(outHeadingDelta < 0 &&
+ outHeadingDelta >= -veryShallowTurnDelta) {
+ log.warn("Found very shallow turn (" + outHeadingDelta + " deg) from " + inArc.getRoadDef().getName() + " to " + otherArc.getRoadDef().getName() + " at " + coord.toOSMURL());
+ int newHeading = continuingHeading - minHeadingChangeWanted/2;
+ if(newHeading < -180)
+ newHeading += 360;
+ otherArc.setInitialHeading(newHeading);
+ }
+ */
+ }
+ }
+ }
+ }
+ /*
+ else {
+ log.warn("Node has " + arcs.size() + " arcs at " + coord.toOSMURL());
+ for(RouteArc a : arcs)
+ log.warn(" arc " + a.getRoadDef().getName());
+ }
+ */
+ }
}
diff --git a/src/uk/me/parabola/mkgmap/general/RoadNetwork.java b/src/uk/me/parabola/mkgmap/general/RoadNetwork.java
index 8506381..d885612 100644
--- a/src/uk/me/parabola/mkgmap/general/RoadNetwork.java
+++ b/src/uk/me/parabola/mkgmap/general/RoadNetwork.java
@@ -112,16 +112,39 @@ public class RoadNetwork {
// Create forward arc from node1 to node2
Coord bearing = coordList.get(lastIndex + 1);
- RouteArc arc = new RouteArc(road.getRoadDef(), node1, node2, bearing, arcLength);
+ if(lastCoord.equals(bearing)) {
+ // bearing point is too close to last node to be
+ // useful - try some more points
+ for(int bi = lastIndex + 2; bi <= index; ++bi) {
+ if(!lastCoord.equals(coordList.get(bi))) {
+ bearing = coordList.get(bi);
+ break;
+ }
+ }
+ }
+ RouteArc arc = new RouteArc(road.getRoadDef(),
+ node1,
+ node2,
+ (int)lastCoord.bearingTo(bearing),
+ arcLength);
arc.setForward();
- node1.addArc(arc);
// Create the reverse arc
bearing = coordList.get(index - 1);
+ if(co.equals(bearing)) {
+ // bearing point is too close to this node to be
+ // useful - try some more points
+ for(int bi = index - 2; bi > lastIndex; --bi) {
+ if(!co.equals(coordList.get(bi))) {
+ bearing = coordList.get(bi);
+ break;
+ }
+ }
+ }
RouteArc arc2 = new RouteArc(road.getRoadDef(),
- node2, node1,
- bearing, arcLength);
- node2.addArc(arc2);
+ node2, node1,
+ (int)co.bearingTo(bearing),
+ arcLength);
} else {
// This is the first node in the road
road.getRoadDef().setNode(getNode(id, co));
@@ -162,8 +185,10 @@ public class RoadNetwork {
NOD1Part nod1 = new NOD1Part();
- for (RouteNode node : nodes.values())
+ for (RouteNode node : nodes.values()) {
+ node.tweakArcs();
nod1.addNode(node);
+ }
centers = nod1.subdivide();
}
diff --git a/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java b/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
index 2e124ea..f05829d 100644
--- a/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
+++ b/src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
@@ -28,6 +28,7 @@ import uk.me.parabola.imgfmt.app.Area;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.imgfmt.app.CoordNode;
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.general.AreaClipper;
@@ -98,6 +99,9 @@ public class StyledConverter implements OsmConverter {
private final Rule relationRules;
private boolean ignoreMaxspeeds;
+ private boolean driveOnLeft;
+ private boolean driveOnRight;
+ private boolean checkRoundabouts;
class AccessMapping {
private final String type;
@@ -139,6 +143,10 @@ public class StyledConverter implements OsmConverter {
nodeRules = style.getNodeRules();
relationRules = style.getRelationRules();
ignoreMaxspeeds = props.getProperty("ignore-maxspeeds") != null;
+ driveOnLeft = props.getProperty("drive-on-left") != null;
+ NODHeader.setDriveOnLeft(driveOnLeft);
+ driveOnRight = props.getProperty("drive-on-right") != null;
+ checkRoundabouts = props.getProperty("check-roundabouts") != null;
LineAdder overlayAdder = style.getOverlays(lineAdder);
if (overlayAdder != null)
@@ -523,6 +531,69 @@ public class StyledConverter implements OsmConverter {
}
if("roundabout".equals(way.getTag("junction"))) {
+ List<Coord> points = way.getPoints();
+ // if roundabout checking is enabled and roundabout has at
+ // least 3 points and it has not been marked as "don't
+ // check", check its direction
+ if(checkRoundabouts &&
+ way.getPoints().size() > 3 &&
+ !way.isBoolTag("mkgmap:no-dir-check")) {
+ Coord centre = way.getCofG();
+ int dir = 0;
+ // check every third segment
+ for(int i = 0; (i + 1) < points.size(); i += 3) {
+ Coord pi = points.get(i);
+ Coord pi1 = points.get(i + 1);
+ // don't check segments that are very short
+ if(pi.quickDistance(centre) > 2.5 &&
+ pi.quickDistance(pi1) > 2.5) {
+ // determine bearing from segment that starts with
+ // point i to centre of roundabout
+ double a = pi.bearingTo(pi1);
+ double b = pi.bearingTo(centre) - a;
+ while(b > 180)
+ b -= 360;
+ while(b < -180)
+ b += 360;
+ // if bearing to centre is between 15 and 165
+ // degrees consider it trustworthy
+ if(b >= 15 && b < 165)
+ ++dir;
+ else if(b <= -15 && b > -165)
+ --dir;
+ }
+ }
+ if(dir != 0) {
+ boolean clockwise = dir > 0;
+ if(points.get(0) == points.get(points.size() - 1)) {
+ // roundabout is a loop
+ if(!driveOnLeft && !driveOnRight) {
+ if(clockwise) {
+ log.info("Roundabout " + way.getId() + " is clockwise so assuming vehicles should drive on left side of road (" + centre.toOSMURL() + ")");
+ driveOnLeft = true;
+ NODHeader.setDriveOnLeft(true);
+ }
+ else {
+ log.info("Roundabout " + way.getId() + " is anti-clockwise so assuming vehicles should drive on right side of road (" + centre.toOSMURL() + ")");
+ driveOnRight = true;
+ }
+ }
+ if(driveOnLeft && !clockwise ||
+ driveOnRight && clockwise) {
+ log.warn("Roundabout " + way.getId() + " direction is wrong - reversing it (see " + centre.toOSMURL() + ")");
+ way.reverse();
+ }
+ }
+ else if(driveOnLeft && !clockwise ||
+ driveOnRight && clockwise) {
+ // roundabout is a line
+ log.warn("Roundabout segment " + way.getId() + " direction looks wrong (see " + points.get(0).toOSMURL() + ")");
+ }
+ }
+ else
+ log.info("Roundabout segment " + way.getId() + " direction unknown (see " + points.get(0).toOSMURL() + ")");
+ }
+
String frigFactorTag = way.getTag("mkgmap:frig_roundabout");
if(frigFactorTag != null) {
// do special roundabout frigging to make gps
diff --git a/src/uk/me/parabola/mkgmap/reader/osm/Way.java b/src/uk/me/parabola/mkgmap/reader/osm/Way.java
index 1f2242b..1c152ef 100644
--- a/src/uk/me/parabola/mkgmap/reader/osm/Way.java
+++ b/src/uk/me/parabola/mkgmap/reader/osm/Way.java
@@ -101,4 +101,18 @@ public class Way extends Element {
sb.append(toTagString());
return sb.toString();
}
+
+ public Coord getCofG() {
+ int lat = 0;
+ int lon = 0;
+ int numPoints = points.size();
+ if(numPoints < 1)
+ return null;
+ for(Coord p : points) {
+ lat += p.getLatitude();
+ lon += p.getLongitude();
+ }
+ return new Coord((lat + numPoints / 2) / numPoints,
+ (lon + numPoints / 2) / numPoints);
+ }
}
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
