Boost C++ Libraries: Ticket #6063: resize does not offset rectangles (etc.) correctly or crashes

attachment set

dbfaken@… — Wed, 26 Oct 2011 21:20:30 GMT

attachment → make_arc_16segments.PNG

output of boost::polygon's make_arc for 16 segments

attachment set

dbfaken@… — Thu, 27 Oct 2011 16:38:34 GMT

attachment → boost_polygon_bug6063.diff

patch for ticket 6063

dbfaken@… — Thu, 27 Oct 2011 16:40:25 GMT

Attaching a patch which implements the final suggestion:

scale the circle generated by make_arc() so that the *minimum* (instead of maximum) bloating distance is given by 'resizing'. (or, for resizing < 0, the maximum shrinking distance)
intersect the results of the minkowski sum with the 'normal offset' of the initial shape (or its inverse, for resizing < 0).

dbfaken@… — Thu, 27 Oct 2011 20:00:55 GMT

Attaching another version of the patch (this time in 'unified diff' patch format) which adds an optional parameter double minUnroundedAngleDegrees.

This fixes another problem in the corner-rounding - that all corners get rounded, even though the docs say that rounding is only applied to "acute corners".

The new parameter allows the caller to control which corners get rounded. For example, setting it to 90.0 will only allow acute-angled corners (<90) to get rounded. This is typically desired in, e.g. VLSI layout - you don't want your purely-90-degree corners to get rounded!

Setting it to 45.0 will likewise preserve Polygon_45-type objects as containing only 45-degree angles.

I have set the default to 180.0 to preserve the original behaviour, but as mentioned above I would suggest making it 90.0 to match the docs.

Note this patch includes/supercedes the previous .diff file I attached.

For simplicity in the patch I have only added this parameter to the boost::polygon::polygon_set_data<T>::resize() function, not to the generic boost::polygon::resize() operator.

If this extra parameter is found pleasing, the parameter should be propagated through to the other versions, with the default value. (if you want me to post a patch for this just say so in a comment)

Quick description of the fix (see also the comments in the code):

This builds upon the previous fix.

I simply set the radius of the convolved circle to the distance of the 'elbow' generated by a corner of angle minUnroundedAngleDegrees. The extra area generated by the larger circle still gets trimmed off by the intersection with the 'unrounded offset', as before.

attachment set

dbfaken@… — Thu, 27 Oct 2011 20:02:10 GMT

attachment → boost_polygon_bug6063_fix2.patch

Second version of fix for ticket 6063. Created against boost 1.47.0.

dbfaken@… — Tue, 07 Feb 2012 19:45:51 GMT

Another wrinkle: Corner-rounding-offset is being done via a minkowski sum of the given shape with a polygonalized "circle", but the vertices are being snapped to integral values (e.g. int) via round_down(). This causes the 'circle' to be skewed toward the lower-left-hand quadrant, instead of being symmetric about its center-point.

This in turn can cause improper offsetting of a simple square with the given code, since even with the 'arcRadScaling' and 'elbowDist' compensation in polygon_set_data<T>::resize(), a circle passed through round_down() may not reach the appropriate corners when minUnroundedAngleDegrees=90.

The solution is to use a circle where the points are symmetrically rounded 'away' from the center of the circle.

The next patch fixes this by adding a required parameter 'round_away_from_center' to make_arc. It is set to true when called from polygon_set_data<T>::resize(). I have left it as false (so that round_down<T>() is still used - same behaviour as in 1.47) when called from make_resizing_vertex_list() for now, though this case should presumably also be fixed. There is also a small tweak to avoid dividing by zero, and a tweak to make_arc so it doesn't include the center in the polygon when generating a full circle.

attachment set

dbfaken@… — Tue, 07 Feb 2012 19:47:34 GMT

attachment → boost_polygon_bug6063_fix3.patch

Third version of fix for boost::polygon bug ticket #6063. Also includes a patch for ticket 6051 (commented and easily removed if desired).

dbfaken@… — Tue, 07 Feb 2012 19:48:55 GMT

Forgot to note - last patch ('fix3') was against boost 1.47.0.

dbfaken@… — Thu, 05 Jul 2012 18:34:07 GMT

Attaching a patch that works with boost 1.49.0.

This does not include the patch for ticket 6051.

Could someone please integrate this into the next release?

thanks, Daniel

attachment set

dbfaken@… — Thu, 05 Jul 2012 18:35:35 GMT

attachment → boost_polygon_bug6063_diffForBoost1_49_0.patch

Patch for boost v1.49.0

Lucanus Simonson — Wed, 19 Sep 2012 01:38:55 GMT

I'll have to follow up on this.

Andrii Sydorchuk — Sun, 16 Jun 2013 01:52:56 GMT

Hi,

There was a change in maintainers of the Boost Polygon, and this ticket was lost for a while. First of all thanks for your patches. I am going to have a deeper look in the following few weeks.

Andrii

owner, status changed

Andrii Sydorchuk — Sun, 16 Jun 2013 01:53:34 GMT

owner changed from Lucanus Simonson to Andrii Sydorchuk
status new → assigned

Andrii Sydorchuk — Wed, 06 Nov 2013 23:42:51 GMT

Adding duplicate ticket #6080:

