boost::geometry::within() does not recognize empty boxes

[bromeon@…]

If boost::geometry::within() is used to check whether an empty box (i.e. a point) is within another box, false is always returned. This is not the correct behavior because:

1. OGC defines: a.Within(b) ⇔ (a∩b=a) ∧ (I(a)∩E(b)=∅) which holds true. The intersection of an empty box a and a surrounding box b yields a. Since a has no interior, I(a)=∅, thus the second condition is also true.
2. Empty boxes should be treated as points. When using a point model instead of an empty box, the check returns the correct result as expected.

See also the following complete minimal code (it includes also other geometry algorithms that are computed consistently for points and empty boxes):

#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/algorithms/convert.hpp>
#include <boost/geometry/algorithms/within.hpp>
#include <boost/geometry/algorithms/covered_by.hpp>
#include <boost/geometry/algorithms/intersects.hpp>
#include <boost/geometry/algorithms/disjoint.hpp>
#include <boost/geometry/algorithms/distance.hpp> // needed for within() -- is this intended?
#include <iostream>

namespace bg = boost::geometry;
typedef bg::model::d2::point_xy<float> Point;
typedef bg::model::box<Point> Box;

int main()
{
    Point point(3, 4);
    Box pointAsBox;
    bg::convert(point, pointAsBox);

    Box surrounding;
    surrounding.min_corner() = Point(2, 2);
    surrounding.max_corner() = Point(5, 5);

    std::cout << "            Point Box" << std::endl;
    std::cout << "within:        " << bg::within(point,      surrounding)
                         << "    " << bg::within(pointAsBox, surrounding)     << "\n"; // 1 0 <-
    std::cout << "within (self): " << bg::within(point,      point)           
                         << "    " << bg::within(pointAsBox, pointAsBox)      << "\n"; // 1 0 <-
    std::cout << "covered_by:    " << bg::covered_by(point,      surrounding) 
                         << "    " << bg::covered_by(pointAsBox, surrounding) << "\n"; // 1 1
    std::cout << "intersects:    " << bg::intersects(point,      surrounding) 
                         << "    " << bg::intersects(pointAsBox, surrounding) << "\n"; // 1 1
    std::cout << "disjoint:      " << bg::disjoint(point,      surrounding)   
                         << "    " << bg::disjoint(pointAsBox, surrounding)   << "\n"; // 0 0
    std::cout << std::endl;
}

The implementation looks as follows (boost/geometry/strategies/cartesian/box_in_box.hpp, line 32):

struct box_within_range
{
    template <typename BoxContainedValue, typename BoxContainingValue>
    static inline bool apply(BoxContainedValue const& bed_min
                , BoxContainedValue const& bed_max
                , BoxContainingValue const& bing_min
                , BoxContainingValue const& bing_max)
    {
        return bing_min <= bed_min && bed_max <= bing_max // contained in containing
            && bed_min < bed_max;                         // interiors overlap
    }
};

The problem is the second line, which uses < and thus returns false if the coordinates are equal. I'm not sure what the intention is (despite the comment), and whether it is needed at all.

The documentation about box model and concept doesn't state whether max_corner's coordinates must be component-wise greater or equal than min_corner's. If so, it seems like valid boxes are a precondition to within() and this line could be removed.

[awulkiew]

Do you have in mind some specific use case where this is problematic for you or do you think that the library is not OGC-conformant enough in this case? In the first case covered_by() could be used instead. If the latter is true then see below.

TL,DR

The OGC standard doesn't define Box Geometry (or to be more precise axis-aligned box), it doesn't define when a Box is valid and what's the interior, boundary and exterior of a Box. It's not said that a Box may degenerate to a Point or to a Segment and be still valid Geometry. It's not clear that the definition of an interior and boundary should be taken from other geometries like a Point or a Segment or a Polygon in the case of degenerated 3D Box. And even if it'd probably work well both points mentioned by you not necessarily are true simply because in the OGC specs axis-aligned Boxes doesn't exist.

Indeed currently the library uses Box definition different than the one you presented. That is currently a degenerated Box consists only of a boundary (opposed to a Point which has no boundary). It's because this way it allows to use only this small set of 3 conditions to check the within predicate. The last condition is there because for within to be true the interiors must overlap. This way also a small set of conditions is needed to check touches or overlaps predicates and be consistent with within.

Btw, I'm calling it "degenerated" because if it was empty it'd probably have no interior nor boundary, it'd be treated as an exterior so any special predicate should probably return false for it.

Now, if we wanted to treat degenerated Box as a Point (a Geometry with no boundary) or Segment (linear interior and 2-point boundary) we couldn't remove the 3rd condition. Without the 3rd condition within would return true incorrectly e.g. for a degenerated Box overlapping the boundary of a second non-degenerated Box. In order to make it "OGC-conformant" we'd be forced to add 2 more conditions:

• check if a contained degenerated Box/Point is on the boundary of containing because then the interiors wouldn't overlap
• check if containing Box is not degenerated as well because in this case it wouldn't have a boundary, so a within could return true in this case (for both degenerated).

Not to mention that we'd be forced to change the implementation of touches in a similar way, so add more conditions. Also, since a Box might degenerate to a Segment we'd be forced to add more conditions to overlaps and support Boxes in crosses. To sum up, currently within uses a definition of a Box which is consistent across spatial predicates and allows to implement them with a minimal set of conditions.

With that said, I'm not against removing the third condition. However I'd like to hear more "complete" proposal, taking into account other predicates and providing a clear definition of a Box. If we removed the 3rd condition the predicate check would be simpler/faster. The Box is not defined in the OGC-specification so we may basically do whatever we think is the best. But it would be less consistent across functions and still not "OGC-conformant". It would work exactly how covered_by works right now so wouldn't add functionality.