polygon_set_data<int> bug with small coordinates

["Patrick LoPresti" <lopresti@…>]

The attached test program creates a small polygon with a hole and adds it to a polygon_set_data<int>. The internal representation of the polygon set is rather messed up, as you can confirm by calling .get() or .get_trapezoids().

This test program demonstrates the bug by comparing the area of the polygon to the area of a polygon set containing that single polygon. The area of the polygon is correctly computed as 32; the area of the polygon set is incorrectly computed as 30.

Doubling all coordinates avoids the bug.

[lopresti@…]

Small test case demonstrating bug in Boost.Polygon polygon_set_data

[Andrii Sydorchuk]

Hi Patrick,

Thank you for your report. The issue was fixed as part of ticket #10976 . I added your example as another unittest. The fix was merged into master and develop branches and will be part of the Boost 1.58 release.

[anonymous]

Are you sure this is fixed in master? I ask because I just pulled a fresh copy from github and this test case still fails.

Also the patch adding the unit test (commit 3189de98d8299075d725bb59beb5c89cf53195e4) appears to have a typo... It reads:

BOOST_CHECK_EQUAL(32.0, area(polygon)); BOOST_CHECK_EQUAL(32.0, area(polygon));

I believe one of those should be "area(pset)" instead of "area(polygon)".

[anonymous]

Are you sure this is fixed in master? I ask because I just pulled a fresh copy from github and this test case still fails.

Also the patch adding the unit test (commit 3189de98d8299075d725bb59beb5c89cf53195e4) appears to have a typo... It reads:

BOOST_CHECK_EQUAL(32.0, area(polygon)); BOOST_CHECK_EQUAL(32.0, area(polygon));

I believe one of those should be "area(pset)" instead of "area(polygon)".

[Andrii Sydorchuk]

No, it's not fixed. That's why the ticket was reopened yesterday. I am going to do a deeper investigation of the issue this weekend.

[Andrii Sydorchuk]

The issue is related to the integer grid snapping logic the Polygon uses to handle boolean ops. Basically, any edge of the polygon that has another vertex of a polygon located within an integer 1x1 square has a chance to be broken into two separate edges at that point. That is what happens in this case. One way of fixing it, is to scale polygon to make sure that it doesn't have vertices and edges in 1x1 grid proximity. The best solution would be to fix snapping implementation, however this requires too many changes to the large legacy code base. Thus, I am skipping this option, being a single maintainer.

I am going to update the documentation that Polygon operations require sufficient proximity between polygon elements.