Bug in "boost::polygon::contains" for polygon_90 type

[sebastien.mirabel@…]

For a polygon ((0,0) (10,0) (10,10) (0,10)) the function "contains" returns true for (15,5) whereas it should return true

#include <boost/polygon/polygon.hpp>

#include <cassert>
#include <iostream>

namespace gtl = boost::polygon;
using namespace boost::polygon::operators;

int main() {
    //lets construct a 10x10 rectangle shaped polygon
    typedef gtl::polygon_90_data<int> Polygon;
    typedef gtl::polygon_traits_90<Polygon>::point_type Point;
	Point pts[] = {
		gtl::construct<Point>(0, 0),
		gtl::construct<Point>(10, 0),
		gtl::construct<Point>(10, 10),
		gtl::construct<Point>(0, 10)};
    Polygon poly;
    gtl::set_points(poly, pts, pts+4);
	
    Point point = gtl::construct<Point>(15, 5);
	{
		// Wrong result here :
		bool result = gtl::contains(poly, point);
		std::cout << std::boolalpha << result << std::endl;
	}
    //assert(!gtl::contains(poly, point));
    //assert(!gtl::contains(poly, gtl::construct<Point>(15, 5)));
    return 0;
}

The bugs seems to come from line 1176 of "boost\polygon\polygon_traits.hpp" :

    //an odd number of edges to the left implies interior pt
    return counts[winding(polygon) == COUNTERCLOCKWISE ? 0 : 1] % 4 != 0; 

There is "% 4" whereas the previous comment indicate "an odd number of edges" (this logicaly should be "% 2")

[sebastien.mirabel@…]

Based on "gtl_polygon_usage" from the documentation

[Lucanus Simonson]

This was fixed a long time ago.

[sebastien.mirabel@…]

The bug is still there in 1.51 and in trunk. The bug fixed "a long time ago" is probably an other one with similar behaviour.

Here is a program that show more obviously the bug:

#include <boost/polygon/polygon.hpp>

#include <cassert>
#include <iostream>

namespace gtl = boost::polygon;
using namespace boost::polygon::operators;

int main() {
    typedef gtl::polygon_90_data<int> Polygon;
    typedef gtl::polygon_traits_90<Polygon>::point_type Point;
    //lets construct a 10x10 rectangle shaped polygon
    Point pts1[] = {
        gtl::construct<Point>(0, 0),
        gtl::construct<Point>(10, 0),
        gtl::construct<Point>(10, 10),
        gtl::construct<Point>(0, 10)
    }; 

    Point pts2[] = {
        gtl::construct<Point>(0, 10),
        gtl::construct<Point>(10, 10),
        gtl::construct<Point>(10, 0),
        gtl::construct<Point>(0, 0)
    };

    Polygon poly1;
    gtl::set_points(poly1, pts1, pts1+4);
    Polygon poly2;
    gtl::set_points(poly2, pts2, pts2+4);

    Point point1 = gtl::construct<Point>(15, 5);
    Point point2 = gtl::construct<Point>(5, 5);

    {
        bool result;
        result = gtl::contains(poly1, point1);
        std::cout << "15,5 in poly1 " << std::boolalpha << result << std::endl;

        result = gtl::contains(poly1, point2);
        std::cout << " 5,5 in poly1 " << std::boolalpha << result << std::endl;

        result = gtl::contains(poly2, point1);
        std::cout << "15,5 in poly2 " << std::boolalpha << result << std::endl;

        result = gtl::contains(poly2, point2);
        std::cout << " 5,5 in poly2 " << std::boolalpha << result << std::endl;
    }
    return 0;
}

Output:

15,5 in poly1 true
 5,5 in poly1 true
15,5 in poly2 false
 5,5 in poly2 true

[Andrii Sydorchuk]

Patch

[Andrii Sydorchuk]

Hi Sebastien,

I fixed the issue. You can either sync with trunk or patch (check attachments).

[sebastien.mirabel@…]

Hi Andrii,

It works now (tested with trunk). Thanks !

Sébastien

[anonymous]

The bug is still there in 1.55

