2012/3/11 Martin <mkmap@snailrun.de>:

Looks like a coastline-problem. Which parameter you use for mkgmap?

The options are: ----- BEGIN ----- code-page=1252 latin1 reduce-point-density=4 reduce-point-density-polygon=8 min-size-polygon=8 remove-short-arcs merge-lines add-pois-to-areas pois-to-areas-placement style-file=/home/matteo/opt/mkgmap_styles/teo_style overview-mapname=teo family-name=teo mapname=63240001 family-id=6324 series-name=teo country-name=Italia country-abbr=IT area-name=Italia bounds=/home/matteo/opt/mkgmap_styles/bounds/europe location-autofill=bounds generate-sea=multipolygon coastlinefile=/home/matteo/opt/mkgmap_styles/coastlines_europe-latest.osm.pbf ignore-maxspeeds ignore-turn-restrictions tdbfile ----- END ----- The style file is the default one with some minor changes. The lake is a multipoligon, tagged natural=water in the relation. If it can help, you can download the bad tile at http://www.gomatteo.net/63240018.osm.pbf , or download the italy file from http://download.geofabrik.de/osm/europe/italy.osm.pbf and split it. -- * Matteo Gottardi | matgott@tin.it * ICQ UIN 20381372 * Linux - the choice of a GNU generation * GPG Fingerprint: * B9EE 108F 52C8 D50C B667 B1F2 AB56 8A01 BA3D 36A1

Hi Wolfgang, I'll try to find a solution once the remaining problems in the performance branch are solved. Gerd

Date: Mon, 12 Mar 2012 00:14:42 +0100 From: wolfgang.hammel@gmx.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] Problem with splitter

Hi,

yes you are right, this is a splitter problem which is already known.

As you can see in your example, the lake is split in a way that requires it to be split more than once along the bounding rectangle.

see : http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2011q3/012119.html and http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2011q3/012120.html

This prob. may occur, when the polygon to be split has more than two intersections with the bounding rectangle and consists of some ways that have all their nodes outside the clipping rectangle. As lakes and riverbanks may have curved outlines this can occasionally occur when the bounding rectangle intersects the polygon in a way such that the clipped polygon falls into more than one (or probably two) parts.

I usually take the following manual procedure to circumvent the problem when it occurs.

1. Run Tile splitter once and create a map 2. check the map for floodings along large riverbanks or lakes 3. edit the file areas.list (back up the original one createt by splitter) in order to move the border of the tiles away from the offending riverbank or lake. But take care: you have to modify the corner coordinates of at least two areas in a consistent way in order to get a map without holes The modification of the coordinates should be done in multiples of 0x800. 3a. If needed you can visualize the splitting rectangles when you use the --write-kml option in step 1 paste the complete contents of the generated kml-file here: http://display-kml.appspot.com/ 4. rerun splitter using the option --split-file=<edited areas.list> 5. I use the same edited areas.list later again after I have downloaded new OSM-data so this manual procedure has to be done only once for a certain area

Maybe someone has enough time to enhance TileSpltter, I unfortunately don't have at the moment.

But anyhow: All those working on splitter and mkgmap are doing a great job. Thank you!

Wolfgang

Am 11.03.2012 22:16, schrieb Martin:

...

Looks like a coastline-problem. Which parameter you use for mkgmap?

//Martin

Am 11.03.2012 um 22:10 schrieb GerdP:

...

Hi Matteo,

can you please describe the problem and what it is that makes you believe that this is a splitter problem?

Gerd

Matteo Gottardi-2 wrote

...

Hi, I noticed a problem splitting the geofabrik pbf extract of Italy using the standard splitter-r200 options.

The area is at http://osm.org/go/0CmXpRz , and at http://www.gomatteo.net/10.jpg you can see how it look in QlandkarteGT.

The osm data seem ok, is a splitter problem? _______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

-- View this message in context: http://gis.19327.n5.nabble.com/Problem-with-splitter-tp5555886p5555911.html Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

2012/3/11 GerdP <gpetermann_muenchen@hotmail.com>:

Hi Matteo,

can you please describe the problem and what it is that makes you believe that this is a splitter problem?

Hi, I don't speak english very well, so maybe a screenshot can help :) If you look at http://www.gomatteo.net/out.jpeg you can see the generated map. I marked with the red color the shape of the lake (taken from the osm data). As you can see there is some flooding, and the flooding end exactly at the end of the splitted tile. Thank you for your help, Teo -- * Matteo Gottardi | matgott@tin.it * ICQ UIN 20381372 * Linux - the choice of a GNU generation * GPG Fingerprint: * B9EE 108F 52C8 D50C B667 B1F2 AB56 8A01 BA3D 36A1

On Mon, Mar 12, GerdP wrote:

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?

You need the exact same tiles, else you will not see it. I think to reproduce you need the areas.list from Teo. Thorsten

