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.