v4 I have gone back to the original ordering of doing short arc removal before clipping as the previous version of this patch badly broke polygons As for arcs whose length is less 5m, I am not convinced they are actually a problem as far as routing is concerned as my tests show that mapsource can happily route through zero length arcs that occur at tile boundaries. It would be good if people who have been obliged to use a minimum arc length of > 0 would provide examples of where the routing is broken. i.e. without using this patch, find an example which doesn't route when --remove-short-arcs is specified but will route when --remove-short-arcs=5 is specified. What is still an issue and was discussed a while ago is the problem where routing will fail (or produce a big diversion) when routing out of one tile into another and then back to a destination in the first tile. That never seems to work, short arcs or not. -------------------- v3 This patch is getting serious! To reduce the number of short arcs that are being generated at tile boundaries, this now clips the ways before the short arc removal is done. However, it isn't a perfect solution because some map data is very hard to deal with: a - If a way crosses a tile boundary right in the corner such that both ends are clipped and the resulting sub-way is less than 5m long, it will fail to fix that. A possible workaround could be to introduce extra points to elongate the arc. b - a much more common problem is where a way forks very close to a tile boundary and more than one of the connected ways cross the boundary so you end up with several boundary nodes that should be merged to remove the short arc(s) but they can't be moved as they are boundary nodes! I believe that this could be fixed by not merging the forking node but, instead, moving it away from the boundary such that the ways connected to it that do cross the boundary are not less than 5m long! Alternatively, adding extra points to elongate the forking arcs could be done. With this patch, I processed a 14 tile map of the Netherlands and it produced 21 of these short arc errors (all due to forks close to the tile boundaries). I then tested the routing at 5 of these positions (using mapsource) and only 1 of the 5 showed any sign of breakage, the other 4 all routed happily in all directions. The one that was broken was a junction of three ways and one pair of the ways had no connectivity but the others were ok. On the upside, the patch removed 147 short arcs introduced by the clipping. So more work is required here to fix the corner cases (ha ha) but please test this patch anyway as I expect it to have problems due to the big change it has introduced. As usual, all feedback is appreciated. ---------------- v2 of this patch not only enables remove-short-arcs by default when routing is in use (as previously discussed on ML) but it also fixes some problems in the way splitting code. I would be grateful if people could test this patch because it could possibly cure some routing failures. Cheers, Mark
2009/8/13 Mark Burton <markb@ordern.com>
v4
I have gone back to the original ordering of doing short arc removal before clipping as the previous version of this patch badly broke polygons
As for arcs whose length is less 5m, I am not convinced they are actually a problem as far as routing is concerned as my tests show that mapsource can happily route through zero length arcs that occur at tile boundaries.
It would be good if people who have been obliged to use a minimum arc length of > 0 would provide examples of where the routing is broken. i.e. without using this patch, find an example which doesn't route when --remove-short-arcs is specified but will route when --remove-short-arcs=5 is specified.
it is difficult to find those places, I just noticed that I can sometimes route over longer distances, and that sometimes the chosen route is slightly different. I did not have any complete breakages like when discovering the short arc problem in the beginning (which was a street cupped because it was only 4m long)
What is still an issue and was discussed a while ago is the problem where routing will fail (or produce a big diversion) when routing out of one tile into another and then back to a destination in the first tile. That never seems to work, short arcs or not.
--------------------
v3
This patch is getting serious!
To reduce the number of short arcs that are being generated at tile boundaries, this now clips the ways before the short arc removal is done. However, it isn't a perfect solution because some map data is very hard to deal with:
a - If a way crosses a tile boundary right in the corner such that both ends are clipped and the resulting sub-way is less than 5m long, it will fail to fix that. A possible workaround could be to introduce extra points to elongate the arc.
b - a much more common problem is where a way forks very close to a tile boundary and more than one of the connected ways cross the boundary so you end up with several boundary nodes that should be merged to remove the short arc(s) but they can't be moved as they are boundary nodes! I believe that this could be fixed by not merging the forking node but, instead, moving it away from the boundary such that the ways connected to it that do cross the boundary are not less than 5m long! Alternatively, adding extra points to elongate the forking arcs could be done.
With this patch, I processed a 14 tile map of the Netherlands and it produced 21 of these short arc errors (all due to forks close to the tile boundaries). I then tested the routing at 5 of these positions (using mapsource) and only 1 of the 5 showed any sign of breakage, the other 4 all routed happily in all directions. The one that was broken was a junction of three ways and one pair of the ways had no connectivity but the others were ok.
On the upside, the patch removed 147 short arcs introduced by the clipping.
So more work is required here to fix the corner cases (ha ha) but please test this patch anyway as I expect it to have problems due to the big change it has introduced.
As usual, all feedback is appreciated.
----------------
v2 of this patch not only enables remove-short-arcs by default when routing is in use (as previously discussed on ML) but it also fixes some problems in the way splitting code.
I would be grateful if people could test this patch because it could possibly cure some routing failures.
Cheers,
Mark
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
It would be good if people who have been obliged to use a minimum arc length of > 0 would provide examples of where the routing is broken. i.e. without using this patch, find an example which doesn't route when --remove-short-arcs is specified but will route when --remove-short-arcs=5 is specified. I am finding routing totally broken in Massachusetts; routes (etrex vista hcx) are computed apparently using the basemap. I have not tested enough to figure out why. Is anyone producing a routable map of mass? If so, please send me your splitter/mkgmap script. I think lambertus's maps did work at one point, but I'm not sure.
On Thu, Aug 13, 2009 at 8:52 PM, Greg Troxel<gdt@ir.bbn.com> wrote:
I am finding routing totally broken in Massachusetts; routes (etrex vista hcx) are computed apparently using the basemap. I have not tested enough to figure out why.
Which extract are you using (geofabrik, cloudmade?), and what command line options? If I have time, I'll try to reproduce. Cheers.
Clinton Gladstone <clinton.gladstone@googlemail.com> writes:
On Thu, Aug 13, 2009 at 8:52 PM, Greg Troxel<gdt@ir.bbn.com> wrote:
I am finding routing totally broken in Massachusetts; routes (etrex vista hcx) are computed apparently using the basemap. I have not tested enough to figure out why.
Which extract are you using (geofabrik, cloudmade?), and what command line options?
I am using the cloudmade extract from: http://downloads.cloudmade.com/north_america/united_states/massachusetts except now 12 august is available and I used 5 august. But it seems to be something about the data, not a bad extract - I think cloudmade's extracts are just fine. I most recently built with all 6 NE states (conn, ri, mass, vermont, new hampshire, maine) all together, invoking the script 'do-mkgmap' which follows as something like $ do-mkgmap *.osm.bz2 where I had symlinks for all 6 state .osm.bz2 in the directory where I invoked it, and have symlinks for splitter and mkgmap to jars I built with ant. I usually compute routes in mass, e.g. to work when driving there to see what happens, and they seem to use the basemap. I wondered if it was mass specific, so I picked a random place in vermont, and asked my etrex for a route. It got me onto 2W which is sensible, and then in vt seemed very sensible, but getting to 2 was by teleporting to a major highway, not using local roads, so I think it's using the basemap in Mass and then OSM data in Vermont. In OSM, Mass is very different from the other states. We have massgis data and they have tiger. massgis data is much better in most (all?) respects. It also has a ton of points at curvy sections of roads and parcels, rather than tiger's "nodes are a scarce resources; use only as many as you need to get close enough" ethic (which has some merit!), so I wouldn't be surprised if it provokes more issues. I do get a few warnings about remaining short arcs, but there are only about 5 of them. Also my test map (in script as well) works on the garmin but crashes roadtrip. All of this is on mac 10.5.x with java 1.6 installed, and I ran the most recent build wednesday night. Thanks for looking at this. ---------------------------------------- #!/bin/sh cd $HOME/OSM || exit 1 # rm all img/tdb/etc. rm -f *.img *.tdb INPUT=$* ## SPLIT INPUT MAPS if [ "$INPUT" != "" -o ! -f template.args ]; then rm -f 63*.osm.gz if [ "$INPUT" = "" ]; then INPUT=`ls *.osm.bz2` fi rm -f areas.list template.args* echo "SPLITTING $INPUT:" time \ java \ -enableassertions \ -Xmx2000m \ -jar splitter.jar \ --max-nodes=1600000 \ $INPUT \ > OUT.01.splitter 2>&1 cp -pf template.args template.args.orig ed template.args <<EOF g/^description:/d w EOF fi ## BUILD MAPS echo "BUILDING:" time \ java \ -enableassertions \ -Xmx2048m \ -jar mkgmap.jar \ --description="OSM_gdt" \ --country-abbr="US" \ --country-name="United States" \ --region-abbr="MA" \ --region-name="Massachusetts" \ --series-name="OSM_gdt_series" \ --family-id=401 \ --family-name="OSM_gdt_family" \ --product-id=13 \ --series-name="OSM_gdt_series" \ --area-name="OSM_gdt_area" \ --tdbfile \ --remove-short-arcs=6 \ --add-pois-to-areas \ --route \ -c template.args \ --gmapsupp \ > OUT.02.mkgmap 2>&1 echo OPTIONS not used: \ --overview-mapname=63240000 - test default claim \ --ignore-osm-bounds \ ## PREPARE GMAPI FORMAT FOR ROADMAP mkdir -p GMAPI echo "GMAPI:" time \ /Users/gdt/SOFTWARE/GMAPIBUILDER/gmapi-builder/gmapi-builder.py \ -o GMAPI \ -t 63240000.tdb \ -b 63240000.img \ -v 6324*.img \ > OUT.03.gmapi 2>&1 echo "test-map:all-elements" export BASE_LAT=42.0 export BASE_LONG=-70.0 time \ java \ -enableassertions \ -Xmx2048m \ -jar mkgmap.jar \ --overview-mapname=63500000 \ --mapname=63500001 \ --description="OSM_test" \ --country-abbr="US" \ --country-name="United States" \ --region-abbr="MA" \ --region-name="Massachusetts" \ --series-name="OSM_test_series" \ --family-id=402 \ --family-name="OSM_test_family" \ --product-id=14 \ --series-name="OSM_test_series" \ --area-name="OSM_test_area" \ --tdbfile \ test-map:all-elements > OUT.04.mkgmap 2>&1 mkdir -p GMAPI-TEST echo "GMAPI-TEST:" time \ /Users/gdt/SOFTWARE/GMAPIBUILDER/gmapi-builder/gmapi-builder.py \ -o GMAPI-TEST \ -t 63500000.tdb \ -b 63500000.img \ -v 6350*.img \ > OUT.05.gmapi-test 2>&1
On Fri, Aug 14, 2009 at 2:44 PM, Greg Troxel<gdt@ir.bbn.com> wrote:
I most recently built with all 6 NE states (conn, ri, mass, vermont, new hampshire, maine) all together, invoking the script 'do-mkgmap' which follows as something like
$ do-mkgmap *.osm.bz2
In this case, routing will not work across state boundaries. You know that though, right? I compiled Massachusetts and experimented with routing in Mapsource (I will try Roadtrip later). I found that routing only works for very short distances (even without crossing tile boundaries). For example, I tried the I95 around Boston. There, I could only route along segments which were less than 1 km long. It seemed, although I have not tested enough to confirm, that it was hardest routing along the more curved sections of highway. This would support the hypothesis that the node density is too high for proper routing. I have not had time to download the OSM data to take a look. I wonder if a way simplification patch could help here. I'm surprised that you were able to create routable maps using --max-nodes=1600000. I had to lower max nodes to 800000 in order to compile. Cheers.
I slurped most of I95 into josm and it's a bit of a mess. For example, The Northbound carriageway is disconnected at node 73082202 and just below that is a section of link road that's pointing in the wrong direction. Various spurious ways are lying around not connected to anything like they are left over from some previous version I did, however, manage to route over 50 km in both directions using mapsource so it can't be completely broken! Perhaps, the mappers should put some effort into cleaning up/validating the data? Cheers, Mark
Perhaps, the mappers should put some effort into cleaning up/validating the data? Absolutely we should. I had thought things were better than they seem to be. But computing routes on a dataset with problems should still 'work', where work means you get a route that's obviously nonoptimal. I will try smaller routes and try some local data fixups and see if I can find out more information about what's going wrong.
Mark Burton <markb@ordern.com> writes:
I slurped most of I95 into josm and it's a bit of a mess. For example, The Northbound carriageway is disconnected at node 73082202
Perhaps a town boundary - see below.
and just below that is a section of link road that's pointing in the wrong direction.
MassGIS data has the oneway property but not the direction. It was set randomly and is partially fixed. One of the reasons I want routing is to notice these problems - I have fixed a lot of them already.
Various spurious ways are lying around not connected to anything like they are left over from some previous version
That sounds worse than most areas, but agreed it needs fixing.
I did, however, manage to route over 50 km in both directions using mapsource so it can't be completely broken!
Some more data: I was able to route within a town. I found that on a highway between towns that the ways were not connected, and the ends that should have been had nodes with the same coordinates. Almost like boundary nodes at tile boundaries :-) "duplicate node, not connected" is an artifact of the MassGIS data which is segmented by town, so there are nodes more or less on the town border that are duplicated with disconnected ways. At this point I am convinced that 95%+ of my problem is bad data in Mass and not mkgmap. I withdraw my "routing broken in mass" complaint and will see where I am when the mass data is better - there may or may not be residual issues due to excessive node density, but hopefully not. Thanks for all the help and pointers.
Clinton Gladstone <clinton.gladstone@googlemail.com> writes:
On Fri, Aug 14, 2009 at 2:44 PM, Greg Troxel<gdt@ir.bbn.com> wrote:
I most recently built with all 6 NE states (conn, ri, mass, vermont, new hampshire, maine) all together, invoking the script 'do-mkgmap' which follows as something like
$ do-mkgmap *.osm.bz2
In this case, routing will not work across state boundaries. You know that though, right?
No, I didn't know that. But now that I think about, I think I can see why. Is the issue that the extracts are split with polygons and osmosis, and there is no overlap and synthetic nodes at the boundary? I wonder if the polygons overlapped enough to make sure that there was a node in common, if that would make things work. But that's almost certainly not the big issue - if I can get to where intrastate routing works in each state that would be great.
I compiled Massachusetts and experimented with routing in Mapsource (I will try Roadtrip later). I found that routing only works for very short distances (even without crossing tile boundaries). For example, I tried the I95 around Boston. There, I could only route along segments which were less than 1 km long.
I'll take a look, and also try shorter routes not on the motorways. MassGIS data has the one-way property but not the direction. I've straightened out a lot of 495 and 2 but not I95 (=MA128). So motorways are particularly likely to be trouble, compared to normal state highways or regular roads.
It seemed, although I have not tested enough to confirm, that it was hardest routing along the more curved sections of highway. This would support the hypothesis that the node density is too high for proper routing. I have not had time to download the OSM data to take a look. I wonder if a way simplification patch could help here.
I suppose I could run --remove-short-arcs with 20m. Or a new option that drops nodes within 50m as long as they only have 2 arcs and the resulting position of the midpoint doesn't move by more than 2m, or something like that.
I'm surprised that you were able to create routable maps using --max-nodes=1600000. I had to lower max nodes to 800000 in order to compile.
I didn't realize that 1600000 was too big. My machine has 4G ram with a heapsize of 2G. Is it safe to assume that if it completes without error that things fit? In Mass I think the ratio of nodes to ways is much higher than in other places, so perhaps that explains it. Thanks very much for looking into this - now I'm pretty sure that I'm not doing something dumb, and that digging into it more is sensible.
On Aug 14, 2009, at 14:44, Greg Troxel wrote:
Also my test map (in script as well) works on the garmin but crashes roadtrip.
You know, I tried this too, and noticed that the test map ( test- map:all-elements) also crashes Mapsource. Also in my tests, gmapi- builder.py displayed an "Unknown Block: 54" error when converting the map. Does this happen for you too? Here is the MapSource error: App: MapSource At: 8/14/2009 9:58:03 PM (UTC) OS: Windows XP Service Pack 3 Processor: x86, Processor Level: 6, Processors:2, Model: 23 Stepping: 10, RAM: 2097151 MPL_MAP.CPP-1250-6.13.6.0 Language ID: 1033 Part Number: 006-A0041-00 Build Type: Release Extra: Product id: 26345486 Map id: 63500001 Image: C:\users\blarg\My Documents\Documents\maps\mkgmap-test \63500001.img Record type: 4 Record: 0000: 00 00 00 00 08 00 6a 00 d8 ff 2f 00 00 66 2d 1e ......j.Øÿ/..f-. 0010: 00 2f a4 cd 00 00 f3 00 ff ff ff ff ff ff ff ff ./¤Í..ó.ÿÿÿÿÿÿÿÿ 0020: ff ff ff ff ff ff ff ff ff ff ff ff 00 00 00 00 ÿÿÿÿÿÿÿÿÿÿÿÿ.... 0030: ff ff 4d 00 ÿÿM. Error code: 3 mpl::Map_t::GetLabelAndId Point id: 6946824 Point lbl id: 3145688 Sub ID: 3
participants (4)
-
Clinton Gladstone -
Felix Hartmann -
Greg Troxel -
Mark Burton