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@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/geometry