logo separator

[mkgmap-dev] Problem with splitter

From Gerd Petermann gpetermann_muenchen at hotmail.com on Sun Mar 18 06:14:48 GMT 2012

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

            > To: 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&lt;gpetermann_muenchen@&gt;:

            > >>>>>>> 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

            > >>>>>> 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

            > >>>>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

            > >>>>>

            > >>>>
            _______________________________________________

            > >>>> mkgmap-dev mailing list

            > >>>> 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

            > >>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

            > >>>

            > >>
            _______________________________________________

            > >> mkgmap-dev mailing list

            > >> 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

            > > 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
    
  


_______________________________________________
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/20120318/b9b4f607/attachment.html 


More information about the mkgmap-dev mailing list