polygon contains() gives wrong values for axis-aligned rectangles

[Andy Ross <andy@…>]

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;
}

[anonymous]

I overlooked the vertical edge case. point on-above-or-below line segment returns on the line for vertical case even if the point is past the end of the line. Now vertical segments are special cased and handled correctly.