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

Thu Aug 28 13:29:51 PDT 2003

> of self-intersection when you process a polygon. So why not put it in as an
> method that is only a member of LineString / MultiLineString class ? 

If we were putting D-P into JTS, that would be one place to put it, alright.  However, as I said I'd really rather keep JTS focussed on core algorithms.  

On a philosophical note, adding algorithms as methods to Geometry objects seems to be encouraged by the OO paradigm, but it's not the most scalable or flexible way of doing things.  For algorithms such as D-P which are pretty independent of the internal representation of the Geometry I think it's nicer to keep them outside the Geometry class in a separate algorithm class.

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: Chris Faulkner [mailto:chrisf at oramap.com]
> Sent: Thursday, August 28, 2003 12:54 PM
> To: PostGIS Users Discussion
> Subject: RE: [postgis-users] How to generalize or simplify a Polygon
> 
> 
> I take the point about not implementing D-P into JTS because 
> of the problems
> of self-intersection when you process a polygon. So why not 
> put it in as an
> method that is only a member of LineString / MultiLineString 
> class ? I am no
> great Java or JTS expert so what I have said may not be 
> feasible but as I
> look around at the classes, I seen methods like getLineBuffer in
> BufferLineBuilder which are specifically for lines so why not 
> do the same
> for generalisation ?
> 
> Thanks
> 
> Chris
> 
> -----Original Message-----
> From: postgis-users-bounces at postgis.refractions.net
> [mailto:postgis-users-bounces at postgis.refractions.net]On Behalf Of
> Martin Davis
> Sent: 28 August 2003 20:05
> To: PostGIS Users Discussion
> Subject: RE: [postgis-users] How to generalize or simplify a Polygon
> 
> 
> 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
> >
> 
> _______________________________________________
> 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
> 