crash in processEvent_

[mhilferink@…]

In polygon/details/polygon_arbitrary_formation.hpp, at the end of function processEvent_ (line 1768), I had a case where iter is dereferenced illegally.

Changing line 1741 from:

if(verticalTail && !(verticalCount.second)) {

to

if (verticalTail && !(verticalCount.second) && iter != scanData_.end()) {

fixes this problem, but it might be the case that this just misses the addition of a new hole.

I have processed many polygons and this only happened with a specific polygon, but looking at the iter determining code earlier in processEvent_ (lines 1669..1698), iter referring to the end of scanData might not be such a special case:

iterator iter = lookUp_(currentY);

while(iter != scanData_.end() && ((iter->first.pt.x() == x_ && iter->first.pt.y() == currentY) or (iter->first.other_pt.x() == x_ && iter->first.other_pt.y() == currentY))) {

elementIters.push_back(iter);

...

++iter;

}

If the original coder assumed that (verticalTail && !(verticalCount.second)) implies that (iter != scanData_.end()), well, sometimes it does not. I'll provide more info on actual case(s) (instantiation types, coordinates) in additional notes.

In the seen case, scanData_ contained 3 elements, and elementIters had 2.

[mhilferink@…]

This crash occurred in polygon_set_data<int>::clean() compiled with MSVC 12.0 with both boost 1.56.0 as well as boost 1.58.0 with a large polygon resulting from a Minkowski convolution of a many edged polygon with an 8 egded kernel. In trying to reduce to a less sizable case I found a polygon with 206 edges resulting from a 6 edged polygon convoluted with the same 8 edged kernel ( 6*8*4 + 6 + 8 = 206 ) that causes clean() not to crash but to result in an unexpected empty geometry. I'll attach a demonstrating program.

Note that with MSVC, long double is 64 bit with a 53 bit mantissa. When translating the coordinates such that none is above (1 << 25), both issues (the original crash and the unexpected empty result) disappears and results are as expected. I also noticed that the original and translated cases have a different number of found intersections in validate_scan. It seems that loss of precision in the calculation of the intersection coordinates causes an inconsistency in the subsequent sweep.

[mhilferink@…]

This crash occurred in polygon_set_data<int>::clean() compiled with MSVC 12.0 with both boost 1.56.0 as well as boost 1.58.0 with a large polygon resulting from a Minkowski convolution of a many edged polygon with an 8 egded kernel. In trying to reduce to a less sizable case I found a polygon with 206 edges resulting from a 6 edged polygon convoluted with the same 8 edged kernel ( 6*8*4 + 6 + 8 = 206 ) that causes clean() not to crash but to result in an unexpected empty geometry. I'll attach a demonstrating program.

Note that with MSVC, long double is 64 bit with a 53 bit mantissa. When translating the coordinates such that none is above (1 << 25), both issues (the original crash and the unexpected empty result) disappears and results are as expected. I also noticed that the original and translated cases have a different number of found intersections in validate_scan. It seems that loss of precision in the calculation of the intersection coordinates causes an inconsistency in the subsequent sweep.

[mhilferink@…]

main.cpp demonstrating issue 11415