[postgis-users] Simplify() and direction dependency
Andreas Neumann
neumann at karto.baug.ethz.ch
Thu Jan 13 08:08:38 PST 2005
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/
More information about the postgis-users
mailing list