Polygon Clipping: a Wrapper, a Benchmark
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 the grayed out legend items.
- Linear charts can be zoomed by dragging the mouse on the plot area.
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.
GPC spends > 99% of its time is extracting the scanline y's from the input vertices before dooing the polygon op.This should not be included in the cpu times as any wise developer can cut that time down by just sorting the y values instead of using the Murta sort..which is sub sub linear for large polygons. GPC has other more severe problems.
ReplyDelete@Ignorant
ReplyDeleteWhat you describe is a problem of the library as it is released from the University of Manchester. Optimize it or not is a matter of choice.
Hi Rogue Modron.
ReplyDeleteThanks for the very informative comparison.
I look forward to more of your blogs :).
Angus (author of Clipper)
@Angus Johnson
ReplyDeleteThanks Angus. Keep up the good work.
@Rogue Modron
ReplyDeleteI'd be also be very interested in how boost.geometry performs in these tests.
@Angus Johnson
ReplyDeleteThat is interesting, and for the curious they have a benchmark buried here. Also, I'd like to give a second chance to CGAL. In the next few weeks I will see what I can do.
Hi again Rogue.
ReplyDeleteFirstly, thanks for the update where you've added boost geometry into the comparison mix.
Also, one final comment on these benchmarks - I think it's important to note that they test only one small (though very important) part of polygon clipping. Other things to be considered when choosing between libraries might include: the ability to handle self-intersecting polygons; the polygon fill rules that are supported; numerical robustness; and other polygon functions (eg triangulation) that users might require.
Herewith my reply on this on the GGL-list.
ReplyDeleteThanks for the benchmark.
how about running a comparision using complex intersections rather than complex polygons.I am sure clipper will throw all the others away.
ReplyDeleteGPC is probably delibrately slow so that others can write their journal papers on better! algorithms.
any other known gpc library other than manchester's?. That on is everones favorite thrashing polygon
ReplyDeleteboolean manipulator. favorite of cpu vendors.
@Ignorant
ReplyDeleteI have no more interest in this benchmark but the code is available (see link above) even for Vatti's followers :p
Err... where is the benchmark source.
ReplyDeleteI want to set it up on my machine..especially the boost one..[It is a laptop with a intel inside warning sticker..centrino 1.7..]
@Ignorant
ReplyDeleteSee "Downloads", click on "source code".
Hi Angus and Rogue Modron.
ReplyDeleteI'm develop software for hobbies and I use VC++6(old one I know...).
Is possible to implement the Clipper Library on VC++6 ?
Many Thanks
Mirko
@Mirko
ReplyDeleteHi Mirko,
I don't have Visual Studio 6 so I can't do a test. You could consider using Visual Studio 2010 Express (which is free), otherwise, if you have to stick with VS6, you should ask in the clipper forum, here.
Hi Rogue,
ReplyDeletemany thanks for your fast reply !!
With Visual Studio 2010 Express you can't create or modify a MFC Application and I have a lot of them :-(
Thanks again for the forum link..... :-)
Mirko
I've written another C++ library for polygon clipping: http://wwwdi.ujaen.es/~fmartin/bool_op.html
ReplyDeleteIt would be great if you could add my libray to your comparison.
Best regards,
Francisco MartÃnez
Hi,
ReplyDeleteI work on Boost.Geometry
Any chance that you are willing to create repository at GitHub for your benchmark sources?
I'd really like to fork it and contribute.
By the way, original general benchmarks published by Boost.Geometry project are available from OSGeo Foundation subversion:
http://svn.osgeo.org/osgeo/foss4g/benchmarking/geometry_libraries/
please include the Angus jhonson's crazy polygon generator at the site.It can supply nice crazy self intersecting polygon contours on the fly ..more than your cpu+memory can warm itself with.
DeleteHi Mateusz,
ReplyDeleteI am glad to see such an interest.
In the past I have expressed the intention to stop developing this benchmark (a comment above and another one on the Ggl mailing-list) and I have not changed my mind. The major part of the recent update was developed months ago when I had plenty of time due to a temporary lack of work so I took it up again mainly to close what I considered 'unfinished business' (in particular adding Cgal and the 'grid' test), then, last month, the publishing of the results has become part of a restyling of the whole blog. Now, if I have committed serious mistakes that shed a bad light on one of the libraries I will do what I can to repair, but nothing more than this. However the source code is released as 'public domain' and if someone is willing to take the burden to enhance/change it, to execute it on different hardware, and then to publish the results on other sites, well, I have nothing against it.