59 typedef polygon_90_data<int> Polygon; 60 typedef polygon_traits_90<Polygon>::point_type Point; 61 Point pts1[] = { 62 construct<Point>(25200, 7100), 63 construct<Point>(29000, 7100), 64 construct<Point>(29000, 4950), 65 construct<Point>(27100, 4950), 66 construct<Point>(27100, 4250), 67 construct<Point>(33050, 4250), 68 construct<Point>(33050, 7050), 69 construct<Point>(36300, 7050), 70 construct<Point>(36300, 2300), 71 construct<Point>(34700, 2300), 72 construct<Point>(34700, 1600), 73 construct<Point>(37000, 1600), 74 construct<Point>(37000, 3500), 75 construct<Point>(40550, 3500), 76 construct<Point>(40550, 4850), 77 construct<Point>(37000, 4850), 78 construct<Point>(37000, 7100), 79 construct<Point>(37900, 7100), 80 construct<Point>(37900, 7800), 81 construct<Point>(32350, 7800), 82 construct<Point>(32350, 4950), 83 construct<Point>(29700, 4950), 84 construct<Point>(29700, 7100), 85 construct<Point>(30300, 7100), 86 construct<Point>(30300, 7800), 87 construct<Point>(25200, 7800) 88 }; 89 90 Point pts2[] = { 91 construct<Point>(25200, 7800), 92 construct<Point>(30300, 7800), 93 construct<Point>(30300, 7100), 94 construct<Point>(29700, 7100), 95 construct<Point>(29700, 4950), 96 construct<Point>(32350, 4950), 97 construct<Point>(32350, 7800), 98 construct<Point>(37900, 7800), 99 construct<Point>(37900, 7100),

100 construct<Point>(37000, 7100), 101 construct<Point>(37000, 4850), 102 construct<Point>(40550, 4850), 103 construct<Point>(40550, 3500), 104 construct<Point>(37000, 3500), 105 construct<Point>(37000, 1600), 106 construct<Point>(34700, 1600), 107 construct<Point>(34700, 2300), 108 construct<Point>(36300, 2300), 109 construct<Point>(36300, 7050), 110 construct<Point>(33050, 7050), 111 construct<Point>(33050, 4250), 112 construct<Point>(27100, 4250), 113 construct<Point>(27100, 4950), 114 construct<Point>(29000, 4950), 115 construct<Point>(29000, 7100), 116 construct<Point>(25200, 7100) 117 }; 118 119 Polygon poly1; 120 set_points(poly1, pts1, pts1+4); 121 Polygon poly2; 122 set_points(poly2, pts2, pts2+4); 123 124 Point point2 = construct<Point>(28000, 4950); 125 Point point1 = construct<Point>(41900, 4950); 126 127 { 128 bool result; 129 result = contains(poly1, point1, true); 130 std::cout << x(point1) << ", " << y(point1) << " in poly1 " << std::boolalpha << result << std::endl; 131 132 result = contains(poly2, point1, true); 133 std::cout << x(point1) << ", " << y(point1) << " in poly2 " << std::boolalpha << result << std::endl; 134 135 result = contains(poly1, point2, true); 136 std::cout << x(point2) << ", " << y(point2) << " in poly1 " << std::boolalpha << result << std::endl; 137 138 result = contains(poly2, point2, true); 139 std::cout << x(point2) << ", " << y(point2) << " in poly2 " << std::boolalpha << result << std::endl; 140 }

Output: 41900, 4950 in poly1 false 41900, 4950 in poly2 false 28000, 4950 in poly1 true 28000, 4950 in poly2 false

[anonymous]

The bug is still there in boost_1_55_0!!

typedef polygon_90_data<int> Polygon;

typedef polygon_traits_90<Polygon>::point_type Point;

Point pts1[] = {

construct<Point>(25200, 7100), construct<Point>(29000, 7100), construct<Point>(29000, 4950), construct<Point>(27100, 4950), construct<Point>(27100, 4250), construct<Point>(33050, 4250), construct<Point>(33050, 7050), construct<Point>(36300, 7050), construct<Point>(36300, 2300), construct<Point>(34700, 2300), construct<Point>(34700, 1600), construct<Point>(37000, 1600), construct<Point>(37000, 3500), construct<Point>(40550, 3500), construct<Point>(40550, 4850), construct<Point>(37000, 4850), construct<Point>(37000, 7100), construct<Point>(37900, 7100), construct<Point>(37900, 7800), construct<Point>(32350, 7800), construct<Point>(32350, 4950), construct<Point>(29700, 4950), construct<Point>(29700, 7100), construct<Point>(30300, 7100), construct<Point>(30300, 7800), construct<Point>(25200, 7800)

};

