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