Modify

Ticket #6366 (closed Bugs: fixed)

Opened 2 years ago

Last modified 5 weeks ago

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

Reported by: sebastien.mirabel@… Owned by: asydorchuk
Milestone: Boost 1.57.0 Component: polygon
Version: Boost 1.51.0 Severity: Problem
Keywords: Cc: sebastien.mirabel@…

Description

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")

Attachments

gtl_polygon_usage_bug.cpp Download (868 bytes) - added by sebastien.mirabel@… 2 years ago.
Based on "gtl_polygon_usage" from the documentation
polygon_traits.patch Download (2.8 KB) - added by asydorchuk 18 months ago.
Patch
0001-Polygon-fixing-reopend-issue-6366-defect-in-polygon-.patch Download (3.1 KB) - added by asydorchuk 5 weeks ago.

Change History

Changed 2 years ago by sebastien.mirabel@…

Based on "gtl_polygon_usage" from the documentation

comment:1 Changed 19 months ago by ljsimons

  • Status changed from new to closed
  • Resolution set to fixed

This was fixed a long time ago.

comment:2 Changed 18 months ago by sebastien.mirabel@…

  • Status changed from closed to reopened
  • Version changed from Boost 1.48.0 to Boost 1.51.0
  • Resolution fixed deleted

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

Changed 18 months ago by asydorchuk

Patch

comment:3 follow-up: ↓ 4 Changed 18 months ago by Andrii Sydorchuk

Hi Sebastien,

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

comment:4 in reply to: ↑ 3 Changed 18 months ago by sebastien.mirabel@…

Hi Andrii,

It works now (tested with trunk). Thanks !

Sébastien

comment:5 Changed 18 months ago by asydorchuk

  • Owner changed from ljsimons to asydorchuk
  • Status changed from reopened to new
  • Milestone changed from To Be Determined to Boost 1.53.0

comment:6 Changed 14 months ago by asydorchuk

  • Status changed from new to closed
  • Resolution set to fixed

comment:7 Changed 2 months ago by 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

comment:8 Changed 2 months ago by 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

comment:9 Changed 8 weeks ago by asydorchuk

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

Andrii

comment:10 Changed 8 weeks ago by 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 ?

comment:11 Changed 8 weeks ago by 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

comment:12 Changed 7 weeks ago by 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.

comment:13 Changed 7 weeks ago by asydorchuk

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

Andrii

comment:14 Changed 5 weeks ago by asydorchuk

  • Milestone changed from Boost 1.53.0 to 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.

View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
The resolution will be deleted. Next status will be 'reopened'
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.