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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk