Hi Tom, just for reference, you can find a benchmark of various polygon libraries here:
http://rogue-modron.blogspot.de/2011/04/polygon-clipping-wrapper-benchmark.html It shows as well that Clipper performs better than Boost.Polygon and thus is a good selection. And CGAL is well known but slow compared to the alternatives. However it makes maybe sense to have a look at Boost.Geometry (not Boost.Polygon) - because this library has almost the same performance compared to Clipper but is more general; because they use metaprogramming (header-only template library). There you can find many useful algorithms and also spatial indexes like R-Trees. One advantage that I'd see is that you can adapt directly the VECTOR2 class. http://www.boost.org/doc/libs/1_58_0/libs/geometry/doc/html/index.html Greetings, Torsten > Hi, > It took me a bit longer than initially anticipated to write the > fracturing (polygon with holes -> single outline conversion) algorithm > that was missing in Clipper. I managed to generate correct zones and the > algorithm does not crash on the test cases that were crashing > Boost.Polygon. My plan is now to: > - clean SHAPE_POLY_SET code and send the patch asap (perhaps Monday, I'm > out for the weekend), > - optimize fracturing, which is taking most of the calculation time. To > my surprise, Clipper performs calculations faster than BPL, > - look into possibility of having a single polygon set class, merging > the functionality of CPolyLine, CPOLYGONS_LIST and all BPL-derived classes, > - keep "fallback" BPL zone code which could be switched on in the > preferences. > - add an option to dump zone geometry (outline, holes, thermals, full > poly) to a text file while refilling zones. > The last two options are temporary - to gather confidence in Clipper, > compare the performance of BPL/Clipper and, in case of trouble, obtain > test cases for both backends. > Cheers, > Tom _______________________________________________ Mailing list: https://launchpad.net/~kicad-developers Post to : [email protected] Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
