[Boost-bugs] [Boost C++ Libraries] #10772: boost::geometry::within() does not recognize empty boxes

Subject: [Boost-bugs] [Boost C++ Libraries] #10772: boost::geometry::within() does not recognize empty boxes
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-11-08 19:04:31

#10772: boost::geometry::within() does not recognize empty boxes
------------------------------+---------------------------
 Reporter:  bromeon@…         |      Owner:  barendgehrels
     Type:  Bugs              |     Status:  new
Milestone:  To Be Determined  |  Component:  geometry
  Version:  Boost 1.57.0      |   Severity:  Problem
 Keywords:                    |
------------------------------+---------------------------
 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.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/10772>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.