[Boost-bugs] [Boost C++ Libraries] #10647: backlog in for_each_range.hpp causes incorrect result of disjoint

Subject: [Boost-bugs] [Boost C++ Libraries] #10647: backlog in for_each_range.hpp causes incorrect result of disjoint
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-10-10 22:15:17

#10647: backlog in for_each_range.hpp causes incorrect result of disjoint
------------------------------------+---------------------------
 Reporter:  Petr Doubrava <petr@…>  |      Owner:  barendgehrels
     Type:  Bugs                    |     Status:  new
Milestone:  To Be Determined        |  Component:  geometry
  Version:  Boost 1.56.0            |   Severity:  Problem
 Keywords:                          |
------------------------------------+---------------------------
 simple test program,
 Polygon poly2 is entirely within the hole in the polygon poly1, the result
 of disjonit may be true, but is false.

 {{{
 #include <boost/geometry.hpp>
 #include <boost/geometry/geometries/point_xy.hpp>
 #include <boost/geometry/geometries/polygon.hpp>

 #include <assert.h>

 void test_polygon_disjoint()
 {
     typedef boost::geometry::model::point<double, 2,
 boost::geometry::cs::cartesian> Point;
     boost::geometry::model::polygon<Point> poly1, poly2;


     boost::geometry::read_wkt("POLYGON((0.0 0.0, 0.0 5.0, 5.0 5.0, 5.0
 0.0, 0.0 0.0)(1.0 1.0, 4.0 1.0, 4.0 4.0, 1.0 4.0, 1.0 1.0))", poly1);
     boost::geometry::correct(poly1);

     boost::geometry::read_wkt("POLYGON((2.0 2.0, 2.0 3.0, 3.0 3.0, 3.0
 2.0, 2.0 2.0))", poly2);
     boost::geometry::correct(poly2);

     bool res=boost::geometry::disjoint(poly1,poly2);
     assert(res==true);
     // res is false :-(
 }

 int main(int argc, char* argv[])
 {
   test_polygon_disjoint();
   return 0;
 }

 }}}

 The reason is probably this backlog in
 boost\geometry\algorithms\detail\for_each_range.hpp

 {{{
 ...
 template <typename Polygon, typename Actor>
 struct fe_range_polygon
 {

     static inline void apply(Polygon & polygon, Actor & actor)
     {
         actor.apply(exterior_ring(polygon));

         // TODO: If some flag says true, also do the inner rings.
         // for convex hull, it's not necessary
     }
 };
 ...
 }}}

 I created this workaround and disjoint works correctly in this case.

 {{{
 template <typename Polygon, typename Actor>
 struct fe_range_polygon
 {
     static inline void apply(Polygon & polygon, Actor & actor)
     {
         actor.apply(exterior_ring(polygon));

         if (actor.has_within) {
             Polygon::inner_container_type::const_iterator
 it=interior_rings(polygon).begin();
             for (;it!=interior_rings(polygon).end();++it)
             {
                actor.apply(*it);
                if (actor.has_within)
                {
                    actor.has_within = false;
                    break;
                }
            }
        }
    }
 };

 }}}

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