[Git][debian-gis-team/mkgmap][upstream] New upstream version 0.0.0+svn4922
Bas Couwenberg (@sebastic)
gitlab at salsa.debian.org
Sun Sep 1 06:28:02 BST 2024
Bas Couwenberg pushed to branch upstream at Debian GIS Project / mkgmap
Commits:
9bd8c9a7 by Bas Couwenberg at 2024-09-01T07:15:09+02:00
New upstream version 0.0.0+svn4922
- - - - -
2 changed files:
- resources/mkgmap-version.properties
- src/uk/me/parabola/imgfmt/app/net/AngleChecker.java
Changes:
=====================================
resources/mkgmap-version.properties
=====================================
@@ -1,2 +1,2 @@
-svn.version: 4921
-build.timestamp: 2024-06-10T15:46:04+0100
+svn.version: 4922
+build.timestamp: 2024-08-31T05:45:39+0100
=====================================
src/uk/me/parabola/imgfmt/app/net/AngleChecker.java
=====================================
@@ -13,13 +13,13 @@
package uk.me.parabola.imgfmt.app.net;
import java.util.ArrayList;
-import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import uk.me.parabola.log.Logger;
import uk.me.parabola.util.EnhancedProperties;
+import uk.me.parabola.mkgmap.reader.osm.FakeIdGenerator;
/**
* Find sharp angles at junctions. The Garmin routing algorithm doesn't
@@ -29,15 +29,15 @@ import uk.me.parabola.util.EnhancedProperties;
* mode it is zero, for bicycles it is rather small, for cars it is high.
* The sharp angles typically don't exist in the real world, they are
* caused by the simplifications done by mappers.
- *
- * Maps created for cyclists typically "abuse" the car routing for racing
+ *
+ * Maps created for cyclists typically "abuse" the car routing for racing
* bikes, but in this scenario the time penalties are much too high,
* and detours are likely.
- *
- * This method tries to modify the initial heading values of the arcs
+ *
+ * This method tries to modify the initial heading values of the arcs
* which are used to calculate the angles. Where possible, the values are
- * changed so that angles appear larger.
- *
+ * changed so that angles appear larger.
+ *
* @author Gerd Petermann
*
* Somehow these penalties are also applied to "shortest" routing,
@@ -55,6 +55,13 @@ import uk.me.parabola.util.EnhancedProperties;
*
* Ticker Berkin
*
+ * This code has two other functions:
+ *
+ * When increasing a sharp angle, try to trigger better turn-instructions by the
+ * choice of which arcs to adjust.
+ *
+ * Use compactDir format (4bits) rather than 8bits for initial heading representaton
+ * when this will give a space saving and not compromise the turn-instructions.
*/
public class AngleChecker {
private static final Logger log = Logger.getLogger(AngleChecker.class);
@@ -68,8 +75,9 @@ public class AngleChecker {
// 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)
-
+ private static final float MIN_ANGLE = 23f; // don't reduce angles to less than this (1 sector + bit)
+ private static final float STRAIGHT_EPSILON = 3f; // for angle.straightEnough()
+
// helper class to collect multiple arcs with (nearly) the same initial headings
private class ArcGroup {
float initialHeading;
@@ -78,9 +86,8 @@ public class AngleChecker {
int maxRoadSpeed;
int maxRoadClass;
byte orAccessMask;
- HashSet<RoadDef> roadDefs = new HashSet<>();
-
List<RouteArc> arcs = new ArrayList<>();
+
public void addArc(RouteArc arc) {
arcs.add(arc);
if (arc.getRoadDef().isOneway())
@@ -92,27 +99,50 @@ public class AngleChecker {
if (arc.getRoadDef().getRoadClass() > maxRoadClass)
maxRoadClass = arc.getRoadDef().getRoadClass();
orAccessMask |= arc.getRoadDef().getAccess();
- roadDefs.add(arc.getRoadDef());
}
public float getInitialHeading() {
return initialHeading;
}
-
+
public boolean isOneway() {
+ // ??? ignore for pedestrian only group members
return isOneWayTrueCount == arcs.size();
}
-
+
public boolean isForward() {
return isForwardTrueCount == arcs.size();
}
-
+
+ public boolean sameWay(ArcGroup other) {
+ for (RouteArc thisArc : arcs)
+ for (RouteArc otherArc : other.arcs) {
+ // same roadDefs have same wayIds. WayIds are unique, so this is OK
+ if (thisArc.getRoadDef() == otherArc.getRoadDef())
+ return true;
+ }
+ return false;
+ }
+
+ public boolean sameName(ArcGroup other) {
+ for (RouteArc thisArc : arcs) {
+ String thisName = thisArc.getRoadDef().getName();
+ // RoadDefs also have 4 labels, but not bothering to check them
+ if (thisName != null)
+ for (RouteArc otherArc : other.arcs)
+ if (thisName.equals(otherArc.getRoadDef().getName()))
+ return true;
+ }
+ return false;
+ }
+
public void modInitialHeading(float modIH) {
initialHeading += modIH;
if (initialHeading >= 180)
initialHeading -= 360;
else if (initialHeading < -180)
initialHeading += 360;
+ log.info("modInitialHeading arc from", arcs.get(0).getInitialHeading(), "by", modIH, "to", initialHeading);
for (RouteArc arc : arcs) {
arc.modInitialHeading(modIH);
@@ -123,7 +153,7 @@ public class AngleChecker {
return arcs.get(0).toString();
}
}
-
+
public void config(EnhancedProperties props) {
// undocumented option - usually used for debugging only
ignoreSharpAngles = props.getProperty("ignore-sharp-angles", false);
@@ -132,10 +162,28 @@ public class AngleChecker {
public void check(Map<Integer, RouteNode> nodes) {
if (!ignoreSharpAngles){
- byte sharpAnglesCheckMask = cycleMap ? (byte) (0xff & ~AccessTagsAndBits.FOOT) : AccessTagsAndBits.BIKE;
+/*
+I don't understand the original setting and logic for sharpAnglesCheckMask.
+
+If it is a cycle-map, sharpAnglesCheckMask is set to all but ACCESS...FOOT,
+so that, if the common access of the arcs is FOOT only, the sharp angle won't
+be increased as if for vehicles, but there is logic to do this anyway.
+If not a cycle-map, it was set to ACCESS...BIKE,
+so that, if BIKE access isn't common to both arcs, the sharp angle won't
+be increased, so motor vehicles, allowed to turn here, might suffer
+a time penalty.
+
+I've left the cycle-map value untouched but changed the other value so that
+angle expansion is handled as normal
+
+Ticker Berkin 23-Aug-2024
+
+ byte sharpAnglesCheckMask = cycleMap ? (byte) (0xff & ~AccessTagsAndBits.FOOT) : AccessTagsAndBits.BIKE;
+*/
+ byte sharpAnglesCheckMask = cycleMap ? (byte) (0xff & ~AccessTagsAndBits.FOOT) : (byte) 0xff;
for (RouteNode node : nodes.values()){
- fixSharpAngles(node, sharpAnglesCheckMask);
+ fixSharpAngles(node, sharpAnglesCheckMask);
}
}
}
@@ -145,6 +193,8 @@ public class AngleChecker {
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;
+ // RouteNode default is setUseCompactDirs(false);
+ node.setUseCompactDirs(true); // assume algo will do enough to make this OK
if (arcs.size() == 2) { // common case where two roads join but isn't a junction
doSimpleJoin(node, arcs);
return;
@@ -165,7 +215,7 @@ public class AngleChecker {
}
if (directArcs.size() <= 1)
return; // should not happen
-
+
// sort the arcs by initial heading
directArcs.sort((ra1,ra2) -> {
int d = Float.compare(ra1.getInitialHeading(), ra2.getInitialHeading());
@@ -183,7 +233,7 @@ public class AngleChecker {
Iterator<RouteArc> iter = directArcs.listIterator();
RouteArc arc1 = iter.next();
boolean addArc1 = false;
- float minAngle = 180;
+ float smallestAngle = 180;
while (iter.hasNext() || addArc1) {
ArcGroup ag = new ArcGroup();
ag.initialHeading = arc1.getInitialHeading();
@@ -198,8 +248,8 @@ public class AngleChecker {
log.warn("sharp angle < 1° at", node.getCoord(), ",maybe duplicated OSM way with bearing", getCompassBearing(arc1.getInitialHeading()));
ag.addArc(arc2);
} else {
- if (angleBetween < minAngle)
- minAngle = angleBetween;
+ if (angleBetween < smallestAngle)
+ smallestAngle = angleBetween;
arc1 = arc2;
if (!iter.hasNext())
addArc1 = true;
@@ -207,38 +257,72 @@ public class AngleChecker {
}
}
}
-
- 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;
+ int lastInx = arcGroups.size()-1;
+ if (lastInx > 0) {
+ float angleBetween = arcGroups.get(0).initialHeading - arcGroups.get(lastInx).initialHeading + 360;
+ if (angleBetween < 1) {
+ for (RouteArc arc : arcGroups.get(lastInx).arcs)
+ arcGroups.get(0).addArc(arc);
+ arcGroups.remove(lastInx);
+ } else if (angleBetween < smallestAngle) {
+ smallestAngle = angleBetween;
+ }
}
-
- if (minAngle >= SHARP_DEGREES) {
- if (minAngle >= COMPACT_DIR_DEGREES)
- // RouteNode default is setUseCompactDirs(false);
- node.setUseCompactDirs(true);
+
+ if (smallestAngle >= SHARP_DEGREES && arcGroups.size() == arcs.size()) // show diags if real groups
return;
+
+ if (log.isInfoEnabled()) {
+ log.info("fixSharpAngles at", node.getCoord(),
+ "mask", String.format("0x%02x", sharpAnglesCheckMask),
+ "nArcs", arcs.size(),
+// "nDirectArcs", directArcs.size(), // already warned
+ arcGroups.size() < arcs.size() ? "nGroups " + arcGroups.size() : "",
+ "smallestAngle", smallestAngle);
+ float lastHeading = directArcs.get(directArcs.size()-1).getInitialHeading() - 360;
+ for (RouteArc arc : directArcs) {
+ RoadDef rd = arc.getRoadDef();
+ log.info("Arc", /*arc,*/
+ "heading", arc.getInitialHeading(), getCompassBearing(arc.getInitialHeading()),
+ "angToPrev", arc.getInitialHeading() - lastHeading,
+ "class", rd.getRoadClass(),
+ "speed", rd.getRoadSpeed(),
+// "rdDef", System.identityHashCode(rd),
+ "way", rd.getId(), "isFake", FakeIdGenerator.isFakeId(rd.getId()),
+ "name", rd.getName(),
+ "access", String.format("0x%02x", rd.getAccess()),
+ "oneway", rd.isOneway(),
+ "forward", arc.isForward(),
+ "paved", rd.paved()
+ );
+ lastHeading = arc.getInitialHeading();
+ }
}
+ if (arcGroups.size() == 1) { // 1 set of close but possibly different headings, use 8bit dirs
+ node.setUseCompactDirs(false);
+ return;
+ } else if (smallestAngle >= SHARP_DEGREES)
+ 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
+ // but, because no-access angles are widend (if possible) to 23 degrees, there should
+ // be 46 degrees between the two roads either side
class AngleAttr {
float angle;
float minAngle;
+
+ private boolean straightEnough() {
+ return angle > 180-STRAIGHT_EPSILON && angle < 180+STRAIGHT_EPSILON;
+ }
+
}
+ boolean someNeedIncrease = false;
AngleAttr[] angles = new AngleAttr[n];
for (int i = 0; i < n; i++){
ArcGroup ag1 = arcGroups.get(i);
@@ -248,26 +332,12 @@ public class AngleChecker {
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() && 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
-
- aa.minAngle = SHARP_DEGREES;
// int sumSpeeds = ag1.maxRoadSpeed + ag2.maxRoadSpeed;
- // the Garmin algorithm sees rounded values, so the thresholds are probably
+ // the Garmin algorithm sees rounded values, so the thresholds are probably
// near 22.5 (0x10), 45(0x20), 67.5 (0x30), 90, 112.5 (0x40)
- // the following code doesn't seem to improve anything, I leave it as comment
+ // the following code doesn't seem to improve anything, I leave it as comment
// for further experiments.
// if (cycleMap){
// if (sumSpeeds >= 14)
@@ -285,31 +355,62 @@ public class AngleChecker {
// }
// With changes to switch compactDirs and working in degrees rather than masked sectors,
// the above variables are wrong, but the idea holds
-
- if (aa.angle >= aa.minAngle)
- continue;
-
- String ignoredReason = null;
- if ((pathAccessMask & sharpAnglesCheckMask) == 0)
- ignoredReason = "because it can not be used by bike";
- 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)){
- ignoredReason = "because both arcs belong to the same road";
- }
- if (ignoredReason != null){
- if (log.isInfoEnabled()){
- log.info("sharp angle", aa.angle, "° at", node.getCoord(),
- "headings", getCompassBearing(ag1.getInitialHeading()), getCompassBearing(ag2.getInitialHeading()),
- "speeds", ag1.maxRoadSpeed, ag2.maxRoadSpeed);
- log.info("ignoring", ignoredReason);
+
+ aa.minAngle = MIN_ANGLE;
+ String minimalReason = null;
+ byte pathAccessMask = (byte) (ag1.orAccessMask & ag2.orAccessMask);
+ if (pathAccessMask == 0)
+ minimalReason = "no common vehicle allowed on both arcs";
+ else if (pathAccessMask == AccessTagsAndBits.FOOT)
+ minimalReason = "only pedestrians - sharp angle not a problem";
+ else if ((pathAccessMask & sharpAnglesCheckMask) == 0) // see comment in check(...) above
+ minimalReason = "because it can not be used by bike";
+ else if (Math.min(ag1.maxRoadSpeed, ag2.maxRoadSpeed) == 0)
+ minimalReason = "eg service/parking where sharp angle probably indicates shouldn't turn here";
+ else if (ag1.isOneway() && ag2.isOneway()) {
+ if (!ag1.isForward() && !ag2.isForward()) {
+ minimalReason = "two one-ways merge";
+ if (aa.angle < MIN_ANGLE)
+ aa.minAngle = aa.angle; // don't expand. compactDir format no problem
+ } else if (ag1.isForward() && ag2.isForward()) {
+ minimalReason = "two one-ways split";
+ if (aa.angle < MIN_ANGLE && n == 3 && ag1.maxRoadClass == ag2.maxRoadClass && ag1.sameName(ag2)) {
+ // maybe this is a major road split and don't want to encourage a turn-instruction
+ ArcGroup ag3 = arcGroups.get(i+2 < n ? i+2 : i+2-n);
+ if (ag3.isOneway() && ag3.maxRoadClass == ag1.maxRoadClass) {
+ minimalReason = "major road split";
+ aa.minAngle = aa.angle; // don't expand
+ node.setUseCompactDirs(false); // use 8bit dirs
+ }
+ }
+ } /* else if (n == 3) {
+ // both arcs are one-ways in opposite directions (ie continuous)
+ // could check that the one-way directions correspond to the driving side
+ minimalReason = "because it seems to be a flare road";
+ // it could also be a sharp turn, so best to let it expand. Flare angles
+ // are typically 30-45 degrees so expanding to SHARP_DEGREES won't be significant
+ } */
+ } /* else if (ag1.sameWay(ag2)) {
+ // I don't think this is a good reason to ignore the sharp angle
+ // however all the cases I've found are where there is a flair road with
+ // an extra track that stops the above test working
+ minimalReason = "because both arcs belong to the same road";
+ } */
+ if (minimalReason != null) {
+ if (log.isInfoEnabled()) {
+ log.info(aa.angle < aa.minAngle ? "minAngleSharp" : "minAngleOK", aa.angle,
+ "minAngle", aa.minAngle,
+ "reason", minimalReason);
}
- aa.minAngle = saveMinAngle; // restore as don't want to widen
- }
+ } else
+ aa.minAngle = SHARP_DEGREES;
+ if (aa.angle < aa.minAngle)
+ someNeedIncrease = true;
}
-
+
+ if (!someNeedIncrease)
+ return;
+
// 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];
@@ -319,12 +420,6 @@ public class AngleChecker {
float oldAngle = aa.angle;
ArcGroup ag1 = arcGroups.get(i);
ArcGroup ag2 = arcGroups.get(i+1 < n ? i+1 : 0);
- if (log.isInfoEnabled()){
- log.info("sharp angle", aa.angle, "° at", node.getCoord(),
- "headings", getCompassBearing(ag1.getInitialHeading()), getCompassBearing(ag2.getInitialHeading()),
- "speeds", ag1.maxRoadSpeed, ag2.maxRoadSpeed,
- "classes",ag1.maxRoadClass, ag2.maxRoadClass);
- }
// XXX restrictions ?
AngleAttr predAA = angles[i == 0 ? n - 1 : i - 1];
@@ -335,21 +430,73 @@ public class AngleChecker {
float deltaPred = predAA.angle - predAA.minAngle;
float deltaNext = nextAA.angle - nextAA.minAngle;
+ if (log.isInfoEnabled()) {
+ log.info("Angle", aa.angle,
+ "between", ag1.getInitialHeading(),
+ "and", ag2.getInitialHeading(),
+ "minAngle", aa.minAngle,
+ "wantedInc", wantedIncrement,
+ "deltaPred", deltaPred,
+ "deltaNext", deltaNext);
+ }
+
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
+ ArcGroup ag0 = null;
+ ArcGroup ag3 = null;
+ int chooseWhich = 0; // -ve to take from prev, +ve take from next
+ // To influence possible turn-instructions look at the information
+ // easily available to prefer altering one arc instead of both.
+ // If both are altered this can make turn-instructions even more likely
+ // to be wrong because the adjustment is in proportion to the space
+ // available.
+ // The order of {road_class, sameWay, straightness, roadName, road_speed}
+ // clauses can adjusted for priority.
+ // Hoping sameWay before road_class fixes more problems than it might cause
+
+ if (chooseWhich == 0) {
+ // if the two arcs either side of the sharp angle belong to the same
+ // way then change the arc on the other side
+ ag0 = arcGroups.get(i > 0 ? i-1 : n-1);
+ ag3 = n == 3 ? ag0 : arcGroups.get(i+2 < n ? i+2 : i+2-n);
+ if (ag2.sameWay(ag3))
+ chooseWhich = -1;
+ else if (ag1.sameWay(ag0))
+ chooseWhich = +1;
+ }
+ if (chooseWhich == 0)
+ // adjust the lower class road
+ chooseWhich = ag1.maxRoadClass - ag2.maxRoadClass;
+ if (chooseWhich == 0) {
+ // where there is a straight road with a sharp turn-off then just adjust the turn-off
+ if (nextAA.straightEnough())
+ chooseWhich = -1;
+ else if (predAA.straightEnough())
+ chooseWhich = +1;
+ }
+ if (chooseWhich == 0) {
+ // NB set ag0 & 3 if move this before sameWay()
+ // Way might have changed but could still be the same road by name or ref
+ // This is best after straightEnough.
+ if (ag2.sameName(ag3))
+ chooseWhich = -1;
+ else if (ag1.sameName(ag0))
+ chooseWhich = +1;
+ }
+ if (chooseWhich == 0)
+ // adjust the slower road
+ chooseWhich = ag1.maxRoadSpeed - ag2.maxRoadSpeed;
+
+ if (chooseWhich == 0 ) { // 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
+ } else if (chooseWhich > 0) { // 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
+ } else { // take as much as possible from pred
if (deltaPred >= wantedIncrement) {
deltaPred = wantedIncrement;
deltaNext = 0;
@@ -379,8 +526,9 @@ public class AngleChecker {
predAA.angle -= deltaPred;
wantedIncrement -= deltaPred;
}
-
+
if (wantedIncrement > 0) {
+ node.setUseCompactDirs(false); // angle might be wide enough in 8bit dirs
if (aa.angle == oldAngle)
log.info("don't know how to fix it", wantedIncrement);
else
@@ -388,14 +536,6 @@ public class AngleChecker {
}
}
- // 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);
}
@@ -431,7 +571,6 @@ public class AngleChecker {
arc1.modInitialHeading(+extra/2);
arc2.modInitialHeading(-extra/2);
}
- node.setUseCompactDirs(true); // this won't cause any problems
}
View it on GitLab: https://salsa.debian.org/debian-gis-team/mkgmap/-/commit/9bd8c9a75b3e30821e7393f835af6ecd97aae42b
--
View it on GitLab: https://salsa.debian.org/debian-gis-team/mkgmap/-/commit/9bd8c9a75b3e30821e7393f835af6ecd97aae42b
You're receiving this email because of your account on salsa.debian.org.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://alioth-lists.debian.net/pipermail/pkg-grass-devel/attachments/20240901/0d74a5ab/attachment-0001.htm>
More information about the Pkg-grass-devel
mailing list