What I found is that your algorithm scales quadratically wrt. number of edges (as expected), and quickly performs 100X slower than my own implementation. Thanks for pointing this out, Luke. This quadratic behaviour is solved now (but we've still room for improvement). This new case is indeed different than our three cases tested. Here the number of input polygons (or holes) is varied. We'll add this case to our suite.
During the benchmarking of your library I encountered a bug in your polygon intersection algorithm. This leads to the area computation resulting in an awkwardly negative value. Thanks also for pointing this out. It is also solved. What happened was
When using 60 polygons (the number your reported), the performance is now similar. Using more polygons, Boost.Polygon is faster, so scales better. Using a spatial index we can improve more, but for now the solution proves that the design is reasonable and we can quickly adapt it. that the outer ring was detected equal, but the assemble function (which is relatively new indeed) failed to output one of them. Therefore only the inner rings, which were intersected correctly, were outputted, resulting in a negative area (which is correct without outer ring). Luke, you wrote that the outer ring was dropped and that was correct, but you immediately gave the wrong reason for it, criticizing the whole algorithm. I think you should not guess. This found bug was in the logics of gathering correctly intersected rings. Not an error in numerical calculations or degeneracies. I'm explaining this explicitly because of the other discussions on this topic. However, I'm glad that these things were discovered and that they could be solved easily. Regards, Barend