Boost logo

Geometry :

Subject: Re: [geometry] Degenerated geometries
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-05-07 06:09:47


2014-05-07 10:40 GMT+02:00 Barend Gehrels <barend_at_[hidden]>:

> 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.
Ah yes, this is another thing. I'm not sure if this should be allowed (and
e.g. should assign_inverse() be deprecated). It's because for non-cartesian
system this kind of Box can be a valid one, e.g. for spherical/geographic.
But maybe not? Maybe e.g. in expand() we should ensure that always min<=max?


Geometry list run by mateusz at