[PATCH v1] remove bogus nodes
With the recent reversion of the Table A breakage, it's now useful to post this patch for wider testing as it no longer causes my Nuvi to barf. What it does is remove routing nodes from ways that should never have been put there in the first place. Without this patch, a routable way will have a node for each of its points that are shared by any other way (whether the other ways are routable or not). For example, at the moment, if a way shares its points with a boundary line or shape, each of those points will become nodes. From the routing point of view, that's (essentially) harmless but having extra nodes does take up space and must slow down the routing calculation. It therefore makes sense to remove the bogus nodes. What this patch does is defer the processing of all of the points/lines/shapes until after their types have been computed. Having computed the ways' types we know what's routable and what isn't so nodes only need to be created where routable ways meet. That's the theory, in practice, it produces slightly smaller maps. Whether it actually improves the routing quality is yet to be determined. Obviously, the gain you will see depends on how many bogus nodes are in your maps. All feedback welcome. Mark
Hi Mark, in general i like this idea. Removing superfluos nodes also improves the dp filter, as it can remove more nodes. I would be very pleased, if with this patch it would be possible to store the information of the resolution of the GType in the nodes. Do you think it is possible? This would help me very much with the missing part of the dp filter. But now I am a little confused with the incHighwayCounter function. I see that it is used in different situations to mark a point as a node, e.g. border nodes, street end nodes or splitting nodes. Would this work after your patch? Also I think the highway count gets counted up while importing, afterwards it is set to zero and then counted up again. Could the first step be ommited? Last comment: I think, but am not sure, that with this large lists (>10000) a LinkedList<> performs much better than a ArrayList<>. Would need some testing. Regards, Johann Mark Burton schrieb:
With the recent reversion of the Table A breakage, it's now useful to post this patch for wider testing as it no longer causes my Nuvi to barf.
What it does is remove routing nodes from ways that should never have been put there in the first place. Without this patch, a routable way will have a node for each of its points that are shared by any other way (whether the other ways are routable or not). For example, at the moment, if a way shares its points with a boundary line or shape, each of those points will become nodes. From the routing point of view, that's (essentially) harmless but having extra nodes does take up space and must slow down the routing calculation.
It therefore makes sense to remove the bogus nodes.
What this patch does is defer the processing of all of the points/lines/shapes until after their types have been computed. Having computed the ways' types we know what's routable and what isn't so nodes only need to be created where routable ways meet.
That's the theory, in practice, it produces slightly smaller maps.
Whether it actually improves the routing quality is yet to be determined.
Obviously, the gain you will see depends on how many bogus nodes are in your maps.
All feedback welcome.
Mark
------------------------------------------------------------------------
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Johann, Sorry for not replying sooner, I have been concentrating on fixing the bug that Felix unearthed.
in general i like this idea. Removing superfluos nodes also improves the dp filter, as it can remove more nodes. I would be very pleased, if with this patch it would be possible to store the information of the resolution of the GType in the nodes. Do you think it is possible? This would help me very much with the missing part of the dp filter.
Not 100% sure exactly what you want storing in the nodes. However, in principle, we can store what we like as long as we don't mind the space overhead.
But now I am a little confused with the incHighwayCounter function. I see that it is used in different situations to mark a point as a node, e.g. border nodes, street end nodes or splitting nodes. Would this work after your patch?
Yes, I certainly hope so.
Also I think the highway count gets counted up while importing, afterwards it is set to zero and then counted up again. Could the first step be ommited?
The highway counts simply track how many ways reference each point. If a point has a highway count > 1 then it's a candidate for being a routing node. At the moment, that info is used in the OSM input class to do the short arc removal. That can only be done when all the ways/relations/nodes have been read in. I think that all of the processing from the reading of the XML to the point where the map objects are added to the map could do with refactoring to simplify how it works and to remove redundant operations. However, that's a big job and as what we currently have basically works pretty well, it will have to wait until someone has enough free time to work on it. Personally, I would rather spend time working on adding new features and improving the routing quality. So yes, to answer your question, almost certainly the highway counting code could be refactored to only do it once. Mind you, even with very big tiles the highway counting introduced by this patch in StyledConverter takes of the order of 1 second to do so it's not a big overhead.
Last comment: I think, but am not sure, that with this large lists (>10000) a LinkedList<> performs much better than a ArrayList<>. Would need some testing.
I guess that rather depends on how the list is grown when the array fills up. If it gets doubled in size then it won't need to be reallocated a lot of times. The downside of the linked list is probably just that it will take up a lot more space. However, these lists get thrown away as soon as the ways have been processed. If you want to see if linked lists go quicker, please let us know the results. Cheers, Mark
Mark Burton wrote:
With the recent reversion of the Table A breakage, it's now useful to post this patch for wider testing as it no longer causes my Nuvi to barf.
What it does is remove routing nodes from ways that should never have been put there in the first place. Without this patch, a routable way will have a node for each of its points that are shared by any other way (whether the other ways are routable or not). For example, at the moment, if a way shares its points with a boundary line or shape, each of those points will become nodes. From the routing point of view, that's (essentially) harmless but having extra nodes does take up space and must slow down the routing calculation.
It therefore makes sense to remove the bogus nodes.
What this patch does is defer the processing of all of the points/lines/shapes until after their types have been computed. Having computed the ways' types we know what's routable and what isn't so nodes only need to be created where routable ways meet.
That's the theory, in practice, it produces slightly smaller maps.
Whether it actually improves the routing quality is yet to be determined.
Obviously, the gain you will see depends on how many bogus nodes are in your maps.
All feedback welcome.
Just trying it out. I'm allways eager to see routing improvemtns. However can't get my maps to compile: java.lang.AssertionError: Point in way Achenseeschiffahrt ferry (http://www.openstreetmap.org/browse/way/35958231) has zero highway count at http://www.openstreetmap.org/?lat=47.42624&lon=11.72947&zoom=17 at uk.me.parabola.mkgmap.osmstyle.StyledConverter.addRoadWithoutLoops(StyledConverter.java:1287) at uk.me.parabola.mkgmap.osmstyle.StyledConverter.addRoadAfterSplittingLoops(StyledConverter.java:1055) at uk.me.parabola.mkgmap.osmstyle.StyledConverter.addRoad(StyledConverter.java:983) at uk.me.parabola.mkgmap.osmstyle.StyledConverter.convertWay(StyledConverter.java:287) at uk.me.parabola.mkgmap.reader.osm.xml.Osm5XmlHandler.endDocument(Osm5XmlHandler.java:563) at com.sun.org.apache.xerces.internal.parsers.AbstractSAXParser.endDocument(Unknown Source) at com.sun.org.apache.xerces.internal.xinclude.XIncludeHandler.endDocument(Unknown Source) at com.sun.org.apache.xerces.internal.impl.XMLDocumentFragmentScannerImpl.scanDocument(Unknown Source) at com.sun.org.apache.xerces.internal.parsers.XML11Configuration.parse(Unknown Source) at com.sun.org.apache.xerces.internal.parsers.XML11Configuration.parse(Unknown Source) at com.sun.org.apache.xerces.internal.parsers.XMLParser.parse(Unknown Source) at com.sun.org.apache.xerces.internal.parsers.AbstractSAXParser.parse(Unknown Source) at com.sun.org.apache.xerces.internal.jaxp.SAXParserImpl$JAXPSAXParser.parse(Unknown Source) at javax.xml.parsers.SAXParser.parse(Unknown Source) at javax.xml.parsers.SAXParser.parse(Unknown Source) at uk.me.parabola.mkgmap.reader.osm.xml.Osm5MapDataSource.load(Osm5MapDataSource.java:81) at uk.me.parabola.mkgmap.main.MapMaker.loadFromFile(MapMaker.java:148) at uk.me.parabola.mkgmap.main.MapMaker.makeMap(MapMaker.java:56) at uk.me.parabola.mkgmap.main.Main$1.call(Main.java:187) at uk.me.parabola.mkgmap.main.Main$1.call(Main.java:185) at java.util.concurrent.FutureTask$Sync.innerRun(Unknown Source) at java.util.concurrent.FutureTask.run(Unknown Source) at java.util.concurrent.ThreadPoolExecutor$Worker.runTask(Unknown Source) at java.util.concurrent.ThreadPoolExecutor$Worker.run(Unknown Source) at java.lang.Thread.run(Unknown Source) Exiting - if you want to carry on regardless, use the --keep-going option
Mark
------------------------------------------------------------------------
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Felix,
Just trying it out. I'm allways eager to see routing improvemtns. However can't get my maps to compile:
java.lang.AssertionError: Point in way Achenseeschiffahrt ferry (http://www.openstreetmap.org/browse/way/35958231) has zero highway count at http://www.openstreetmap.org/?lat=47.42624&lon=11.72947&zoom=17
Sorry it's failed so soon. Do you have any style magic you are using that affects that ferry route? I can process the map without problems using, essentially, the default style files. I notice that the way's name comes from the relation and not the way itself. Are you doing that with some style stuff? Cheers, Mark
Mark Burton wrote:
Hi Felix,
Just trying it out. I'm allways eager to see routing improvemtns. However can't get my maps to compile:
java.lang.AssertionError: Point in way Achenseeschiffahrt ferry (http://www.openstreetmap.org/browse/way/35958231) has zero highway count at http://www.openstreetmap.org/?lat=47.42624&lon=11.72947&zoom=17
Sorry it's failed so soon.
Do you have any style magic you are using that affects that ferry route? I can process the map without problems using, essentially, the default style files.
I notice that the way's name comes from the relation and not the way itself. Are you doing that with some style stuff?
I just compiled clean when deleting ferries from my style-file. Here's the lines I had to comment out: # route1=ferry { name '${name1}'; set toll=yes } [0x06 road_class=1 road_speed=0 resolution 18 continue] # route=ferry { name '${name} ferry' | 'ferry'; set toll=yes } [0x06 road_class=1 road_speed=0 resolution 18 continue] route1=ferry are ferries from relations. Did not notice any improvements on autorouting so far however (only tried in Mapsource).
Cheers,
Mark _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Felix,
Here's the lines I had to comment out:
# route1=ferry { name '${name1}'; set toll=yes } [0x06 road_class=1 road_speed=0 resolution 18 continue] # route=ferry { name '${name} ferry' | 'ferry'; set toll=yes } [0x06 road_class=1 road_speed=0 resolution 18 continue]
route1=ferry are ferries from relations.
I can't see what's wrong at the moment. In your style file do any other rules match the ferry route (will any other lines be output for it?)
Did not notice any improvements on autorouting so far however (only tried in Mapsource).
You may see some improvement where routable ways share a lot of points with areas and other unroutable lines. Mark
Mark Burton wrote:
Felix,
Here's the lines I had to comment out:
# route1=ferry { name '${name1}'; set toll=yes } [0x06 road_class=1 road_speed=0 resolution 18 continue] # route=ferry { name '${name} ferry' | 'ferry'; set toll=yes } [0x06 road_class=1 road_speed=0 resolution 18 continue]
route1=ferry are ferries from relations.
I can't see what's wrong at the moment. In your style file do any other rules match the ferry route (will any other lines be output for it?)
Well I don't explicitly search for anything else with "& route=ferry". However I match the ferry itself two times. First time I match the ferry via relations file, the second time I match the way itself. No other rule matches. Here's my relations file entry: route=ferry & name=* { apply { set name1 = '${name} ferry' | 'ferry'; add fromrelation=yes; add route1=ferry; set toll=yes } } route=ferry { apply { add fromrelation=yes; add route=ferry; set toll=yes } }
Did not notice any improvements on autorouting so far however (only tried in Mapsource).
You may see some improvement where routable ways share a lot of points with areas and other unroutable lines.
The crazy thing is that routing works less well. Maybe my introducing of identical copies of the ways for displaying like routes and cycleway=* improves routing on such ways?
Mark _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Mark Burton wrote:
Felix,
Here's the lines I had to comment out:
# route1=ferry { name '${name1}'; set toll=yes } [0x06 road_class=1 road_speed=0 resolution 18 continue] # route=ferry { name '${name} ferry' | 'ferry'; set toll=yes } [0x06 road_class=1 road_speed=0 resolution 18 continue]
route1=ferry are ferries from relations.
I can't see what's wrong at the moment. In your style file do any other rules match the ferry route (will any other lines be output for it?)
It seems that there is a problem if you output two times a routable object. I removed the "double ferry" action and at that place it compiled fine. It would then crash here however: http://www.openstreetmap.org/edit?lat=48.50799&lon=13.73188&zoom=17 I did not correct the ferry, but some fool has put highway=cycleway & route=ferry on the same way - probably to have autorouting over the ferry as he thinks it's part of the Donauradweg. (plus I match of course the unroutable cycleway=lane; which has nothing to do on a ferry either). So this patch will crash if you use continue on route=ferry and afterwards have highway=cycleway routable.
Did not notice any improvements on autorouting so far however (only tried in Mapsource).
You may see some improvement where routable ways share a lot of points with areas and other unroutable lines.
Mark _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Felix, thanks for the high quality feedback - new patch has been posted. Cheers, Mark
Mark Burton wrote:
Hi Felix,
Just trying it out. I'm allways eager to see routing improvemtns. However can't get my maps to compile:
java.lang.AssertionError: Point in way Achenseeschiffahrt ferry (http://www.openstreetmap.org/browse/way/35958231) has zero highway count at http://www.openstreetmap.org/?lat=47.42624&lon=11.72947&zoom=17
Sorry it's failed so soon.
Do you have any style magic you are using that affects that ferry route? I can process the map without problems using, essentially, the default style files.
I notice that the way's name comes from the relation and not the way itself. Are you doing that with some style stuff?
Just as a follow up, I noticed that the v8 patch (simplify ...) - actually routing over long distances in Mapsource became worse. Some routes I can calculate without using this patch, don't calculate with the patch anymore.
Cheers,
Mark _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Just as a follow up, I noticed that the v8 patch (simplify ...) - actually routing over long distances in Mapsource became worse. Some routes I can calculate without using this patch, don't calculate with the patch anymore.
This is a point I absolutely not understand. The merge filter works only at levels 23...0 (not 24!) and merges the ways after the routing tables are generated. There should be no references from the routing tables to the lines at lower resolutions. So why routing is influenced?
Hi Felix (cc Johann)
Just as a follow up, I noticed that the v8 patch (simplify ...) - actually routing over long distances in Mapsource became worse. Some routes I can calculate without using this patch, don't calculate with the patch anymore.
You posted this comment with a subject line related to "remove bogus nodes" but I guess you're really talking about the latest patch from Johann. If you're saying that with that patch some long distance routing is broken it doesn't surprise me. I haven't looked at the patch in detail but my initial impression is that it can't work because it joins up line segments that "belong" to different roads. Here's my reasoning: Basically, each routable road generates 2 data items: 1 - the routing data (nodes and arcs used to calculate routes) 2 - the graphical line data (what you see on the screen) So if a route across the country uses, say, 4 different roads (for this discussion assume the roads just connect one end to the other without side roads) then there will be 4 arcs in the route. On the screen, the line segments for the 4 roads will be displayed. There is a one-to-one correspondence between the displayed lines and the underlying routing arcs. In fact, there is a real linkage between the line data and the routing info. The simplify patch in it's current form reduces the number of drawn lines by merging the graphical line data. It doesn't (unless I am mistaken) merge the routing information. So now there is no-longer a one-to-one correspondence between the displayed line(s) and the underlying routing arcs. Imagine that in our 4 road route, the 3 following roads are merged into the first. So now we have 1 graphical entity but we still have 4 arcs. The linkage from the remaining line relates to the 1st arc only even though the graphical line spans the whole route. As I said, I haven't studied the patch in detail. I could be wrong. Cheers, Mark
Mark Burton wrote:
Hi Felix (cc Johann)
Just as a follow up, I noticed that the v8 patch (simplify ...) - actually routing over long distances in Mapsource became worse. Some routes I can calculate without using this patch, don't calculate with the patch anymore.
You posted this comment with a subject line related to "remove bogus nodes" but I guess you're really talking about the latest patch from Johann.
No Johanns (v8) patch actually improves long distance routing (2-3 additional turns), while the remove bogus roads makes long distance routing worse for me (3-4 turns less). Sorry for the wrong text. I have no clue why the remove bogus nodes makes routing worse. v3 actually is great insofar as it allows several routable roads with different speed, but so far I have not been able to make such ways opposing oneways - but they are different speed. Currently playing around to find out how I can trick it into two opposing oneways (while the oneway is "artificial" in both directions in so far that I use incomplete rules to set it up).
If you're saying that with that patch some long distance routing is broken it doesn't surprise me. I haven't looked at the patch in detail but my initial impression is that it can't work because it joins up line segments that "belong" to different roads. Here's my reasoning:
Basically, each routable road generates 2 data items:
1 - the routing data (nodes and arcs used to calculate routes)
2 - the graphical line data (what you see on the screen)
So if a route across the country uses, say, 4 different roads (for this discussion assume the roads just connect one end to the other without side roads) then there will be 4 arcs in the route. On the screen, the line segments for the 4 roads will be displayed. There is a one-to-one correspondence between the displayed lines and the underlying routing arcs. In fact, there is a real linkage between the line data and the routing info.
The simplify patch in it's current form reduces the number of drawn lines by merging the graphical line data. It doesn't (unless I am mistaken) merge the routing information. So now there is no-longer a one-to-one correspondence between the displayed line(s) and the underlying routing arcs.
Imagine that in our 4 road route, the 3 following roads are merged into the first. So now we have 1 graphical entity but we still have 4 arcs. The linkage from the remaining line relates to the 1st arc only even though the graphical line spans the whole route.
As I said, I haven't studied the patch in detail. I could be wrong.
Cheers,
Mark _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Felix,
No Johanns (v8) patch actually improves long distance routing (2-3 additional turns), while the remove bogus roads makes long distance routing worse for me (3-4 turns less). Sorry for the wrong text.
OK, thanks for clarifying that. My comments in the last message can therefore be totally ignored. Mind you, I still don't understand how the simplify way patch can work correctly. Perhaps it's time I actually tried it out.
I have no clue why the remove bogus nodes makes routing worse. v3 actually is great insofar as it allows several routable roads with different speed, but so far I have not been able to make such ways opposing oneways - but they are different speed. Currently playing around to find out how I can trick it into two opposing oneways (while the oneway is "artificial" in both directions in so far that I use incomplete rules to set it up).
The change that v3 introduced could be retro-fitted to trunk as it's essentially independent of the bogus node removal. Cheers, Mark
Mark Burton wrote:
Hi Felix,
No Johanns (v8) patch actually improves long distance routing (2-3 additional turns), while the remove bogus roads makes long distance routing worse for me (3-4 turns less). Sorry for the wrong text.
OK, thanks for clarifying that. My comments in the last message can therefore be totally ignored. Mind you, I still don't understand how the simplify way patch can work correctly. Perhaps it's time I actually tried it out.
I have no clue why the remove bogus nodes makes routing worse. v3 actually is great insofar as it allows several routable roads with different speed, but so far I have not been able to make such ways opposing oneways - but they are different speed. Currently playing around to find out how I can trick it into two opposing oneways (while the oneway is "artificial" in both directions in so far that I use incomplete rules to set it up).
The change that v3 introduced could be retro-fitted to trunk as it's essentially independent of the bogus node removal.
I don't know what's the difference between patch v3 and patch v2, but v3 makes no practical improvement. Yes it sets the different speeds and road_class for 0x01 and 0x02, but impossible to set different restrictions, they are simply dropped. The following example does output both 0x01 and 0x02 with their respective speeds, but does not set emergency=no, does not set oneway=no, nor taxi=no: / highway=* & copy=99 [0x01 road_class=2 road_speed=2 resolution 24 continue] highway=* & copy=98 [0x01 road_class=2 road_speed=2 resolution 24 continue] highway=path { set oneway=no; set emergency=no; set taxi=no } [0x02 road_class=0 road_speed=0 resolution 24]/ The way in question is a path - I just use this quick example because when it works, I probably have to put 5-6 hours time into rewriting my style-file, so I just use this as a test scenario. With the restrictions not enacted on the simple highway=path rule, the different speeds and road classes are only usable insofar as it could be used to have slow ways on top of fast ways so if the GPS/Mapsource thinks the quick way means too much penalty time for turning, the slow way could be chosen. In reality I think that use will not help a lot (though could be interesting to try out for special cases, like motorway junctions) - because in 99% of all cases the way with higher road_speed will be chosen.
Cheers,
Mark _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Felix,
I don't know what's the difference between patch v3 and patch v2, but v3 makes no practical improvement. Yes it sets the different speeds and road_class for 0x01 and 0x02, but impossible to set different restrictions, they are simply dropped.
Having made a complete fool of myself once tonight, I may as well try again.. That's because the restrictions are stored as tags in the way/node and not in the GType. All the tags in the way will be visible for each map object that is generated from that way. With the "remove bogus nodes" patch in its current form, that can't be avoided because all of the nodes/ways are processed by the rules before any map objects are generated. If the way was duplicated before the rules were processed, what you are trying to do could work better. I will make a patch for trunk that duplicates the ways/nodes before the style processing and let's see what good that does. Standby... Mark
Mark Burton wrote:
Standby...
Attached, completely untested, probably destroy the universe...
not destroying anything, but also not helping. Restrictions are still set by the first way (using continue) the second routable way restrictions set via {} are not enacted. Oneway also not changed.
------------------------------------------------------------------------
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Felix,
not destroying anything, but also not helping. Restrictions are still set by the first way (using continue) the second routable way restrictions set via {} are not enacted. Oneway also not changed.
Well, I tried an example like yours but could not get any sense out of it at all. Problem is, I haven't a clue how the style rules work and I don't think I ever will - my brain is missing the neurons required to perceive and understand that stuff. Sorry. Mark
Mark Burton wrote:
Felix,
I don't know what's the difference between patch v3 and patch v2, but v3 makes no practical improvement. Yes it sets the different speeds and road_class for 0x01 and 0x02, but impossible to set different restrictions, they are simply dropped.
Having made a complete fool of myself once tonight, I may as well try again..
That's because the restrictions are stored as tags in the way/node and not in the GType. All the tags in the way will be visible for each map object that is generated from that way.
With the "remove bogus nodes" patch in its current form, that can't be avoided because all of the nodes/ways are processed by the rules before any map objects are generated. If the way was duplicated before the rules were processed, what you are trying to do could work better.
I will make a patch for trunk that duplicates the ways/nodes before the style processing and let's see what good that does.
Standby...
That would be awesome. BTW the v8 patch really improves both map panning on my etrex, as well as routing (though again pretty strange why it does because it changes nothing at resolution 24), my only guess is that the limitation of memory on the etrex (but also in Mapsource which does seem to try to use as few memory as possible for routing - maybe because it tries to mimic routing behavior on GPS, even though modern Nuvis route much better) and also Mapsource means the less detailed the map, the better the routing. If this were the case then maybe maps only containing resolution=24 would route better - could be worth a try. I think Mapsource 6.16 will improve routing which would be really great, because one can then use WinGDB and fix the routing behavior with additional nodes every X km (intelligently) for the GPS so that it can recalculate a route. Noticed you new patch just poppin in, will try out ASAP.
Mark _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Mark Burton schrieb:
Hi Felix (cc Johann)
Just as a follow up, I noticed that the v8 patch (simplify ...) - actually routing over long distances in Mapsource became worse. Some routes I can calculate without using this patch, don't calculate with the patch anymore.
You posted this comment with a subject line related to "remove bogus nodes" but I guess you're really talking about the latest patch from Johann.
'v8 patch (simplify) is really missleading. I too was unsure, which patch you meant.
If you're saying that with that patch some long distance routing is broken it doesn't surprise me. I haven't looked at the patch in detail but my initial impression is that it can't work because it joins up line segments that "belong" to different roads. Here's my reasoning:
Basically, each routable road generates 2 data items:
1 - the routing data (nodes and arcs used to calculate routes)
2 - the graphical line data (what you see on the screen)
So if a route across the country uses, say, 4 different roads (for this discussion assume the roads just connect one end to the other without side roads) then there will be 4 arcs in the route. On the screen, the line segments for the 4 roads will be displayed. There is a one-to-one correspondence between the displayed lines and the underlying routing arcs. In fact, there is a real linkage between the line data and the routing info.
Thanks for explaining that in detail. I am fully aware of the fact, that there is a one to one linking between the routing data and the drawing data. But to my understanding, this linking exists only in resolution 24, not in lower resolutions. (Or is there really routing information with lower resolution?? I doubt that strongly.)
The simplify patch in it's current form reduces the number of drawn lines by merging the graphical line data. It doesn't (unless I am mistaken) merge the routing information. So now there is no-longer a one-to-one correspondence between the displayed line(s) and the underlying routing arcs.
Yes, you're right. My patch tries only to merge draing data. The initial intention was only to speedup drawing on the etrexes. I could not imagine how to merge routing data. In my opinion it should be absolutely not neccessary to 'merge' rounting data, as there should be no mergable arcs existing. If such nodes would exist, this would mean, that there is a arc connecting exactly two lines of same type. This would mean a node in the middle of road. This should not exist or at least filtered out in previous stages. (Ignoring the special case of splitted arcs)
Imagine that in our 4 road route, the 3 following roads are merged into the first. So now we have 1 graphical entity but we still have 4 arcs. The linkage from the remaining line relates to the 1st arc only even though the graphical line spans the whole route.
As I said, I haven't studied the patch in detail. I could be wrong.
Seems you missed the important fact, that the merging takes place only at resolutions <=23. As far as I understand the whole thing, line data at lower resolutions is used only for displaying. Please correct me, if I'm wrong. In this case the merging would have to take place before generating of routing tables. Another coder has tried it (can't find the thread at the moment), but this is also unfinished work. Regards, Johann
Hi Johann, Thanks for taking the time to explain your patch.
Seems you missed the important fact, that the merging takes place only at resolutions <=23. As far as I understand the whole thing, line data at lower resolutions is used only for displaying.
Yes, I missed that crucial point. I really should have studied the code more before opening my mouth.
Please correct me, if I'm wrong.
I'm sure you're right. It's me that's on the wrong planet. Cheers, Mark
Johann Gail wrote:
Mark Burton schrieb:
Hi Felix (cc Johann)
Just as a follow up, I noticed that the v8 patch (simplify ...) - actually routing over long distances in Mapsource became worse. Some routes I can calculate without using this patch, don't calculate with the patch anymore.
You posted this comment with a subject line related to "remove bogus nodes" but I guess you're really talking about the latest patch from Johann.
'v8 patch (simplify) is really missleading. I too was unsure, which patch you meant.
If you're saying that with that patch some long distance routing is broken it doesn't surprise me. I haven't looked at the patch in detail but my initial impression is that it can't work because it joins up line segments that "belong" to different roads. Here's my reasoning:
Basically, each routable road generates 2 data items:
1 - the routing data (nodes and arcs used to calculate routes)
2 - the graphical line data (what you see on the screen)
So if a route across the country uses, say, 4 different roads (for this discussion assume the roads just connect one end to the other without side roads) then there will be 4 arcs in the route. On the screen, the line segments for the 4 roads will be displayed. There is a one-to-one correspondence between the displayed lines and the underlying routing arcs. In fact, there is a real linkage between the line data and the routing info.
Thanks for explaining that in detail. I am fully aware of the fact, that there is a one to one linking between the routing data and the drawing data. But to my understanding, this linking exists only in resolution 24, not in lower resolutions. (Or is there really routing information with lower resolution?? I doubt that strongly.)
I actually think that one should even thing about simplifying routable ways at resolution=24. Especially those that directly originate from GPS tracks (that will be difficult to find out though), maybe only if nodes are closer than 20m over longer distances. So say 6 nodes in 60m okay, 20 nodes over 200m simplify because it seems to originate directly from a track. Often people put nodes on curves very close to each other, I think one would have to experiment whether routing works better if those nodes are simplified (maybe only for routing, but not for display?). I noticed that some Garmin maps display 1:1 to openstreetmap data, but on route calculation show up to 10% shorter distance. Maybe here only routing nodes are simplifed (straighter line).
The simplify patch in it's current form reduces the number of drawn lines by merging the graphical line data. It doesn't (unless I am mistaken) merge the routing information. So now there is no-longer a one-to-one correspondence between the displayed line(s) and the underlying routing arcs.
Yes, you're right. My patch tries only to merge draing data. The initial intention was only to speedup drawing on the etrexes. I could not imagine how to merge routing data. In my opinion it should be absolutely not neccessary to 'merge' rounting data, as there should be no mergable arcs existing. If such nodes would exist, this would mean, that there is a arc connecting exactly two lines of same type. This would mean a node in the middle of road. This should not exist or at least filtered out in previous stages. (Ignoring the special case of splitted arcs)
Imagine that in our 4 road route, the 3 following roads are merged into the first. So now we have 1 graphical entity but we still have 4 arcs. The linkage from the remaining line relates to the 1st arc only even though the graphical line spans the whole route.
As I said, I haven't studied the patch in detail. I could be wrong.
Seems you missed the important fact, that the merging takes place only at resolutions <=23. As far as I understand the whole thing, line data at lower resolutions is used only for displaying. Please correct me, if I'm wrong. In this case the merging would have to take place before generating of routing tables. Another coder has tried it (can't find the thread at the moment), but this is also unfinished work.
Regards, Johann
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
I actually think that one should even thing about simplifying routable ways at resolution=24. Especially those that directly originate from GPS tracks (that will be difficult to find out though), maybe only if nodes are closer than 20m over longer distances. So say 6 nodes in 60m okay, 20 nodes over 200m simplify because it seems to originate directly from a track. Often people put nodes on curves very close to each other,
Yes, I know such ways. You could see at a glance, that this ways are directly converted from gps tracks. This would be well handled be the dp filter. But as Mark has explained very well, at the lowest level is a one to one linking with rounting data. In the very first playings with the dp filter I enabled it in resolution 24 too, but destroyed routing completely. I think it is not immposible, but a very complex task to do. The routing tables would have to be modified afterwards. Out of scope at the moment, sorry. :-)
I think one would have to experiment whether routing works better if those nodes are simplified (maybe only for routing, but not for display?). The dp improves only displaying. Full stop. At least it is supposed to do. :-) Its nice, if you tells me it improves routing too. But I dont understand how it happens. Maybe it is a side effect of the smaller drwaing data, leaving more space for routing data, so that less routing centers are needed? I really don't know.
I noticed that some Garmin maps display 1:1 to openstreetmap data, but on route calculation show up to 10% shorter distance. Maybe here only routing nodes are simplifed (straighter line).
Sorry, could you explain in more detail? I'm not sure what you mean here. 'Simplifiing routing nodes' is the thing, which tries Mark with his bogus node patch.
Hi Felix, What I don't understand is how the ferry route in your original bug report was generating multiple routable ways. It's not tagged as being a cycleway. I guess that your style rules must have matched it twice and both times set the road class or speed. Mark
Felix, Another thought: The current code will probably not work as expected if you generate any lines (most likely routable lines, but could also be long non-routable line) that are split and you then go on to generate more lines (routable or not) from the same way. The problem is that once the way is split, the original way only has the points from the beginning to the split point, all the other points will be missing. This is not a new issue, it's always been like that. So, trying to generate multiple routable ways from the same way is currently doomed to failure unless the way is very short/simple. Perhaps we should copy the list of points in the way before processing it so the original list doesn't get modified. Cheers, Mark
Mark Burton wrote:
Felix,
Another thought:
The current code will probably not work as expected if you generate any lines (most likely routable lines, but could also be long non-routable line) that are split and you then go on to generate more lines (routable or not) from the same way.
The problem is that once the way is split, the original way only has the points from the beginning to the split point, all the other points will be missing.
This is not a new issue, it's always been like that. So, trying to generate multiple routable ways from the same way is currently doomed to failure unless the way is very short/simple.
Perhaps we should copy the list of points in the way before processing it so the original list doesn't get modified.
Cheers,
Mark
I had two routable ferry lines, because I wanted to have both names show up (which was not working anyhow) of a) the ferry relation, and b) the ferry "way". Therefore both came up. Before the patch, having two routable lines worked out in identical copies. So the first time road_speed/class/oneway was set, it got taken over on all copies - at least according to gpsmapedit (you have to be on level=0, res=24 to see the details, otherwise it always shows 0/0). It would be super great to have the ability to include different routable ways on top of each other (i.e. different speed for different restrictions, or different speed if using a cycleway=opposite against the direction of the general traffic flow). For car autorouting I am sure someone could also come up with examples how it could be useful. The easiest way to achieve this IMHO would be to have a file called lines2, that after lines has been completed, will be run again against all lines just like lines file, as if "lines" would not exist.
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
participants (3)
-
Felix Hartmann -
Johann Gail -
Mark Burton