[mkgmap-dev] Inter-tile routing failures - not all our fault?

Fri Aug 14 10:43:24 BST 2009

Hi Mark,

MB> The bug can easily be reproduced by finding a road on tile A that
MB> forks on one side of a boundary and both of the forkees? cross the
MB> boundary to tile B. You then try and route between the ways on tile
MB> B. Sometimes it works OK and sometimes not. Another example is
MB> simply where a road goes across a tile boundary and then back to the
MB> original tile.

Thanks for the clear example, I'll see what I can find when I get home. One 
thing I have noticed, especially with the more recent Garmin maps, is that 
they appear to have quite carefully handcrafted the tile boundaries such 
that it might be quite hard to find an example like this - possibly even 
because this problem is exactly what they're trying to circumvent!

MB> So, at this time, I can't imagine what we could be doing wrong to
MB> cause this but I can easily imagine how a routing algorithm could
MB> have problems when faced with non-trivial boundary crossings.

I tend to agree which is why I hope looking at the Garmin maps will shed 
some more light on the situation. However I can still imagine scenarios that 
would break the routing intermittently where the map might be at fault rather 
than the algorithm (or it could be a combination of the two). It could be 
a subtle alignment issue (similar to the tile problem I recently fixed(?) 
in the splitter). For example imagine trying to route from point 'a' in tile 
A to point 'c' in tile A, where passing through point 'b' in tile B should 
in theory be the optimal route. If there was a problem calculating how far 
tile B is offset from tile A, the routing algorithm might decide it's shorter 
to take a longer route that stays on tile A because it calculates that point 
'b' is a lot further away than it really is. If on the other hand you were 
trying to get to somewhere on tile B anyway, that extra distance has to be 
covered regardless, so the routing would suddenly appear to work.

Hope that example makes sense. Of course I have no idea how valid that particular 
theory is given I currently still know nothing about the img file format 
or how the distance and routing calculations are performed.

Chris