kicad-developers team mailing list archive

["Torsten Hüter" <torstenhtr@xxxxxx>]

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