[geos-devel] Polygon simplification
frederik at remote.org
Sun May 8 07:29:26 EDT 2011
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
* 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...
Frederik Ramm ## eMail frederik at remote.org ## N49°00'09" E008°23'33"
More information about the geos-devel