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.
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;
@@ -49,10 +49,8 @@
/** 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,7 +59,7 @@
*
* @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;
@@ -139,6 +137,7 @@
Coord cEnd = way.getPoints().get(way.getPoints().size() - 1);
if (cStart != mergePoint && cEnd != mergePoint) {
// it doesn't => roads not mergeable at mergePoint
+ log.debug("Merge point not at start/end of",way.getId());
return false;
}
@@ -149,17 +148,20 @@
if (cOtherStart != mergePoint && cOtherEnd != mergePoint) {
// otherRoad does not start or stop at mergePoint =>
// roads not mergeable at mergePoint
+ log.debug("Merge point not at start/end of",otherRoad.way.getId());
return false;
}
// check if merging would create a closed way - which should not
// be done (why? WanMil)
- if (cStart == cOtherEnd) {
+ if ((cStart == cOtherEnd && cStart != mergePoint) || (cEnd == cOtherStart && cEnd != mergePoint)) {
+ log.debug("Do not merge",way.getId(),"and",otherRoad.way.getId(),"- closed way");
return false;
}
// check if the GType objects are the same
if (isGTypeMergable(otherRoad.getGtype()) == false) {
+ log.debug("Do not merge",way.getId(),"and",otherRoad.way.getId(),"- different gtype");
return false;
}
@@ -252,7 +254,7 @@
if (thisStart == otherStart) {
// both ways are oneway but they have a different direction
- log.warn("oneway with different direction", way.getId(),
+ log.debug("oneway with different direction", way.getId(),
otherWay.getId());
return false;
}
@@ -322,10 +324,10 @@
// 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,"°");
+ log.debug("Do not merge ways",getWay().getId(),"and",otherWay.getId(),"because they span a too big angle",angle,"°");
return false;
}
-
+
return true;
}
@@ -358,6 +360,10 @@
public final int getIndex() {
return index;
}
+
+ public int compareTo(Road otherRoad) {
+ return Integer.compare(index, otherRoad.index);
+ }
}
public RoadMerger(List<Way> ways, List<GType> gtypes,
@@ -367,9 +373,10 @@
this.roads = new ArrayList<Road>(ways.size());
+ 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)));
+ roads.add(new Road(roadIndex++, ways.get(i), gtypes.get(i)));
}
this.restrictions = new MultiIdentityHashMap<Coord, Long>();
@@ -436,7 +443,7 @@
}
private boolean hasRestriction(Coord c, Way w) {
- List<Long> wayRestrictions = restrictions.get(c);
+ Set<Long> wayRestrictions = restrictions.get(c);
return wayRestrictions.contains(w.getId());
}
@@ -446,24 +453,37 @@
* 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) {
+ private void mergeRoads(Coord mergePoint, Road road1, Road road2) {
// Removes the second line,
// Merges the points in the first one
+
+ // Remove the second road from the roads list
+ roads.set(road2.getIndex(), null);
+
List<Coord> points1 = road1.getWay().getPoints();
+ if (mergePoint == points1.get(0)) {
+ road1.getWay().reverse();
+ assert road1.getWay().isBoolTag("oneway") == false;
+ }
+
List<Coord> points2 = road2.getWay().getPoints();
+ if (mergePoint != points2.get(0)) {
+ road2.getWay().reverse();
+ assert road2.getWay().isBoolTag("oneway") == false;
+ }
- Coord mergePoint = points2.get(0);
Coord endPoint= points2.get(points2.size()-1);
- startPoints.remove(mergePoint, road2);
- endPoints.remove(endPoint, road2);
- endPoints.remove(mergePoint, road1);
+ roadEndPoints.remove(mergePoint, road2);
+ roadEndPoints.remove(endPoint, road2);
+ roadEndPoints.remove(mergePoint, road1);
points1.addAll(points2.subList(1, points2.size()));
- endPoints.add(endPoint, road1);
+ roadEndPoints.add(endPoint, road1);
// merge the POI info
String wayPOI2 = road2.getWay().getTag(StyledConverter.WAY_POI_NODE_IDS);
@@ -486,6 +506,24 @@
}
+ private static class MergeClassification implements Comparable<MergeClassification> {
+ Road road1;
+ Road road2;
+ 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 +533,25 @@
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) {
+ for (Road road : this.roads) {
List<Coord> points = road.getWay().getPoints();
Coord start = points.get(0);
Coord end = points.get(points.size() - 1);
if (start == end) {
// do not merge closed roads
- roads.add(road);
+ log.debug("Do not merge closed road", road.getWay().getId());
continue;
}
mergePoints.add(start);
mergePoints.add(end);
- startPoints.add(start, road);
- endPoints.add(end, road);
+ roadEndPoints.add(start, road);
+ roadEndPoints.add(end, road);
}
// a set of all points where no more merging is possible
@@ -525,42 +560,61 @@
// 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> startRoads = roadEndPoints.get(mergePoint);
- if (endRoads.isEmpty() || startRoads.isEmpty()) {
- // this might happen if another merge operation changed endPoints and/or startPoints
+ if (startRoads.size() < 2) {
+ // there is less than two roads => no merge possible
+ mergeCompletedPoints.add(mergePoint);
+ continue;
+ }
+
+ ArrayList<Road> mergeableRoads = new ArrayList<>(startRoads.size());
+ for (Road road : startRoads) {
+ if (hasRestriction(mergePoint, road.getWay())) {
+ if (log.isDebugEnabled())
+ log.debug("Do not merge road", road.getWay().getId(), "at point", mergePoint, "because there is a restriction.");
+ } else {
+ mergeableRoads.add(road);
+ }
+ }
+
+ // check again how many roads are known
+ if (mergeableRoads.size() < 2) {
+ // there is less than two roads => no merge possible
mergeCompletedPoints.add(mergePoint);
continue;
}
// 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()/2);
- 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;
- }
-
+ for (int firstIndex = 0; firstIndex < mergeableRoads.size(); firstIndex++) {
+ Road road1 = mergeableRoads.get(firstIndex);
List<Coord> points1 = road1.getWay().getPoints();
+ int startCheckAt = firstIndex+1;
+ if (road1.getWay().isBoolTag("oneway")) {
+ // if the way is oneway all other ways need to be check
+ // because for oneway roads
+ startCheckAt = 0;
+ }
+
// go through all candidates to merge
- for (Road road2 : startRoads) {
- if (hasRestriction(mergePoint, road2.getWay())) {
+ for (int secondIndex = startCheckAt; secondIndex < mergeableRoads.size(); secondIndex++) {
+ if (secondIndex == firstIndex) {
continue;
}
+
+ Road road2 = mergeableRoads.get(secondIndex);
List<Coord> points2 = road2.getWay().getPoints();
+
+ log.debug("Check if road",road1.getWay().getId(),"and",road2.getWay().getId(),"can be merged");
// the second road is merged into the first road
// so only the id of the first road is kept
@@ -575,49 +629,81 @@
// 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)));
+ Coord c1 = null;
+ if (mergePoint == points1.get(0)) {
+ c1 = points1.get(1);
+ } else {
+ c1 = points1.get(points1.size()-2);
+ }
+ Coord c2 = null;
+ if (mergePoint == points2.get(0)) {
+ c2 = points2.get(1);
+ } else {
+ c2 = points2.get(points2.size()-2);
+ }
+
+ double angle = Math.abs(Utils.getAngle(c1, mergePoint, c2));
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;
- }
+ MergeClassification mergeClassification = new MergeClassification();
+ mergeClassification.angle = angle;
+ mergeClassification.road1 = road1;
+ mergeClassification.road2 = road2;
+ possibleMerges.add(mergeClassification);
}
}
}
- // 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);
- noMerges++;
- } else {
- // no => do not check again this point again
- mergeCompletedPoints.add(mergePoint);
+ Collections.sort(possibleMerges);
+ while (possibleMerges.isEmpty() == false) {
+ 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
+ log.debug("Merge",bestMerge.road1.getWay().getId(),"and",bestMerge.road2.getWay().getId(),"with angle",bestMerge.angle);
+ mergeRoads(mergePoint, bestMerge.road1, bestMerge.road2);
+ noMerges++;
}
+ // 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);
- }
+// // copy all merged roads to the roads list
+// for (Set<Road> mergedRoads : roadEndPoints.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());
- }
- });
+// // 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
