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-28 13:31:50

Hi Volker,

On 28-2-2012 10:31, Volker Schöch wrote:
> Hi Barend,
> I've been pondering your reply quite a bit, but I'm not satisfied. We are talking about this polygon:
> 	
>>> B1: MULTIPOLYGON(((2079 1968,2301 1968,2301 1968,2079 1968)))
> You said (Wednesday, February 22, 2012 7:44 PM):
>
>> B1 repeats "2301 1968,2301 1968 " which makes it a polygon of basically only two distinct points, which is always invalid. So this is truly invalid input. [...] this one will not be fixed - we might enhance the error messages.
> Here are some things I wonder:
>
> - Why would a polygon of only two distinct points be invalid in the first place? Is this considered "self-intersecting"?

It is invalid by definition of OGC. A polygon may not contain spikes. 
This is a sort of "spike-only" polygon.

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.

Stated otherwise this is a linear feature. It maybe should be considered 
as linear.

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

> - In the general case, how would I detect and fix such a polygon? I tried calling correct() on the input, but the result was still not accepted by the difference() algorithm:
>
> boost::geometry::correct( MULTIPOLYGON(((2079 1968,2301 1968,2301 1968,2079 1968))) )
> result: MULTIPOLYGON(((2079 1968,2301 1968,2301 1968)))

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

I mentioned above that a spike-only polygon should be considered as 
linear. Some applications do that and their "make_valid" algorithm 
converts it to a linestring (I think - I tried SQL Server but that 
refuses any polygon with less than 3 distinct points). But we cannot 
convert a polygon to a linestring automatically because we're living in 
the (happy) templated typesafe C++ world...

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

But yes, by rounding you can create any invalid polygon.

Our library can certainly produce invalid polygons, for example by the 
simplify algorithm (a warning is now described there in the documentation).

> I can see two approaches to fix the library: Either allow this kind of polygons as input for all algorithms; or enhance the correct() algorithm to take input like this and create a polygon from it that is valid input to all other algorithms. Obviously, in the latter case, your algorithms should never produce a result that requires calling correct() before it can be passed as input to another algorithm.
>
> I hope you reconsider this issue.

Yes we will reconsider this. I must see what is exactly the problem.

I'm now busy with the "buffer" algorithm, where several kind of 
collinearities have to be solved. A spike is a collinearity too. Maybe 
we can relax this condition a bit. Also because we can never make such a 
polygon officially "valid".

I will come back to this.

Thanks for your input,
Barend