[mkgmap-dev] [PATCH v4] - min arc length fixes

Thu Aug 13 17:51:34 BST 2009

2009/8/13 Mark Burton <markb at 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 at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20090813/257ff071/attachment.html 