Attached is another patch that reverses roads in the RoadMerger if
applicable.
I have checked the patch by adding debug statements to the
RestrictionRelation.addRestriction(..) method. There are some
differences but as far as I could see the differences are only in some
coords. I have checked some and all were caused by road merges.
Example:
3---2---
\
4--------1---5
When having a only_straightforward restriction from 4 via 1 to 5 point 2
is added to the restriction without merging. When merging the road 1-2
and 2-3 node 2 is no longer a routing node and therefor point 3 is added
to the restriction instead of point 2.
@Gerd: can you please check again if your tests still show any problem?
Thanks!
WanMil
Hi Gerd,
I've found two problems but have no time today to fix it. Will post a
patch within the next days.
Thanks a lot for testing!!
WanMil
Hi Gerd,
I will check that.
WanMil
Hi WanMil,
the patch has an influence on the number of turn restrictions.
For a tile in northern Germany GPSMapEdit shows :
r2946 with --x-no-mergeroads: 264 (valid) turn restirictions, 22 invalid
r2946 with activated mergeroads : 264 (valid) turn restirictions, 22
invalid
r2946 with patch and --x-no-mergeroads: 264 (valid) turn restirictions,
22 invalid
r2946 with patch and activated mergeroads : *223* (valid) turn
restirictions, *25 *invalid
(The invalid turn restrictions are listed in the log. Those are the ones
that prohibit
to drive into the wrong end of a oneway road, but GPSMapEdit doesn't
care when
the turn restriction also forbids to walk into the road)
Do you think that this could be okay?
Gerd
Date: Wed, 8 Jan 2014 22:55:43 +0100
From: [email protected]
To: [email protected]
Subject: [mkgmap-dev] [PATCH] RoadMerger reverses roads
Attached patch improves the RoadMerger so that roads are reversed when
it is required to be merged with another road.
A small test increased the mergerate by 2% (avg. 17% => 19% road network
reduction).
Please check it. The p-road check is not yet implemented.
There are also some performance improvements possible which I will post
with the next patch version.
Unit tests may fail.
WanMil
Hi Gerd,
Hi WanMil,
two points:
1) line 517 is obsolete:
mergePoints.add(end);
It just blows up the size of the list and processing time.
Yep.
I've found another important thing: the road merger can merge many more
ways when it reverses non oneway ways. This should be no problem so
let's do it :-)
I will post another patch.
_______________________________________________ mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Index: src/uk/me/parabola/mkgmap/osmstyle/RoadMerger.java
===================================================================
--- src/uk/me/parabola/mkgmap/osmstyle/RoadMerger.java (revision 2954)
+++ src/uk/me/parabola/mkgmap/osmstyle/RoadMerger.java (working copy)
@@ -15,10 +15,10 @@
import java.util.ArrayList;
import java.util.Collections;
-import java.util.Comparator;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.List;
+import java.util.ListIterator;
import java.util.Map;
import java.util.Set;
@@ -31,6 +31,7 @@
import uk.me.parabola.mkgmap.reader.osm.Relation;
import uk.me.parabola.mkgmap.reader.osm.RestrictionRelation;
import uk.me.parabola.mkgmap.reader.osm.Way;
+import uk.me.parabola.util.MultiHashMap;
import uk.me.parabola.util.MultiIdentityHashMap;
/**
@@ -44,15 +45,11 @@
private static final double MAX_MERGE_ANGLE = 130d;
- /** maps which coord of a way(id) are restricted - they should not be merged */
- private final MultiIdentityHashMap<Coord, Long> restrictions;
/** Contains a list of all roads (GType + Way) */
private final List<Road> roads;
- /** maps the start point of a road to its road definition */
- private final MultiIdentityHashMap<Coord, Road> startPoints = new MultiIdentityHashMap<Coord, Road>();
- /** maps the end point of a road to its road definition */
- private final MultiIdentityHashMap<Coord, Road> endPoints = new MultiIdentityHashMap<Coord, Road>();
+ /** maps the two end points of a road to its road definition */
+ private final MultiIdentityHashMap<Coord, Road> roadEndPoints = new MultiIdentityHashMap<Coord, Road>();
/**
* Helper class to keep the Way and the GType object of a road.
@@ -61,11 +58,13 @@
*
* @author WanMil
*/
- private static class Road {
+ private static class Road implements Comparable<Road> {
/** gives the index of the original position in the way/road list */
private final int index;
private final Way way;
private final GType gtype;
+ private boolean firstPointRestricted;
+ private boolean lastPointRestricted;
/**
* For these tags two ways need to return the same value for {@link Way#isNotBoolTag(String)}
@@ -123,9 +122,39 @@
this.index = index;
this.way = way;
this.gtype = gtype;
+ this.firstPointRestricted = false;
+ this.lastPointRestricted = false;
+ }
+
+ /**
+ * Helper method to receive the first point of the road.
+ * @return first point of road
+ */
+ public Coord getFirstPoint() {
+ return getWay().getPoints().get(0);
+ }
+
+ /**
+ * Helper method to receive the last point of the road.
+ * @return last point of road
+ */
+ public Coord getLastPoint() {
+ return getWay().getPoints().get(getWay().getPoints().size()-1);
}
/**
+ * Reverses the road.
+ */
+ public void reverse() {
+ log.debug("Reverse road",getWay().getId());
+ getWay().reverse();
+ boolean restrSave = firstPointRestricted;
+ firstPointRestricted = lastPointRestricted;
+ lastPointRestricted = restrSave;
+ }
+
+
+ /**
* Checks if the given {@code otherRoad} can be merged with this road at
* the given {@code mergePoint}.
* @param mergePoint the coord where this road and otherRoad might be merged
@@ -133,45 +162,136 @@
* @return {@code true} this road can be merged with {@code otherRoad};
* {@code false} the roads cannot be merged at {@code mergePoint}
*/
- public boolean isMergable(Coord mergePoint, Road otherRoad) {
- // first check if this road starts or stops at the mergePoint
- Coord cStart = way.getPoints().get(0);
- Coord cEnd = way.getPoints().get(way.getPoints().size() - 1);
- if (cStart != mergePoint && cEnd != mergePoint) {
- // it doesn't => roads not mergeable at mergePoint
- return false;
+ public MergeClassification getMergeClassification(Coord mergePoint, Road otherRoad) {
+
+ // the other road must not have any restriction
+ if (otherRoad.isFirstPointRestricted() || otherRoad.isLastPointRestricted()) {
+ log.debug("Do not merge",way.getId(),"and",otherRoad.getWay().getId(),"- way 2 has restriction on first or last point");
+ return null;
}
- // do the same check for the otherRoad
- Coord cOtherStart = otherRoad.getWay().getPoints().get(0);
- Coord cOtherEnd = otherRoad.getWay().getPoints()
- .get(otherRoad.getWay().getPoints().size() - 1);
- if (cOtherStart != mergePoint && cOtherEnd != mergePoint) {
- // otherRoad does not start or stop at mergePoint =>
- // roads not mergeable at mergePoint
- return false;
+ // check if the GType objects are the same
+ // this is an easy check which often fails so do it on the first place
+ if (isGTypeMergable(otherRoad.getGtype()) == false) {
+ log.debug("Do not merge",way.getId(),"and",otherRoad.way.getId(),"- different gtype");
+ return null;
+ }
+
+ // check first/last points and restrictions
+ Coord cFirst = getFirstPoint();
+ Coord cLast = getLastPoint();
+ Coord cOtherFirst = otherRoad.getFirstPoint();
+ Coord cOtherLast = otherRoad.getLastPoint();
+
+ boolean reverseRoad1 = false;
+ boolean reverseRoad2 = false;
+ if (getWay().isBoolTag("oneway")) {
+ if (otherRoad.getWay().isBoolTag("oneway") == false) {
+ log.debug("Do not merge",way.getId(),"and",otherRoad.getWay().getId(),"- different oneway");
+ return null;
+ }
+ if (cLast != mergePoint) {
+ log.debug("Do not merge",way.getId(),"and",otherRoad.getWay().getId(),"- way 1 does not end at the merge point");
+ return null;
+ }
+ if (cOtherFirst != mergePoint) {
+ log.debug("Do not merge",way.getId(),"and",otherRoad.getWay().getId(),"- way 2 does not start at the merge point");
+ return null;
+ }
+ if (isLastPointRestricted()) {
+ log.debug("Do not merge",way.getId(),"and",otherRoad.getWay().getId(),"- way 1 has restriction on merge point");
+ return null;
+ }
+ } else if (otherRoad.getWay().isBoolTag("oneway")) {
+ log.debug("Do not merge",way.getId(),"and",otherRoad.getWay().getId(),"- different oneway");
+ return null;
+ } else {
+ // both roads are not oneway
+
+ // first check if this road starts or stops at the mergePoint
+ // use an assertion only because this should be checked before calling this method
+ assert cFirst == mergePoint || cLast == mergePoint;
+
+ // check if roads need to be reversed and if this conflicts with restrictions
+ if (cLast == mergePoint) {
+ // this road does not need to be reversed
+ if (isLastPointRestricted()) {
+ log.debug("Do not merge",way.getId(),"and",otherRoad.getWay().getId(),"- way 1 has restriction on merge point");
+ return null;
+ }
+ } else {
+ reverseRoad1 = true;
+ if (isFirstPointRestricted()) {
+ log.debug("Do not merge",way.getId(),"and",otherRoad.getWay().getId(),"- way 1 has restriction on merge point");
+ return null;
+ }
+ }
+
+ assert cOtherFirst == mergePoint || cOtherLast == mergePoint;
+ reverseRoad2 = (cOtherLast == mergePoint);
+ if (reverseRoad1 && reverseRoad2) {
+ // do not merge them
+ // when both ways need to be reversed they should be merged exchanged
+ log.debug("Do not merge",way.getId(),"and",otherRoad.getWay().getId(),"- both ways need to be reversed");
+ return null;
+ }
}
// check if merging would create a closed way - which should not
// be done (why? WanMil)
- if (cStart == cOtherEnd) {
- return false;
- }
-
- // check if the GType objects are the same
- if (isGTypeMergable(otherRoad.getGtype()) == false) {
- return false;
+ if ((cFirst == cOtherLast && cFirst != mergePoint) || (cLast == cOtherFirst && cLast != mergePoint)) {
+ log.debug("Do not merge",way.getId(),"and",otherRoad.way.getId(),"- closed way");
+ return null;
}
// checks if the tag values of both ways match so that the ways
// can be merged
- if (isWayMergable(mergePoint, otherRoad.getWay()) == false) {
- return false;
+ if (isWayTaggingMergable(mergePoint, otherRoad.getWay()) == false) {
+ return null;
}
- return true;
+ // Check the angle of the two ways
+ double angle = getAngle(mergePoint, getWay(), reverseRoad1, otherRoad.getWay(), reverseRoad2);
+ if (angle > MAX_MERGE_ANGLE) {
+ // The angle exceeds the limit => do not merge
+ // Don't know if this is really required or not.
+ // But the number of merges which do not succeed due to this
+ // restriction is quite low and there have been requests
+ // for this: http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2013q3/018649.html
+
+ log.debug("Do not merge ways",getWay().getId(),"and",otherRoad.getWay().getId(),"- they span a too big angle",angle,"°");
+ return null;
+ }
+
+ // the roads are mergeable
+ log.debug("Road",getWay().getId(),"and road",otherRoad.getWay().getId(),"are mergeable with angle",angle);
+ // create the merge classification
+ MergeClassification mc = new MergeClassification();
+ mc.road1 = this;
+ mc.road1Reversed = reverseRoad1;
+ mc.road2 = otherRoad;
+ mc.road2Reversed = reverseRoad2;
+ mc.angle = angle;
+ return mc;
}
+ private double getAngle(Coord mergePoint, Way way1, boolean reverse1, Way way2, boolean reverse2) {
+ // calculate the angle between them
+ Coord c1 = null;
+ if (reverse1) {
+ c1= way1.getPoints().get(1);
+ } else {
+ c1= way1.getPoints().get(way1.getPoints().size()-2);
+ }
+ Coord c2 = null;
+ if (reverse2) {
+ c2= way2.getPoints().get(way2.getPoints().size()-2);
+ } else {
+ c2= way2.getPoints().get(1);
+ }
+ return Math.abs(Utils.getAngle(c1, mergePoint, c2));
+ }
+
/**
* Checks if the given GType can be merged with the GType of this road.
* @param otherGType the GType of the other road
@@ -224,40 +344,9 @@
* @return {@code true} tag values match so that both roads might be merged;
* {@code false} tag values differ so that road must not be merged
*/
- private boolean isWayMergable(Coord mergePoint, Way otherWay) {
-
- // oneway must not only be checked for equal tag values
- // but also for correct direction of both ways
-
- // first map the different oneway values
- String thisOneway = getWay().getTag("oneway");
- // map oneway value for the other way
- String otherOneway = otherWay.getTag("oneway");
+ private boolean isWayTaggingMergable(Coord mergePoint, Way otherWay) {
- if (stringEquals(thisOneway, otherOneway) == false) {
- // the oneway tags differ => cannot merge
- // (It might be possible to reverse the direction of one way
- // but this might be implemented later)
- log.debug("oneway does not match", way.getId(), "("
- + thisOneway + ")", otherWay.getId(), "(" + otherOneway
- + ")");
- return false;
-
- } else if ("yes".equals(thisOneway)) {
- // the oneway tags match and both ways are oneway
- // now check if both ways have the same direction
-
- boolean thisStart = (getWay().getPoints().get(0) == mergePoint);
- boolean otherStart = (otherWay.getPoints().get(0) == mergePoint);
-
- if (thisStart == otherStart) {
- // both ways are oneway but they have a different direction
- log.warn("oneway with different direction", way.getId(),
- otherWay.getId());
- return false;
- }
- }
- // oneway matches
+ // oneway tagging is already checked
// now check the other tag lists
@@ -299,33 +388,6 @@
}
}
- // Check the angle of the two ways
- Coord c1;
- if (getWay().getPoints().get(0) == mergePoint) {
- c1 = getWay().getPoints().get(1);
- } else {
- c1 = getWay().getPoints().get(getWay().getPoints().size() - 2);
- }
- Coord cOther;
- if (otherWay.getPoints().get(0) == mergePoint) {
- cOther = otherWay.getPoints().get(1);
- } else {
- cOther = otherWay.getPoints().get(
- otherWay.getPoints().size() - 2);
- }
-
- double angle = Math.abs(Utils.getAngle(c1, mergePoint, cOther));
- if (angle > MAX_MERGE_ANGLE) {
- // The angle exceeds the limit => do not merge
- // Don't know if this is really required or not.
- // But the number of merges which do not succeed due to this
- // restriction is quite low and there have been requests
- // for this: http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2013q3/018649.html
-
- log.info("Do not merge ways",getWay().getId(),"and",otherWay.getId(),"because they span a too big angle",angle,"°");
- return false;
- }
-
return true;
}
@@ -358,6 +420,34 @@
public final int getIndex() {
return index;
}
+
+ public int compareTo(Road otherRoad) {
+ return Integer.compare(index, otherRoad.index);
+ }
+
+ public void setRestriction(Coord restrictedPoint) {
+ if (restrictedPoint == getFirstPoint())
+ firstPointRestricted = true;
+
+ if (restrictedPoint == getLastPoint())
+ lastPointRestricted = true;
+ }
+
+ /**
+ * Checks if the first point of the road is part of a restriction.
+ * @return {@code true} first point is part of a restriction; {@code false} else
+ */
+ public final boolean isFirstPointRestricted() {
+ return firstPointRestricted;
+ }
+
+ /**
+ * Checks if the last point of the road is part of a restriction.
+ * @return {@code true} last point is part of a restriction; {@code false} else
+ */
+ public final boolean isLastPointRestricted() {
+ return lastPointRestricted;
+ }
}
public RoadMerger(List<Way> ways, List<GType> gtypes,
@@ -365,35 +455,68 @@
List<Relation> throughRouteRelations) {
assert ways.size() == gtypes.size();
+ // create an internal list with all roads
this.roads = new ArrayList<Road>(ways.size());
+ // internal helper structure to easier assign restrictions
+ MultiHashMap<Long, Road> roadByWayId = new MultiHashMap<>();
+
+ int roadIndex = 0;
for (int i = 0; i < ways.size(); i++) {
- if (ways.get(i) != null)
- roads.add(new Road(i, ways.get(i), gtypes.get(i)));
+ if (ways.get(i) != null) {
+ Road road = new Road(roadIndex++, ways.get(i), gtypes.get(i));
+ roads.add(road);
+ roadByWayId.add(road.getWay().getId(), road);
+ }
}
- this.restrictions = new MultiIdentityHashMap<Coord, Long>();
- workoutRestrictionRelations(restrictions);
- workoutThroughRoutes(throughRouteRelations);
+ workoutRestrictionRelations(restrictions, roadByWayId);
+ workoutThroughRoutes(throughRouteRelations, roadByWayId);
}
- private void workoutRestrictionRelations(Map<Coord, List<RestrictionRelation>> restrictionRels) {
+ /**
+ * Workout the restriction relations and flag the points in the roads that are restricted.
+ * @param restrictionRels the restrictions
+ * @param roadByWayId all roads
+ */
+ private void workoutRestrictionRelations(Map<Coord, List<RestrictionRelation>> restrictionRels,
+ MultiHashMap<Long, Road> roadByWayId) {
+ if (restrictionRels.isEmpty()) {
+ return;
+ }
for (List<RestrictionRelation> rels : restrictionRels.values()) {
for (RestrictionRelation rel : rels) {
- if (rel.getViaCoord() == null) {
+ Coord viaCoord = rel.getViaCoord();
+
+ if (viaCoord == null) {
continue;
}
+
if (rel.getFromWay() != null) {
- restrictions.add(rel.getViaCoord(), rel.getFromWay().getId());
+ List<Road> roads = roadByWayId.get(rel.getFromWay().getId());
+ for (Road road : roads) {
+ road.setRestriction(viaCoord);
+ log.debug("Relation",rel.getId(),"marks road",road.getWay().getId(),"with restriction");
+ }
}
if (rel.getToWay() != null) {
- restrictions.add(rel.getViaCoord(), rel.getToWay().getId());
+ List<Road> roads = roadByWayId.get(rel.getToWay().getId());
+ for (Road road : roads) {
+ road.setRestriction(viaCoord);
+ log.debug("Relation",rel.getId(),"marks road",road.getWay().getId(),"with restriction");
+ }
}
}
}
}
- private void workoutThroughRoutes(List<Relation> throughRouteRelations) {
+ /**
+ * Workout the through route relations and flag the points in the roads that are restricted by them.
+ * @param throughRouteRelations the through route relations
+ * @param roadByWayId all roads
+ */
+ private void workoutThroughRoutes(List<Relation> throughRouteRelations,
+ MultiHashMap<Long, Road> roadByWayId) {
for (Relation relation : throughRouteRelations) {
Node node = null;
Way w1 = null;
@@ -403,9 +526,8 @@
if (node == null)
node = (Node) member.getValue();
else
- log.warn("Through route relation "
- + relation.toBrowseURL()
- + " has more than 1 node");
+ log.debug("Through route relation",
+ relation.toBrowseURL() ,"has more than 1 node");
} else if (member.getValue() instanceof Way) {
Way w = (Way) member.getValue();
if (w1 == null)
@@ -413,57 +535,103 @@
else if (w2 == null)
w2 = w;
else
- log.warn("Through route relation "
- + relation.toBrowseURL()
- + " has more than 2 ways");
+ log.debug("Through route relation",
+ relation.toBrowseURL(), "has more than 2 ways");
}
}
if (node == null)
- log.warn("Through route relation " + relation.toBrowseURL()
- + " is missing the junction node");
+ log.debug("Through route relation", relation.toBrowseURL(),
+ "is missing the junction node");
if (w1 == null || w2 == null)
- log.warn("Through route relation "
- + relation.toBrowseURL()
- + " should reference 2 ways that meet at the junction node");
+ log.warn("Through route relation", relation.toBrowseURL(),
+ "should reference 2 ways that meet at the junction node");
if (node != null && w1 != null && w2 != null) {
- restrictions.add(node.getLocation(), w1.getId());
- restrictions.add(node.getLocation(), w2.getId());
+ List<Road> roads1 = roadByWayId.get(w1.getId());
+ for (Road road1 : roads1)
+ road1.setRestriction(node.getLocation());
+
+ List<Road> roads2 = roadByWayId.get(w2.getId());
+ for (Road road2 : roads2)
+ road2.setRestriction(node.getLocation());
}
}
}
- private boolean hasRestriction(Coord c, Way w) {
- List<Long> wayRestrictions = restrictions.get(c);
- return wayRestrictions.contains(w.getId());
- }
-
/**
* Merges {@code road2} into {@code road1}. This means that
* only the way id and the tags of {@code road1} is kept.
* For the tag it should not matter because all tags used after the
* RoadMerger are compared to be the same.
*
+ * @param mergePoint merge the roads at this point
* @param road1 first road (will keep the merged road)
* @param road2 second road
*/
- private void mergeRoads(Road road1, Road road2) {
+
+ /**
+ * Merges the road2 into road1 of the given MergeClassification. This means
+ * that only the way id and the tags of {@code road1} is kept. For the tag
+ * it should not matter because all tags used after the RoadMerger are
+ * compared to be the same. If specified in {@code mc} roads become reversed.
+ *
+ * @param mergePoint merge the roads at this point
+ * @param mc information structure how to merge
+ */
+ private void mergeRoads(Coord mergePoint, MergeClassification mc) {
+ log.info("Merge",mc.road1.getWay().getId(),"and",mc.road2.getWay().getId(),"with angle",mc.angle);
// Removes the second line,
// Merges the points in the first one
- List<Coord> points1 = road1.getWay().getPoints();
- List<Coord> points2 = road2.getWay().getPoints();
+ Road road1 = mc.road1;
+ Road road2 = mc.road2;
+
+ if (mc.road1Reversed) {
+ road1.reverse();
+ assert road1.getWay().isBoolTag("oneway") == false;
+ }
+
+ if (mc.road2Reversed) {
+ road2.reverse();
+ assert road2.getWay().isBoolTag("oneway") == false;
+ }
+
+
+ // Remove the second road from the roads list
+ roads.set(road2.getIndex(), null);
+
+ // set a tag in road1 so that it can be traced which roads are merged
+ String mergeIds = road1.getWay().getTag("mkgmap:mergeids");
+ if (mergeIds == null)
+ // set the own id
+ mergeIds = "["+road1.getWay().getId()+"]";
+ // get the merge information of the second road and add it to the first
+ String merge2Ids = road2.getWay().getTag("mkgmap:mergeids");
+ if (merge2Ids == null)
+ mergeIds += "["+road2.getWay().getId()+"]";
+ else
+ mergeIds += merge2Ids;
+ road1.getWay().addTag("mkgmap:mergeids", mergeIds);
+
+ // do some checks
+ // road1 must not have a restriction on its end
+ // road2 must not have any restriction
+ assert road1.isLastPointRestricted() == false;
+ assert road2.isFirstPointRestricted() == false;
+ assert road2.isLastPointRestricted() == false;
+
- Coord mergePoint = points2.get(0);
- Coord endPoint= points2.get(points2.size()-1);
+ Coord lastPoint= road2.getLastPoint();
- startPoints.remove(mergePoint, road2);
- endPoints.remove(endPoint, road2);
- endPoints.remove(mergePoint, road1);
+ roadEndPoints.remove(mergePoint, road1);
+ roadEndPoints.remove(mergePoint, road2);
+ roadEndPoints.remove(lastPoint, road2);
+ List<Coord> points1 = road1.getWay().getPoints();
+ List<Coord> points2 = road2.getWay().getPoints();
points1.addAll(points2.subList(1, points2.size()));
- endPoints.add(endPoint, road1);
+ roadEndPoints.add(lastPoint, road1);
// merge the POI info
String wayPOI2 = road2.getWay().getTag(StyledConverter.WAY_POI_NODE_IDS);
@@ -481,11 +649,30 @@
// // the mergePoint is now used by one highway less
mergePoint.decHighwayCount();
- // road2 is removed - it must not be part of a restriction
- assert (restrictions.get(endPoint).contains(road2.getWay().getId()) == false);
+ }
+
+ private static class MergeClassification implements Comparable<MergeClassification> {
+ Road road1;
+ boolean road1Reversed;
+ Road road2;
+ boolean road2Reversed;
+ double angle;
+ public int compareTo(MergeClassification otherMC) {
+ if (this == otherMC) {
+ return 0;
+ }
+ int angleCmp = Double.compare(angle, otherMC.angle);
+ if (angleCmp != 0) {
+ return angleCmp;
+ }
+
+ return Integer.compare(road1.getIndex(), otherMC.road1.getIndex());
+ }
}
+
+
/**
* Merge the roads and copy the results to the given lists.
* @param resultingWays list for the merged (and not mergeable) ways
@@ -495,28 +682,29 @@
int noRoadsBeforeMerge = this.roads.size();
int noMerges = 0;
- List<Road> roadsToMerge = new ArrayList<Road>(this.roads);
- this.roads.clear();
-
List<Coord> mergePoints = new ArrayList<>();
- // first add all roads with their start and end points to the
- // start/endpoint lists
- for (Road road : roadsToMerge) {
- List<Coord> points = road.getWay().getPoints();
- Coord start = points.get(0);
- Coord end = points.get(points.size() - 1);
+ // first add all roads with their first and last points to the
+ // first/last lists
+ for (Road road : this.roads) {
+ Coord firstPoint = road.getFirstPoint();
+ Coord lastPoint = road.getLastPoint();
- if (start == end) {
+ if (firstPoint == lastPoint) {
// do not merge closed roads
- roads.add(road);
+ log.debug("Do not merge closed road", road.getWay().getId());
+ continue;
+ }
+ if (road.isFirstPointRestricted() && road.isLastPointRestricted()) {
+ // this road has restrictions on both sides
+ log.debug("Do not merge road", road.getWay().getId(),"which has restrictions on both sides");
continue;
}
- mergePoints.add(start);
- mergePoints.add(end);
- startPoints.add(start, road);
- endPoints.add(end, road);
+ mergePoints.add(firstPoint);
+ mergePoints.add(lastPoint);
+ roadEndPoints.add(firstPoint, road);
+ roadEndPoints.add(lastPoint, road);
}
// a set of all points where no more merging is possible
@@ -525,99 +713,88 @@
// go through all start/end points and check if a merge is possible
for (Coord mergePoint : mergePoints) {
if (mergeCompletedPoints.contains(mergePoint)) {
- // a previous run did not show any possible merge
+ // a previous run already processed the point
// do not check again
continue;
}
- // get all road that start with the merge point
- List<Road> startRoads = startPoints.get(mergePoint);
- // get all roads that end with the merge point
- List<Road> endRoads = endPoints.get(mergePoint);
+ // get all road that start or end with the merge point
+ Set<Road> roadsAtPoint = roadEndPoints.get(mergePoint);
- if (endRoads.isEmpty() || startRoads.isEmpty()) {
- // this might happen if another merge operation changed endPoints and/or startPoints
- mergeCompletedPoints.add(mergePoint);
+ if (roadsAtPoint.size() < 2) {
+ // there is less than two roads => no merge possible
+// do not add it to the set because the overhead is probably more costly than it's advantage
+// mergeCompletedPoints.add(mergePoint);
continue;
}
+ List<Road> mergeableRoads = new ArrayList<>(roadsAtPoint);
// go through all combinations and test which combination is the best
- double bestAngle = Double.MAX_VALUE;
- Road mergeRoad1 = null;
- Road mergeRoad2 = null;
+ List<MergeClassification> possibleMerges = new ArrayList<>(mergeableRoads.size());
- for (Road road1 : endRoads) {
- // check if the road has a restriction at the merge point
- // which does not allow us to merge the road at this point
- if (hasRestriction(mergePoint, road1.getWay())) {
- continue;
- }
-
- List<Coord> points1 = road1.getWay().getPoints();
+ for (int firstIndex = 0; firstIndex < mergeableRoads.size(); firstIndex++) {
+ Road road1 = mergeableRoads.get(firstIndex);
// go through all candidates to merge
- for (Road road2 : startRoads) {
- if (hasRestriction(mergePoint, road2.getWay())) {
+ for (int secondIndex = firstIndex+1; secondIndex < mergeableRoads.size(); secondIndex++) {
+ if (secondIndex == firstIndex) {
continue;
}
- List<Coord> points2 = road2.getWay().getPoints();
- // the second road is merged into the first road
- // so only the id of the first road is kept
- // This also means that the second road must not have a restriction on
- // both start and end point
- if (hasRestriction(points2.get(points2.size()-1), road2.getWay())) {
- continue;
- }
+ Road road2 = mergeableRoads.get(secondIndex);
+ log.debug("Check if road",road1.getWay().getId(),"and",road2.getWay().getId(),"can be merged");
- // check if both roads can be merged
- if (road1.isMergable(mergePoint, road2)) {
- // yes they might be merged
- // calculate the angle between them
- // if there is more then one road to merge the one with the lowest angle is merged
- double angle = Math.abs(Utils.getAngle(points1.get(points1.size()-2), mergePoint, points2.get(1)));
- log.debug("Road",road1.getWay().getId(),"and road",road2.getWay().getId(),"are mergeable with angle",angle);
- if (angle < bestAngle) {
- mergeRoad1 = road1;
- mergeRoad2 = road2;
- bestAngle = angle;
- }
+ // check if the roads are mergeable
+ MergeClassification mc = road1.getMergeClassification(mergePoint, road2);
+ if (mc == null) {
+ // check the other way round
+ mc = road2.getMergeClassification(mergePoint, road1);
+ }
+ if (mc != null) {
+ possibleMerges.add(mc);
}
}
}
- // is there a pair of roads that can be merged?
- if (mergeRoad1 != null && mergeRoad2 != null) {
- // yes!! => merge them
- log.debug("Merge",mergeRoad1.getWay().getId(),"and",mergeRoad2.getWay().getId(),"with angle",bestAngle);
- mergeRoads(mergeRoad1, mergeRoad2);
+ // sort the merges to get the best merge first
+ Collections.sort(possibleMerges);
+ while (possibleMerges.isEmpty() == false) {
+ // the first in the list is the best merge (with smallest angle)
+ MergeClassification bestMerge = possibleMerges.remove(0);
+
+ // remove all other merges with one of both roads
+ ListIterator<MergeClassification> otherMerges = possibleMerges.listIterator();
+ while (otherMerges.hasNext()) {
+ MergeClassification nextMerge = otherMerges.next();
+ if (nextMerge.road1 == bestMerge.road1 ||
+ nextMerge.road1 == bestMerge.road2 ||
+ nextMerge.road2 == bestMerge.road1 ||
+ nextMerge.road2 == bestMerge.road2) {
+ // these roads cannot be merge twice at the same point
+ // so the nextMerge is not possible => remove it
+ otherMerges.remove();
+ }
+ }
+
+ // perform the bestMerge
+ mergeRoads(mergePoint, bestMerge);
noMerges++;
- } else {
- // no => do not check again this point again
- mergeCompletedPoints.add(mergePoint);
}
+ // the point is fully merged => do not process again
+ mergeCompletedPoints.add(mergePoint);
}
-
- // copy all merged roads to the roads list
- for (List<Road> mergedRoads : endPoints.values()) {
- this.roads.addAll(mergedRoads);
- }
-
- // sort the roads to ensure that the order of roads is constant for two runs
- Collections.sort(this.roads, new Comparator<Road>() {
- public int compare(Road o1, Road o2) {
- return Integer.compare(o1.getIndex(), o2.getIndex());
- }
- });
// copy the roads to the resulting lists
for (Road r : roads) {
+ if (r == null) {
+ continue;
+ }
resultingWays.add(r.getWay());
resultingGTypes.add(r.getGtype());
}
// print out some statistics
- int noRoadsAfterMerge = this.roads.size();
+ int noRoadsAfterMerge = resultingWays.size();
log.info("Roads before/after merge:", noRoadsBeforeMerge, "/",
noRoadsAfterMerge);
int percentage = (int) Math.round((noRoadsBeforeMerge - noRoadsAfterMerge) * 100.0d
Index: src/uk/me/parabola/util/MultiIdentityHashMap.java
===================================================================
--- src/uk/me/parabola/util/MultiIdentityHashMap.java (revision 2949)
+++ src/uk/me/parabola/util/MultiIdentityHashMap.java (working copy)
@@ -13,39 +13,38 @@
package uk.me.parabola.util;
-import java.util.ArrayList;
import java.util.Collections;
import java.util.IdentityHashMap;
-import java.util.LinkedList;
-import java.util.List;
+import java.util.Set;
+import java.util.TreeSet;
-public class MultiIdentityHashMap<K,V> extends IdentityHashMap<K,List<V>> {
+public class MultiIdentityHashMap<K,V> extends IdentityHashMap<K,Set<V>> {
/**
- * the empty list to be returned when there is key without values.
+ * the empty set to be returned when there is key without values.
*/
- private final List<V> emptyList = Collections.unmodifiableList(new ArrayList<V>(0));
+ private final Set<V> emptySet = Collections.unmodifiableSet(Collections.<V>emptySet());
/**
- * Returns the list of values associated with the given key.
+ * Returns the values set associated with the given key.
*
* @param key the key to get the values for.
* @return a list of values for the given keys or the empty list of no such
* value exist.
*/
- public List<V> get(Object key) {
- List<V> result = super.get(key);
- return result == null ? emptyList : result;
+ public Set<V> get(Object key) {
+ Set<V> result = super.get(key);
+ return result == null ? emptySet : result;
}
public V add(K key, V value )
{
- List<V> values = super.get(key);
+ Set<V> values = super.get(key);
if (values == null ) {
- values = new LinkedList<V>();
+ values = new TreeSet<>();
super.put( key, values );
}
@@ -57,7 +56,7 @@
public V remove(K key, V value )
{
- List<V> values = super.get(key);
+ Set<V> values = super.get(key);
if (values == null )
return null;
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
