[PATCH v1] Merge similar lines and ways
The attached will merge lines that are similar* after styling. It is activated by the switch "--merge-lines". As there are less way fragments, the Douglas-Peucker filter will work better and the routing should improve somewhat, because the ways will be longer and the routing algorithm won't give up too soon. The size of the resulting map is reduced a little bit as well. The patch is based on code published by Johann Gail on this mailing list. *) similar means that they have the same attributes: name, ref, access, etc. Regards Thilo
Hi Thilo,
The attached will merge lines that are similar* after styling. It is activated by the switch "--merge-lines".
As there are less way fragments, the Douglas-Peucker filter will work better and the routing should improve somewhat, because the ways will be longer and the routing algorithm won't give up too soon. The size of the resulting map is reduced a little bit as well.
The patch is based on code published by Johann Gail on this mailing list.
Will this cause a problem with ways that have been split on purpose because they are longer than the maximum allowed arc length? Cheers, Mark
Am 15.08.2009 um 13:04 schrieb Mark Burton:
Will this cause a problem with ways that have been split on purpose because they are longer than the maximum allowed arc length?
No, not at all. The reason is that the merging of the ways is done before they are split again if necessary. The net effect is still a size reduction of the map (with the style I'm using). I hope that I also got everything else right: relations, turn-restrictions, etc. Please test and complain ;). Note that the argument "--merge-lines" is needed for the merging to take place. The more detailed the OSM data becomes, the more the merging will be helpful. The main reason are the route relations. Here in my hometown all the bus routes are mapped and of course they go all over the place. Each time a bus route enters or leaves a street, the street has to be chopped up. Add to that a lot of cycle routes, hiking routes etc. and you see that the street gets chopped up into tiny bits. Depending on the map you try to create, you will ignore most of those relations and they will make no difference, so all those tiny bits have the same attributes. Merging them again will reduce the number of ways. This at least reduces the size of the map slightly and probably also helps routing and improves the drawing speed somewhat. Regards Thilo
Please test and complain ;). Note that the argument "--merge-lines" is needed for the merging to take place.
Are there patches in the latest?
What I meant: Are all these patches which are announced on the list as [PATCH vx] included in the mkgmap-latest? If not - where can I download the patched versions? Chris
Hi Chris,
Are all these patches which are announced on the list as [PATCH vx] included in the mkgmap-latest?
If not - where can I download the patched versions?
No, it's up to the individual developer to "mix and match" whatever patches they wish to try. They have to be applied to trunk. Cheers, Mark
Thilo,
Am 15.08.2009 um 13:04 schrieb Mark Burton:
Will this cause a problem with ways that have been split on purpose because they are longer than the maximum allowed arc length?
No, not at all. The reason is that the merging of the ways is done before they are split again if necessary. The net effect is still a size reduction of the map (with the style I'm using). I hope that I also got everything else right: relations, turn-restrictions, etc. Please test and complain ;). Note that the argument "--merge-lines" is needed for the merging to take place.
The more detailed the OSM data becomes, the more the merging will be helpful. The main reason are the route relations. Here in my hometown all the bus routes are mapped and of course they go all over the place. Each time a bus route enters or leaves a street, the street has to be chopped up. Add to that a lot of cycle routes, hiking routes etc. and you see that the street gets chopped up into tiny bits. Depending on the map you try to create, you will ignore most of those relations and they will make no difference, so all those tiny bits have the same attributes. Merging them again will reduce the number of ways. This at least reduces the size of the map slightly and probably also helps routing and improves the drawing speed somewhat.
I understand the potential benefits of this patch. However, looking at the code it seems to me that the merging happens after StyledConverter.addRoad() is called and that is where the way lengths are limited. So you either have to do the merging earlier, or you need to add a constraint to limit the length of the merged way. Actually, there are several constraints in StyledConverter: // limit arc lengths to what can currently be handled by RouteArc private final int MAX_ARC_LENGTH = 25000; private final int MAX_POINTS_IN_WAY = 200; private final int MAX_NODES_IN_WAY = 16; Cheers, Mark
Hi Mark, Am 15.08.2009 um 13:45 schrieb Mark Burton:
However, looking at the code it seems to me that the merging happens after StyledConverter.addRoad() is called and that is where the way lengths are limited. So you either have to do the merging earlier, or you need to add a constraint to limit the length of the merged way.
I see what you mean. Damn. I assumed that the length limiting would only occur in the filters later on. Thank you for pointing this out. I will modify the code that the merging is applied even earlier. Shouldn't be too hard to do. @Chris:
If not - where can I download the patched versions?
You can download a version of mkgmap with all the patches that I do apply from http://wiki.openstreetmap.org/wiki/User:Radfahrer/Radkarte (it's in German though, it's the second link in the section "Entwicklung": "Ausserdem sind die Stil-Dateien, die TYP-Datei und das gepatchte mkgmap auch ->hier<- verfügbar". The current version has the patch in it, but as discussed above this patch is buggy. Also beware that this is no "official" version of mkgmap, so please don't ask for support for it on this mailing list. The mkgmap I use is heavily patched and by asking about problems with it on the mailing list you will only tie up resources for bugs that the official version of mkgmap doesn't have (and with that therefore nobody can help you). The better approach is to wait until the patch makes it to trunk, which it will or will not, depending on whether the maintainers deem it beneficial or not. Regards Thilo
Hi Thilo,
I will modify the code that the merging is applied even earlier. Shouldn't be too hard to do.
Did you do that? I would be keen to try a version because I notice on my first few trips with the Nuvi that sometimes it says "keep right/left" when it should say "turn right/left". I think that is because the way looks like this: AAAAAAAAAAAAAAABBBBBBBBBBBBBBB C C C C When it should look like this: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA C C C C i.e. A and B are really the same road as far as routing is concerned. It would be good to have an option to merge those ways. Cheers, Mark
Mark Burton escribió:
Hi Thilo,
I will modify the code that the merging is applied even earlier. Shouldn't be too hard to do.
Did you do that? I would be keen to try a version because I notice on my first few trips with the Nuvi that sometimes it says "keep right/left" when it should say "turn right/left". I think that is because the way looks like this:
AAAAAAAAAAAAAAABBBBBBBBBBBBBBB C C C C
When it should look like this:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA C C C C
i.e. A and B are really the same road as far as routing is concerned. It would be good to have an option to merge those ways.
I think in many cases it depends on the angle between the "from" road and the "to" one. Changing the "to" way type to XXX_link gives a "turn" instruction instead of "keep", but can only be done in some cases. Regards Carlos
Cheers,
Mark _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Mark, Am 09.09.2009 um 19:58 schrieb Mark Burton:
I will modify the code that the merging is applied even earlier. Shouldn't be too hard to do.
Did you do that? I would be keen to try a version because I notice on my first few trips with the Nuvi that sometimes it says "keep right/left" when it should say "turn right/left". I think that is because the way looks like this:
I was too optimistic in saying that it "shouldn't be too hard to do". Actually I could not get it working. The merging of the ways works fine, but the routing on the resulting maps is broken. The problem here is that it is not possible to merge the ways just after reading from the osm file, because then the attributes are not determined completely yet. But it is also not possible to merge the ways after all the styling has been done, because then there are already references written to the Garmin structures that would point to removed portions of the merged ways. So it has to be somewhen in between and that makes it diffcult. Anyway, as soon as I find some time I'll update the patch to work against the current revision and post it here, maybe somebody can help. Regards Thilo
Thilo Hannemann wrote:
Hi Mark,
Am 09.09.2009 um 19:58 schrieb Mark Burton:
I will modify the code that the merging is applied even earlier. Shouldn't be too hard to do.
Did you do that? I would be keen to try a version because I notice on my first few trips with the Nuvi that sometimes it says "keep right/left" when it should say "turn right/left". I think that is because the way looks like this:
Some remarks about the merge lines concept, and the reasoning why it will not help much and needs to be extended/changed. *1.* There is absolutely no need to merge lines in case the way continues at 0° angle (no change in direction). *2. *There is no time penalty in Mapsource for a way zig-zagging, as long as there is no junction/change of way. The more the angle approaches 180° , the bigger the time penalty. *2a* 180° exact i.e. only change in direction of way in osm database without oneway attribute does not matter of course, On the other hand every single route viapoint you set additionally will give you a time penalty. So if you route along a completely straight line and you put additional via points, the calculated arrival time gets bigger. This of course is irrelevant to mkgmap. The effect of the time penalty for via points, is only around 5-20seconds, so should be irrelevant (maybe maximum 1-2% of added time) to total travel time of a route. *3.* If two ways meet on a straight line: *a)* no time penalty is added at all *b)* no turn indication is given This means that you can well turn around a whole circle without any turn indication and many way changes, as long as the junctions themselves lie on a straight line. There is not even an indication of streetname changes. So in the directions window of mapsource, or route window of GPS it will not tell you that you get on another street (meaning another streetname) as long as you continue straight. * Taking into account the above:* Yes a merging lines patch will help for bicycle/pedestrian routing. Though much more effective would be a patch that actually changes the angle streets meet. Let's first look at what happens when two streets meet at extreme angle. notice total time is 03:27min (with no junction at all it would be 01:28): original / *Concept1*/ So if two ways meet: y y y xxxxxxxx y y y We should make additional ways like this (this will help a tiny bit, but not much). ("." means that 2 ways lie on top of each other, ";" means at this point there are four ways on top of each other, so the direction change is not at the junction but done on the intermediary way) y y . xxx. . .xxxx . y y concept1 So we notice now that the time is actually the same as if there was no junction 1:28min. Note, no junction/direction change is shown at all (the GPS will still warn however when approaching). This achieves the same effect as the merge line patch would do in case both streets have the same name. */Concept 2:/* By having the turn on the intermediary way, instead of the junction itself) we completely avoid the time penalty (though we also miss the name change of the street in the route window, nor any indication in the route window about the turn). Therefore we have to change the above still a tiny bit. By playing around with changing the distance I have found out that we need to put nodes at least around 1m distance of each other (otherwise we get short arc problem), so while the /Concept1/ I chose to have a rather large distance for the straight part, I now reduce the distance to 1m between each node (this means that we need to have 2m additional width for the junction - /Concept1/ could be achieved on 1m), the even dirtier hack to get junctions back into the route window has to make the whole thing rounded. So assume you come from top (north) and want to continue to the right (east) we have to add a new way like this (only showing added ways, we should never remove the original ways of course, so that crossing straight is still possible). The new way is drawn as . y y . .. xxxxxxxxxxxxxxx This distance | | being 5.4m, while distance from north to south should be made around 1m. By doing this we get the best possible. a) we are notified about the junction/street change, b) we are taking a time penalty for turning. This time penalty is however very small (5-10 seconds), and should be more or less equal to what we need in real life to orientate here and change streets. The proof in Mapsource of concept 2 (time penalty decreased to a mere 12 seconds), reducing the distance between the two additional nodes to the junction of 1m makes this more or less invisible: concept2 * The much bigger advantage however is*, that the above concept would allow us on GPS to always route along the maximum of 100 direction changes (at least the old GPS can't route over more than 100 direction changes without via point) and over more or less indefinite distances in Mapsource (think Spain to Germany using small streets, cycleways and so on only). Transferring such a long route to GPS is even possible, using WinGDB to insert a via point every 99th direction change (Mapsource puts direction change points internally, but does not show them, they are saved in the .gdb file which is created if you save a calculated route. This way you could theoretically transfer a route going along 99.000 junctions to your GPS which is still easily able to recalculate it (well I'm sure GPS runs out of memory long before, but we will be able to have as long routes as fit into the memory, I think routes over 1000-2000km should still work). A closeup of the work shown in JOSM zoomed up very close looks like this (red is original way): closeup josm *Is there anyone* who thinks the above concept2 can be implemented into mkgmap? I don't have the skills to code this. But maybe someone has the skills, and feels motivated by knowing that shitty routing for bicycle/pedestrian use, can be easily adapted by changing junctions with the above concept. Without implementing the above, we will never have good routing in Mapsource or on GPS. Using concept2 would get splendid routing (and make the merge lines patch discussed before obsolete!). Off course the above would not be needed, if Garmin would make the penalty adjustable, but that day will probably not come...... Also as a benegit the keep left vs turn left could be solved this way (increasing the angle of the junction high enough to get turn instead of keep, or in contrast decrease angle of the road you want to stay on so that it reminds you to keep left/right). See attached also screenshots of one more example (classic junction) and a osm testfile for you to play with.
Hi Felix,
Some remarks about the merge lines concept, and the reasoning why it will not help much and needs to be extended/changed.
Your remarks are most interesting. I have been considering writing some code to tweak the arc headings to help make the routing directions more sensible. In my head, I have already thought how and where to do that. I would be happy to incorporate your ideas into the experimental code so we can evaluate them. I'm away for a couple of days now but should be able to start on this next week. Cheers, Mark
Mark Burton wrote:
Hi Felix,
Some remarks about the merge lines concept, and the reasoning why it will not help much and needs to be extended/changed.
Your remarks are most interesting. I have been considering writing some code to tweak the arc headings to help make the routing directions more sensible. In my head, I have already thought how and where to do that.
I would be happy to incorporate your ideas into the experimental code so we can evaluate them.
Go for it, this would really make mkgmap awesome (it's already great). I'm happy to bugtrack as usual :)
I'm away for a couple of days now but should be able to start on this next week.
Cheers,
Mark _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
I will modify the code that the merging is applied even earlier. Shouldn't be too hard to do.
Did you do that? I would be keen to try a version because I notice on my first few trips with the Nuvi that sometimes it says "keep right/left" when it should say "turn right/left". I think that is because the way looks like this:
I was too optimistic in saying that it "shouldn't be too hard to do". Actually I could not get it working. The merging of the ways works fine, but the routing on the resulting maps is broken. The problem here is that it is not possible to merge the ways just after reading from the osm file, because then the attributes are not determined completely yet. But it is also not possible to merge the ways after all the styling has been done, because then there are already references written to the Garmin structures that would point to removed portions of the merged ways. So it has to be somewhen in between and that makes it diffcult.
Anyway, as soon as I find some time I'll update the patch to work against the current revision and post it here, maybe somebody can help.
Regards Thilo
Hi Thilo, what is the state of this patch? Is it runable, or have you stopped work on it because of unsolvable problems? Maybe the garmin strucutres need to be made more dynamic, getting its final values in a later step? I remembered that there was some problems, but have not investigated further. In general the concept seems ok to me. Regards, Johann
Am 29.11.2009 um 18:20 schrieb Johann Gail:
Hi Thilo,
what is the state of this patch? Is it runable, or have you stopped work on it because of unsolvable problems? Maybe the garmin strucutres need to be made more dynamic, getting its final values in a later step?
I remembered that there was some problems, but have not investigated further. In general the concept seems ok to me.
Hi Johann, I couldn't get the patch working properly with routing. The main problem is that to merge the ways I need the processed ways, so that I can compare the attributes that are actually put into the IMG files. It is of no use to compare the OSM tags, because then even minor differences would prevent merging of the ways, even if most tags won't influence the resulting Garmin ways at all. The IMG files are build "along the way" when the OSM data is processed, so I never have all processed ways available. This is made worse by the structure of the code, where the classes get nested deeper and deeper during processing... I had to change quite a lot of code to make all *processed* OSM data available at some point. But somehow this broke the routing. Probably this has to do with the way the ways that are split along the way are tracked. But it ended in a massive rewrite anyway, so it would have been a nightmare to maintain as a patch. And the resulting code wasn't nice and clean either, because it went against the work flow of the existing code. Therefore, I stopped working on it. Regards Thilo
participants (6)
-
Carlos Dávila -
Chris-Hein Lunkhusen -
Felix Hartmann -
Johann Gail -
Mark Burton -
Thilo Hannemann