[mkgmap-dev] Problem with splitter

Sat Mar 17 23:03:02 GMT 2012

On 2012-03-17 14:31, Gerd Petermann wrote:
>>> a) for each coord, way: find out all tiles that are "touched",
>>> save the infoin a map
>>
>> What is the definition of "touched"?
>
> A point normally lies in exactly one tile.  Nevertheless a point can
> be written to more tiles because of the overlap handling.  With
> "touched" I mean the point is contained in the bounding box of the
> tile with its overlap.

If I understand your definition correctly, in the following ASCII art 
figure, the way is not touching the tile because none of the nodes are 
in the tile's extended bounding box.  Correct?

     o-----------o
     |  _______  |
     | |       | |
     | |       | |
     | |_______| |
     o-----------o

If the way designates a lake, wouldn't this definition result in a hole 
in the lake?

Also, what if a way passes through a tile but none of that way's nodes 
are in the tile?  Does the way touch the tile?  An illustration of this 
scenario:

         _______
        |       |
     o--|-------|--o
        |_______|

>>> b) for each relation, find out all tiles that are "touched", and
>>> add this information to the way map (so that each way belonging
>>> to a relation will be written to all tiles that is touched by the
>>> relation)
>>
>> Same question: What does it mean for a relation to touch a tile?
>
> This is something I want to find out with this discussion.
> Splitter r200 simply does this:
> If a way has at least one point in a tile, then the way is written
> to that tile.
> If a relation has at least one point or a way that is written to a
> tile, then the relation is also written to that tile.
> I think a correct solution should additionally write the relation to
> all tiles that are fully enclosed.

Couldn't a similar argument be made for closed ways?  (A way should be 
written to a tile if the tile is fully enclosed by the closed way.)

>> Suppose I feed all of North America to splitter. Wouldn't this
>> algorithm write all of the nodes, ways, and relations that compose the
>> United States administrative boundary to every tile in the US?
>
> Yes, without a clever filter algorithm this could be the case.  I
> still hope that we can find an algorithm that writes all that is
> needed, but not more.  With needed I mean all information that mkgmap
> needs to correctly handle the ways and relations.

For a tile in the middle of the United States, mkgmap doesn't need all 
of the ways and nodes that compose the complete United States 
administrative boundary.  It only needs to know that the tile is 
completely contained within relation 148838 and therefore all of that 
relation's tags apply to the tile's entire area.

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.

I see two ways to obtain complete data in a tile:

   1. Splitter simply acts as a filter, choosing which objects to 
include in a tile.  In this case, to have complete information, every 
tile in the middle of the United States would have to include all of the 
objects that compose the complete United States administrative boundary.
   2. Splitter somehow communicates extra data to mkgmap.  The extra 
data indicates which parts of the tile are covered by an incomplete way 
or relation.

I don't think option #1 will work; each tile would contain too many objects.

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.  Handling the case where part of an area's 
border passes through a tile would be a bit tricky but doable.

Here's my attempt at an algorithm.  It's conceptual; I don't attempt to 
minimize memory usage for example.

1. calculate tile areas by only looking at nodes
2. for each object:
    a. if the object is a node, write the node to the appropriate tile
    b. if the object is a way:
       i. for each node in the way, write the way to the tile containing 
the node (unless already written)
       ii. for each line segment in the way:
           A. if the segment touches more than one tile, write the way 
and the two nodes on either end of the line segment to each tile touched 
by the line segment (unless already written)
       iii. if the way intersects itself one or more times, determine 
the areas defined by the way
       iv. for each area defined by the way:
           A. if the area's size > 0 and the area intersects more than 
one tile, write the way to each intersecting tile (unless already 
written).  also, for each intersecting tile, write aux data indicating 
which parts of the tile are covered by the area.
    c. if the object is a relation:
       i. if one of the relation's members was written to a tile, write 
the relation to the same tile (unless already written)
       ii. determine the areas defined by the relation (if any)
       iii. for each area defined by the relation:
           A. if the area's size > 0 and the area intersects more than 
one tile, write the relation to each intersecting tile (unless already 
written).  also, for each intersecting tile, write aux data indicating 
which parts of the tile are covered by the relation.

Writing aux data indicating which parts of the tile are covered by the 
way/relation:

1. if the entire tile is covered by the way/relation, write something 
that means "way/relation XYZ covers the entire tile" to the tile's aux file
2. otherwise:
    a. determine the area(s) that result from calculating the 
intersection of the tile area and the way/relation area.
    b. for each area calculated above:
       i. if the area does not touch the tile bounding box, skip it 
(mkgmap will have enough information in the tile to derive it on its own)
       ii. if the area's size = 0, skip it
       iii. pick an arbitrary point inside the area, call it P
       iv. the area's border is defined by the tile's bounding box and 
one or more ways.  determine those ways (e.g., foo, bar, baz)
       v. write something that means "way/relation XYZ covers the part 
of the tile containing point P whose border is defined by ways foo, bar, 
and baz and the tile bounding box" to the tile's aux file.  Or maybe 
just write a sequence of points that define the area's border (whatever 
is easiest for splitter and mkgmap).

Thoughts?

-Richard

> See also Wolfgangs suggestions:
> http://gis.19327.n5.nabble.com/Problem-with-splitter-tp5555886p5573307.html
>
> I personally also don't like the idea of inventing points or ways, so
> I'd prefer a
> solution that simply doesn't write what isn't needed.
>
> Gerd
>
>  > -Richard
>  > _______________________________________________
>  > mkgmap-dev mailing list
>  > mkgmap-dev at lists.mkgmap.org.uk
>  > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
>
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev