[geos-devel] Polygon simplification

[Stephen Woodbridge]

Hi Frederick,

First off your contains requirement means you have to start with a 
buffered polygon because all of the original boundary points will fail 
the contains test.

Idea 1:
So starting with your buffered polygon; It would seem that you could 
achieve this by adding and additional constraint to the Douglas-Peucker 
algorithm that only allow the removal of points where the new edges 
after removal of a point(s) does not cross the original boundary.

Also if you need to iterate, I would buffer the simplified polygon on 
the next iteration rather than starting with the original one again.

Idea 2:
Regarding the simplest polygon, granted that would be triangle but a 
more realistic polygon would be a convex hull around your original 
polygon with a slight buffer. Another idea might be to compute the 
convex hull and you could then iterate along the original polygon edge 
in steps and compute the distance from the edge to the nearest convex 
hull edge. Then find the largest distance and split that hull edge and 
move the new node on the split edge inbound until the adjacent edges to 
the point being moved intersect with the original edge and then save the 
last location. You want to find the largest gap and process that first, 
then recompute the gaps along that edge, and repeat with the next 
largest gap until you reach your number of points limit or some 
acceptable size delta between the polygons.

This is sort of building a concave hull, you might also look into 
algorithms for building concave hull.

-Steve

On 5/8/2011 7:29 AM, Frederik Ramm wrote:
> 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
>