[postgis-users] Simplify() and direction dependency

[Martin Davis]

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?]

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
>