what should be the minimum size of geometries supported in BG algorithms?

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

what should be the minimum size of geometries supported in BG algorithms?

Menelaos Karavelas
Hello all and happy new year.

I have been facing the following issue when implementing support for various algorithms in BG and for various geometries (especially with bg::distance): what should be the minimum sized geometry that should be supported by the algorithm?

More precise questions:
  • should bg::distance be able to return a distance when one-point linestrings are passed to it?
  • should bg::distance be able to return a distance when one of the two input geometries is a closed polygon with less than four points?

In both cases above the geometries are invalid (in the OGC sense), and this actually brings up a more general question. To what extend should we support invalid geometries in BG algorithms?

In the current version of bg::distance if the uses passes an one-point linestring the algorithm sometimes returns something meaningful, and other times an assertion is triggered. Such a behavior is IMHO in some sense okay: BG algorithms are not guaranteed to work on invalid input (but they should work with valid input). So either returning something meaningful or triggering an assertion, or even returning something not meaningful is okay in the sense that the algorithm's behavior is undefined.

Motivated by the above I decided to implement a new algorithm called is_below_minimum_size. It takes a geometry as input and returns true if the geometry's size is below the minimum acceptable valid size (see also the corresponding PR: https://github.com/boostorg/geometry/pull/193). In the PR there is a related new exception, and my intention was to use that exception instead of the empty_geometry_exception currently used in the bg::distance code. Using the new exception would avoid some assertion failures, and would treat geometries with very few points in a unified manner (through exceptions).
On the other hand, it would limit the support for bg::distance on invalid geometries.

I would like your thoughts/suggestions/comments on any of the statements made above.

All the best,

- m.


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

Re: what should be the minimum size of geometries supported in BG algorithms?

Adam Wulkiewicz
Hi Menelaos

Menelaos Karavelas wrote:
Hello all and happy new year.

Happy new year!

I have been facing the following issue when implementing support for various algorithms in BG and for various geometries (especially with bg::distance): what should be the minimum sized geometry that should be supported by the algorithm?

More precise questions:
  • should bg::distance be able to return a distance when one-point linestrings are passed to it?
  • should bg::distance be able to return a distance when one of the two input geometries is a closed polygon with less than four points?

In both cases above the geometries are invalid (in the OGC sense), and this actually brings up a more general question. To what extend should we support invalid geometries in BG algorithms?

In the current version of bg::distance if the uses passes an one-point linestring the algorithm sometimes returns something meaningful, and other times an assertion is triggered. Such a behavior is IMHO in some sense okay: BG algorithms are not guaranteed to work on invalid input (but they should work with valid input). So either returning something meaningful or triggering an assertion, or even returning something not meaningful is okay in the sense that the algorithm's behavior is undefined.


Only one remark, to be clear. By "work" do you mean "return valid result" or "not blow up the whole program"?
I mean assertions should fail when a programmer's error was hit. In this case the input data which could be loaded from some external source represents an invalid geometry. At least it's my understanding. So in my opinion in this case an algortihm could return some result (maybe in some cases the correct one) or an exception could be thrown.

Motivated by the above I decided to implement a new algorithm called is_below_minimum_size. It takes a geometry as input and returns true if the geometry's size is below the minimum acceptable valid size (see also the corresponding PR: https://github.com/boostorg/geometry/pull/193). In the PR there is a related new exception, and my intention was to use that exception instead of the empty_geometry_exception currently used in the bg::distance code. Using the new exception would avoid some assertion failures, and would treat geometries with very few points in a unified manner (through exceptions).
On the other hand, it would limit the support for bg::distance on invalid geometries.

I would like your thoughts/suggestions/comments on any of the statements made above.

 
Some functions already handle such degenerated geometries somehow (buffer?, centroid, area).
Other functions just ignore them (get_turns and therefore all relops and setops).
But currently there is no function throwing an exception in this case.

Do you think that along with this change all other function should be consistently changed to throw this exception?
Or should various functions handle such degenerated geometries differently?
Or something else?

AFAIU in BG a tradition is to throw an exception when there is nothing else that could be done.
E.g. a centroid() of empty geometry can't be calculated in any way, but for invalid geometry it can be, the result just may be invalid. In some cases it'd be even correct or close.
area() is quite obvious case which can be calculated and even for an empty geometry == 0.

What do you think about being in line with this approach and instead of throwing an exception returning some (in some cases correct) result when a geometry hasn't enough points?
E.g. just use the first point of a geometry (or rather sub-geometry), e.g. returned by point_iterator<> or point_on_porder().
This'd give the correct result at least for linestrings and polygons degenerated to a point.
For other cases like polygon containing too small number of points it'd give more or less the correct result.

