Boost logo

Geometry :

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

It's not a proposal/suggestion but an invitation to a mindstorm.


Geometry list run by mateusz at