Boost logo

Geometry :

Subject: [geometry] Degenerated geometries
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-05-03 09:16:18


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)

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


Geometry list run by mateusz at loskot.net