An experiment about nine open source polygon clipping libraries written in C/C++ that have been benchmarked after being wrapped for use with .Net.
** LAST UPDATE - MAR 04, 2013 **
Note that there could be errors and that no consideration is made about the robustness or optimization of the libraries so this benchmark must be taken with a grain of salt
.
The nine libraries
| Library | Version | License |
|---|---|---|
| Boost.Geometry | Boost 1.53 | Boost v1.0 |
| Boost.Polygon | Boost 1.53 | Boost v1.0 |
| Bop | 1.2 (from the site and zip file) | Public domain |
| Cgal | 4.1 | Various (mainly GPL and LGPL) / Commercial |
| Clipper | 5.1.2 | Boost v1.0 |
| Geos | 3.3.7 | LGPL v2.1 |
| Gpc | 2.32 | Free for non-commercial use / Commercial |
| KBool | 2.1 | GPL v3 / Commercial |
| TerraLib | svn 10190 | LGPL v2.1 |
The guests
For comparative purposes other libraries have been used during the benchmark.
| Library | Version | License |
|---|---|---|
| PolyBoolean.NET | 2.0.0 (demo) | Commercial |
| SQL Server System CLR Types 2012 | 2011.110.2100.60 | Proprietary |
Wrappers
The open source libraries compared in this benchmark are written in C or C++ and are wrapped with a light C++/Cli wrapper that exposes only the polygon set operations (union, difference, intersection, disjoint-union).
C++/Cli provides a relatively easy solution to interoperability with native libraries but, actually, renders the wrappers tied to the Windows platform.
Hardware and software
| CPU | Intel Core i5 3570k |
|---|---|
| RAM | 8 GB |
| OS | Windows 8 x64 |
| SDK | Windows 8 Sdk + Visual Studio 2012 Express |
| Settings | x64 release build, /O2 |
Notes
- Boost.Geometry, also known as Ggl, can be used with Mpir (a Gmp fork) or with TTMath, for more precision but with a significant slowdown. The vanilla version is used.
- Boost.Polygon, also known as Gtl, can be used with Mpir with no speed penalty. The vanilla version is used.
- Bop has two implementations, one depends on Cgal. The version with no dependencies is used.
- Cgal is built with Boost (1.53), Mpir (2.6.0), Mpfr (svn 8450). A Simple_cartesian<double> kernel is used given the fact that it seems faster than other kernel types.
- KBool source has been patched to avoid creating the file keygraphfile.key.
- PolyBoolean.c20.NET is used instead of PolyBoolean.c30.NET because it is faster but coordinates values are restricted to a 20 bit range, so all tests comply to this constraint. Furthermore the demo version of PolyBoolean throws an exception when the number of vertices returned is a multiple of 7.
- Boost.Geometry, Geos, TerraLib and SQL Server System Types require closed polygons. The polygons are closed for these libraries only.
- An intersection operation is executed in all tests.
Notes about the charts
- In order to show all the results click on the crossed out items in the legend.
Benchmark - Classic
The polygons used in this test are the same ones used to benchmark PolyBoolean (C++ version) and Clipper on their websites (in particular see the test with 174239 vertices) and are extracted from True Type Font contours.
Clipper is the fastest followed by Boost.Geometry, Sql Server ST and TerraLib.
Clipper is faster than PolyBoolean and PolyBoolean is faster than Gpc. This result seems coherent with the same benchmark on the PolyBoolean and Clipper websites.
Benchmark - Known
In this test one operand is a polygon that resembles a gear while the other operand is formed by a set of concentric rings. During the test the gear teeth are increased in number and length as well as the number of rings. The polygons are composed of lines with various slopes and at the same time the theoretical number of intersections is known.
In the long term, Boost.Geometry is the fastest, then Sql Server ST and Boost.Polygon come. However Clipper starts better.
Note that from a certain point onward Bop always crashes. Moreover Cgal was stopped before the end because it was taking too long to finish.
Benchmark - Random
In this test the operands are polygons obtained subtracting random triangles from a square and Boost.Polygon is used to prepare those operands.
Bop is the fastest followed by Sql Server ST, Boost.Geometry and TerraLib.
Cgal is excluded from this test because too much susceptible, in particular it requires simple polygons. During other preparatory tests, Bop, PolyBoolean and Sql Server ST have crashed towards the end.
Benchmark - Grid
In this test the operands are squares containing a grid of holes. During the test the total number of input polygons and vertices is constant but the holes are positioned in order to obtain an increasing number of intersections.
The interesting thing to note here is that some libraries such as Boost.Geometry and Geos give the best performance when the number of intersections increases (Boost.Geometry is one of the slowest at the start and one of the fastest at the end). This is a factor to consider in the results of the previous tests, in particular the benchmark with random polygons (in practice, in that test, if the size of the outer square is increased and the other parameters are mantained we can see a very different progression for certain libraries).
x32 vs x64
Benchmark - Classic, a comparison with the same libraries built for an x32 release.Certain libraries seem to be faster when built for an x32 system, in particular Cgal gains over 100 seconds. Previous versions of this benchmark, on different hardware and operating system (and with different operands), did not show this aspect.
Gpc - C# wrapper vs C++/Cli wrapper
Gpc has a C# wrapper and here is a comparison with the C++/Cli wrapper. The input polygons are obtained as in Benchmar - Known.
Not a big difference between a P/Invoke and a C++/Cli wrapper but P/Invoke is a portable solution that can be used with Mono.
Clipper - C# vs C++/Cli wrapper
Clipper has a C# implementation and here is a comparison with the wrapped C++ implementation. The input polygons are obtained as in Benchmar - Known.
The C# implementation is slower but can be used directly with .Net and Mono.
Downloads
Source code (Wrappers - C++/Cli + Benchmark - VB.Net)
Source code for the libraries must be downloaded from the respective sites.
Important updates
MARCH 04, 2013
- Added: Bop, Cgal, TerraLib.
AUGUST 14, 2011
- Added: Geos, SQL Server System Types.
JULY 23, 2011
- Added: Boost.Geometry.
