[mkgmap-dev] Problem with splitter
From Wolfgang Hammel wolfgang.hammel at gmx.de on Mon Mar 19 00:13:15 GMT 2012
Hi Gerd,
my proposal was just about ways that have no nodes inside the (extended)
bbox.
This is the case for way no. 2 in both of my examples
So if, for example, node 6 would be inside the ext. bbox, this is no
longer considere to be an "outside way" andthe complete way with all its
nodes should be written. In that case no angle measurement for that way
is necessary.
The same would be the case for a zig-zag line going in and out, again
all the nodes of that way would have to be written.
Our previous discussion was going in the direction of dropping all the
unnecessary nodes of the outsides ways (these are ways that have no node
in the ext. bbox). At the moment I think it is enough information for
mkgmap to fully reconstruct anything that is inside the tile, when we
have the first node, the last node and the angle between those two nodes
measured against the tile center for each of the outside ways. So this
is just an extension to your proposal in your mail dated 2012-03-15 that
helps to reduce the file size of the tiles by omitting the superfluous
"inner" nodes of the "outside" ways.
So to sum up what the strategy is that I have in mind at the moment:
1. check if a relation touches the tile
1a. this is the case if at least one node of at least one ways lies
inside the ext. bbox
1b. if no node of the relation is inside the ext. bbox, according
the Richard's input
the multipolygon may still touch the tile for example if the
tile is completely contained in the multipolygon
1c. there are some other situations where a tile is touched by a
multipolyon
think of a polygon that has one edge that cuts through the
tile's bbox without having a node inside the bbox
so the check if a relation touches a tile has to be refined,
but there are existing algos that
allow to check for that condition
2. if the check is positive, the relation is written to the tile
including the references to all its ways
3. all the referenced ways are written to the tile
- if a way has at least one node inside the ext. bbox, all the
references to all the nodes of that way are written
- if a way has no node inside the ext. bbox, only references to the
first an last node of that way are written
additionally that way is tagged as an "outside way" and the angle
between the first and last node
as shown in my sketches is also tagged to that way
4. all the nodes that have been referenced in step 3. are written to the
tile
Gerd at 2012-03-17 19:31
> "Just to clarify: Writing a relation means writing the id, all tags,
and the ids of the members."
I think if an id of a member is written, the complete member that is
referenced by that id sould always be written too. A tile file should
always be self contained, that means there should be no "dead"
references to members. That is the problem at the moment, that makes it
impossible for mkgmap to correctly proceed.
Richard at 2012-03-17 18:43
> 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?
Gerd at 2012-03-17 19:31
> 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.
In my opinion the answer should be "yes" even for a small tile that lies
in the middle of nowhere inside the US boundary without touching that
boundary. Splitting into tiles should not remove any information for a
certain location that could be extracted from the planet.osm file
before it was going to be split. The algo we are looking for should not
try to remove that info (the info is: all locations inside the tile are
inside the US boundary). Instead splitter should try to store the
minimum amount of information about the US boundary in that tile file,
that allows to deduce the correct info without any guessing (which could
fail).
Wolfgang
Am 18.03.2012 07:14, schrieb Gerd Petermann:
> Hi Wolfgang,
>
> I think your solution is too simple. Using your graphik, imagine node
> 6 would lie somewhere inside the bbox.
> Or, for a more complex case, imagine a zig-zag line going in and out
> (sorry, I have no experience creating graphics).
> In these cases, you have multiple angles, and it will be required to
> store the angle and the point(s) to which it belongs.
> I fear this is too complicated.
>
> Gerd
>
>
>
> ------------------------------------------------------------------------
> Date: Sat, 17 Mar 2012 10:37:32 +0100
> From: wolfgang.hammel at gmx.de
> To: mkgmap-dev at lists.mkgmap.org.uk
> Subject: Re: [mkgmap-dev] Problem with splitter
>
> Hi Gerd,
>
> my proposal from yesterday needs some refinement in order to provide
> enough information to mkgmap.
> I have attached some sketches that might help to explain the need for
> that extension.
> Consider the different situations in the left and right column.
>
> Situation 1: (left column, top)
> we have a multipolygon consisting of 3 ways:
> way no. 1: nodes 1, 2, 3, 4
> way no. 2: nodes 4, 5, 6, 7, 8, 9, 10
> way no. 3: nodes 10, 11, 12, 1
>
> only nodes 2, 3, 11 and 12 are inside of the extended bounding box I
> was talking about yesterday
> according to your new algorithm ways no. 1 and 3 will be fully
> included in the tile,
> that makes nodes 1, 2, 3, 4, 10, 11, 12 to be written to the tile
> and ways no. 1 and 3 are written to the tile
> way no. 2 is also included in the tile by your new algorithm as it
> belongs to a multipolygon, that is included in the tile
> but for way no. 2 only the first and last node are written to the tile
> (nodes no. 4 and 10, which are already included
> through ways no. 1 and 3 respectively)
> and way no. 2 will be tagged as an "outside way"
>
> in the second row the shaded areas are the ones the have to be the
> output of mkgmap
> in situation 1 this makes two subpolygons (hopefully mkgmap can handle
> this correctly...)
>
> Situation 2 (right column, top)
> we have a multipolygon consisting of 3 ways:
> way no. 1: nodes 1, 2, 3, 4 (same as in situation 1)
> way no. 2: nodes 4, 5, 10
> way no. 3: nodes 10, 11, 12, 1 (same as in situation 1)
>
> again ways 1 and 3 will be included and so are all their nodes
> that again makes nodes 1, 2, 3, 4, 10, 11, 12 to be written to the tile
> way no. 2 is an outside way and marked as such by an additional tag
> for way no. 2 we drop node 5 and write only nodes 4 and 10 to the tile
> (these are already included
> through ways no. 1 and 3)
> So mkgmap has exactly the same data as input as in situation no. 1
> but in situation 2 a completely different area has to be te output of
> mkgmap, shown
> in the right column second row.
>
> This gives the need for more detailed information passed to mkgmap if
> we want to omit the
> nodes of the outside ways.
> I would propose to store the angle between the first and last node of
> the outside way
> measured against the center of the tile.
> This is shown in the third row for both situations. In situation 1,
> the outside way circumnavigates the
> tile in positive mathematical direction covering +300 degrees on its
> way from node 4 to node 10.
> In situation 2, the outside way covers a negative angle of -60 degrees
> on its way from node 4 to node 10.
> So storing that angle as an additional information should give mkgmap
> the ability to eventually
> reconstruct the area of the multipolygon that falls inside the
> bounding rectangle.
>
> In fact it would be sufficient to store a single bit that tells mkgmap
> if the outside way passes in
> clockwise or counter clockwise direction from the beginning node to
> the end node.
> But I think this may lead to some errors due to numerical rounding
> when both the first and last
> node of an outside way have nearly the same angle as measured against
> the tile center.
> So this is completely avoided when the angle itself and not just the
> sign of the angle is written to the tile.
>
> And a final remark:
> As a possible optimization a consecutive sequence of outside ways may
> be stripped together
> into one single outside way. This may be useful if we think of the
> administrative boundaries.
>
> I don't know how complicated this will get to be implemented in
> splitter and mkgmap,
> so these are just my thoughts on a possible solution.
>
> Wolfgang
>
>
>
>
>
>
>
> Am 16.03.2012 12:24, schrieb Gerd Petermann:
>
> Hi Wolfgang.
>
> thanks for you input. See below..
>
> > Date: Fri, 16 Mar 2012 00:11:58 +0100
> > From: wolfgang.hammel at gmx.de <mailto:wolfgang.hammel at gmx.de>
> > To: mkgmap-dev at lists.mkgmap.org.uk
> <mailto:mkgmap-dev at lists.mkgmap.org.uk>
> > Subject: Re: [mkgmap-dev] Problem with splitter
> >
> > Hi Gerd,
> >
> > your description of splitter's algorithm is in accordance to what I
> > observed when I used some
> > simple test data.
> > But beside the mulitpolygon problem there is another issue that
> results
> > from the present
> > algorithm.
> > If you consider one single tile, splitter writes a certain node
> to that
> > tile if it is no more than
> > 2000 increments (2^24 incr. <=> 360°) away from the tile's boundary.
> > I think this is the overlap which leads to a maximum of 4 tiles
> each
> > node is written to.
> > If we consider a single tile this works like a frame that is
> 2000 incr.
> > wide around the
> > tile's bounding rectangle and if a certain node falls inside this
> > extended bounding rectangle
> > it is written to the tile.
> > Now consider a way that has some nodes inside the tile (the
> original
> > tile without the extension)
> > and some nodes outside the extended tile boundary. All these
> outer nodes
> > will not be written
> > to the tile. This may lead to a situation where a way for
> example starts
> > inside the tile, has
> > a node at a certain distance from the tile's original boundary,
> then the
> > leaves the tile without having
> > any node in the "extended frame" of that tile and finally some
> nodes
> > outside the "extended frame"
> > where the way ends. So only the first mentioned nodes will be
> written to
> > the tile and mkgmap
> > will be unable to generate the endnode on the tile boundary as
> all outer
> > nodes are dropped.
> > However this situation is very unlikely as ways usually have
> nodes at
> > smaller distances.
>
> Yes, this problem occurs, and my new algorithm can fix that problem
> because it allows to write all points of a way to each tile that
> it belongs to.
>
> > The width of the "frame" is about 4.77 km in north-south
> direction and
> > 3.07 km in east-west direction
> > at 50° latitude.
> > Splitters algorithm may lead to corrupted multipolygons with
> missing
> > ways but
> > also creates corrupted ways with missing nodes, but that is less
> important
> > and may very seldom be a real problem.
> >
> > Yes you are right, writing only the endpoints of the "outside
> ways" will
> > not work.
> > This could be done if it would be possible to give those ways some
> > hidden attribute
> > (maybe some additional tag, that is not used in the original
> OSM-data)
> > that is
> > added by splitter and marks those "shortened" ways as outside
> ways, that
> > have
> > missing nodes.
> > This information could be used by mkgmap to correctly
> reconstruct the
> > multipolygon.
> > The exact location of the outside nodes that gives the original
> shape is
> > not needed for
> > this task by mkgmap.
> > It is true that just storing the end nodes will give errors as
> mkgmap
> > would assume
> > a straight line between those end nodes which again may cross
> the tile
> > boundaries
> > which the original shape of the multipolygon doesn't. However if
> mkgmap
> > would know
> > that this is an outside way by means of an additional tag in the
> outside
> > way's data, it
> > has all the information that is needed to generate the correct
> data that
> > falls inside the tile.
> > But this approach would also require modification of mkgmap.
>
> I like the idea of writing only one new tag instead of many points
> and ways.
> The problem is that it is quite difficult to calculate the
> original shape in
> splitter without blowing up memory.
> I have ideas for this, but it will take a few days to think it over.
>
> Gerd
>
>
>
>
>
>
> >
> > Wolfgang
> >
> > Am 15.03.2012 08:51, schrieb GerdP:
> > > Hi Wolfgang,
> > >
> > > I've described splitters algorithm as it is now here:
> > >
> http://gis.19327.n5.nabble.com/Problem-with-splitter-tp5555886p5561551.html
> > >
> > > I am now working on a first approach that looks like this:
> > > pass 1: calculate tile areas
> > > pass 2:
> > > a) for each coord, way: find out all tiles that are "touched",
> save the info
> > > in a map
> > > 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)
> > > pass 3: for each node of each way: add the info from the way
> map to the
> > > coords map
> > > (so that each coord belonging to a way will be written to all
> tiles that is
> > > touched by the way)
> > > pass 4: for each node, way, and relation: write to the output
> files
> > >
> > > pass 1 and 2 are more or less equal to the current version,
> only the writing
> > > is removed.
> > >
> > > Up to now I see no way to reduce the number of points without
> risking
> > > errors. My idea regarding
> > > "saving only the endpoints" will not work, a simple example
> shows that:
> > > Think of a relation that contains just two long ways. Each way
> forms one
> > > half of an elliptic area. If we only save the endpoints of
> these two ways
> > > (which should be identical), we only see two points and it is
> impossible to
> > > guess how the original shape looked like. So,
> > > we would need an algorithm that reduces only those points that
> are not
> > > needed, but I see no way
> > > to do this in splitter because it has to store too much
> information for
> > > that.
> > >
> > > So, let's see what happens if we write all points and ways...
> > >
> > > Gerd
> > >
> > >
> > > Wolfgang Hammel wrote
> > >> Hi Gerd,
> > >>
> > >> my first thought was also in the direction of option 2)
> > >> but yes you are right, the administrative boundaries and the
> coastlines
> > >> may blow up
> > >> the tiles a lot and that may probably also increase
> processing time in
> > >> mkgmap afterwards.
> > >> Option 3) would be the most precise one but I don't know
> anything about
> > >> splitter's
> > >> internal structure, and this may be complicated and a lot of
> work because
> > >> splitter seems to have no interpretetation of the data it
> processes up
> > >> to now.
> > >>
> > >> But what about the following option which is a combination of
> your
> > >> proposals no. 2) and 3) without the need for an additional file.
> > >>
> > >> Enhance splitter in a way that it includes all the ways of a
> > >> multipolygon that finds its way
> > >> into the output of a certain tile.
> > >> But for the ways it would have dropped up to now only the
> first and last
> > >> nodes are written
> > >> to the output. As these ways always have no node inside the
> tile, this
> > >> woud give
> > >> exactly the same data to mkgmap after the polygons have been
> clipped by
> > >> the
> > >> tile's bounding rectangle.
> > >> The clipping procedure can be done in mkgmap without guessing any
> > >> missing data.
> > >> So this would increase the tile size only by a small amout
> and we have
> > >> all the data
> > >> we need in the tile.
> > >> But in order to give a consistent and correct osm-data file the
> > >> references to the
> > >> dropped nodes should be removed from those ways.
> > >> Otherwise we have the same situation as now where the
> relation of a
> > >> multipolygon contains "dead" references
> > >> to the ways that are not included in the tile's file.
> > >> As I did not have a look at splitter's code up to now, I'm
> not sure if
> > >> this
> > >> can be easily implemented.
> > >>
> > >> By the way:
> > >> I tried to create a minimal working example where the problem
> can be
> > >> reproduced.
> > >> But this is not finished up to now. What I already know is that
> > >> splitter's algorithm
> > >> does not consequently drop all the ways that are outside the
> tile's
> > >> boundaries.
> > >> Maybe you know more details about the criteria splitter uses for
> > >> dropping ways?
> > >>
> > >> Wolfgang
> > >>
> > >> Am 13.03.2012 06:59, schrieb GerdP:
> > >>> Hi Wolfgang,
> > >>>
> > >>> yes, that' s exactly what happens. I see three ways to solve
> this
> > >>> problem:
> > >>> 1) Enhance the logic in mkgmap that guesses how the missing ways
> > >>> completed
> > >>> the multipolygon, e.g. by adding a backtracking algorithmn
> (this is
> > >>> already
> > >>> suggested in the code).
> > >>> 2) Enhance splitter so that it writes all points and all ways of
> > >>> multipolygon to each tile.
> > >>> 3) Enhance splitter to write one extra output file that
> contains only the
> > >>> 1st and last point of each way that is part of a
> multipolygon, and create
> > >>> a
> > >>> method in mkgmap that looks for this data when
> > >>> it doesn't find the way in the normal input. We need only
> the end points
> > >>> because we use the data only in cases where we know that
> they are outside
> > >>> of
> > >>> the bounding box. Maybe that can be done with osmfilter as
> well ?
> > >>>
> > >>> I did not start coding, but I think option 3) should be easy
> to do and I
> > >>> hope it solves most
> > >>> of the problems. Option 2) looks more difficult and will
> blow up tile
> > >>> sizes
> > >>> and CPU cost both in splitter and mkgmap. Option 1) can be
> done as well.
> > >>>
> > >>> Does that sound reasonable?
> > >>>
> > >>> Gerd
> > >>>
> > >>>
> > >>> Wolfgang Hammel wrote
> > >>>> Hi Gerd,
> > >>>>
> > >>>> when I had the problem some time ago, I did some rough
> checking on
> > >>>> splitters output.
> > >>>> What I know so far is, that splitter removes all the ways
> from a certain
> > >>>> tile that have no
> > >>>> node inside this tile.
> > >>>> The problem arises when a tile boundary divides a
> multipolyon that
> > >>>> consist of normally
> > >>>> a lot of different ways. Tile splitter includes the
> complete relation
> > >>>> for that multipolygon
> > >>>> in the output including all the references to the ways that
> > >>>> mulitipolygon originally consisted of.
> > >>>> But as some of the ways are removed from the output, the
> multipolygon is
> > >>>> corrupted and
> > >>>> mkgmap is later no more able to correctly reconstruct the
> part (or
> > >>>> parts) of the multipolygon
> > >>>> that fall inside the tile.
> > >>>>
> > >>>> Wolfgang
> > >>>>
> > >>>> Am 12.03.2012 16:06, schrieb GerdP:
> > >>>>> Hi Matteo,
> > >>>>>
> > >>>>> okay, I am able to reproduce the problem (also without the
> coastfile
> > >>>>> parameter).
> > >>>>> The log shows some warnings for relation 541757 (the Lago
> di Como) ,
> > >>>>> so
> > >>>>> I
> > >>>>> should be
> > >>>>> able to understand what's happening and why it fails.
> > >>>>>
> > >>>>> Gerd
> > >>>>>
> > >>>>>
> > >>>>>
> > >>>>> Matteo Gottardi wrote
> > >>>>>> 2012/3/12 GerdP<gpetermann_muenchen@>:
> > >>>>>>> Hi Teo,
> > >>>>>>>
> > >>>>>>> I tried to reproduce the problem with mkgmap trunk
> version r2248, but
> > >>>>>>> I
> > >>>>>>> get
> > >>>>>>> different results, esp. I don't see this flooding.
> > >>>>>>> I am using coastlines_europe-120128.osm.pbf, maybe your
> file is
> > >>>>>>> older?
> > >>>>>> Hi Gerd,
> > >>>>>> my coastlines file was the same as yours, only with a
> different name
> > >>>>>> :)
> > >>>>>>
> > >>>>>> I did some tests. The results were a bit different
> because of my typ
> > >>>>>> and style files.
> > >>>>>> Using no typ file, the default style file and passing only
> > >>>>>> --generate-sea=multipolygon
> > >>>>>> --coastlinefile=coastlines_europe-120128.osm.pbf the
> result look like
> > >>>>>> this: http://www.gomatteo.net/17.png
> > >>>>>>
> > >>>>>> PS: I would like to thank all the developers who spends
> their time
> > >>>>>> working on this great project, without mkgmap my
> gpsmap60c would be
> > >>>>>> useless :)
> > >>>>>>
> > >>>>>> --
> > >>>>>> * Matteo Gottardi | matgott@
> > >>>>>> * ICQ UIN 20381372
> > >>>>>> * Linux - the choice of a GNU generation
> > >>>>>> * GPG Fingerprint:
> > >>>>>> * B9EE 108F 52C8 D50C B667 B1F2 AB56 8A01 BA3D 36A1
> > >>>>>> _______________________________________________
> > >>>>>> mkgmap-dev mailing list
> > >>>>>> mkgmap-dev at .org <mailto:mkgmap-dev at .org>
> > >>>>>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > >>>>>>
> > >>>>> --
> > >>>>> View this message in context:
> > >>>>>
> http://gis.19327.n5.nabble.com/Problem-with-splitter-tp5555886p5558068.html
> > >>>>> Sent from the Mkgmap Development mailing list archive at
> Nabble.com.
> > >>>>> _______________________________________________
> > >>>>> mkgmap-dev mailing list
> > >>>>> mkgmap-dev at .org <mailto:mkgmap-dev at .org>
> > >>>>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > >>>>>
> > >>>> _______________________________________________
> > >>>> mkgmap-dev mailing list
> > >>>> mkgmap-dev at .org <mailto:mkgmap-dev at .org>
> > >>>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > >>>>
> > >>> --
> > >>> View this message in context:
> > >>>
> http://gis.19327.n5.nabble.com/Problem-with-splitter-tp5555886p5560021.html
> > >>> Sent from the Mkgmap Development mailing list archive at
> Nabble.com.
> > >>> _______________________________________________
> > >>> mkgmap-dev mailing list
> > >>> mkgmap-dev at .org <mailto:mkgmap-dev at .org>
> > >>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > >>>
> > >> _______________________________________________
> > >> mkgmap-dev mailing list
> > >> mkgmap-dev at .org <mailto:mkgmap-dev at .org>
> > >> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > >>
> > >
> > > --
> > > View this message in context:
> http://gis.19327.n5.nabble.com/Problem-with-splitter-tp5555886p5567230.html
> > > Sent from the Mkgmap Development mailing list archive at
> Nabble.com.
> > > _______________________________________________
> > > mkgmap-dev mailing list
> > > mkgmap-dev at lists.mkgmap.org.uk
> <mailto: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
> <mailto: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 <mailto: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
>
>
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20120319/72b05113/attachment.html
- Previous message: [mkgmap-dev] Problem with splitter
- Next message: [mkgmap-dev] Problem with splitter
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the mkgmap-dev mailing list