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

[Martin Davis]

That's what I figured... hence my (somewhat disingenuous) question.    This is one reason why generalization remains a hard problem!  (It's also one reason why we chose not to build D-P into JTS.   We wanted JTS to be focussed on core geometric manipulation, and not just be a grab-bag of algorithms which people may or may not use.  Besides, it's easy to write a D-P external to JTS - I know, I just did it yesterday  8^)

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: Christoph Spoerri [mailto:spoerri at duke.edu]
> Sent: Thursday, August 28, 2003 11:13 AM
> To: PostGIS Users Discussion
> Subject: Re: [postgis-users] How to generalize or simplify a Polygon
> 
> 
> 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
> 
> 
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users
>