Boost logo

Geometry :

Subject: [geometry] R-tree bounds, spatial relations and envelope
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2015-08-24 09:47:10


Recently I've run into an issue that is related for instance with the
R-tree. It's caused by the fact that the if the floating-point
coordinates are used, spatial relations of OGC-Geometries like Point or
Segment are checked WRT machine epsilon but in the case of Boxes the
coordinates are compared without taking epsilon into account. This of
course makes the Boxes checks faster. However it also means that if a
Box is a "minimum bounding box/rectangle", i.e. min/max values are
exactly the min/max coordinates of the corresponding bounded geometries,
the spatial relation may give unexpected results. For instance:

point p(0, 0);
point p_eps(-eps/2, -eps/2);
box b(point(0, 0), point(1, 1));

bg::equals(p, p_eps) == true;
bg::intersects(b, p) == true;
// but
bg::intersects(b, p_eps) == false;

It looks more or less like this:

And this is true for any non-Box geometry, e.g. for two Polygons and
their bounding boxes the results may be similar to the ones showed
above. It could be observed in the R-tree or any other space
partitioning data structure or algorithm using Boxes. In particular, it
means that in some very specific cases R-tree spatial queries may give
different results than spatial relations checks done without the spatial

Have anyone noticed this problem?
Do you think that it is a problem that needs to be fixed?
Now that I've described this problem, do you find some specific case in
your own code that could be affected by it?
I'm asking because it may be acceptible to prune slightly more
nodes/values (so not interesting space) even if the result wouldn't be
prefectly "correct".

To improve/fix it we could check the spatial relations for Boxes WRT
epsilon. However this slows down many algorithms in the library, e.g.
buffer() by 25% and the rtree spatial queries 2x or more which I think
is unacceptable.

Another thing that could be done is to enlarge the bounding boxes WRT
epsilon, in a way consistent with the spatial equality checks used in
the library. This solves the problem and there is no direct performance
loss. I'm saying direct because this would cause that slightly greater
number of nodes could be traversed and values returned simply because
this would be the correct behavior. Though the enlargement is so small
that this shouldn't be noticeable, at least I haven't noticed any
change. So it seems that this is the way to go. The catch is that the
rtree bounds (bounding box) would no longer have the min/max coordinates
exactly the same as the min/max coordinates of represented Points or
Segments stored in the rtree.

Btw, there is no need to enlarge the nodes' Boxes if value Boxes are
stored because the spatial relations are checked the same way for both.
If the value Boxes represented some non-Box Geometries like Polygons
they could probably be enlarged before storing them in the index. Then
the R-tree would simply use those enlarged Boxes.

Do you think that the slightly enlarged R-tree bounds for Point and
Segments could cause some other problems?
Would you prefer if it was possible to enable or disable this feature?
Would you prefer to have it enabled or disabled by default?



Geometry list run by mateusz at