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

Subject: Re: [geometry] difference algorithm produces invalid polygon?
From: Barend Gehrels (barend_at_[hidden])
Date: 2012-02-29 17:16:58

Hi Volker,

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

Thanks! I will look at this soon but not right now.

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

It is in the extension folders of the Trunk. Actually it might be that 
I've broken it last weekend (the unit-tests for this are not run 
automatically), will look at that soon.

file:///C:/_svn/boost/trunk/boost/geometry/extensions/algorithms/buffer/

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

Yes, I understand this though I did not see it until now. But admitted, 
did not heavily test with all kinds of integer input.

>
>> 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. Many libraries do (it is certainly not trivial to do it otherwise, 
to say the least). But e.g. PostGIS does have the topological correct 
version (called SimplifyPreserveTopology).

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

I will come back to this. To make things more complicated, a 
"self-touching" polygon is actually not having a spike (IIRC). It has a 
self-tangency that is at most one point, and not a linear thing... Maybe 
my message about this was a bit misleading.

About your other mail shortly:

> Next we'd like to see support for circles... Barend, would you like to comment?

Circular features were planned (the n-sphere was originally there but 
also in extensions now, very limitted support). But currently they are 
out of scope - I mean: we first want to concentrate on the quality of 
the current set, and completeness of the combinations of the current 
algorithms. Some things from the extensions should be there soon as well 
(dissolve, buffer) because belonging to the OGC set and already started 
long ago (buffer) or just necessary as in the discussions above.

Regards, Barend