Geometry Boost List: Re: [geometry] Degenerated geometries

Subject: Re: [geometry] Degenerated geometries
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-05-05 20:40:45

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.

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

Regards,
Adam