Re: [boost] Boost.Polygon issues

Subject: Re: [boost] Boost.Polygon issues
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2011-03-06 20:19:58

Barend Gehrels wrote:
> Hi Luke,
> 
> You asked me on the GGL mailing list ( http://bit.ly/hCwdJx ) to
> verify 
> tests using Boost.Polygon to check Boost.Geometry's behaviour at some
> points.
> 
> I cannot reach that point. I ported a test that I already had
> (recursive polygons) to Boost.Polygon. I'm using the Polygon Set
> Concept with 
> integer coordinates. Actually all input is in the 90/45 degree range.
> 
> If I run the program, it often gives me the wrong results, even in the
> simpler cases. And often it just crashes, in the line 1748 of file
> polygon_arbitrary_formation.hpp (called from the area function)
> 
> I extracted two (wrong but not crashing) cases. Source code here:
> http://bit.ly/fCYRWL
> 
> Summary of second case:
> area p: 45000
> area q: 55000
> area intersection: 0
> area union: 60000
> 
> The last one, area of union, should be 100000, if the intersection is
> zero, the union contains everything and its area therefore should sum
> to 100000

Hi Barend,

I'm glad you followed my suggestion, and quite sorry you encountered a problem.

Your test case proved quite helpful in nailing the issue down, thank you for posting it.

In my investigation of your test case I found that it works fine in the 45-degree algorithm when exercised through the polygon_45_set, and works fine also in the general algorithm when I disable the optimization to use the 45-degree algorithm for 45-degree data.  The issue is in the way the 45-degree algorithm is used by the arbitrary angle interface, as I suspected when I first saw your email.  For background, the arbitrary angle polygon formation provides a post condition that polygon vertices be "linearly consistent" which is a requirement for some meshing applications.  What that means is that when the vertex of one polygon touches the edge of another polygon, that vertex should be inserted on that edge so that the edge is broken into two colinear segments.  A minimal example of this is shown below as ascii art.  Imagine that the triangle touches the rectangle, but does not overlap it.  The general algorithm is expected to report the rectangle with an extra vertex at the point where the triangle touches it.  This behavior has been discussed on this list before.
 __
|  |__
|  |\ |
|__| \|

Crashes and dropped polygons are the two failure modes for the polygon formation algorithm (which is where the line number you cite is.)  There is actually one issue here with two different failure modes.  The algorithm is expected to fail in this way whenever one of its preconditions are violated.  I don't check the preconditions of this algorithm because itsn't interface isn't exposed as a public interface and only my own library code ever uses it.  It is my job to ensure that the post-conditions of whatever code that comes before it satisfy the preconditions.  It turns out linearly consistent vertices is a post condition of the general booleans algorithm (the one that would normally run right before polygon formation), but not of the 45-degree booleans algorithm.  You test case includes these kinds of topologies, and exposed the semantic error in the way I was trying to use the 45-degree boolean algorithm to drive the general polygon formation algorithm.

I did, of course, test the usage of the 45-degree optimization for general polygons, but I didn't give it the same ammount of testing as the core booleans algorithms because integrating two trusted components is the type of thing I test minimally instead of exhaustively.  The reason the bug occurred was because I mistakenly believed that linearly consistent vertices was not a precondition of the arbitrary angle polygon formation algorithm since it is not a necessary precondition and it was my intention to handle such cases correctly when I wrote that code.  However, upon further reflection, the equivalence operation on polygon sets would be broken if comparing two equivalent sets produced by 45-degree and arbitrary angle boolean operations respectively.  This is because the representation of a polygon set is connonical and contains the colinear vertices topologies, but when 45-degree boolean algorithm is used it would not.

There are several things I could do to address the problem, but for now I have opted to disable the feature of using the 45-degree booleans algorithm from the arbitrary angle polygon set interface since it is merely an optimization.  I will update the documentation accordingly.

I would encourage you to modify your test to use the polygon_45_set instead of polygon_set so that you can use that algorithm as a reference as you intended.  I realize that it is not your wish to test my code, but rather to test yours.  Rest assured, I did the sort of testing myself years ago that I'm suggesting you do now and am confident in the core algorithm.  Moreover, there is a team of people in Intel who have been stress testing the 45-degree boleans (through the polygon_45_set interface) to try to induce them to fail for about a week now without finding any issues with the core algorithm.  The core booleans algorithms (90, 45 and general) have been free of issues for a couple years now and have gotten quite a bit of usage both in and outside of Intel.

Thanks again,
Luke