Re: [Boost-users] [Polygon] Test among 3 libraries

Subject: Re: [Boost-users] [Polygon] Test among 3 libraries
From: Angus Johnson (angus_at_[hidden])
Date: 2010-09-11 22:32:57

> 1.5 is a lot slower than 1.05 once you get over one million (like 500X slower) so this is a big issue.

I've created an small application* that compares performance (and 
scaling) of Clipper and GPC. I haven't gotten around to looking at GTL 
or other libraries yet.
At the bottom of this email there's a snapshot of what I get with my 
Sony Laptop (2.53 gigahertz Intel Core2 Duo P8700 processor with 4GB 
RAM) running Window 7.
I think this shows that Clipper still performs extremely well up to a 
million edges. Nevertheless, I'm not denying that clipping libraries 
with better scaling factors will eventually outperform. Also, from my 
testing, triangles (and complex self-intersecting polygons) perform the 
worst, followed by rectangles. Ellipses perform the best as I would 
expect with libraries based on the Vatti algorithm due to the low number 
of 'local minima' (ie 1) per polygon.

*application (with C++Builder source) here: 
http://www.angusj.com/temp/scaling_test.zip

> Please read the references of my boostcon paper http://www.boost.org/doc/libs/1_44_0/libs/polygon/doc/GTL_boostcon2009.pdf, in particular Ruud, B. Building a Mutable Set, 2003. Retrieved March 3, 2009, from Dr. Dobb's Portal: http://www.ddj.com/cpp/184401664 gives a clear description of how to use the std set or map to implement the sweepline data structure.

Thanks for the links. Both interesting reads. A quick read has already 
given me a couple of ideas for improvements (though I think they will 
only be marginal).

===================================
Clipper Library:
===================================

Clipping triangles:
Total edge count Time
(incl output edges)   (seconds)
76663                 0.22676
187318                0.706356
306353                1.485881
583294                4.023969
797229                7.672673
1024124               11.507399
trendline equation: y = 7E-09x^1.5267

Clipping ellipses:
Total edge count Time
(incl output edges)   (seconds)
173609                1.428628
361264                3.58896
597069                6.470583
1286326               16.237705
trendline equation: y = 7E-07x^1.2111

===================================
GPC Library:
===================================

Clipping triangles:
Total edge count Time
(incl output edges)   (seconds)
52011                 1.009507
67157                 1.657865
102433                7.958484
119676                13.501837
184910                42.55886
trendline equation: y = 3E-15x^3.0774

Clipping ellipses:
Total edge count Time
(incl output edges)   (seconds)
59861                 0.849011
81796                 1.572399
88384                 1.8164
115281                3.940039
151506                12.479672
trendline equation: y = 1E-14x^2.8838