Hi Gerd
I've deleted the dead code and commented out the node/arc investigation
code - it isn't "hard coded tests", rather a harness of a useful
diagnostic to see what is happening with the routing structures in
geographical areas and some examples of how to use it. It was under the
control of:
uk.me.parabola.imgfmt.app.net.AngleChecker.level=INFO
Also clarified some comments about indirect arcs and their headings.
Patch attached
Ticker
On Tue, 2020-10-20 at 13:32 +0000, Gerd Petermann wrote:
> Hi Ticker,
>
> OK, let's try it. Some cleanup is needed. I see
> - hard coded tests like if (isClose(51.182575, -1.388928, 0.002))
> - dead code: getImgAngle() is not used
>
> Gerd
>
> ________________________________________
> Von: mkgmap-dev <mkgmap-dev-boun...@lists.mkgmap.org.uk> im Auftrag
> von Ticker Berkin <rwb-mkg...@jagit.co.uk>
> Gesendet: Dienstag, 20. Oktober 2020 15:21
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] Resurrect adjust-turn-headings
>
> Hi Gerd
>
> I kept the existing logic that takes all arcs within one degree and
> treats them as one (and fixed the extra case where they straddle +
> -180)
> so there should be no difference in this aspect.
>
> Ticker
>
> On Tue, 2020-10-20 at 12:48 +0000, Gerd Petermann wrote:
> > Hi Ticker,
> >
> > OK, I believe that you tested it well with the default style? Did
> > you
> > also try a style that adds multiple routable ways for one OSM way?
> > Not sure if Felix still uses this for his maps on
> > https://www.velomap.org/ but in the past this lead to all kinds of
> > special cases that do not appear with the default style.
> >
> > Gerd
> >
> > ________________________________________
> > Von: mkgmap-dev <mkgmap-dev-boun...@lists.mkgmap.org.uk> im Auftrag
> > von Ticker Berkin <rwb-mkg...@jagit.co.uk>
> > Gesendet: Dienstag, 20. Oktober 2020 14:30
> > An: Development list for mkgmap
> > Betreff: Re: [mkgmap-dev] Resurrect adjust-turn-headings
> >
> > Hi Gerd
> >
> > With sharp-angle code enabled, most junctions will get compactDirs;
> > just a few less than the existing code. Original gmapsupp.img for
> > my
> > test area was 9801728 and with this change it is 4096 bytes bigger.
> >
> > I looked at some of the NodCheck angle errors and decided that not
> > much
> > could be done as it only has the low-res road points to work with.
> >
> > In mkgmap, the algo using hi-res points gave a good angle in all
> > the
> > cases I looked at, so the code is now really there to deal with
> > real
> > sharp junctions that cause the time penalty and misleading
> > direction
> > pop-ups.
> >
> > I had a list of troublesome junctions and looked at the angles in 8
> > -bit
> > and 4-bit format before & after my changes to see that it was doing
> > as
> > expected. I also looked the leg-time info from MapSource for
> > various
> > routes. Since then I've been using it a lot for car routing and it
> > hasn't done anything that I've disagreed with.
> >
> > It seemed that you had determined that there was no benefit in
> > increasing angles so that there was more than 1 empty sector
> > between
> > vehicle arcs, so I just did the same such that it was also
> > guaranteed
> > to work if the junction went non-compact for some other reason - an
> > angle of 23 degrees, say the arcs were at -11.5 and +11.5, would
> > considered non-sharp in compact format but is sharp in 8-bit
> > format.
> >
> > Ticker
> >
> > On Tue, 2020-10-20 at 09:25 +0000, Gerd Petermann wrote:
> > > Hi Ticker,
> > >
> > > my understanding is that original Garmin maps use compact dirs a
> > > lot,
> > > so I think it is not a good idea to disable them. My problem with
> > > the
> > > patch is that NodCheck complains a lot more
> > > Steve and I are not sure how Garmin calculates the encoded
> > > angles,
> > > so
> > > we are still just guessing. Your approach might well be the best
> > > so
> > > far.
> > > The code in NodCheck has one big problem: It uses the data stored
> > > in
> > > RGN to calculate the bearings, and that means 24 bit precision.
> > > So
> > > for nearby nodes the rounding errors are too big and NodCheck
> > > uses
> > > a
> > > fallback algo which selects another point.
> > > I guess Garmin also calculates the NOD data with more than 24 bit
> > > precision, so they probably also have some kind of angle fixer.
> > > How did you test your changes? I think I used fake data that
> > > contained two alternative routes. That helped me to find the
> > > threshold values for the penalties.
> > > I also used real world OSM data to check special cases like
> > > roundabouts or *_link roads.
> > > Unfortunately it is very difficult to create unit tests for this,
> > > and
> > > the risk is high that a change improves 10 cases but worsens
> > > another
> > > 10, esp. with other styles or in other countries.
> > >
> > > Maybe there is only one way to find out. I commit your patch and
> > > we
> > > wait for comments here or in the Garmin forum...
> > >
> > > Gerd
> >
> > _______________________________________________
> > mkgmap-dev mailing list
> > mkgmap-dev@lists.mkgmap.org.uk
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > _______________________________________________
> > mkgmap-dev mailing list
> > mkgmap-dev@lists.mkgmap.org.uk
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev@lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev@lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
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,127 @@
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);
+ else
+ // AngleChecker runs before addArcsToMajorRoads so there shouldn't be any indirect arcs yet.
+ // If this changes, extra care needs to be taken check they are positioned correctly in the list
+ // of arcs or that their heading is kept consistent with changes to their direct base arc.
+ log.warn("Unexpected indirect arc", arc, "from", node);
+ }
+ 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 +282,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 +300,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);
}
}
+
+ // see what the smallest angle is now; 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
*/
@@ -384,19 +442,4 @@
return Math.round(cb) + "°";
}
- /**
- * Debugging aid: guess what angle the Garmin algorithm is using.
- * @param heading1
- * @param heading2
- * @return
- */
- private static int getImgAngle(byte heading1, byte heading2){
- int angle = heading2 - heading1;
- if (angle < 0)
- angle += 256;
- if (angle > 255)
- angle -= 256;
- return angle;
- }
-
}
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();
}
/*
@@ -680,8 +691,12 @@
* always point to a higher road than the previous arc.
* The length and direct bearing of the additional arc is measured
* from the target node of the preceding arc to the new target node.
- * The initial bearing doesn't really matter as it is not written
- * for indirect arcs.
+ *
+ * Arcs for the same road/direction must be inserted directly after the
+ * direct arc and this allows the optimisation of initial bearing not being
+ * written. Note that this routine is called after AngleChecker.fixSharpAngles
+ * so the bearings will be consistent anyway.
+ *
* @param road
*/
public void addArcsToMajorRoads(RoadDef road){
@@ -888,4 +903,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