Matteo Gottardi-2 wrote

...

Hi, I noticed a problem splitting the geofabrik pbf extract of Italy using the standard splitter-r200 options.

The area is at http://osm.org/go/0CmXpRz , and at http://www.gomatteo.net/10.jpg you can see how it look in QlandkarteGT.

The osm data seem ok, is a splitter problem? _______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

-- View this message in context: http://gis.19327.n5.nabble.com/Problem-with-splitter-tp5555886p5556974.html Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

-- Thorsten Kukuk, Project Manager/Release Manager SLES SUSE LINUX Products GmbH, Maxfeldstr. 5, D-90409 Nuernberg GF: Jeff Hawn, Jennifer Guild, Felix Imendörffer, HRB 16746 (AG Nürnberg)

2012/3/12 GerdP <gpetermann_muenchen@hotmail.com>:

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@tin.it * ICQ UIN 20381372 * Linux - the choice of a GNU generation * GPG Fingerprint: * B9EE 108F 52C8 D50C B667 B1F2 AB56 8A01 BA3D 36A1

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@.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@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

On Mon, Mar 12, GerdP wrote:

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.

I don't like Option 1) at all, guessing what the data was will only create new problems. I would prefer Option 2), even if it is more difficult, for several reasons. You have the correct data. You cannot run into problems if the extra output file from 3) get's out of sync to the tiles. And every tile is self-contained, means you can mix them with others, use only a subset, or give it away to somebody else without the need to fiddle with other extra files, which have always to fit. I'm not that sure option 2 will really blow up the tile size and CPU cost. Today, most people creating a map use a very huge number for --overlap to avoid this kind of problems. And how many multipolygons are really that big that they go over several tiles? Thorsten -- Thorsten Kukuk, Project Manager/Release Manager SLES SUSE LINUX Products GmbH, Maxfeldstr. 5, D-90409 Nuernberg GF: Jeff Hawn, Jennifer Guild, Felix Imendörffer, HRB 16746 (AG Nürnberg)

Hi Gerd, On Tue, Mar 13, Gerd Petermann wrote:

...

I'm not that sure option 2 will really blow up the tile size and CPU cost. Today, most people creating a map use a very huge number for --overlap to avoid this kind of problems. And how many multipolygons are really that big that they go over several tiles?

I fear the administrative boundaries and coastlines.

You are right, this could become a real problem :( I think the coastlines are already incomplete for europe if you don't work on the planet file. Since they are no longer closed, would they really end in every tile? Of course if you have an extract for great britain, or even more worse, for complete north america. Especially in the last case, you will have about 1500 tiles all containing the boundaries and the coastline. Maybe the solution would be to merge mkgmap and tilesplitter and do the split on the processed mkgmap data. But I don't know enough about how this works to know if this is doable at all. Thorsten -- Thorsten Kukuk, Project Manager/Release Manager SLES SUSE LINUX Products GmbH, Maxfeldstr. 5, D-90409 Nuernberg GF: Jeff Hawn, Jennifer Guild, Felix Imendörffer, HRB 16746 (AG Nürnberg)

Hi, the current implementation of splitter doesn't even try to detect if a polygon contains a split tile. In short it works like this: a) read osm data and calculate the tile areas. b) Close file and start reading again c) Distribute all nodes, each node is written to a maximum of 4 different tiles. d) for ways, look at which tiles the points of the way were written, and write the way to all of them e) for relations, look at which tiles the nodes and points of the rel were written and write the rel to all of them There is no calculation in splitter that tries to connect the ways of a relation to find out what is inside or outside of the relation. So, if you look at one tile, you see only ways and rels that have at least one point in it. I think it is quite easy to implement a 3rd pass in splitter that a) detects to what tiles a relation was written and makes sure that all members (ways and nodes) belonging to this relation are also written to each tile (if not already done) a) detects to what tiles a way was written and makes sure that at least the 1st and last node of the way is written to each tile. This will allow mkgmap to calculate the details within the tile area as well as the multipolygons that have at least one point in that tile without any guessing. Maybe I also find a way to detect those ways and relations that may completely contain a tile. If I see this right, we just have to calculate the bounding box of all points and check if the tile area intersects with it This will find all good candidates, but maybe requires a lot more cpu time. Gerd

Date: Tue, 13 Mar 2012 16:30:22 +0100 From: osm@aighes.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] Problem with splitter

Maybe splitter could detect, if a tile is completely inside such a "polygon" and then only add a rectangle with a negative ID (or parse for highest used node/way-ID).

At all I think, that needed diskspace isn't a huge problem, if there is no more guessing.

Henning

Am 13.03.2012 16:06, schrieb Thorsten Kukuk:

...

Hi Gerd,

On Tue, Mar 13, Gerd Petermann wrote:

...

...

