Boost C++ Libraries: Ticket #6366: Bug in "boost::polygon::contains" for polygon_90 type

attachment set

sebastien.mirabel@… — Sat, 07 Jan 2012 15:27:07 GMT

attachment → gtl_polygon_usage_bug.cpp

Based on "gtl_polygon_usage" from the documentation

status changed; resolution set

Lucanus Simonson — Wed, 19 Sep 2012 00:36:05 GMT

status new → closed
resolution → fixed

This was fixed a long time ago.

status, version changed; resolution deleted

sebastien.mirabel@… — Mon, 29 Oct 2012 01:05:16 GMT

status closed → reopened
version Boost 1.48.0 → Boost 1.51.0
resolution fixed

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

attachment set

Andrii Sydorchuk — Tue, 30 Oct 2012 22:23:40 GMT

attachment → polygon_traits.patch

Patch

Andrii Sydorchuk — Tue, 30 Oct 2012 22:24:47 GMT

Hi Sebastien,

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

sebastien.mirabel@… — Sat, 03 Nov 2012 15:17:32 GMT

Hi Andrii,

It works now (tested with trunk). Thanks !

Sébastien

owner, status, milestone changed

Andrii Sydorchuk — Wed, 14 Nov 2012 11:41:23 GMT

owner changed from Lucanus Simonson to Andrii Sydorchuk
status reopened → new
milestone To Be Determined → Boost 1.53.0

status changed; resolution set

Andrii Sydorchuk — Wed, 06 Mar 2013 22:53:37 GMT

status new → closed
resolution → fixed

anonymous — Tue, 25 Feb 2014 17:19:36 GMT

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 — Tue, 25 Feb 2014 17:24:34 GMT

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 — Wed, 26 Feb 2014 21:56:43 GMT

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

Andrii

Sébastien — Thu, 27 Feb 2014 01:03:53 GMT

@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 — Thu, 27 Feb 2014 13:30:25 GMT

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

Mon, 03 Mar 2014 01:09:52 GMT

@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 — Mon, 03 Mar 2014 02:00:53 GMT

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

Andrii

milestone changed

Andrii Sydorchuk — Wed, 19 Mar 2014 20:20:40 GMT

milestone Boost 1.53.0 → Boost 1.57.0

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.

attachment set

Andrii Sydorchuk — Wed, 19 Mar 2014 20:21:27 GMT

attachment → 0001-Polygon-fixing-reopend-issue-6366-defect-in-polygon-.patch