[mkgmap-dev] Coastline issues - analysis and possible solution

Mon Aug 29 20:23:34 BST 2011

Bartosz,

thanks for you detailed analysis!!

I have never seen the splitter problem you've described.
Maybe the overlap parameter of splitter prevented that because splitter 
puts all points in the tile that is either contained in the bounding box 
or contained in a overlap region with width "overlap" garmin units. If 
overlap is larger than the expansion you don't see this problem.

If you go in such details I propose to make use of the GpxCreator class 
in the mkgmap source code. It has helped me very much to visualize the 
different steps during processing. You have to add some code to the 
lines where the GPX files should be created and with which data but 
that's not a big deal.

The --coastlinefile option is a good way to be 100% sure that you get 
valid coastlines and no flooded tiles. But only if you use "confirmed" 
coastlines (so a file that is confirmed to be error free).
You also pointed to a very big disadvantage: the memory usage is very 
HIGH, because the coastline file needs to be completey loaded in parallel.

This might be fixed by adapting the bounds file algorithm to the 
coastline processing. A precompiler (that can be run on a system with 
very much memory) can compile coast tiles. These tiles can be used by 
mkgmap to fill the complete OSM tiles with this coastline information. 
The memory requirements and the processing time are low for this step.

I don't have time to implement that but if someone likes to do that I 
can give hints where to start and which part of the boundary precompiler 
can be reused (with small changes).

WanMil

> Hi list
>
> I spent the last 12 hours debugging sea generation problems in Europe.
> After digging through a lot of mkgmap and splitter code, I believe I
> understand the source of the issues now.
>
> Since data is processed in tiles, the sea generator will often encounter
> coastlines clipped at the tile boundaries. There are heuristics in the
> code that should produce valid sea multipolygons for tiles with
> incomplete coastlines as well. However, the heuristics fail for the
> Geofabrik extracts of several European countries. Here is what I believe
> the problem to be:
>
> The sea generator correctly identifies incomplete coastlines. It then
> attempts to determine for each such coastline whether it was clipped by
> a tile boundary. It is this test that fails for some countries, leading
> to missing or inverted sea. The source of this issue can be traced back
> to the splitter. Here, tile boundaries are expanded to coarse multiples
> of Garmin map units. Tiles therefore become larger than originally
> requested. If map data for the entire expanded area is available, this
> is OK. But when dealing with country extracts, there may be no data
> available for some of the expanded regions.
>
> Here is an ASCII art example, a rectangular extract with a coastline
> inside, shown as a double line:
>
>    +---------+
>    |         |
>    |         |
>    |=========|
>    |         |
>    +---------+
>
> If this data is fed to mkgmap directly, the sea generator will correctly
> determine that the coastline was clipped by the left and right tile
> boundaries.
>
> If the data is passed through the splitter first, even if no splitting
> into multiple tiles should be needed, the tile boundaries are rounded to
> the multiples of Garmin map units mentioned above. The tile may thus grow:
>
> +-----------+
> |           |
> |           |
> |           |
> | ========= |
> |           |
> |           |
> +-----------+
>
> The problem is that now, the coastline no longer touches the tile
> boundaries. The mkgmap sea generator is confused by this and produces
> invalid or no sea at all.
>
> An obvious but incorrect solution is for the sea generator to check
> whether the coastline reaches the *original* tile boundary, not the
> rounded one. This would require the splitter to pass the original
> boundary to mkgmap along with each tile. The real issue with this
> solution would be that even if mkgmap correctly detects a clipped
> coastline, there is no valid data between the original and rounded
> boundaries. To construct a proper sea multipolygon, mkgmap would have to
> synthesize a coastline in that space, likely introducing ugly artifacts.
>
> A correct solution, already implemented in mkgmap today, is to read
> coastlines from a separate file. The file should contain coastlines that
> extend at least as far as the rounded tile boundaries. From the mail
> archives, it appears that WanMil has identified the same issue before
> and proposed this very solution [1]. Coastlines for a larger area can be
> extracted using:
>
> osmosis \
>     --rb larger_area.osm.pbf \
>     --tf accept-ways natural=coastline \
>     --tf reject-relations \
>     --used-node \
>     --wb coastlines.osm.pbf omitmetadata=true
>
> The coaslines.osm.pbf file can then be fed to mkgmap via the
> --coastlinefile option.
>
> While WanMil described this solution in December 2010 already, it seems
> to have been buried in the mailing list without becoming common
> knowledge. Another mailing list post [2] shows that the --coastlinefile
> had been broken for a while without anyone noticing, confirming that it
> is not in common use.
>
> After spending 12 hours on this today, I hope that others will benefit
> from this write-up instead of having to repeat my odyssey.
>
> Anyone wanting to use the --coastlinefile option will require coastlines
> for a larger region than the extract they are processing. While the
> option does allow several files to be specified whose contents are then
> concatenated, it is easiest to load a single file with coastlines for a
> larger area.
>
> I have prepared two such files, one from today's Geofabrik
> europe.osm.pbf extract, the other from the most recent
> planet-latest.osm.pbf. Both files can be found at [3]. I am providing
> these files so that anyone working with extracts can download compact
> coastlines only instead of having to extract them from the huge
> europe.osm.pbf or planet-latest.osm.pbf files.
>
> Right now, the files were generated once-off. If they are found to be
> useful by others, I am happy to automate the process and make updated
> coastline files available on a regular basis.
>
> Finally, a word of warning: When using coastlines_planet.osm.pbf, mkgmap
> needs a *lot* of memory. I found that even for small tiles, 4.5GB of RAM
> are consumed by the Java process. With coastlines_europe.osm.pbf, the
> memory consumption is about 2.5GB.
>
> - Bartosz
>
> [1] http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2010q4/009636.html
> [2] http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2011q1/010138.html
> [3] http://www.fabianowski.eu/osm/coastlines/
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>