
Geometry : 
Subject: Re: [geometry] difference algorithm produces invalid polygon?
From: Volker Schöch (vschoech_at_[hidden])
Date: 20120229 09:04:02
Hi Barend,
Thank you very much for your detailed reply. I'm still in the process of digesting it, but here is a preliminary answer:
> The intersection of two spikeonly polygons would be empty. The area is empty. The union would be empty. So this polygon is virtually empty, it should not exist.
Well, not necessarily the union, but I get your drift. I agree that in the space of polygons it is equivalent to "the" empty polygon. That's why I expected the library would treat it like that.
> >  I can easily imagine having 2*n Points P1...P2n and a polgon that runs (P1, ..., P2n), where Pnm happens to at the same coordinates as Pn+1+m for m=0..(n1), and Pm>x < Pm+1>x for m=1..n. Polygons of this form do not contain holes, and in my application I can assure that points are listed in correctly oriented order. I would like the library to correctly handle these polygons (this is no issue with GPC).
> Can you send a (WKT) sample of such a polygon? I think I understand but don't see how the xconstraint fit into this.
MULTIPOLYGON(((1716 1554,2076 2250,2436 2352,2796 1248,3156 2484,3516 2688,3516 2688,3156 2484,2796 1248,2436 2352,2076 2250, 1716 1554)))
This seems to me like a more general form of the "spike only"type polygon that I originally submitted. I merely mentioned the xconstraint to rule out any real selfintersections (and this constraint incidentially holds in my application, allowing to ensure correct order of points).
> The "dissolve" algorithm is designed to do that but due to found indeficiences we moved that to the extensions, before release. So it contains some defects still to be solved. But in the end, it will be there too.
>
> What would this do with the polygon with 2 points? The most correct behaviour (I think) is to remove the spikes, so it will result in an empty polygon... (don't know if you want that).
Fine with me, that would certainly be the correct thing to do wrt operations between polygons. Otherwise, as you pointed out, I could and should use a linear feature.
Is a version of the dissolve algorithm readily available (even if not currently part of boost), that would implement this behavior? Where could I get it? I'd happily use it for the problem at hand.
> >  I didn't try (but I will, if need be) but I assume that a polygon like that can easily be the result of applying some of the boost::geometry algorithms, simply due to rounding. Although it's also possible with double values, it is much more obvious when you think integer. Example: Imagine an integerbased, valid polygon which is very "narrow", like the example above, but the distance between Pn/2m and Pn/2+1+m is 1 for m=0..(n/21). Now use boost::geometry::for_each_point() and integerdivide all coordinates by 3. Ooops? ;) This should be a valid transformation.
> Yes, I can imagine this. Are the polygons you described result of a difference or intersection of our library?
No, it's input created by my application. While it is easy to avoid actual selfintersection, there is no trivial way to avoid selftangency while composing the polygons.
> But yes, by rounding you can create any invalid polygon.
My point is that, due to limited precision in the numeric data types we use, it seems that for specific, but valid, input your algorithms should also produce "spikeonly" polygons (except when you run a dissolvelike cleanup afterwards). Strictly speaking, this means that your algorithms are not closed (domain of definition of f is not a superset of the image of f) which leaves me scratching my head with regard to the definition of "valid" polygons (I understand it's a given by OGC and hardly debatable).
> Our library can certainly produce invalid polygons, for example by the simplify algorithm (a warning is now described there in the documentation).
That's unexpected, at least to me. IMO a warning in the docs is in order, but hardly a remedy. Anyway, since I have no use for the simplify algorithm right now we don't have to fight that fight...
> Yes we will reconsider this. I must see what is exactly the problem.
Thanks! Let me know if I can be of any help.
> It now throws because the intersection fails and it states that it is selfintersecting. In a future version we will distinguish between "selfintersecting", where a real intersection is, and "selftouching", which has a self tangency or other kind of artefact, but is not really intersecting. And it should not throw then (if throwing at all).
I am not sure if I understand that correctly. Would this mean that "spikeonly" polygons would yield the same result as "the" empty polygon? How about nonempty selftouching polygons  would they be treated correctly, too? I understand that the correct() algorithm should decompose selftouching polygons into multiple separate polygons. If I want/need to apply correct() as well as dissolve()  in which order should they be applied?
Thank you again for your efforts and your comments,
Volker
 Volker Schöch  vschoech_at_[hidden] Senior Software Engineer thinkcell Software GmbH  Chausseestr. 8/E  10115 Berlin  Germany http://www.thinkcell.com  phone +49 30 66647310  US phone +1 800 891 8091 Amtsgericht BerlinCharlottenburg, HRB 85229  European Union VAT Id DE813474306 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl
Geometry list run by mateusz at loskot.net