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-28 04:31:58

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

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

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

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

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