[postgis-users] Simplify() and direction dependency

[strk at refractions.net]

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/