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

[Martin Davis]

Chris, does your D-P algorithm guarantee to return valid polygons?  It seems to me that standard D-P does not check whether removing points introduces self-intersections...

Martin Davis, Senior Technical Architect
Vivid Solutions Inc.
Suite #1A-2328 Government Street   Victoria, B.C.   V8T 5G5
Phone: (250) 385 6040    Fax: (250) 385 6046
EMail: mbdavis at vividsolutions.com  Web: www.vividsolutions.com


> -----Original Message-----
> From: chodgson at refractions.net [mailto:chodgson at refractions.net]
> Sent: Thursday, August 28, 2003 10:37 AM
> To: PostGIS Users Discussion
> Subject: RE: [postgis-users] How to generalize or simplify a Polygon
> 
> 
> Quoting Chris Faulkner <chrisf at 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
> 
> 
> 
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users
>