How to reduce LOD of line for small-scale?

I want to extract the coastline data from .osm dump and store it so that it is suitable for low-scale maps.

For that I need to reduce the number of points in the lines. What algorithms are there for this operation? How does mapnik render this, for example?

I’ve found one simple approach, which is to pick a point and walk along the line, skipping all the points that are closer than a certain distance (depending on the scale). I thought of making an “average point” of those that are near, but I’m not sure this will make sensible results.

Any recommendations?

We make the low-zoom coastline shapefiles by running it through the simplify function in postgis:

shp2pgsql -s 900913 -g way processed_p shoreline_a | psql -U mapnik -q coastlines

pgsql2shp -u mapnik -f shoreline_300 coastlines "select simplify(way, 300) as the_geom,gid as id from shoreline_a where area(simplify(way,300)) > 0"

The resulting shoreline_300 shapefile is used for zooms 0-9 in the default OSM ‘mapnik’ map.

That was useful! I found the description of this algorithm, (Ramer-Douglas-Peucker). Looks easy to implement.

mkgmap uses the Douglas-Peucker algorithm, so check out the source code [1] if you want to see an implementation.