Another thing is that the function is_below_minimum_size() would just return true if any of the sub-geometries was degenerated.
M
aybe it could be convenient for the users if such geometry was ignored instead?
The same is true for interior rings, maybe they should be handled differently than the exterior ring?
This way the distance function wouldn't throw an exception if a MultiPolygon containing one Polygon with one degenerated interior ring was found. And it'd be a great probability that a result of distance() would be the correct one.

Regards,
Adam

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

Re: what should be the minimum size of geometries supported in BG algorithms?

Barend
Hi Menelaos,


Adam Wulkiewicz schreef op 13-1-2015 om 17:46:
Hi Menelaos

Menelaos Karavelas wrote:
Hello all and happy new year.

Happy new year!

I have been facing the following issue when implementing support for various algorithms in BG and for various geometries (especially with bg::distance): what should be the minimum sized geometry that should be supported by the algorithm?

More precise questions:
  • should bg::distance be able to return a distance when one-point linestrings are passed to it?

Why not?

  • should bg::distance be able to return a distance when one of the two input geometries is a closed polygon with less than four points?

Why is that important for distance?

In both cases above the geometries are invalid (in the OGC sense), and this actually brings up a more general question. To what extend should we support invalid geometries in BG algorithms?


We don't check them before. We do best-effort. For length (of a one-point linestring) we return just 0. For area (for a 2 point polygon) we return just 0. For distance we can return anything, provided that there is at least one point.

You can't analyse the polygon completely. Also a polygon with 100 points can be invalid. So we should, basically, be able to handle invalid polygons in some sense...


In the current version of bg::distance if the uses passes an one-point linestring the algorithm sometimes returns something meaningful, and other times an assertion is triggered. Such a behavior is IMHO in some sense okay: BG algorithms are not guaranteed to work on invalid input (but they should work with valid input). So either returning something meaningful or triggering an assertion, or even returning something not meaningful is okay in the sense that the algorithm's behavior is undefined.


Only one remark, to be clear. By "work" do you mean "return valid result" or "not blow up the whole program"?
I mean assertions should fail when a programmer's error was hit. In this case the input data which could be loaded from some external source represents an invalid geometry. At least it's my understanding. So in my opinion in this case an algortihm could return some result (maybe in some cases the correct one) or an exception could be thrown.


Agree with this.


Motivated by the above I decided to implement a new algorithm called is_below_minimum_size. It takes a geometry as input and returns true if the geometry's size is below the minimum acceptable valid size (see also the corresponding PR: https://github.com/boostorg/geometry/pull/193). In the PR there is a related new exception, and my intention was to use that exception instead of the empty_geometry_exception currently used in the bg::distance code.


It looks like a complete implementation including tests and variants...  But why not discuss it (the part above) before implementing? Now the work has been done, it is harder to reject it...


Using the new exception would avoid some assertion failures, and would treat geometries with very few points in a unified manner (through exceptions).
On the other hand, it would limit the support for bg::distance on invalid geometries.

I would like your thoughts/suggestions/comments on any of the statements made above.

 
Some functions already handle such degenerated geometries somehow (buffer?, centroid, area).
Other functions just ignore them (get_turns and therefore all relops and setops).
But currently there is no function throwing an exception in this case.

True - they only throw if there is no point at all.


Do you think that along with this change all other function should be consistently changed to throw this exception?
Or should various functions handle such degenerated geometries differently?
Or something else?

AFAIU in BG a tradition is to throw an exception when there is nothing else that could be done.

Yep.

E.g. a centroid() of empty geometry can't be calculated in any way, but for invalid geometry it can be, the result just may be invalid. In some cases it'd be even correct or close.
area() is quite obvious case which can be calculated and even for an empty geometry == 0.

What do you think about being in line with this approach and instead of throwing an exception returning some (in some cases correct) result when a geometry hasn't enough points?
E.g. just use the first point of a geometry (or rather sub-geometry), e.g. returned by point_iterator<> or point_on_porder().
This'd give the correct result at least for linestrings and polygons degenerated to a point.
For other cases like polygon containing too small number of points it'd give more or less the correct result.

Another thing is that the function is_below_minimum_size() would just return true if any of the sub-geometries was degenerated.
M
aybe it could be convenient for the users if such geometry was ignored instead?
The same is true for interior rings, maybe they should be handled differently than the exterior ring?
This way the distance function wouldn't throw an exception if a MultiPolygon containing one Polygon with one degenerated interior ring was found. And it'd be a great probability that a result of distance() would be the correct one.

Agree with Adam's questions, I've the same doubts about this feature...


Regards, Barend




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