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

Mon Aug 29 00:45:17 BST 2011

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/