[postgis-users] Simplify() and direction dependency

[Andreas Neumann]

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/