[postgis-users] Simplify() and direction dependency
strk at refractions.net
strk at refractions.net
Tue Jan 18 00:08:40 PST 2005
On Mon, Jan 17, 2005 at 03:22:24PM -0800, Martin Davis wrote:
> I think that the problem of simplifying polygonal coverages (what you
> are calling mosaics) is more complicated than simply using a
> "direction-independent" simplifying algorithm. In general the approach
> to simplifying polygonal coverages requires two key ideas:
>
> 1) You need to convert the coverage to a edge-node based topology model,
> so that shared edges are simplified in the same way. (This has already
> been pointed out in a post by Markus Schaber)
>
> 2) Another problem with using raw D-P (and most other straightforward
> simplification algorithms, including the one you mention) is that they
> do not ensure that there are no intersections in the simplified
> linework. To do this requires a much more sophisticated approach, which
> performs global checks to ensure that no intersections are created.
> (Markus, have you encountered this problem at all?)
>
> JTS contains an algorithm which implements the check in #2 above, called
> the TopologyPreservingSimplifier. It could be used in conjunction with
> code to create edge-node topology to perform topology-safe coverage
> simplification. [I'm not sure if this is the algorithm that is exposed
> by the PostGIS simplify function, however. Strk, can you confirm this?]
The postgis simplify() function does a straight D-P pass on lines,
no topology preservation. I think it's worth adding another function
capable of implementing what's in #1 above (including checks in #2).
--strk;
> Ultimately, a goal for JTS is to provide a Coverage datatype. This
> could be easily used in conjunction with the existing
> TopologyPreservingSimplifier code to allow straightforward coverage
> simplification.
>
> Martin Davis, Senior Technical Architect
> Vivid Solutions Inc. www.vividsolutions.com
> Suite #1A-2328 Government Street Victoria, B.C. V8T 5G5
> Phone: (250) 385 6040 - Local 308 Fax: (250) 385 6046
>
>
> > -----Original Message-----
> > From: Andreas Neumann [mailto:neumann at karto.baug.ethz.ch]
> > Sent: January 13, 2005 8:09 AM
> > To: postgis-users at postgis.refractions.net
> > Subject: [postgis-users] Simplify() and direction dependency
> >
> >
> > Hello!
> >
> > I successfully use Simplify() in my Postgis/SVG projects and
> > found it to
> > be very useful.
> >
> > It works fine for MULTILINESTRINGs/LINESTRINGs and POLYGONs
> > that aren't
> > part of a polygon mosaic. However, for polygon mosaics, I
> > can't use the
> > current Simplify() function because it is not direction independent.
> > That means that for polygons that run in opposite directions
> > we will get
> > different results, resulting in sliver polygons.
> >
> > A colleague of mine explained me a direction independent
> > generalization
> > algorithm that would partially solve that problem. It would be slower
> > though, than the Douglas-Poiker algorithm.
> >
> > That algorithm would not start with the start and endpoint of
> > the line
> > (as in the Douglas-Poiker algorithm), but would always look at three
> > points at the time, move forward one vertex to the next three
> > points and
> > after looking through all coordinate-triples would first
> > eliminate only
> > the point in the triple with the lowest distance. In another
> > iteration
> > it would remove again the one with the lowest distance and so
> > on, until
> > all distances are longer than the tolerance. To speed up things one
> > could store the distances in the first iteration in an array and only
> > re-calculate the distances where the vertices in the
> > neighbourhood change.
> >
> > I could further explain the algorithm and make an
> > illustration if that
> > is of interest.
> >
> > One problem that remains, is that in polygon mosaics one has
> > to detect
> > and flag the nodes where 2 or more polygons meet and remove
> > those nodes
> > from the list of removable points. Is there any way in
> > current postgis
> > to detect those nodes where polygon edges meet? I guess this would
> > require a node/edge topology.
> >
> > I am personally not a C programmer but could make a prototype
> > implementation in perl, if that would help. If another person that is
> > able to make C contributions to Postgis could transfer this later, I
> > would be willing to make such a prototype in Perl or PHP.
> >
> > What do you think? Is someone else working on something similar?
> >
> > Thanks for your ideas,
> > Andreas
> >
> > --
> > --
> > ----------------------------------------------
> > Andreas Neumann - Department of Cartography
> > Swiss Federal Institute of Technology (ETH)
> > ETH Hoenggerberg, CH-8093 Zurich, Switzerland
> > Phone: ++41-1-633 3031, Fax: ++41-1-633 1153
> > e-mail: neumann at karto.baug.ethz.ch
> > www: http://www.karto.ethz.ch/neumann/
> > SVG.Open: http://www.svgopen.org/
> > Carto.net: http://www.carto.net/
> >
> > _______________________________________________
> > 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
--
For standing up against patentability of software,
Thank You, Poland!
Read the intervention: http://kwiki.ffii.org/ConsPolon041221En
Send your thanks: thankyoupoland.info
Read/do more: http://www.noepatents.org/
More information about the postgis-users
mailing list