Re: [boost] [Polygon] performance

Subject: Re: [boost] [Polygon] performance
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-09-02 17:21:45

Hi Luke,

Simonson, Lucanus J wrote:
> [...] My understanding of Barend's algorithm is based solely on what he has told me, and he refused to tell me enough to allow me to implement it myself, so if I am in error in my description of it I trust he will promptly correct me.
>   

So I'll promply react indeed. "Refusing" is a great word, I've told 
several times that I'll describe it in a paper. You cannot expect me 
giving you a verbose description of 10 pages of paper just promptly in 
an e-mail. I have told several things, some of them already in this 
mailing list, and I'm prepared to write it down (and started), it just 
takes time, especially if you want to implement it (I didn't know that 
that was the intention, but you're welcome of course)

> First, I do not believe that Barend's implementation is numerically robust when instantiated with float or double.  

Quite a statement.

> [...] Second, Barend has stated that his algorithm does the same thing as mine.  This is simply not true.  Barend's algorithm imposes quite a few preconditions on its inputs (non-self intersecting being just one example) while mine imposes none.  
OK, besides that you have the 45/90 case.

> The two arguments of a boolean operation in my library may be any number of intersecting and overlapping polygons, Barend requires that all polygons be simple and non-overlapping.  My algorithm accepts a broader range of inputs, which makes it more general and more powerful than Barend's algorithm and a better algorithm to use in a generic interface where preconditions become concept requirements for input geometry data.  Furthermore, my algorithm has more output modes such as trapezoidization and keyholing as well as the flexibility to perform n-layer operations such as connectivity extraction and map overlay.  Barend's algorithm does not.  
Sorry Luke, you enumerate quite a lot of statements that I've never told 
you. Non-self-intersecting is indeed assumed, but actually I didn't test 
for it until now, the algorithm should be generic enough to handle those 
cases. But I should prove that, it needs time. The algorithm is quite 
new and even not completely finished.

I think I've told you that it is designed to do multiple polygons at the 
same time. Not finished, but it is prepared.

The algorithm is finished enough to do benchmarks, but some things still 
have to be done. Such as assembling polygons/holes in multiple polygon 
intersections and unions. Those do not occur in the current benchmark. 
Therefore preview 5 was postponed from august to october.
Indeed this might have a small influence on performance. But a "grain of 
salt" is probably an overestimation.

If necessary the (unfinished) sources (now hosted at Geodan) of these 
can be moved to boost.sandbox.

> [...]
>
> For these two reasons I think we should take Barend's performance claims with a grain of salt.  When compared to other libraries that are known to be numerically robust (GPC, CGAL, Geos) my library is sometimes slower, sometimes faster in Barend's own benchmarking.  Only Barend's algorithm is always faster in his benchmarking.  However, if Barend's library has the potential to produce self intersecting output it is not even in the same class as these others.
>   
You mailed this more, but you've not yet answered the question about 
precision. The output of all tests is up to at least 5 decimals the same 
for GEOS, GPC, Terralib and GGL. Boost.Polygon is the one who deviates 
becuase of precision. CGAL also deviates but just because of 
self-touching input.

My original statement on this review was not intended to show that GGL 
is that fast. It was to indicate that Boost.Polygon is too slow and I 
compared it to GPC and CGAL (and also GGL indeed). In (maybe ridiculous) 
cases Boost.Polygon is faster, but then not correct. Your paper 
indicates that Boost.Polygon is more scalable then CGAL but I cannot 
reproduce that.

> My benchmark data can be reproduced using the forcgal.cpp file in the sandbox/gtl directory.  I provided it when Andreas asked.
>   
OK, thanks
> I admit that my algorithm could be faster.  For the benchmarks I performed I estimated it could be up to 10X faster.  

Estimations cannot be measured.

> Barend has made quite a bit a progress since boostcon and I am genuinely happy for him for what he has achieved.
>   
Thanks Luke,

I'm off and disconnected from now until this extended review ends. 
Therefore this answer is also a little short. Anyway, I wish you all the 
best, it will be a busy week for you. Thanks for all your efforts.

Regards, Barend