Point pts2[] = {

construct<Point>(25200, 7800), construct<Point>(30300, 7800), construct<Point>(30300, 7100), construct<Point>(29700, 7100), construct<Point>(29700, 4950), construct<Point>(32350, 4950), construct<Point>(32350, 7800), construct<Point>(37900, 7800), construct<Point>(37900, 7100), construct<Point>(37000, 7100), construct<Point>(37000, 4850), construct<Point>(40550, 4850), construct<Point>(40550, 3500), construct<Point>(37000, 3500), construct<Point>(37000, 1600), construct<Point>(34700, 1600), construct<Point>(34700, 2300), construct<Point>(36300, 2300), construct<Point>(36300, 7050), construct<Point>(33050, 7050), construct<Point>(33050, 4250), construct<Point>(27100, 4250), construct<Point>(27100, 4950), construct<Point>(29000, 4950), construct<Point>(29000, 7100), construct<Point>(25200, 7100)

};

Polygon poly1;

set_points(poly1, pts1, pts1+4);

Polygon poly2;

set_points(poly2, pts2, pts2+4);

Point point2 = construct<Point>(28000, 4950);

Point point1 = construct<Point>(41900, 4950);

{

bool result;

result = contains(poly1, point1, true);

std::cout << x(point1) << ", " << y(point1) << " in poly1 " << std::boolalpha << result << std::endl;

result = contains(poly2, point1, true);

std::cout << x(point1) << ", " << y(point1) << " in poly2 " << std::boolalpha << result << std::endl;

result = contains(poly1, point2, true);

std::cout << x(point2) << ", " << y(point2) << " in poly1 " << std::boolalpha << result << std::endl;

result = contains(poly2, point2, true);

std::cout << x(point2) << ", " << y(point2) << " in poly2 " << std::boolalpha << result << std::endl;

}

Output:

41900, 4950 in poly1 false

41900, 4950 in poly2 false

28000, 4950 in poly1 true

28000, 4950 in poly2 false

[Andrii Sydorchuk]

From the brief view on the last example I don't see any unexpected behavior. Please clarify the issue.

Andrii

[Sébastien]

@Andrii: I just take a look at "anonymous" test and there is un error in his code because he uses "set_points(poly1, pts1, pts1+4);" whereas he use an array of 26 points.

@anonymous: Do you still have the bug if you replace 4 by the correct size ?

[anonymous]

Sorry for my typo, set_points(poly1, pts1, pts1+4) and set_points(poly2, pts2, pts2+4) should be set_points(poly1, pts1, pts1+26) and set_points(poly2, pts2, pts2+26), respectively.

However, it still got the wrong results after fixing the typo. poly1 and poly2 are actually the same shape and the results I got are shown as follows:

41900, 4950 in poly1 true

41900, 4950 in poly2 true

28000, 4950 in poly1 true

28000, 4950 in poly2 true

The correct results should be as follows, where poly1(poly2) does not contain point1:

41900, 4950 in poly1 false

41900, 4950 in poly2 false

28000, 4950 in poly1 true

28000, 4950 in poly2 true

[Sébastien <sebastien.mirabel@…>]

@anonymous: I'm not sure "contains" is aware of orientation of polygons (I don't know very well this library, I have only submitted the bug). You should probably use it in combination with "winding" function. Somebody will probably answer you if you ask on boost mailing list.

[Andrii Sydorchuk]

Thanks for the follow up, I was able to reproduce the issue. Investigating.

Andrii

[Andrii Sydorchuk]

Thanks for the report again! I've fixed the issue in both develop and master branches of ​https://github.com/boostorg/polygon. Please find the patch for your convenience attached. The change will permanently go into Boost 1.57.