resize does not offset rectangles (etc.) correctly or crashes

[dbfaken@…]

When using the 'corner_fill_arc' parameter to polygon_set_concept<T>::resize(), a minkowski sum using a polygonalized circle is used to get the offset shape.

A symptom of the problem is demonstrated by the following code:

 {
  polygon_set_data<int> ps1, ps2, ps3;
  ps1.insert(rectangle_data<int>(0, 0, 50, 50));
  ps2.insert(rectangle_data<int>(0, 0, 50, 50));
  ps3.insert(rectangle_data<int>(0, 0, 50, 50));
  std::cout << "rect before resize: " << ps1 << std::endl;
  ps1.resize(6, true, 0);
  ps2.resize(6, true, 5);
  ps3.resize(6, true, 6);
  rectangle_data<int> ps1_extents, ps2_extents, ps3_extents;
  extents(ps1_extents, ps1);
  extents(ps2_extents, ps2);
  extents(ps3_extents, ps3);
  std::cout << "extents of resized rect with '0' (4) segments in circle: " << ps1_extents << std::endl;
  std::cout << "extents of resized rect with 5 segments in circle: " << ps2_extents << std::endl;
  std::cout << "extents of resized rect with 6 segments in circle: " << ps3_extents << std::endl;
  }

If I put this at the end of the gtl_boost_unit_test.cpp, I get the following output:

rect before resize: Polygon Set Data { <0 0, 50 0>:1 <50 0, 50 50>:-1 <0 50, 50 50>:-1 <0 0, 0 50>:1 }
extents of resized rect with '0' (4) segments in circle: -5 54 -5 54
extents of resized rect with 5 segments in circle: -6 54 -6 55
extents of resized rect with 6 segments in circle: -6 55 -6 56

This shows that the extents of the offset shape vary as the number of segments does - which should not be the case!

The extents should all be: -6 56 -6 56

---

The problem (to my eyes) is that the polygonalized circle does not generally have the right shape to get proper offsets in axis-oriented directions, so the offset is basically multiplied by some factor of sqrt(2). Attached is an image of the circle generated with num_circle_segments=16. The radius of the circle - i.e. distance from center to each vertex - is 2. The grid spacing is 1. As can be seen, the top/bottom and left/right sides of the circle do not lie on the grid. If the circle started with a vertex at(0,2) this would not occur and one would presumably get proper offsets in axis-aligned directions. Alternately one could offset all the vertices slightly farther, but this would offset some vertices farther than desired.

I would guess the fix is to change the behaviour of make_arc(), which generates these points, but I'm not sure exactly what the original author's intent was - so maybe just using a new function would be best (after all, the complexity of make_arc is overkill when you're generating a simple full circle)

---

Another problem is that the behaviour of the 'corner_fill_arc' parameter is not really well described. Using this gives much more than corner-filling behaviour - it gives different offsets in different directions. I would suggest explaining it as it is - a minkowski sum with a polygonalized circle, with all that implies.

E.g. for a 45-degree segment the offset will differ from a 90-degree segment unless you pick the right value of num_circle_segments.

Maybe a more comprehensible solution would be to implement corner rounding by the intersection of the normal resize()d shape (as given by corner_fill_arc=false) with the resize()d shape given by corner_fill_arc=true with a larger 'resizing' (picked so that the minimum resizing equals the original resizing).

This would only affect corners, instead of the whole shape.

[dbfaken@…]

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

[dbfaken@…]

patch for ticket 6063

[dbfaken@…]

Attaching a patch which implements the final suggestion:

1. 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)
2. intersect the results of the minkowski sum with the 'normal offset' of the initial shape (or its inverse, for resizing < 0).

[dbfaken@…]

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.

[dbfaken@…]

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

[dbfaken@…]

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.

[dbfaken@…]

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

[dbfaken@…]

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

[dbfaken@…]

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

[dbfaken@…]

Patch for boost v1.49.0

[Lucanus Simonson]

I'll have to follow up on this.

[Andrii Sydorchuk]

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

[Andrii Sydorchuk]

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

[Andrii Sydorchuk]

ticket_9036

[Andrii Sydorchuk]

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

[Andrii Sydorchuk]

ticket_9168

[Andrii Sydorchuk]

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

[Andrii Sydorchuk]

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@…]

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@…]

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]

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