Geometry Boost List: Re: [geometry] Degenerated geometries

Subject: Re: [geometry] Degenerated geometries
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-05-07 06:09:47

Hi,

2014-05-07 10:40 GMT+02:00 Barend Gehrels <barend_at_[hidden]>:

> Hi Adam,
>
>
>
> Adam Wulkiewicz wrote On 6-5-2014 2:40:
>
>  Hi Barend,
>>
>> Barend Gehrels wrote:
>>
>>> Hi Adam,
>>>
>>> Adam Wulkiewicz wrote On 3-5-2014 15:16:
>>>
>>>> Hi,
>>>>
>>>> I'd like to begin a little mindstorm about the degenerated Geometries
>>>> if and how they should be handled in Boost.Geometry.
>>>>
>>>> What do I have in mind? E.g. a Linear geometry degenerated to a single
>>>> Point -> LINESTRING(0 0, 0 0).
>>>> The OGC spec. defines such Geometries as invalid. But it doesn't mean
>>>> that Boost.Geometry shouldn't handle them in some uniform/specified way.
>>>> Especially when we consider some edge-cases - non-OGC Geometries like
>>>> Segment, Box, NSphere, etc. In the case of bounding objects it's even more
>>>> important because it's normal they can be degenerated. E.g. AABB of a Point
>>>> or of a Segment parallel to one of the axes.
>>>>
>>>> For those of you which aren't well versed in the ways of the OGC. OGC
>>>> uses DE9IM model to e.g. define spatial relations. In short, it doesn't
>>>> matter if some geometry has a boundary if we're checking if geometries
>>>> intersects(). But it's important for other relations, like touches().
>>>>
>>>> So in short, we could treat geometries degenerated to a Point like
>>>> Points (topological dimension = 0, no boundaries). Those would be the
>>>> examples of Point-like Geometries:
>>>> linestring(0 0, 0 0)
>>>> segment(0 0, 0 0)
>>>> box(0 0, 0 0)
>>>>
>>>
>>> segment and box are easy to check and I agree with the approach.
>>> However, a linestring can contain a million of the same point, and then
>>> one other point. Is it then degenerate? And should we check that before?
>>> The same for polygons and multi-versions.
>>>
>>>
>> I thought about handling only 2-Point Linestrings this way but all
>> segments are already checked in sectionalize<> so we'd just need to expose
>> the info about the degeneration of all sections.
>>
>
> I see - that makes sense. But sectionalize is not used for all algorithms.
> Handling only 2 point linestrings would indeed solve the problem.
>
>
>
>
>>
>>>> Pros:
>>>> 1. We'd support those edge cases in the unified way.
>>>> 2. The BoundingBox containing some Geometry would have the properties
>>>> of this Geometry (E.g. AABB of a Point would behave the same way as a Point
>>>> which it contains).
>>>> 3. This way we could e.g. store "Points" (Point-sized Linestrings)
>>>> along with the Linestrings in the same Container. But for this better would
>>>> be the support for Variants and GeometryCollection.
>>>> 4. ?
>>>>
>>>> Cons:
>>>> Each spatial relation test would be forced to somehow perform a check
>>>> if a Geometry was degenerated and process them differently. This shouldn't
>>>> be a big overhead even for Linestrings/Polygons.
>>>>
>>>
>>> See above - I would rather avoid this...
>>>
>>>
>> Same here, if all degenerated - a Point.
>>
>>
>>>  In get_turns/sectionalize all segments are already checked for
>>>> degeneration, we could just expose this information. So Point-sized
>>>> geometries could be simply handled. Even Polygons degenerated to a Segment.
>>>> However more complicated cases like Polygon degenerated to a Linestring
>>>> would require more analysis. So we probably wouldn't be fully consistent
>>>> with this and support only Geometries degenerated to a
>>>> Point/Segment/SimplePrimitive (which btw also means that Areal geometry has
>>>> area = 0, Linear has length = 0, Volumetric has volume = 0, etc.).
>>>>
>>>> E.g. in the case of Boxes we should probably handle Boxes degenerated
>>>> to a Point or a Segment (or rectangle for 3d, etc...). In this case we can
>>>> define a consistent behavior. If MIN == MAX for some dimension, there is no
>>>> Boundary in this dimension and the actual topological_dimension is lesser
>>>> by 1. This should work for n-d. The same when we have non-Point 1d Box or
>>>> NSphere, they degenerate to a Segment, which means that they'd have 2-Point
>>>> boundary.
>>>>
>>>> Regards,
>>>> Adam
>>>>
>>>> P.S. Currently Boxes are handled without taking the error into account
>>>> (Box/Box not e.g. Box/Polygon). This means that e.g. intersects() may
>>>> return FALSE for Bounding Boxes and TRUE for Geometries contained within
>>>> them. Shouldn't Boxes be consistent with the rest? Shouldn't we add a
>>>> strategy consistent with OGC geometries (taking errors into account) and
>>>> make it the default one?
>>>>
>>>
>>> Thanks for your suggestions. My opinion is that we should avoid each
>>> check for corner cases (unless it is really easy and fast to check, e.g.
>>> for a segment). I'm not completely sure what it solves for linestrings.
>>> Because if they are partly degenerate (duplicate points) and partly not, we
>>> have to handle them anyway. So what is wrong if we don't do this, but just
>>> enter the current functionality?
>>>
>>
>> This is more important for bounding objects like Boxes. At least I see a
>> small problem here. Because Boxes may degenerate to a Point it's not clear
>> to me how relate() should work for such Boxes.
>> The rest of the degenerated Geometries could just be more-or-less
>> consistent.
>>
>> It's not a proposal/suggestion but an invitation to a mindstorm.
>>
>
> I see, good.
>
> Box is not an OGC geometry, it is more our less on ourselves what to do
> with it. Handling it as a point seems good to me. A box can also be
> degenerated in another way, e.g. if left is on the right of right.
>
>
Ah yes, this is another thing. I'm not sure if this should be allowed (and
e.g. should assign_inverse() be deprecated). It's because for non-cartesian
system this kind of Box can be a valid one, e.g. for spherical/geographic.
But maybe not? Maybe e.g. in expand() we should ensure that always min<=max?

Regards,
Adam