I'm not that sure option 2 will really blow up the tile size and CPU cost. Today, most people creating a map use a very huge number for --overlap to avoid this kind of problems. And how many multipolygons are really that big that they go over several tiles? I fear the administrative boundaries and coastlines. You are right, this could become a real problem :(

I think the coastlines are already incomplete for europe if you don't work on the planet file. Since they are no longer closed, would they really end in every tile?

Of course if you have an extract for great britain, or even more worse, for complete north america. Especially in the last case, you will have about 1500 tiles all containing the boundaries and the coastline.

Maybe the solution would be to merge mkgmap and tilesplitter and do the split on the processed mkgmap data. But I don't know enough about how this works to know if this is doable at all.

Thorsten

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Henning, well, I think this can be done, but I see two problems: 1) Splitter would have to write the data in OSM format, means, it has to invent some ways, nodes and the ids for them. I think we cannot simply invent nodes for existing OSM ways. 2) I think the data structures in splitter don't allow to detect unclosed multipolygons without massive changes. Gerd aighes-2 wrote

Am 13.03.2012 06:59, schrieb GerdP:

...

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 ? Would it be possible, that splitter closes the multipolygons after cutting them?

Henning

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

-- View this message in context: http://gis.19327.n5.nabble.com/Problem-with-splitter-tp5555886p5560548.html Sent from the Mkgmap Development mailing list archive at Nabble.com.

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@.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@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.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@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.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.

Hi Wolfgang. thanks for you input. See below..

Date: Fri, 16 Mar 2012 00:11:58 +0100 From: wolfgang.hammel@gmx.de To: mkgmap-dev@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@.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@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.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@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.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@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Wolfgang, your illustrations shows exactly on typical problem for the "guessing" algorithm. My new algorithm would save all three ways with all points, so this guessing will disappear. I've coded that yesterday with one small modification: Only members of complete relations are added to the tiles, else we just see more guessing. some results using default splitter parms: A small file like portugal.osm.pbf is split into 2 tiles, a larger file italy.osm.pbf is split into 43 tiles. Results (combined file sizes, processing time) r200: portugal: 22.733 kb, ~17 seconds italy: 437.889 kb, ~252 seconds new algorithm: portugal 22.837 kb, ~23 seconds italy 676.166 kb, ~ 412 seconds So, the more tiles, the more data is added to each tile. Unfortunately, mkgmap fails to handle the newer files, I got some null pointer exceptions which have to be fixed first. I see now a way to calculate the shapes of those polygons that spread over multiple tiles, so maybe I can omit writing some points. I did not yet analyse your suggestion regarding the angles. Gerd Wolfgang Hammel wrote

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@ To: mkgmap-dev@.org 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@.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@.org >> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev >> > _______________________________________________ > mkgmap-dev mailing list > mkgmap-dev@.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@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.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@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

-- View this message in context: http://gis.19327.n5.nabble.com/Problem-with-splitter-tp5555886p5573616.html Sent from the Mkgmap Development mailing list archive at Nabble.com.

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@gmx.de To: mkgmap-dev@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@gmx.de <mailto:wolfgang.hammel@gmx.de> > To: mkgmap-dev@lists.mkgmap.org.uk <mailto:mkgmap-dev@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@.org <mailto:mkgmap-dev@.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@.org <mailto:mkgmap-dev@.org> > >>>>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev > >>>>> > >>>> _______________________________________________ > >>>> mkgmap-dev mailing list > >>>> mkgmap-dev@.org <mailto:mkgmap-dev@.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@.org <mailto:mkgmap-dev@.org> > >>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev > >>> > >> _______________________________________________ > >> mkgmap-dev mailing list > >> mkgmap-dev@.org <mailto:mkgmap-dev@.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@lists.mkgmap.org.uk <mailto:mkgmap-dev@lists.mkgmap.org.uk> > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev > > > _______________________________________________ > mkgmap-dev mailing list > mkgmap-dev@lists.mkgmap.org.uk <mailto:mkgmap-dev@lists.mkgmap.org.uk> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk <mailto:mkgmap-dev@lists.mkgmap.org.uk> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

On 2012-03-15 03:51, GerdP wrote:

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

What is the definition of "touched"? If a tile's extended bounding box is completely enclosed by an area, does that way "touch" the tile? What if the way was a closed polyline instead of an area? ASCII art illustration, where 'o' is a node, the outer box is a way (either area or closed polyline), and the inner box is a tile's extended bounding box: o-----------o | _______ | | | | | | | | | | |_______| | 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?

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

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

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@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

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 like: splitter:tile_coverage=complete_tile 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): splitter:tile_coverage={(42.390,-71.148),1234,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:

[snip]

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: o------------------------------o | | (millions of nodes going north) | \ | o | \ +--------+ | #5 o-+-o #4 | | | \ | (tile) | | o #3 | | | / | | #1 o-+-o #2 | | / +--------+ | o | / | (millions of nodes going south) | | | o------------------------------o 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? -Richard