single-point polygons

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

single-point polygons

Volker Schöch

It is now my understanding that WKT demands closing points for polygons. The following should be a well-formed polygon:

 

POLYGON((2079 1968,2301 1968,2079 1968))

 

Calling remove_spikes on the resulting polygon, and outputting it as WKT, results in the following (boost 1.56.0):

 

POLYGON((2079 1968))

 

My questions:

-       Is this expected (no closing point)?

-       I presume that for some algorithms (which?) the position of the single point makes a difference while for others, like difference, any empty polygon should create the same result. Is this correct?

-       A year ago I made a note in my code that some algorithms cannot deal with input polygons that contain spikes (Boost.Geometry Overlay invalid input exception results). Therefore I established an invariant for my own polygons, that requires all polygons to be free of spikes. Is this still necessary?

-       How is a single-point polygon different from a spike?

-       If spikes are not allowed, how should single-point polygons be dealt with? Should they be considered empty, and have their last remaining point removed before passing them to, e.g., the difference algorithm? Or is some wrapper code required that avoids calling certain algorithms with single-point polygons?

 

My internal representation is oriented counter-clockwise and not closed, my point type is based on int.

 

Thanks

   Volker

--
Volker Schöch | [hidden email]
Senior Software Engineer


We are looking for C++ Developers: http://www.think-cell.com/career

think-cell Software GmbH http://www.think-cell.com
Chausseestr. 8/E phone / fax +49 30 666473-10 / -19
10115 Berlin, Germany US phone / fax +1 800 891 8091 / +1 212 504 3039
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schödl


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: single-point polygons

Adam Wulkiewicz
Hi,

Volker Schöch wrote:

It is now my understanding that WKT demands closing points for polygons. The following should be a well-formed polygon:

 

POLYGON((2079 1968,2301 1968,2079 1968))


No, it should be invalid. A valid Polygon should have a non-0 area. This means that it should at least be a triangle - contain 3 points for open, 4 points for closed.
You may now call bg::is_valid() to check it however it is as computionally expensive as set or relation operation, e.g. intersects().

 

Calling remove_spikes on the resulting polygon, and outputting it as WKT, results in the following (boost 1.56.0):

 

POLYGON((2079 1968))

 

My questions:

-       Is this expected (no closing point)?

-       I presume that for some algorithms (which?) the position of the single point makes a difference while for others, like difference, any empty polygon should create the same result. Is this correct?

-       A year ago I made a note in my code that some algorithms cannot deal with input polygons that contain spikes (Boost.Geometry Overlay invalid input exception results). Therefore I established an invariant for my own polygons, that requires all polygons to be free of spikes. Is this still necessary?

-       How is a single-point polygon different from a spike?

-       If spikes are not allowed, how should single-point polygons be dealt with? Should they be considered empty, and have their last remaining point removed before passing them to, e.g., the difference algorithm? Or is some wrapper code required that avoids calling certain algorithms with single-point polygons?

 

My internal representation is oriented counter-clockwise and not closed, my point type is based on int.

 


I'd say that remove_spikes() assume that the Polygon is valid and since an invalid one is passed it treats it as a one spike which is removed.

I guess at the end we could check the number of Points and throw an exception if the result contained too small number of Points.
In some cases numbers of Points are checked at the beginning of a function, maybe for "mutable" functions we should also check this at the end?

Regards,
Adam

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: single-point polygons

Adam Wulkiewicz
Adam Wulkiewicz wrote:
Hi,

Volker Schöch wrote:

It is now my understanding that WKT demands closing points for polygons. The following should be a well-formed polygon:

 

POLYGON((2079 1968,2301 1968,2079 1968))


No, it should be invalid. A valid Polygon should have a non-0 area. This means that it should at least be a triangle - contain 3 points for open, 4 points for closed.
You may now call bg::is_valid() to check it however it is as computionally expensive as set or relation operation, e.g. intersects().

 

Calling remove_spikes on the resulting polygon, and outputting it as WKT, results in the following (boost 1.56.0):

 

POLYGON((2079 1968))

 

My questions:

-       Is this expected (no closing point)?

-       I presume that for some algorithms (which?) the position of the single point makes a difference while for others, like difference, any empty polygon should create the same result. Is this correct?

-       A year ago I made a note in my code that some algorithms cannot deal with input polygons that contain spikes (Boost.Geometry Overlay invalid input exception results). Therefore I established an invariant for my own polygons, that requires all polygons to be free of spikes. Is this still necessary?

-       How is a single-point polygon different from a spike?

-       If spikes are not allowed, how should single-point polygons be dealt with? Should they be considered empty, and have their last remaining point removed before passing them to, e.g., the difference algorithm? Or is some wrapper code required that avoids calling certain algorithms with single-point polygons?

 

My internal representation is oriented counter-clockwise and not closed, my point type is based on int.

 


I'd say that remove_spikes() assume that the Polygon is valid and since an invalid one is passed it treats it as a one spike which is removed.


