Re: [boost] boost::polygon type genericity

Subject: Re: [boost] boost::polygon type genericity
From: T. Raykoff (traykoff_at_[hidden])
Date: 2013-09-24 21:19:42

> 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-tp4651484p4651894.html
Sent from the Boost - Dev mailing list archive at Nabble.com.