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