""" Hi,

I found two bug in polygonset::resize() as follows,

bug1

std::vector<Point> pts; Polygon poly; PolygonSet polySet, polySetResult;

pts.clear(); pts.push_back(Point( 6300, 0)); pts.push_back(Point( 0, 0)); pts.push_back(Point( 0, 4750)); pts.push_back(Point( 1250, 6000)); pts.push_back(Point( 1250, 7500)); pts.push_back(Point( 2850, 7500)); pts.push_back(Point( 2850, 5950)); pts.push_back(Point( 5950, 5950)); pts.push_back(Point( 5950, 5750)); pts.push_back(Point( 6300, 5400));

boost::polygon::set_points(poly, pts.begin(), pts.end());

polySet += poly; polySetResult += polySet-1000;

bug2

std::vector<Point> pts2; Polygon poly2; PolygonSet polySet2, polySetResult2;

pts2.clear(); pts2.push_back(Point(2100, 2575)); pts2.push_back(Point(1700, 2575)); pts2.push_back(Point(1700, 2365)); pts2.push_back(Point(1800, 2265)); pts2.push_back(Point(1835, 2265)); pts2.push_back(Point(1835, 1945)); pts2.push_back(Point(1645, 1945)); pts2.push_back(Point(1645, 2305)); pts2.push_back(Point(1440, 2305)); pts2.push_back(Point(1440, 2790)); pts2.push_back(Point(1145, 2790)); pts2.push_back(Point(1145, 1805)); pts2.push_back(Point(2100, 1805));

boost::polygon::set_points(poly2, pts2.begin(), pts2.end());

polySet2 += poly2; polySetResult2 += polySet2+100;

For bug one,

current result : { 1000 4336, 1000 1000, 5300 1000, 5300 4986, 4950 5336, 4950 4950, 1850 4950, 1850 5186}

correct result : { 1000 4336, 1000 1000, 5300 1000, 5300 4950, 1850 4950, 1850 5186}

For bug two, the result is a polygon with hole. However, I think there shall be no hole in the result.

Please check and thanks for your help.

Regards,

Jay Huang """

attachment set

Andrii Sydorchuk — Wed, 06 Nov 2013 23:44:15 GMT

attachment → test.cpp

ticket_9036

Andrii Sydorchuk — Wed, 06 Nov 2013 23:45:07 GMT

Adding duplicate ticket #9036:

""" On some data (attached) boost::polygon::resize crashes with access violation in release version, in debug there is an assert about invalid iterator access. """

attachment set

Andrii Sydorchuk — Wed, 06 Nov 2013 23:46:33 GMT

attachment → test_resize.cpp

ticket_9168

Andrii Sydorchuk — Wed, 06 Nov 2013 23:47:07 GMT

Adding duplicate ticket #9168:

""" I tried to use resize(pset, -1); resize(pset, 1) to filter the results of a xor which should remove all polygon with only 1 or 2 database unit differences. resize -1 generates wrong output if the polygon are not orthogonal.

input: 0,0 0,5 1,5 1,0 3,-3 resize -1: 0,1 -3,5 0,0 0,1 """

summary changed

Andrii Sydorchuk — Thu, 21 Nov 2013 00:19:07 GMT

summary resize does not offset rectangles (etc.) correctly when using corner_fill_arc → resize does not offset rectangles (etc.) correctly or crashes

Andrii Sydorchuk — Thu, 21 Nov 2013 20:37:15 GMT

dbfaken@ I'd like to thank you for the patches you provided, unfortunately the problem with resize is deeper than it looks, the current approach is basically wrong (numerically and topologically). Without going much into details, the steps to fix the current implementation are the following:
1) The proper implementation for the resize with corner_fill_arc set to false should be based on the straight skeleton extraction.
2) The proper implementation for the resize with corner_fill_arc set to true should be based on the Voronoi diagram extraction. Fortunately Polygon already has robust implementation of Voronoi diagram extraction. However it's not philosophically compatible with the legacy Polygon code (step 3 explains why).
3) Most of the algorithms operating on polygons should accept only integral coordinates (this is already sort of true), however they should return polygons or primitives with floating-point coordinates. It should be the user decision to do the snap and rounding and the library should provide the utilities to do so.

I am still evaluating work to be done to fix the step 3. I will also update the documentation for the next release to clarify that resize implementation is broken.

dbfaken@… — Thu, 21 Nov 2013 22:43:25 GMT

Replying to asydorchuk:

dbfaken@ I'd like to thank you for the patches you provided, unfortunately the problem with resize is deeper than it looks, the current approach is basically wrong (numerically and topologically).

Thank you for looking into this and glad you have a plan. Separation of the snapping logic from the offset operation does seem like a good idea.

z@… — Thu, 06 Feb 2014 23:53:25 GMT

what's the time line for fixing resize() according to your stated plan? I also ran into the problems with resize(). This is a showstopper for us to switch using Boost polygon.

First, with the resize with corner_fill_arc set to false. Apparently, it does bad thing to resulting polygon (see Ticket #5358) when "very small features before shrinking can become very large after if the angle is acute. That is what happened in this case". I don't understand why it was closed as 'invalid'.

Second, with the resize with corner_fill_arc set to true. Apparently, this fixes the problem above, but introduces new problem. That is resize 'offset' is not correct.

Andrii Sydorchuk — Mon, 10 Feb 2014 22:06:28 GMT

There is no explicit timeline for the plan I mentioned before.