[postgis-users] How to generalize or simplify a Polygon

[chodgson@refractions.net]

Quoting Chris Faulkner <chrisf@oramap.com>:

> Good luck with your search for an implementation of a line generalization. I
> am using Java Topology Suite (http://www.vividsolutions.com/jts/jtshome.htm)
> with postgis and was hoping that they would offer something similar.
> Unfortunately, it doesn't.

Either JTS or JCS will have a douglas-peucker algorithm, very soon. I've 
already written it :)
 
> I would have thought that your expectation that the resulting polygon should
> cover at least as much area as the original is unrealistic. It you
> generalise a line around a polygon, you change it's shape and if you change
> shape, you change area. Full stop.

Actually, this is fairly simple and sensible requirement - one doesn't want 
their jurisdictional area to be "shrunk" by the generalization. I'd rather be 
contacted about something outside my jurisdiction due to a generalization 
error, than NOT contacted regarding something that was happening inside my 
jurisdiction. 

Geometrically, this means ensuring that non of the points on the convex hull of 
the polygon are removed during the douglas-peucker... it could be implemented 
with a custom douglas-peucker, that knows it can't delete flagged points, or by 
simplifying the shape and then unioning it back with the original shape. Either 
way should remove at least some points, but it won't have the properties of a 
normally douglas-peucker-ed line.

However, to simplify an already convex shape without reducing its area, is a 
different, and interesting problem - imagine all the points of the polygon are 
equally spaced around a circle - you can't remove any point with reducing the 
area. The only way to use less points to describe "at least" this area, is to 
fabricate new points around the outside (circumscribing the circle with a 
polygon that has fewer points). A more difficult problem no doubt, and I am not 
familiar with a general solution.

Anyways, sorry for rambling...

Chris Hodgson