[postgis-users] Simplify() and direction dependency

[strk at refractions.net]

Someone is working on PHP postgis classes, you might join
them and make that a PHP extension..

Of course if someone comes out with a C implementation that'll
be fine too, as another way of simplifying geoms.

--strk;

On Thu, Jan 13, 2005 at 05:08:38PM +0100, Andreas Neumann wrote:
> 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

-- 

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/