[geos-devel] Polygon simplification

[Martin Davis]

Actually if you use the covers predicate instead of contains, you won't 
need to buffer.  (Covers is a much more useful predicate than contains, 
IMO).

have a look at BufferInputLineSimplifier in JTS (not sure if this has 
been ported to GEOS or not).  It does more or less exactly what you 
want.  The original goal was to simplify geometries for faster 
buffering, since small concavities are not significant to the buffer 
output.  I also had in mind creating a routine to do exactly what your 
use case is (called something like OuterSimplifier).  Sounds like that 
really would be useful.

Martin

On 5/8/2011 7:33 AM, Stephen Woodbridge wrote:
> 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
>>
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/geos-devel
>
>
> -----
> No virus found in this message.
> Checked by AVG - www.avg.com
> Version: 10.0.1325 / Virus Database: 1500/3624 - Release Date: 05/08/11
>
>