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

Fri Aug 28 00:18:05 BST 2009

v5 

in case people are still using this patch, i have reissued it without 
the stuff that is now in commit 1152.

if you are using this patch and think it should also be committed -
please say - it didn't seem conclusive that is was useful when we last
discussed it

-----------------

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mb-min-arc-length-v5.patch
Type: text/x-patch
Size: 8783 bytes
Desc: not available
Url : http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20090828/6881d608/attachment.bin 