Patches are more than welcome. Polygon regression suite is under: http://svn.boost.org/svn/boost/trunk/libs/polygon/test/ The Boost 1.55 release branch will be closed in two weeks for any updates. Regards, Andrii On Tue, Sep 17, 2013 at 2:19 AM, T. Raykoff <traykoff@comcast.net> wrote:

Thanks. I am also evaluating CGAL for this need.

Are you looking for a patch submission for the next release? I can fix some of these and send a patch.

Is there a regression test suite?

Thanks, Taavo

...

-----Original Message----- From: Boost [mailto:boost-bounces@lists.boost.org] On Behalf Of Andrii Sydorchuk Sent: Saturday, September 14, 2013 5:13 PM To: boost@lists.boost.org Subject: Re: [boost] boost::polygon type genericity

Hi Taavo,

I am the current maintainer of the Boost.Polygon library. Generally, hard-coded types should not be used. However, before fixing any places that already use them, it should be ensured that backward compatibility is preserved.

Andrii

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On Tue, 17 Sep 2013, T. Raykoff wrote:

OK. I just officialy gave up on CGAL.

It is between b::p and that c++/Delphi clipper library.

Note that it could be useful for all 3 libraries if you explained what made you chose/reject them. -- Marc Glisse

On Tue, 17 Sep 2013, T. Raykoff wrote:

...

OK.  I just officialy gave up on CGAL. It is between b::p and that c++/Delphi clipper library. Note that it could be useful for all 3 libraries if you explained what made you chose/reject them. I'd also be interested in learning about Taavo's reasons.

