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

[Christoph Spoerri]

I just read a paper on the D-P algorithm where they mentioned that the 
algorithm may result in self-intersecting lines. It also said that there are 
indications that is is computationally infeasible to guarantee valid simple 
lines or polygons after applying a simplification algorithm.

Christoph 

FYI. the paper was: J. Hershberger and J.Snoeyink, 'Speeding Up the 
Douglas-Peucker Line-Simplification Algorithm'


On Thursday 28 August 2003 01:39 pm, Martin Davis wrote:
> 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
>
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users