[mkgmap-dev] Splitter details question

Tue Jan 12 10:03:18 GMT 2010

W> At the moment I try to understand how the splitter works to make the
W> mulitpolygon code splitter compatible.

Hi WanMil,

The statement "tiles join exactly with no overlap or gaps" is referring to 
the bounding boxes of the resultant tiles, not the nodes/ways/rels that end 
up in each tile. There is some deliberate overlap (see the --overlap parameter) 
that causes nodes/ways/rels to be retained even if they fall just outside 
a tile boundary, so that mkgmap can reliably cut ways exactly on the boundaries. 
It's quite possible that a way contains nodes that only fall into the overlap 
area and not the bounding box itself - due to memory & performance concerns 
there's currently no effort made in the splitter to remove such ways & nodes.

The basic algorithm is this:

1) determine where the tile boundaries lie, based on the distribution of 
nodes in the osm file. None of these tiles will overlap.
2) for each node, determine which tile (or tiles) it belongs to. A node is 
considered to belong to a tile if it falls anywhere within the tile itself 
OR the overlap area. It's quite common for a single node to be assigned to 
four tiles - one real tile plus three overlap areas (or to even more tiles, 
if a tile is thinner than double the overlap).
3) for each way, lookup its nodes and find out what tile(s) they were assigned 
to. Assign the way to those tile(s) too.
4) for each relation, find out what tile(s) its nodes and ways were assigned 
to. Assign the relation to those tile(s) too.

I realise this isn't perfect - nodes and ways that fall completely outside 
the tile are included when they don't need to be, and nodes that fall outside 
the overlap are excluded when we may not want them to be. There are also 
problems with ways that cross a tile without actually having any nodes contained 
within the tile (even including the overlap). I'm not sure how much of a 
problem these are in practice.

Any suggestions you have for improvements would be welcome.

Chris