
Geometry : 
Subject: Re: [geometry] difference algorithm produces invalid polygon?
From: Volker Schöch (vschoech_at_[hidden])
Date: 20120228 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 "selfintersecting"?
 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).
 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 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.
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 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