Re: [boost] [GGL] performance and bug

Subject: Re: [boost] [GGL] performance and bug
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-11-17 05:43:57

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

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.

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