Geometry Boost List: Re: [geometry] what should be the minimum size of geometries supported in BG algorithms?

Subject: Re: [geometry] what should be the minimum size of geometries supported in BG algorithms?
From: Barend Gehrels (barend_at_[hidden])
Date: 2015-01-13 16:48:10

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