Boost logo

Geometry :

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

Geometry list run by mateusz at