Geometry Boost List: Re: [geometry] difference algorithm produces invalid polygon?

Subject: Re: [geometry] difference algorithm produces invalid polygon?
From: Volker Schöch (vschoech_at_[hidden])
Date: 2012-02-29 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 spike-only 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 Pn-m happens to at the same coordinates as Pn+1+m for m=0..(n-1), 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 x-constraint 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 x-constraint to rule out any real self-intersections (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 integer-based, valid polygon which is very "narrow", like the example above, but the distance between Pn/2-m and Pn/2+1+m is 1 for m=0..(n/2-1). Now use boost::geometry::for_each_point() and integer-divide 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 self-intersection, there is no trivial way to avoid self-tangency 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 "spike-only" polygons (except when you run a dissolve-like clean-up 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 self-intersecting. In a future version we will distinguish between "self-intersecting", where a real intersection is, and "self-touching", 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 "spike-only" polygons would yield the same result as "the" empty polygon? How about non-empty self-touching polygons -- would they be treated correctly, too? I understand that the correct() algorithm should decompose self-touching 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
think-cell Software GmbH | Chausseestr. 8/E | 10115 Berlin | Germany
http://www.think-cell.com | phone [phone] | US phone [phone]
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl