[postgis-users] Simplify() and direction dependency

[Markus Schaber]

Hi, Andreas,

Andreas Neumann schrieb:

> 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.

I also noted this problem. My solution was to create linework out of the
polygon borders, and extract common parts (using boundary, intersection
and difference). Then process each of those parts independently, and
apply the result to both 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.

Are you shure that this algorithm preserves spikes and round shapes? I
did not test it, but from thinkink, it may cut away round shapes with
rather lots of points. Maybe I should try to illustrate my thoughts with
a picture...

> 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 think with using an intelligent data structure, this would not be so
much slower.

> 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.

Maybe you can use an approach as I described above, applying an
additional "boundary" to (or simply using the first and last point of)
all the extracted partial lines.

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

Maybe the best (but not qickest) way to get this into PostGIS is to
contribute to jts. As geos is a port of jts, and PostGIS makes heavy use
of geos, it would be easy to eventually add (or replace) this improved
simplify() method.

The advantage is that not only PostGIS users, but all other jts/geos
users can profit from your contribution. There may also be geos bindings
for perl or php, I don't know.

Possibly, I can create such a jts implementation, but not before the mid
of February, there's too much other work on my table. Maybe a good PHP
implementatin is helpful, but I'm afraid my lack of Perl knowledge would
bring me any further. (What about Python? *grin*)

Thanks,
Markus

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 256 bytes
Desc: OpenPGP digital signature
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20050114/79fb5c56/attachment.pgp>