Geometry Boost List: Re: [geometry] single-point polygons

Subject: Re: [geometry] single-point polygons
From: Barend Gehrels (barend_at_[hidden])
Date: 2014-10-13 17:05:55

Hi Volker,

Volker Schöch wrote On 13-10-2014 18:28:
>
> The more I think about it, the more confused I get. What are the exact 
> pre-conditions and post-conditions of your algorithms?
>
> On 
> http://www.boost.org/doc/libs/1_56_0/libs/geometry/doc/html/geometry/reference/algorithms/difference.html 
> it says: "Check the Polygon Concept for the rules that polygon input 
> for this algorithm should fulfill".
>
> On 
> http://www.boost.org/doc/libs/1_56_0/libs/geometry/doc/html/geometry/reference/concepts/concept_polygon.html 
> it says "There should be no cut lines, spikes or punctures". It also 
> says "If the input is invalid, the output might be invalid too". Fair 
> enough.
>

I can imagine it is not that simple, and we probably should describe it 
better.

> What it doesn't say is that a polygon without area is invalid. Let's 
> take that at face value, though: It is trivial to imagine, e.g., the 
> difference of two non-empty, valid polygons that results in empty 
> polygon. Does this mean that, e.g., the difference algorithm can take 
> valid input and return invalid output?
>

No: the difference algorithms outputs a multi-polygon, and not a 
polygon. The multi-polygon does not contain any polygons, and is a valid 
geometry. So the output is valid.

Having said that, an empty polygon is also considered as valid by 
several database packages. Our implementation (is_valid is just 
released) reports false to empty polygons, we probably should fix that.

> If I a have a computation that consists of multiple steps, I would 
> like to make sure that the input is valid, and then run my computation 
> as a sequence of calls to geometry algorithms. Given the above -- do I 
> have to verify every intermediate result, and make sure that if I find 
> an invalid polygon, the algorithm returns half way? What is your 
> recommended best practice to deal with this? I am sure that calling 
> correct, unique, remove_spikes (in which order?) and is_valid all over 
> the place cannot be the answer...
>

No, if the input is valid, the output should be valid too. If it is not 
valid, these cases may be reported.

Thanks for your input.

Regards, Barend