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

Subject: Re: [geometry] single-point polygons
From: Menelaos Karavelas (menelaos.karavelas_at_[hidden])
Date: 2014-10-14 04:57:04

Hi Barend. Hi Volker.

On 14/10/2014 12:05 ??, Barend Gehrels wrote:
> 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.
>

Our implementation of is_valid reports all empty geometries (including 
multi-geometries) as invalid.
It took me some time to decide what to do with those, and how to 
implement things. I ended up considering all multi-geometries as 
invalid. The reasoning behind that is that in the OGC standard each 
geometry comes with a dimension, so empty geometries cannot fulfill this 
dimension requirement. For example a multi-linestring is defined as an 
1-dimensional geometry collection (and more stuff...). The way that I 
read it, an empty multi-linestring cannot be 1-dimensional, and in that 
respect it is not valid.

I may be wrong and I may be misunderstanding things. And I perfectly 
happy to change the behavior of is_valid to something that makes sense 
to most/all of us. We should also look at what Oracle/SQL server/PostGIS 
do with empty geometries (not only multigeometries). IIRC, we tried 
other DB's and empty linestrings and polygons where considered as invalid.

Best,

- m.

>> 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
>
>
>
> _______________________________________________
> Geometry mailing list
> Geometry_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/geometry