Well you asked for it, here is a [lengthy] comparison… My computational geometry (“CG”) needs are for a CAM application; generating machine toolpaths for a laser that will expose photoresist on PCB trace patterns. The PCB file (Gerber format) is loaded, it is parsed into polygons (using libgerbv), and then polygon operations are used to generate the toolpaths. The operations needed are fairly basic: 1.) Basic Booleans on simple polygons (with holes) 2.) Minkowski sum of a single poly over a line segment 3.) Internal offsets 4.) Clean and simplify The environment is C++, making heavy use of C++11 features, and will be housed in a Qt application for cross-platform deployment. I did a trial combining all of these operations using CGAL, boost::polygon, and Angus Johnson’s clipper library. The trial exec’ed a stress test of a loop of randomized operations on 1-4 above, which was output into a text file and viewed using R. In short, my observations are: 1. CGAL: Overkill for this need. 2. Boost::polygon: Nice API, but a bit buggy 3. Clipper: Easy and fast, no issues found yet. ____CGAL____ (http://www.cgal.org/) CGAL certainly is the most powerful option, and it seems to provide at least one maybe two ways of doing everything you might want under the topic of CG. In the polygon world, notably it provides numerous options for number types, providing either exact or inexact computation. For exact numbers, it has thunks to gmp, leda, and other libraries. The complexity comes at a price; it takes a fair amount of time and research to understand how all the pieces of the library fit together and where to go. E.g. it made me brush up on some abstract math, like the difference between a ring and a field. C++ guys will feel at home with the CGAL API style; it is STL-ish with heavy use of iterators, templates, etc. However, the design is not very consistent, e.g. some libraries rely upon passing an output iterator to return results, others like to return results as a boost::shared_ptr return value, etc. Compilers struggle with the code. Certain CGAL examples did not compile with clang++ 3.2 on linux or Mingw 4.8.1 on Win when using –std=c+11, but worked with older compilers e.g. g++ 4.7.2. I didn’t invest the time to see if it was a compiler issue, or just stricter conformance to the spec. The resulting objects are really fat: 6MB for the CGAL trial, 2.6 MB for the equivalent operations under boost::polygon, and 400KB for the same using clipper (including the clipper object file). [Sizes are stripped object file byte size on i386]. Compile time is pretty much proportional to this size, with CGAL taking > 600MB virtual memory and > 2 minutes to compile on my setup with gcc 4.7.2. All of which makes this a pain to work with. One nice thing about CGAL is that I didn’t have to roll my own Minkowski sum, as there is a set of library functions to do that (actually at least four different ways, true to CGAL style). In the CGAL trial, I only implemented about half of the routines done in the boost::polygon and the clipper trials before “giving up” on CGAL. For this half, it ran about an order of magnitude _slower_ than the other two options. No doubt, part of the CGAL runtime penalty was my use of a full exact number type in the geometric kernel (The “Epeck” kernel in CGAL-speak). Boost::polygon and clipper use a simple integral type with snap rounding. I tried to use such an approximate number type for parity, but it resulted in internal assertion failures at runtime, no doubt due to approximations; I didn’t delve deeper into resolving these. I am sure I haven’t invested the time to give CGAL a fair shake, and that I could make it work adequately for my needs. But relative to the other options, it was simply overkill for my needs. If I had a more diverse set of CG needs, I’d reconsider CGAL. Finally, I anticipated another disadvantage of having to deal with runtime installation and dependency issues (the linkage is with CGAL, boost, and when using exact numbers, gmp runtime libraries). ____Boost::polygon____ Boost::polygon (“b::p”) is a nice package. It appears to be most heavily optimized and used relative to the 45 & 90 polygon concepts, probably due to its Intel (VLSI?) heritage. Of course, I need the general polygons. The documentation is very nice and I need to credit it with showing how to do a Minkowski sum using the operations it provides. (I ended up using the documented algorithm with the clipper library, which similarly does not provide a Minkowksi sum operation). The operator overloading API with b::p is very elegant and concise. From the whitepapers on the doc site, it seems it uses an algorithm that has a lot of potential. (Clipper uses Vatti’s clipping algorithm). I used the provided classes, e.g. polygon_set_data, instead of trying to fit my own geometry types into their traits scheme. The API provided by these classes is a little bit clumsy, leading one to do more copying of objects than is really needed. For example, if one has a polygon_set and would like to iterate through the polygons, they need to first *copy* all polys to a separate collection using polygon_set::get (output_iterator&). If I were invested in using b::p for this application, it seems to be a simple affair to patch these classes to provide more flexible accessors. Similar to clipper, you need all of your coordinates in integral types. The libraries snap-round to the nearest integral coordinate. Not flexible, but very fast and simple. One needs to scale physical coordinates by an appropriate factor such that the snap-rounding is not a material deviation. B::p has an extremely flexible types-traits system that allows adoption for any combination of types, e.g. integral for coordinates and double for area types. My first trouble with b::p, and the subject of the original post, is that some of the types used in internal operations were hard-coded, rather than referring to the traits. Not a big deal to fix. The b::p trial ran a fair bit slower than the clipper one, but *much* faster than CGAL. I attribute the slowness relative to clipper to the promiscuous copying needed as a result of the API, and slowness of CGAL to the exact number type used. I ran into two issues with using b::p that I’d categorize as “bugs” unless someone can tell me where I did something wrong. (I can provide a short c++ snippet that reproduces the behavior). The first, is that in going from point a to point b on a polygon that was a result of Booleans, there often (but not always) was a detour as per: path of points a -> c -> c’ -> b instead of path of points a->b, where |c-c`| was a single integral unit (e.g. a trivial real-world physical quantity). This messed up the toolpaths. I put in some code to cull these detours from the polygons. That fixed, I noticed that at times an internal offset generated a spurious polygon artifact well outside of the bounds of the work area. I did not work around or try to diagnose this issue, as the clipper option was too easy of an alternative. I am sure both issues have something to do with numerical artifacts from rounding. ___Clipper___ (http://www.angusj.com/delphi/clipper.php) In short, Clipper worked out so well from my needs that I rather short-circuited investigation into the other two options. Clipper comes as *1* source and *1* header file in the c++ distribution (how’s that for simple?). It appears to be mechanically generated code, and I think the master source is in Delphi. The resulting trial routine compile time and object size is considerably smaller than either boost or CGAL. The API is rather simplistic and well documented. In the trial, it ran faster than all other options, and had no apparent issues with artifacts, etc. I didn’t bother to add instrumentation code to get timings of how much faster Clipper was than the other options, as it was visibly and clearly faster. Of note, the trial for both Clipper and b::p used a domain of integer units (0, 10^6) for both x- and y- axis. One would have to take physical quantities and scale out as appropriate such that the integral unit was (much) smaller than the required precision. I’ll just use Clipper unless I find an unexpected reason not to. I’d be happy to provide bug demo code for the issues I ran into with b::p. Finally of note, this page <http://en.wikipedia.org/wiki/Boolean_operations_on_polygons> has a lot of interesting external links towards the bottom, of different comparisons done much more scientifically than what I describe above. Hope this helps anyone going down the same route…. ~Taavo -- View this message in context: http://boost.2283326.n4.nabble.com/boost-polygon-type-genericity-tp4651484p4... Sent from the Boost - Dev mailing list archive at Nabble.com.

On 9/26/2013 9:37 AM, Adam Wulkiewicz [via Boost] wrote:

I wonder what's the reason of not taking the Boost.Geometry into the consideration?

To my knowledge, it does not do polygon offsets, which is a key piece of functionality for generating the toolpaths. Let me know if I'm wrong :) T -- View this message in context: http://boost.2283326.n4.nabble.com/boost-polygon-type-genericity-tp4651484p4... Sent from the Boost - Dev mailing list archive at Nabble.com.