logo separator

[mkgmap-dev] Problem with splitter

From Richard Hansen rhansen at bbn.com on Sun Mar 18 22:15:47 GMT 2012

On 2012-03-18 04:59, Gerd Petermann wrote:
> Hi Richard,
> generally I think an OSM element is "touching" a tile when it would
> change the output of mkgmap if we simply remove it.

I agree with that definition.

> So, splittter should not remove something that "touches" a tile
> without adding something else that allows to produce the same
> result.

Yes.  Figuring out the best way to add something else is the hard part.

> Maybe it would be better to say "has influence on" instead of
> "touches".

Yes, I like "influence" better.

> I have to find out how the algorithms that are triggered with
> parameters like --add-pois-to-lines or --location-autofill=nearest
> are affected.

So a city node influences a tile if there is a point in the tile where 
--location=autofill=nearest would choose that city.  Tricky!

If splitter tries to handle these mkgmap options, the line between 
splitter and mkgmap becomes blurred.  That makes me a bit uncomfortable. 
  Would it be better for mkgmap to handle these cases on its own by 
making multiple passes over the input tiles?

>> If relation 148838 was included in the tile but none of its members
>> were included, mkgmap would not know what part(s) of the tile were
>> covered by the relation.  That information would have to be
>> communicated somehow.
> For that case I would like to write the relation id, its OSM tags
> plus one special tag like
>     mkgmap:covers_tile=y
> and nothing else (assuming that no point or way or sub-relation
> "touches" the tile)

I like this idea; special tags avoid aux files and can be easily 
processed with existing code and manipulated with existing tools.  I'd 
prefer 'splitter:*' instead of 'mkgmap:*' because other tools besides 
mkgmap might use the tiles.

mkgmap:covers_tile may not be sufficiently expressive.  Maybe something 


Or, for single area partial coverage (where the area contains the point 
42.390,-71.148 and its border is defined by the tile bounding box and 
ways 1234 and 5678):


Multiple area partial coverage could be expressed as a comma-separated 
list of single area definitions.

>> I don't know enough about the OSM data format to know if option #2 is
>> palatable. Creating fictitious OSM objects is not a good idea. Perhaps
>> each tile's .pbf file can be accompanied by an .aux file indicating what
>> parts of the tile are covered by each incomplete way or relation
>> mentioned in the .pbf file.
> Well, I already suggested one additional file containing all
> multi-tile-elements (all nodes of all ways that are touching multiple
> tiles, plus all multi-tile-relations with all referenced nodes and
> ways).  Thorsten did not like that idea, see
> http://gis.19327.n5.nabble.com/Problem-with-splitter-tp5555886p5560250.html
> I don't know if he would also complain about one *.aux file for each *.pbf ?

I think your idea of special tags should work just fine; no need for 
*.aux files.

> My proposal for an algorithm to select required nodes for one tile looks
> like this:
> I see no open problem besides runtime.

I may be wrong, but I don't think this algorithm will work efficiently 
in all cases.  For example:

      |                              |
     (millions of nodes going north) |
       \                             |
        o                            |
         \  +--------+               |
       #5 o-+-o #4   |               |
            |  \     | (tile)        |
            |   o #3 |               |
            |  /     |               |
       #1 o-+-o #2   |               |
         /  +--------+               |
        o                            |
       /                             |
     (millions of nodes going south) |
      |                              |

In this case, the algorithm marks nodes #2 through #4 (step 1a), then 
marks #1 and #5 (step a2).  It then marks millions of nodes, one at a 
time, via step c2.  Even if step c2 picks a different node (e.g., random 
or the node in the middle of the largest sequence of unmarked nodes), I 
think it will always be possible to come up with a scenario where all 
nodes will be marked before the algorithm terminates.

Why not mark nodes #1 through #5 and use a special tag to indicate which 
side of that path is covered by the multi-tile polygon?


More information about the mkgmap-dev mailing list