Hi Gerd,
the SimpleTest also randomly fails because the number of resulting lines
is sometimes different.
You are right that the roadmerger does not change the number of lines in
roundabouts. But there are other ways similar to roundabouts:
http://www.openstreetmap.org/?mlat=51.25946&mlon=6.74760&zoom=17#map=19/51.25990/6.74788
I guess such ways are responsible for different number of lines.
Anyhow I have found a quite easy way to make the RoadMerger stable.
When creating the list of roads I copy all start and end points to a
list. This list is stable. Step by step I go through this list to find
merge candidates. No matter if we allow to merge ways to a closed way
this procedure is stable.
Sorting at the end is still required because the roads are copied from
the IdentityHashMap to the resulting list and this is not stable.
Attached patch also contains the creation of a debugging file at the end
of the RoadMerger.merge procedure. The output contains informations
about the roads which makes it easy to compare two runs of mkgmap.
Please give it a check if that solves your problem. I will have a look
on the tests and if the performance is still acceptable using the patch.
WanMil
Hi WanMil,
it's a unit test regarding the style finalizer section which fails and I
don't know why.
reg. RoadMerger:
it makes no sense to create closed ways because we would split them
again later in StyledConverter.
I don't understand the idea about roundabouts.
If one is divided into 4 parts you can do 2 merges without closing it,
no matter which
parts you connect first, and you should always get 2 remaining parts.
Assumes part a,b,c and d:
a+b and c+d or
a+b and a_b + c or
b+c and d+a or
b+c and b_c + d or
b+c and a + b_c or
...
Gerd
> Date: Sun, 5 Jan 2014 12:37:09 +0100
> From: [email protected]
> To: [email protected]
> Subject: Re: [mkgmap-dev] Unit tests in trunk fail
>
> Hi Gerd,
>
> I think I found the problem:
>
> // check if merging would create a closed way - which should not
> // be done (why? WanMil)
> if (cStart == cOtherEnd) {
> return false;
> }
>
> The RoadMerger avoids to create closed roads. In case the roads are not
> merged in exactly the same order this is the reason for different merge
> results due to roundabouts. In case a roundabout is divided in multiple
> ways the number of merged ways is random.
>
> At the moment I have no time to check that more in detail but I think
> the code listed above can be removed.
>
> WanMil
>
> > Hi WanMil,
> >
> > please have a look, I don't fully understand why.
> >
> > Gerd
> >
> >
> > _______________________________________________
> > 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 2939)
+++ src/uk/me/parabola/mkgmap/osmstyle/RoadMerger.java (working copy)
@@ -13,9 +13,14 @@
package uk.me.parabola.mkgmap.osmstyle;
+import java.io.FileWriter;
+import java.io.IOException;
+import java.io.PrintWriter;
+import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
+import java.util.Date;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.List;
@@ -519,6 +524,8 @@
int noMerges = 0;
List<Road> roadsToMerge = new ArrayList<Road>(this.roads);
this.roads.clear();
+
+ List<Coord> mergingCoords = new ArrayList<>();
// first add all roads with their start and end points to the
// start/endpoint lists
@@ -533,96 +540,85 @@
continue;
}
+ mergingCoords.add(start);
+ mergingCoords.add(end);
startPoints.add(start, road);
endPoints.add(end, road);
}
// a set of all points where no more merging is possible
Set<Coord> mergeCompletedPoints = Collections.newSetFromMap(new IdentityHashMap<Coord, Boolean>());
- // flag if at least one road was merged in a merge cycle
- boolean oneRoadMerged = true;
- while (oneRoadMerged) {
- oneRoadMerged = false;
+ for (Coord mergePoint : mergingCoords) {
+ if (mergeCompletedPoints.contains(mergePoint)) {
+ continue;
+ }
- // first get the potential merge points
- Set<Coord> mergePoints = Collections.newSetFromMap(new IdentityHashMap<Coord, Boolean>());
- mergePoints.addAll(endPoints.keySet());
- // remove all coords that have been completely processed and that have no more merge candidates
- mergePoints.removeAll(mergeCompletedPoints);
- // only keep the points where there is a way with a start point identical to the end point of another way
- mergePoints.retainAll(startPoints.keySet());
+ // 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);
- // check all potential merge points for merges
- for (Coord mergePoint : mergePoints) {
- // 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);
-
- if (endRoads.isEmpty() || startRoads.isEmpty()) {
- // this might happen if another merge operation changed endPoints and/or startPoints
+ if (endRoads.isEmpty() || startRoads.isEmpty()) {
+ // this might happen if another merge operation changed endPoints and/or startPoints
+ 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;
+
+ 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();
- // go through all combinations and test which combination is the best
- double bestAngle = Double.MAX_VALUE;
- Road mergeRoad1 = null;
- Road mergeRoad2 = null;
-
- 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())) {
+ // go through all candidates to merge
+ for (Road road2 : startRoads) {
+ if (hasRestriction(mergePoint, road2.getWay())) {
continue;
}
+ List<Coord> points2 = road2.getWay().getPoints();
- List<Coord> points1 = road1.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;
+ }
- // go through all candidates to merge
- for (Road road2 : startRoads) {
- if (hasRestriction(mergePoint, road2.getWay())) {
- 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;
- }
-
- // 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 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;
+ }
}
}
-
- // 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);
- // flag that there was at least one merge in this cycle
- oneRoadMerged = true;
- noMerges++;
- } else {
- // no => do not check again this point in the next cylce
- mergeCompletedPoints.add(mergePoint);
- }
+ }
+
+ // is there a pair of roads that can be merged?
+ if (mergeRoad1 != null && mergeRoad2 != null) {
+ // yes!! => merge them
+ log.debug("Merge",mergeRoad1.getIndex(),mergeRoad1.getWay().getId(),"and",mergeRoad2.getIndex(),mergeRoad2.getWay().getId(),"with angle",bestAngle);
+ mergeRoads(mergeRoad1, mergeRoad2);
+ noMerges++;
+ } else {
+ // no => do not check again this point in the next cycle
+ mergeCompletedPoints.add(mergePoint);
}
}
@@ -638,12 +634,17 @@
}
});
+ String date = new SimpleDateFormat("HHmmss").format(new Date());
+ try (PrintWriter pw = new PrintWriter(new FileWriter("c:/temp/rd_"+date+".txt"))){
// copy the roads to the resulting lists
for (Road r : roads) {
resultingWays.add(r.getWay());
resultingGTypes.add(r.getGtype());
+ pw.println(r.getIndex()+ " " +r.getWay().getPoints().size()+" "+r.getGtype()+" "+r.getWay().getPoints().get(0).toOSMURL());
}
-
+ } catch (IOException exp) {
+ }
+
// print out some statistics
int noRoadsAfterMerge = this.roads.size();
log.info("Roads before/after merge:", noRoadsBeforeMerge, "/",
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
