[mkgmap-dev] Problem with splitter

From Richard Hansen rhansen at bbn.com on 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

> 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