This is not precise enough, sorry. A Polygon containing spikes is of course invalid so remove_spikes() can't assume that it is. It just naiively remove spikes which in some cases may result in a Polygon containing to small number of Points.

I guess at the end we could check the number of Points and throw an exception if the result contained too small number of Points.
In some cases numbers of Points are checked at the beginning of a function, maybe for "mutable" functions we should also check this at the end?

Another possible solution would be to generate invalid Polygon but, containing the "correct" number of Points, e.g.:
POLYGON((2079 1968,2079 1968,2079 1968,2079 1968)) for closed

Btw, this is related to convex_hull() for a 1- or 2-Point geometry (https://github.com/boostorg/geometry/pull/152).

Regards,
Adam

 

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: single-point polygons

Volker Schöch

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.

 

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?

 

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…

 

Thanks again for your help.

   Volker

 

 

--
Volker Schöch | [hidden email]
Senior Software Engineer


We are looking for C++ Developers: http://www.think-cell.com/career

think-cell Software GmbH http://www.think-cell.com
Chausseestr. 8/E phone / fax +49 30 666473-10 / -19
10115 Berlin, Germany US phone / fax +1 800 891 8091 / +1 212 504 3039
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schödl

From: Geometry [mailto:[hidden email]] On Behalf Of Adam Wulkiewicz
Sent: Montag, 13. Oktober 2014 17:35
To: Boost.Geometry library mailing list
Subject: Re: [geometry] single-point polygons

 

Adam Wulkiewicz wrote:

Hi,

Volker Schöch wrote:

It is now my understanding that WKT demands closing points for polygons. The following should be a well-formed polygon:

 

POLYGON((2079 1968,2301 1968,2079 1968))


No, it should be invalid. A valid Polygon should have a non-0 area. This means that it should at least be a triangle - contain 3 points for open, 4 points for closed.
You may now call bg::is_valid() to check it however it is as computionally expensive as set or relation operation, e.g. intersects().


 

Calling remove_spikes on the resulting polygon, and outputting it as WKT, results in the following (boost 1.56.0):

 

POLYGON((2079 1968))

 

My questions:

-       Is this expected (no closing point)?

-       I presume that for some algorithms (which?) the position of the single point makes a difference while for others, like difference, any empty polygon should create the same result. Is this correct?

-       A year ago I made a note in my code that some algorithms cannot deal with input polygons that contain spikes (Boost.Geometry Overlay invalid input exception results). Therefore I established an invariant for my own polygons, that requires all polygons to be free of spikes. Is this still necessary?

-       How is a single-point polygon different from a spike?

-       If spikes are not allowed, how should single-point polygons be dealt with? Should they be considered empty, and have their last remaining point removed before passing them to, e.g., the difference algorithm? Or is some wrapper code required that avoids calling certain algorithms with single-point polygons?

 

My internal representation is oriented counter-clockwise and not closed, my point type is based on int.

 


I'd say that remove_spikes() assume that the Polygon is valid and since an invalid one is passed it treats it as a one spike which is removed.


This is not precise enough, sorry. A Polygon containing spikes is of course invalid so remove_spikes() can't assume that it is. It just naiively remove spikes which in some cases may result in a Polygon containing to small number of Points.


I guess at the end we could check the number of Points and throw an exception if the result contained too small number of Points.
In some cases numbers of Points are checked at the beginning of a function, maybe for "mutable" functions we should also check this at the end?


Another possible solution would be to generate invalid Polygon but, containing the "correct" number of Points, e.g.:
POLYGON((2079 1968,2079 1968,2079 1968,2079 1968)) for closed

Btw, this is related to convex_hull() for a 1- or 2-Point geometry (https://github.com/boostorg/geometry/pull/152).

Regards,
Adam

 


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: single-point polygons

Barend
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


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: single-point polygons

Volker Schöch

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

 

Thank you, that’s the key that I missed.

 

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

 

Perfect.

 

Thanks again

   Volker

 

--
Volker Schöch | [hidden email]
Senior Software Engineer


We are looking for C++ Developers: http://www.think-cell.com/career

think-cell Software GmbH http://www.think-cell.com
Chausseestr. 8/E phone / fax +49 30 666473-10 / -19
10115 Berlin, Germany US phone / fax +1 800 891 8091 / +1 212 504 3039
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schödl


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: single-point polygons

Menelaos Karavelas
In reply to this post by Barend
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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: single-point polygons

Volker Schöch

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

Has there been any progress in this regard? Apparently, in 1.57.0, is_valid(…) still reports false to the empty multi-polygon.

Should I file a boost trac ticket for this?

 

Regards

   Volker

 

--
Volker Schöch | [hidden email]
Senior Software Engineer


We are looking for C++ Developers: http://www.think-cell.com/career

think-cell Software GmbH http://www.think-cell.com
Chausseestr. 8/E phone / fax +49 30 666473-10 / -19
10115 Berlin, Germany US phone / fax +1 800 891 8091 / +1 212 504 3039
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schödl


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry