Hi Gerd
I've been looking at turn pop-ups and routing decisions and attach a
patch that makes improvements:
Move decision about when to use compactDir initialHeadings from
RouteNode to AngleChecker.
The current code checks if any headings from a RouteNode share the same
compactDir/4-bit sector and, if so, revert to the full/8-bit value.
Overlaid roads triggered this, also sharp angles that couldn't be
widened, probably when many paths converge at a road.
AngleChecker::fixSharpAngles was coded on the basis that compactDirs
are used and it tested/increased angles based on this 4-bit step, but
if these are then represented in 8-bit format, the encode angle could
be much (up to 22.5 degrees) less that the code was expecting and
result in turning delays in route calculations.
Recode fixSharpAngles to work in degrees but choose the thresholds to
be good for compactDirs. Test the resultant angles and only use
compactDirs if there are no roads in the same or adjacent 4-bit
sectors.
Not allowing Adjacent is necessary because, in compactDirs format, if
there is a path in the opposite sector to the road and the road
continuation is the adjacent sector, Garmin gives a "turn to stay on
road" pop-up, but with 8-bit headings it doesn't. This is slightly
different from the following case because this concerns an angle that
doesn't need to be "unsharpened" as it isn't permitted for vehicles to
make this turn.
When increasing an angle, change the heading of the lower class/speed
road in preference to the major road.
This helps prevent the "turn to stay on road" type pop-ups when the
lead-off road was more straight-on than the main road and one-way
tagging possibly missing.
Handle simple (<= 2 RouteArcs) RouteNodes as special cases, giving
slight efficiency improvements.
Add some diagnostics for showing RouteNodes and RouteArcs in an area.
Tidy up normalisation of headings.
Fix some bugs.
Ticker
Index: src/uk/me/parabola/imgfmt/app/net/AngleChecker.java
===================================================================
--- src/uk/me/parabola/imgfmt/app/net/AngleChecker.java (revision 4586)
+++ src/uk/me/parabola/imgfmt/app/net/AngleChecker.java (working copy)
@@ -40,6 +40,21 @@
*
* @author Gerd Petermann
*
+ * Somehow these penalties are also applied to "shortest" routing,
+ * often resulting in something that is definitely not the shortest
+ * route.
+ *
+ * Possibly a more significant problem is the very low cost Garmin
+ * gives to a minor road crossing a more major road - much less than
+ * the "against driving-side" turn onto the major road. If there is a
+ * small block/triangle of roads on the other side, the routing
+ * algorithm might prefer crossing the major road then multiple
+ * driving-side turns rather than the correct single turn.
+ *
+ * I haven't found a way of preventing this.
+ *
+ * Ticker Berkin
+ *
*/
public class AngleChecker {
private static final Logger log = Logger.getLogger(AngleChecker.class);
@@ -47,19 +62,21 @@
private boolean ignoreSharpAngles;
private boolean cycleMap;
- private static final int MIN_ANGLE = 0x10;
- private static final int MIN_LOW_SPEED_ANGLE = 0x20;
-
- private int mask;
- private int mrnd;
-
+ // Generally it is safe to use compactDirs when there are no arcs in consecutive
+ // 22.5 degree sectors and this is guaranteed if the minumum angle is >= 45 degrees.
+ private static final float COMPACT_DIR_DEGREES = 45+1; // +bit for 360>256 conversion rounding
+ // If this is >= above, then compactDirs will be used unless other, non-vehicle access angles are sharp
+ private static final float SHARP_DEGREES = COMPACT_DIR_DEGREES;
+ // Experimentation found no benefit in increasing angle beyond 2 "sectors"
+ private static final float MIN_ANGLE = 11.25f; // don't reduce angles to less than this (arbitrary)
+
// helper class to collect multiple arcs with (nearly) the same initial headings
private class ArcGroup {
float initialHeading;
- byte imgHeading;
int isOneWayTrueCount;
int isForwardTrueCount;
int maxRoadSpeed;
+ int maxRoadClass;
byte orAccessMask;
HashSet<RoadDef> roadDefs = new HashSet<>();
@@ -72,6 +89,8 @@
isForwardTrueCount++;
if (arc.getRoadDef().getRoadSpeed() > maxRoadSpeed)
maxRoadSpeed = arc.getRoadDef().getRoadSpeed();
+ if (arc.getRoadDef().getRoadClass() > maxRoadClass)
+ maxRoadClass = arc.getRoadDef().getRoadClass();
orAccessMask |= arc.getRoadDef().getAccess();
roadDefs.add(arc.getRoadDef());
}
@@ -88,19 +107,15 @@
return isForwardTrueCount == arcs.size();
}
- /**
- * @return
- */
- public void setInitialHeading(float modIH) {
- while (modIH > 180)
- modIH -= 360;
- while (modIH < -180)
- modIH += 360;
- initialHeading = modIH;
- imgHeading = calcEncodedBearing(initialHeading);
+ public void modInitialHeading(float modIH) {
+ initialHeading += modIH;
+ if (initialHeading >= 180)
+ initialHeading -= 360;
+ else if (initialHeading < -180)
+ initialHeading += 360;
for (RouteArc arc : arcs) {
- arc.setInitialHeading(modIH);
+ arc.modInitialHeading(modIH);
}
}
@@ -109,11 +124,6 @@
}
}
-
- private byte calcEncodedBearing(float b) {
- return (byte) ((RouteArc.directionFromDegrees(b) + mrnd) & mask);
- }
-
public void config(EnhancedProperties props) {
// undocumented option - usually used for debugging only
ignoreSharpAngles = props.getProperty("ignore-sharp-angles", false);
@@ -125,8 +135,6 @@
byte sharpAnglesCheckMask = cycleMap ? (byte) (0xff & ~AccessTagsAndBits.FOOT) : AccessTagsAndBits.BIKE;
for (RouteNode node : nodes.values()){
- mask = 0xf0; // we assume compacted format
- mrnd = 0x08; // rounding
fixSharpAngles(node, sharpAnglesCheckMask);
}
}
@@ -134,65 +142,122 @@
public void fixSharpAngles(RouteNode node, byte sharpAnglesCheckMask) {
- // get direct arcs leaving the node
- List<ArcGroup> arcGroups = buildArcGroups(node);
+ List<RouteArc> arcs = node.getArcs();
+ if (arcs.size() <= 1) // nothing to do - maybe an edge. Will use 8bit dirs if there is an arc
+ return;
+ if (arcs.size() == 2) { // common case where two roads join but isn't a junction
+ doSimpleJoin(node, arcs);
+ return;
+ }
- int n = arcGroups.size();
- if (n <= 1)
- return;
- // sort the arcs by initial heading
- arcGroups.sort((ag1, ag2) -> Float.compare(ag1.initialHeading, ag2.initialHeading));
+ // Combine arcs with nearly the same initial heading.
+
+ // first get direct arcs leaving the node
+ List<RouteArc> directArcs = new ArrayList<>();
+ for (RouteArc arc : arcs) {
+ if (arc.isDirect())
+ directArcs.add(arc);
+ }
+ if (directArcs.size() <= 1)
+ return; // should not happen
- class AngleAttr {
- int angle;
- int maskedAngle;
- int maskedMinAngle = MIN_ANGLE;
- boolean noAccess;
-
- int maskedDeltaToMin(){
- return maskedAngle - maskedMinAngle;
+ // sort the arcs by initial heading
+ directArcs.sort((ra1,ra2) -> {
+ int d = Float.compare(ra1.getInitialHeading(), ra2.getInitialHeading());
+ if (d != 0)
+ return d;
+ d = Integer.compare(ra1.getPointsHash(), ra2.getPointsHash());
+ if (d != 0)
+ return d;
+ return Long.compare(ra1.getRoadDef().getId() , ra2.getRoadDef().getId());
+ });
+
+ // now combine into groups
+ // also calculate minimum angle between arcs for quick decision if more needs to be done
+ List<ArcGroup> arcGroups = new ArrayList<>();
+ Iterator<RouteArc> iter = directArcs.listIterator();
+ RouteArc arc1 = iter.next();
+ boolean addArc1 = false;
+ float minAngle = 180;
+ while (iter.hasNext() || addArc1) {
+ ArcGroup ag = new ArcGroup();
+ ag.initialHeading = arc1.getInitialHeading();
+ ag.addArc(arc1);
+ arcGroups.add(ag);
+ addArc1 = false;
+ while (iter.hasNext()) {
+ RouteArc arc2 = iter.next();
+ float angleBetween = arc2.getInitialHeading() - ag.initialHeading;
+ if (angleBetween < 1) {
+ if (arc1.getDest() != arc2.getDest() && arc1.getRoadDef().getId() != arc2.getRoadDef().getId())
+ log.warn("sharp angle < 1° at",node.getCoord().toDegreeString(),",maybe duplicated OSM way with bearing",getCompassBearing(arc1.getInitialHeading()));
+ ag.addArc(arc2);
+ } else {
+ if (angleBetween < minAngle)
+ minAngle = angleBetween;
+ arc1 = arc2;
+ if (!iter.hasNext())
+ addArc1 = true;
+ break;
+ }
}
- void setMaskedMinAngle(int maskedMinAngle){
- this.maskedMinAngle = maskedMinAngle;
- }
-
- public String toString(){
- return angle + "° " + maskedAngle + " " + maskedMinAngle + " " + noAccess;
- }
}
-
- // step one: calculate the existing angles
+
+ int lastInx = arcGroups.size()-1;
+ if (lastInx == 0)
+ return;
+ // handle the last > first groups
+ float angleBetween = arcGroups.get(0).initialHeading - arcGroups.get(lastInx).initialHeading + 360;
+ if (angleBetween < 1) {
+ if (lastInx == 1) // just two that would be merged, so can stop
+ return;
+ for (RouteArc arc : arcGroups.get(lastInx).arcs)
+ arcGroups.get(0).addArc(arc);
+ arcGroups.remove(lastInx);
+ } else if (angleBetween < minAngle)
+ minAngle = angleBetween;
+
+ if (minAngle >= SHARP_DEGREES) {
+ if (minAngle >= COMPACT_DIR_DEGREES)
+ // RouteNode default is setUseCompactDirs(false);
+ node.setUseCompactDirs(true);
+ return;
+ }
+
+ final int n = arcGroups.size();
+ // scan the angles and see what needs attention
+ // Note: This algorithm won't spot and fix a sharp angle where there is a 'no-access' arc between
+
+ class AngleAttr {
+ float angle;
+ float minAngle;
+ }
+
AngleAttr[] angles = new AngleAttr[n];
for (int i = 0; i < n; i++){
ArcGroup ag1 = arcGroups.get(i);
ArcGroup ag2 = arcGroups.get(i+1 < n ? i+1 : 0);
- AngleAttr angleAttr = new AngleAttr();
- angles[i] = angleAttr;
- angleAttr.angle = Math.round(ag2.getInitialHeading() - ag1.getInitialHeading());
- angleAttr.maskedAngle = ag2.imgHeading - ag1.imgHeading;
- if (i + 1 >= n){
- angleAttr.angle += 360;
- }
- if (angleAttr.maskedAngle < 0)
- angleAttr.maskedAngle += 256;
+ AngleAttr aa = new AngleAttr();
+ angles[i] = aa;
+ aa.angle = ag2.getInitialHeading() - ag1.getInitialHeading();
+ if (i+1 >= n)
+ aa.angle += 360;
+ aa.minAngle = Math.min(MIN_ANGLE, aa.angle);
+ float saveMinAngle = aa.minAngle;
- if (ag1.isOneway() && ag1.isForward()
- || ag2.isOneway() && !ag2.isForward()) {
- // the "incoming" arc or the "outgoing" is a wrong direction oneway
- angleAttr.noAccess = true;
- }
+ if (ag1.isOneway() && ag2.isOneway() && (ag1.isForward() == ag2.isForward()))
+ continue; // two one-ways entry to entry or exit to exit
+ byte pathAccessMask = (byte) (ag1.orAccessMask & ag2.orAccessMask);
+ if (pathAccessMask == 0)
+ continue; // no common vehicle allowed on both arcs
+ if (pathAccessMask == AccessTagsAndBits.FOOT)
+ continue; // only pedestrians - sharp angle not a problem
+ if (Math.min(ag1.maxRoadSpeed, ag2.maxRoadSpeed) == 0)
+ continue; // eg service/parking where sharp angle probably indicates shouldn't turn here
- int sumSpeeds = ag1.maxRoadSpeed + ag2.maxRoadSpeed;
- if (sumSpeeds <= 1)
- continue;
- byte pathAccessMask = (byte) (ag1.orAccessMask & ag2.orAccessMask);
- if (pathAccessMask == 0) {
- // no common vehicle allowed on both arcs
- angleAttr.noAccess = true;
- }
- if (angleAttr.noAccess)
- continue;
- int maskedMinAngle = MIN_LOW_SPEED_ANGLE;
+ aa.minAngle = SHARP_DEGREES;
+
+// int sumSpeeds = ag1.maxRoadSpeed + ag2.maxRoadSpeed;
// the Garmin algorithm sees rounded values, so the thresholds are probably
// near 22.5 (0x10), 45(0x20), 67.5 (0x30), 90, 112.5 (0x40)
@@ -212,19 +277,17 @@
// else if (sumSpeeds >= 4)
// maskedMinAngle = 0x30;
// }
- angleAttr.setMaskedMinAngle(maskedMinAngle);
+ // With changes to switch compactDirs and working in degrees rather than masked sectors,
+ // the above variables are wrong, but the idea holds
- if (angleAttr.maskedDeltaToMin() >= 0)
+ if (aa.angle >= aa.minAngle)
continue;
-
+
String ignoredReason = null;
- if (pathAccessMask == AccessTagsAndBits.FOOT)
- ignoredReason = "because it can only be used by pedestrians";
- else if ((pathAccessMask & sharpAnglesCheckMask) == 0)
+ if ((pathAccessMask & sharpAnglesCheckMask) == 0)
ignoredReason = "because it can not be used by bike";
- else if (ag1.isOneway() && ag2.isOneway()){
- // both arcs are one-ways, probably the road splits here
- // to avoid the sharp angles we are looking for
+ else if (ag1.isOneway() && ag2.isOneway() & n == 3) {
+ // both arcs are one-ways, probably the road splits/joins carriageways here
ignoredReason = "because it seems to be a flare road";
}
else if (ag1.roadDefs.size() == 1 && ag2.roadDefs.size() == 1 && ag1.roadDefs.containsAll(ag2.roadDefs)){
@@ -232,150 +295,140 @@
}
if (ignoredReason != null){
if (log.isInfoEnabled()){
- String sharpAngle = "sharp angle " + angleAttr.angle + "° at " + node.getCoord().toDegreeString();
- log.info(sharpAngle, "headings",getCompassBearing(ag1.getInitialHeading()) , getCompassBearing(ag2.getInitialHeading()),"speeds",ag1.maxRoadSpeed, ag2.maxRoadSpeed);
- log.info("ignoring", sharpAngle, ignoredReason);
+ log.info("sharp angle", aa.angle, "° at", node.getCoord().toDegreeString(),
+ "headings", getCompassBearing(ag1.getInitialHeading()), getCompassBearing(ag2.getInitialHeading()),
+ "speeds", ag1.maxRoadSpeed, ag2.maxRoadSpeed);
+ log.info("ignoring", ignoredReason);
}
- angleAttr.setMaskedMinAngle(MIN_ANGLE);
- angleAttr.noAccess = true;
+ aa.minAngle = saveMinAngle; // restore as don't want to widen
}
}
+ // go through the angles again and try to increase any that are less than minAngle
for (int i = 0; i < n; i++){
AngleAttr aa = angles[i];
- if (aa.maskedAngle >= aa.maskedMinAngle || aa.noAccess)
+ float wantedIncrement = aa.minAngle - aa.angle;
+ if (wantedIncrement <= 0)
continue;
- int oldAngle = aa.angle;
+ float oldAngle = aa.angle;
ArcGroup ag1 = arcGroups.get(i);
ArcGroup ag2 = arcGroups.get(i+1 < n ? i+1 : 0);
- String sharpAngle = "";
if (log.isInfoEnabled()){
- sharpAngle = "sharp angle " + aa.angle + "° at " + node.getCoord().toDegreeString();
- log.info(sharpAngle, "headings",getCompassBearing(ag1.getInitialHeading()) , getCompassBearing(ag2.getInitialHeading()),"speeds",ag1.maxRoadSpeed, ag2.maxRoadSpeed);
+ log.info("sharp angle", aa.angle, "° at", node.getCoord().toDegreeString(),
+ "headings", getCompassBearing(ag1.getInitialHeading()), getCompassBearing(ag2.getInitialHeading()),
+ "speeds", ag1.maxRoadSpeed, ag2.maxRoadSpeed,
+ "classes",ag1.maxRoadClass, ag2.maxRoadClass);
}
// XXX restrictions ?
- boolean fixed = false;
- int wantedIncrement = Math.abs(aa.maskedDeltaToMin()) ;
- AngleAttr predAA = angles[i == 0 ? n - 1 : i - 1];
+ AngleAttr predAA = angles[i == 0 ? n - 1 : i - 1];
AngleAttr nextAA = angles[i >= n - 1 ? 0 : i + 1];
// we can increase the angle by changing the heading values of one or both arcs
- // find out which one to change first
- byte origImgDir1 = ag1.imgHeading;
- byte origImgDir2 = ag2.imgHeading;
- int origImgAngle = getImgAngle(ag1.imgHeading, ag2.imgHeading);
+ // How much we can encroach on the adjacent angles
+ float deltaPred = predAA.angle - predAA.minAngle;
+ float deltaNext = nextAA.angle - nextAA.minAngle;
- int deltaPred = predAA.maskedDeltaToMin();
- int deltaNext = nextAA.maskedDeltaToMin();
+ if (deltaNext > 0 && deltaPred > 0) { // can take from both
+ if (ag1.maxRoadClass == ag2.maxRoadClass &&
+ ag1.maxRoadSpeed == ag2.maxRoadSpeed) { // take from both in ratio to available
+ deltaNext = Math.min(deltaNext, wantedIncrement * deltaNext / (deltaNext + deltaPred));
+ deltaPred = Math.min(deltaPred, wantedIncrement - deltaNext);
+ } else if (ag1.maxRoadClass > ag2.maxRoadClass ||
+ (ag1.maxRoadClass == ag2.maxRoadClass &&
+ ag1.maxRoadSpeed > ag2.maxRoadSpeed)) { // take as much as poss from next
+ if (deltaNext >= wantedIncrement) {
+ deltaNext = wantedIncrement;
+ deltaPred = 0;
+ } else {
+ deltaPred = Math.min(deltaPred, wantedIncrement - deltaNext);
+ }
+ } else { // take as much as possible from pred
+ if (deltaPred >= wantedIncrement) {
+ deltaPred = wantedIncrement;
+ deltaNext = 0;
+ } else {
+ deltaNext = Math.min(deltaNext, wantedIncrement - deltaPred);
+ }
+ }
+ } else if (deltaNext > 0) {
+ if (deltaNext > wantedIncrement)
+ deltaNext = wantedIncrement;
+ } else {
+ if (deltaPred > wantedIncrement)
+ deltaPred = wantedIncrement;
+ }
- if (deltaNext > 0 && (deltaNext > deltaPred || deltaPred < wantedIncrement)){
- int usedIncrement = Math.min(wantedIncrement, deltaNext);
- float oldIH = ag2.getInitialHeading();
- int modIH = ag2.imgHeading + usedIncrement;
- if (modIH > 128)
- modIH -= 256;
- ag2.setInitialHeading(modIH * 360 / 256f);
- int modAngle = Math.round(ag2.getInitialHeading() - ag1.getInitialHeading());
- if (modAngle < 0)
- modAngle += 360;
- int modImgAngle = getImgAngle(ag1.imgHeading, ag2.imgHeading);
- if (modImgAngle >= aa.maskedMinAngle)
- fixed = true;
- log.info(sharpAngle, "changing arc with heading", getCompassBearing(oldIH), "->",getCompassBearing(ag2.getInitialHeading()),
- "angle is now",modAngle+"°, in img format:",origImgDir2,"->",ag2.imgHeading, "img angle (0-255)",origImgAngle, "->", modImgAngle);
- aa.angle = modAngle;
- nextAA.angle -= usedIncrement;
+ if (deltaNext > 0) { // can take some from the following angle
+ log.info("increasing arc with heading", getCompassBearing(ag2.getInitialHeading()), "by", deltaNext);
+ ag2.modInitialHeading(deltaNext);
+ aa.angle += deltaNext;
+ nextAA.angle -= deltaNext;
+ wantedIncrement -= deltaNext;
}
- if (!fixed && deltaPred > 0){
- wantedIncrement = Math.abs(aa.maskedDeltaToMin());
- int usedIncrement = Math.min(wantedIncrement, deltaPred);
- float oldIH = ag1.getInitialHeading();
- int modIH = ag1.imgHeading - usedIncrement;
- if (modIH < -128)
- modIH += 256;
- ag1.setInitialHeading(modIH * 360 / 256f);
- int modAngle = Math.round(ag2.getInitialHeading() - ag1.getInitialHeading());
- if (modAngle < 0)
- modAngle += 360;
- int modImgAngle = getImgAngle(ag1.imgHeading, ag2.imgHeading);
- if (modImgAngle >= aa.maskedMinAngle)
- fixed = true;
-
- log.info(sharpAngle, "changing arc with heading", getCompassBearing(oldIH), "->", getCompassBearing(ag1.getInitialHeading()),
- "angle is now",modAngle+"°, in img format:",origImgDir1,"->",ag1.imgHeading, "img angle (0-255)",origImgAngle, "->", modImgAngle);
- aa.angle = modAngle;
- predAA.angle -= usedIncrement;
+ if (deltaPred > 0) { // and some from the previous angle
+ log.info("decreasing arc with heading", getCompassBearing(ag1.getInitialHeading()), "by", deltaPred);
+ ag1.modInitialHeading(-deltaPred);
+ aa.angle += deltaPred;
+ predAA.angle -= deltaPred;
+ wantedIncrement -= deltaPred;
}
- if (!fixed){
+
+ if (wantedIncrement > 0) {
if (aa.angle == oldAngle)
- log.info(sharpAngle, "don't know how to fix it");
- else
- log.info(sharpAngle, "don't know how to enlarge it further");
+ log.info("don't know how to fix it", wantedIncrement);
+ else
+ log.info("don't know how to enlarge it further", wantedIncrement);
}
}
+
+ // check that all angles ok. might be some that couldn't fix and some that didn't matter
+ minAngle = 180;
+ for (int i=0; i < n; ++i) {
+ if (angles[i].angle < minAngle)
+ minAngle = angles[i].angle;
+ }
+ if (minAngle >= COMPACT_DIR_DEGREES)
+ node.setUseCompactDirs(true);
}
/**
- * Combine arcs with nearly the same initial heading.
+ * Called when there are exactly 2 arcs on the routing node.
+ * This is a common case where a road changes speed/name/class.
+ * It just checks for the angle of the 2 roads and increases it if sharp to reduce any potential
+ * excessive cost for the section so it won't be avoided unneccessarily by routing decisions elsewhere.
+ * Could check that both arcs usable by vehicles and do nothing if not, but hardly worth the bother.
+ *
* @param node
- * @return
+ * @param arcs
*/
- private List<ArcGroup> buildArcGroups(RouteNode node) {
- List<ArcGroup> arcGroups = new ArrayList<>();
- List<RouteArc> directArcs = new ArrayList<>();
- for (RouteArc arc : node.getArcs()){
- if (arc.isDirect()){
- directArcs.add(arc);
- }
+ private void doSimpleJoin(RouteNode node, List<RouteArc> arcs) {
+ RouteArc arc1 = arcs.get(0);
+ RouteArc arc2 = arcs.get(1);
+ float angle = arc1.getInitialHeading() - arc2.getInitialHeading();
+ float extra = 0; // signed amount where +ve increases arc1 & decreases arc2
+ if (angle > 360 - SHARP_DEGREES) // crosses -180
+ extra = 360 - angle - SHARP_DEGREES;
+ else if (angle < SHARP_DEGREES - 360) // ditto the other way
+ extra = SHARP_DEGREES - angle - 360;
+ else if (angle > 0) {
+ if (angle < SHARP_DEGREES)
+ extra = SHARP_DEGREES - angle;
+ } else if (angle < 0) {
+ if (angle > -SHARP_DEGREES)
+ extra = -angle - SHARP_DEGREES;
+ } // else angle == 0 and can't widen as don't know which way around to do it
+ if (extra != 0) {
+ if (log.isInfoEnabled())
+ log.info("join angle", angle, "° at", node.getCoord().toDegreeString(), "increased by", extra);
+ arc1.modInitialHeading(+extra/2);
+ arc2.modInitialHeading(-extra/2);
}
- if (directArcs.size() < 2)
- return arcGroups; // should not happen
-
- // sort the arcs by initial heading
- directArcs.sort((ra1,ra2) -> {
- int d = Float.compare(ra1.getInitialHeading(), ra2.getInitialHeading());
- if (d != 0)
- return d;
- d = Integer.compare(ra1.getPointsHash(), ra2.getPointsHash());
- if (d != 0)
- return d;
- d = Long.compare(ra1.getRoadDef().getId() , ra2.getRoadDef().getId());
- if (d != 0)
- return d;
- return d;
- });
-
- Iterator<RouteArc> iter = directArcs.listIterator();
- RouteArc arc1 = iter.next();
- boolean addArc1 = false;
- while (iter.hasNext() || addArc1){
- ArcGroup ag = new ArcGroup();
- ag.initialHeading = arc1.getInitialHeading();
- ag.addArc(arc1);
- arcGroups.add(ag);
- addArc1 = false;
- while (iter.hasNext()){
- RouteArc arc2 = iter.next();
- if (Math.abs(arc1.getInitialHeading()- arc2.getInitialHeading()) < 1){
- if (arc1.getDest() != arc2.getDest() && arc1.getRoadDef().getId() != arc2.getRoadDef().getId())
- log.warn("sharp angle < 1° at",node.getCoord().toDegreeString(),",maybe duplicated OSM way with bearing",getCompassBearing(arc1.getInitialHeading()));
- ag.addArc(arc2);
- } else{
- arc1 = arc2;
- if (!iter.hasNext())
- addArc1 = true;
- break;
- }
- }
- }
- for (ArcGroup ag : arcGroups){
- ag.imgHeading = calcEncodedBearing(ag.initialHeading);
- }
- return arcGroups;
+ node.setUseCompactDirs(true); // this won't cause any problems
}
+
/**
* for log messages
*/
Index: src/uk/me/parabola/imgfmt/app/net/RoadNetwork.java
===================================================================
--- src/uk/me/parabola/imgfmt/app/net/RoadNetwork.java (revision 4586)
+++ src/uk/me/parabola/imgfmt/app/net/RoadNetwork.java (working copy)
@@ -203,8 +203,8 @@
double reverseInitialBearing = currNode.bearingTo(reverseBearingPoint);
double reverseDirectBearing = 0;
if (directLength > 0){
- // bearing on rhumb line is a constant, so we can simply revert
- reverseDirectBearing = (forwardDirectBearing <= 0) ? 180 + forwardDirectBearing: -(180 - forwardDirectBearing) % 180.0;
+ // bearing on rhumb line is a constant, so we can simply reverse
+ reverseDirectBearing += 180; // RouteArc will normalise
}
RouteArc reverseArc = new RouteArc(roadDef,
node2, node1,
Index: src/uk/me/parabola/imgfmt/app/net/RouteArc.java
===================================================================
--- src/uk/me/parabola/imgfmt/app/net/RouteArc.java (revision 4586)
+++ src/uk/me/parabola/imgfmt/app/net/RouteArc.java (working copy)
@@ -41,7 +41,7 @@
private int offset;
- // heading / bearing:
+ // heading / bearing: -180 <= val < +180
private float initialHeading; // degrees (A-> B in an arc ABCD)
private final float directHeading; // degrees (A-> D in an arc ABCD)
@@ -97,8 +97,9 @@
this.roadDef = roadDef;
this.source = source;
this.dest = dest;
- this.initialHeading = (float) initialBearing;
- this.directHeading = (directBearing < 180) ? (float) directBearing : -180.0f;
+ this.initialHeading = initialBearing >= 180 ? (float)(initialBearing - 360) : (float)initialBearing;
+ // bearingTo can return +180 and inversions elsewhere simply adds 180 so return to normalised (-180 <= deg < +180)
+ this.directHeading = directBearing >= 180 ? (float)(directBearing - 360) : (float)directBearing;
int len = NODHeader.metersToRaw(arcLength);
if (len >= (1 << 22)) {
log.error("Way " + roadDef.getName() + " (id " + roadDef.getId() + ") contains an arc whose length (" + len + " units) is too big to be encoded, using length",((1 << 22) - 1));
@@ -134,11 +135,20 @@
initialHeading = ih;
}
+ public void modInitialHeading(float adjust) {
+ initialHeading += adjust;
+ if (initialHeading >= 180)
+ initialHeading -= 360;
+ else if (initialHeading < -180)
+ initialHeading += 360;
+ }
+
public float getFinalHeading() {
float fh = 0;
if (lengthInMeter != 0){
- fh = getReverseArc().getInitialHeading();
- fh = (fh <= 0) ? 180.0f + fh : -(180.0f - fh) % 180.0f;
+ fh = getReverseArc().getInitialHeading() + 180;
+ if (fh >= 180)
+ fh -= 360;
}
return fh;
}
@@ -231,9 +241,31 @@
}
public static byte directionFromDegrees(float dir) {
- return (byte) Math.round(dir * 256.0 / 360) ;
+ return (byte) Math.round(dir * 256 / 360);
}
+ /*
+ * return heading as value 0..15, where 0 is North +-11.25 degrees
+ */
+ public static int compactDirFromDegrees(float dir) {
+ return ((directionFromDegrees(dir) + 8) >> 4) & 0x0f;
+ }
+
+ /**
+ * RouteArc binary format has various space saving measures:
+ * 1/ flag on first arc to indicate compactDirs format is used for all arcs in the RouteNode.
+ * 2/ flag on subsequent arcs to indicate a change in indexA==road. Uses the same bit as above.
+ * 3/ flag isForward - the arc destination is further along the line.
+ *
+ * indexA is written for the first arc and when indexA changes.
+ * initialHeading is 'required' for a new indexA or a change in isForward.
+ * NB: addArcsToMajorRoads() adds arcs with the same indexA, initialHeading and isForward.
+ * compactDirs uses 4 bits for the initialHeading rather than 8, giving 16 possible headings
+ * rather than 256. These are grouped in pairs, with the other 4 bits are being used for the
+ * next 'required' initialHeading, independent of changes to indexA/isForward.
+ * There doesn't seem to be any detectable behaviour change in using a compactDirs pair for the
+ * forward and reverse heading for the same road.
+ */
public void write(ImgFileWriter writer, RouteArc lastArc, boolean useCompactDirs, Byte compactedDir) {
boolean first = lastArc == null;
if (first){
Index: src/uk/me/parabola/imgfmt/app/net/RouteNode.java
===================================================================
--- src/uk/me/parabola/imgfmt/app/net/RouteNode.java (revision 4586)
+++ src/uk/me/parabola/imgfmt/app/net/RouteNode.java (working copy)
@@ -74,6 +74,8 @@
private byte nodeGroup = -1;
+ private boolean useCompactDirs = false; // AngleChecker might change
+
public RouteNode(Coord coord) {
this.coord = (CoordNode) coord;
setBoundary(this.coord.getOnBoundary() || this.coord.getOnCountryBorder());
@@ -183,6 +185,20 @@
* Writes a nod1 entry.
*/
public void write(ImgFileWriter writer) {
+ boolean diagNodeArcs = false;
+ if (log.isInfoEnabled()) {
+ String areaName = null;
+ if (isClose(51.182575, -1.388928, 0.002))
+ areaName = "A303 lead off/on";
+ else if (isClose(51.012253, -1.087559, 0.0008))
+ areaName = "West Meon";
+ else if (isClose(51.064075, -1.380348, 0.0001))
+ areaName = "Woodmans";
+ if (areaName != null) {
+ diagNodeArcs = true;
+ log.info("diagNodeArcs", areaName, this, "compactDirs", useCompactDirs, "nArcs", arcs.size(), "cl", nodeClass);
+ }
+ }
if(log.isDebugEnabled())
log.debug("writing node, first pass, nod1", coord.getId());
offsetNod1 = writer.position();
@@ -201,33 +217,28 @@
}
if (!arcs.isEmpty()) {
- boolean useCompactDirs = true;
IntArrayList initialHeadings = new IntArrayList(arcs.size()+1);
RouteArc lastArc = null;
- for (RouteArc arc: arcs){
- if (lastArc == null || lastArc.getIndexA() != arc.getIndexA() || lastArc.isForward() != arc.isForward()){
- int dir = RouteArc.directionFromDegrees(arc.getInitialHeading());
- dir = (dir + 8) & 0xf0;
- if (initialHeadings.contains(dir)){
- useCompactDirs = false;
- break;
- }
- initialHeadings.add(dir);
+ if (useCompactDirs) {
+ for (RouteArc arc: arcs) {
+ if (lastArc == null || lastArc.getIndexA() != arc.getIndexA() || lastArc.isForward() != arc.isForward())
+ initialHeadings.add(RouteArc.compactDirFromDegrees(arc.getInitialHeading()));
+ lastArc = arc;
}
- lastArc = arc;
+ initialHeadings.add(0); // add dummy 0 so that we don't have to check for existence
+ lastArc = null;
}
- initialHeadings.add(0); // add dummy 0 so that we don't have to check for existence
arcs.get(arcs.size() - 1).setLast();
- lastArc = null;
-
int index = 0;
for (RouteArc arc: arcs){
Byte compactedDir = null;
if (useCompactDirs && (lastArc == null || lastArc.getIndexA() != arc.getIndexA() || lastArc.isForward() != arc.isForward())){
if (index % 2 == 0)
- compactedDir = (byte) ((initialHeadings.get(index) >> 4) | initialHeadings.getInt(index+1));
+ compactedDir = (byte) (initialHeadings.get(index) | (initialHeadings.getInt(index+1)<<4));
index++;
}
+ if (diagNodeArcs)
+ log.info(arc, arc.getIndexA(), arc.getInitialHeading(), RouteArc.compactDirFromDegrees(arc.getInitialHeading()), compactedDir, "cl", arc.getRoadDef().getRoadClass());
arc.write(writer, lastArc, useCompactDirs, compactedDir);
lastArc = arc;
}
@@ -330,7 +341,7 @@
}
public String toString() {
- return String.valueOf(coord.getId());
+ return String.valueOf(coord.getId()) + "@" + coord.toOSMURL();
}
/*
@@ -888,4 +899,24 @@
}
}
}
+
+
+ public void setUseCompactDirs(boolean newValue) {
+ useCompactDirs = newValue;
+ }
+
+ public boolean getUseCompactDirs() {
+ return useCompactDirs;
+ }
+
+ /**
+ * simple-minded quick test for enabling RouteNode diagnostic for an area of interest.
+ * leeway is in degrees
+ */
+ private boolean isClose(double latitude, double longitude, double leeway) {
+ double nodeLat = coord.getLatDegrees();
+ double nodeLon = coord.getLonDegrees();
+ return nodeLat >= latitude - leeway && nodeLat <= latitude + leeway &&
+ nodeLon >= longitude - leeway && nodeLon <= longitude + leeway;
+ }
}
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
