Boost logo

Geometry :

Subject: Re: [geometry] Degenerated geometries
From: Barend Gehrels (barend_at_[hidden])
Date: 2014-05-05 15:01:58

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.

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

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

Regards, Barend

Geometry list run by mateusz at