[geos-devel] Polygon simplification

[Frederik Ramm]

Hi,

    I want to simplify a single, hole-less polygon so that the original 
polygon is guaranteed to still be completely covered by the simplified 
polygon, but the simplified polygon doesn't have too much extra area.

More formally, if O is the original polygon and S the simplified one, I 
want:

* S to contain O;
* S to have as little nodes as possible;
* area(S) - area(O) to be as small as possible.

It is clear that my optimising goals are contradictory - the simplified 
polygon with the smallest number of nodes would be a triangle with lots 
of extra area, and the simplified polygon with the smallest extra area 
would have the same, or almost the same, number of nodes as the 
original. I'm sort of looking for the sweet spot between the two extremes.

(My use case is taking a city or county or state boundary from 
OpenStreetMap then regularly cut out this area and make it available for 
download on download.geofabrik.de; the software that does the cutting 
needs simplified polygons else it takes too long.)

My current solution is a program using GEOS to first create a small 
buffer around the polygon and DP-simplify that with about 5 different 
grades of coarseness and check the results to see whether the "contains" 
requirement still holds. If no satisfactory results are achieved (still 
too many nodes), create a slightly larger buffer, etc, until you arrive 
at something that looks ok.

The disadvantage of this is that the resulting polygons are sometimes 
unnecessarily large. If you think of a typical US state that is bounded 
on one side by a straight line and on another side by a winding river, 
the above implementation will probably create a significant buffer to 
smoothe the river boundary (which is ok), but on the straight boundary 
the extra buffer is not necessary.

Does anyone have a suggestion for improvement? Maybe something that lets 
me find a middle line between the original polygon and the simplified 
surrounding polygon, which I would then apply several times or so...

Bye
Frederik

-- 
Frederik Ramm  ##  eMail frederik at remote.org  ##  N49°00'09" E008°23'33"