[Boost-bugs] [Boost C++ Libraries] #5312: polygon contains() gives wrong values for axis-aligned rectangles

Subject: [Boost-bugs] [Boost C++ Libraries] #5312: polygon contains() gives wrong values for axis-aligned rectangles
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2011-03-15 22:06:22

#5312: polygon contains() gives wrong values for axis-aligned rectangles
--------------------------------------------+-------------------------------
 Reporter:  Andy Ross <andy@…>              |       Owner:  ljsimons
     Type:  Bugs                            |      Status:  new     
Milestone:  To Be Determined                |   Component:  polygon 
  Version:  Boost 1.46.0                    |    Severity:  Problem 
 Keywords:                                  |  
--------------------------------------------+-------------------------------
 It appears that when a polygon is an axis-aligned rectangle, all (!)
 points along the projection of the Y-axis sides (i.e. with the same X
 coordinate as an edge of the polygon) show up as "inside" the polygon.

 A workaround for many cases is to pass consider_touch==true, which
 fixes the clearly incorrect results at the expense of proper edge
 sensitivity.

 I didn't test other refinements than polygon, so I don't know if this
 behavior is shared or specific.

 Tested against Boost 1.46.0 and SVN as of submission date.

 {{{
 #include <boost/polygon/polygon.hpp>
 #include <assert.h>

 namespace gtl = boost::polygon;

 typedef gtl::polygon_data<int> Polygon;
 typedef gtl::polygon_traits<Polygon>::point_type Point;

 int main()
 {
     // Axis-aligned rectangle
     const Point rect[] = {
         Point(0, 0),
         Point(0, 1),
         Point(2, 1),
         Point(2, 0)
     };

     Polygon p;
     gtl::set_points(p, rect, rect+(sizeof(rect)/sizeof(rect[0])));

     // Points inside the polygon: these cases work.
     assert(gtl::contains(p, Point(1, 0)));
     assert(gtl::contains(p, Point(1, 1)));

     // Points outside the polygon: these cases work.
     assert(!gtl::contains(p, Point(1, -1)));
     assert(!gtl::contains(p, Point(1, 2)));
     assert(!gtl::contains(p, Point(3, 2)));
     assert(!gtl::contains(p, Point(-1, 2)));

     // Point outside the polygon with consider_touch false, this works
     assert(!gtl::contains(p, Point(2, 2), false));

     // Points outside the polygon: these cases FAIL.  Note X
     // coordinate lies along the projection of the vertical edges.
     assert(!gtl::contains(p, Point(0, 2)));
     assert(!gtl::contains(p, Point(2, -1)));
     assert(!gtl::contains(p, Point(0, -1)));
     assert(!gtl::contains(p, Point(2, 2)));

     return 0;
 }
 }}}

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