Geometry Boost List: Re: [geometry] Degenerated geometries

Subject: Re: [geometry] Degenerated geometries
From: Barend Gehrels (barend_at_[hidden])
Date: 2014-05-07 04:40:32

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.

Regards, Barend