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.
Hi, Rogue,
ReplyDeleteI have two questions. See if you can help me.
1. If I only clip between two triangles, but there are a lot of pairs of them to clip, which library would give the best performance? I doubt the Vatti's algorithm would be the best choice for such a single operation, though.
2. I realized those libraries almost all use Vatti's algorithm. But Greiner proposed his clipping algorithm (http://davis.wpi.edu/~matt/courses/clipping/) and showed it is more efficient than the Vatti's algorithm. Did anyone try the newer algorithm and prove it is better than Vatti's algorithm? If so, I feel the clipping libraries should use the new algorithm.
Thanks in advance,
Xin
Hi Xin,
Delete1. A definitive answer could be provided only by a specific test however the first steps of the "Known" and "Random" benchmarks lead to think that with less polygons and vertices the choice could be between clipper and gpc.
2. Computational geometry is not my field. AFAIK gpc, clipper and Boost.Polygon implement Vatti's algorithm or an adapted version of the same while Boost.Geometry implements "an adapted version of the Weiler-Atherton algorithm":
http://barendgehrels.blogspot.it/2010/12/intersections-1.html
In the end I am comparing implementations, not algorithms.
再见
Hi, Rogue,
ReplyDeleteHa, you recognized I am a Chinese:) Thanks a lot for your replying so quickly!
I developed a simplified algorithm for just clipping between two triangles. I have already got some performance tests on it, and would like to compare with some existing algorithms. Following your suggestion, I will start with Clipper and GPC.
Maybe I can ask the developers of Clipper and Boost.Polygon to see their opinion on the Greiner's algorithm.
Xin
Apparently, the Greiner algorithm does not handle cases (well) where intersections are on the other polygon's edge. Modifications have been proposed to fix those, which is supposed to slow down the algorithm a little, but I think a good question to ask and test is how much slower does those changes make it? Is it still faster than Vatti after the modification? I would love to try to implement the Greiner algorithm since it looks simple enough, but unless there is any funding out there I probably won't have the time, at least not for a while :P
DeleteLink on Greiner modification: http://arxiv.org/pdf/1211.3376v1.pdf
Clipper is a work of passion and much beyond vatti.It can handle winding number based clipping with several contours as subject/clip.
ReplyDeleteGPC has two implementation of parity based clipping,the triangles output code is the second implementation.
[If you convince yourself to write a greiner which will handle multiple contours I will be pleased to get it .[no funding]...
If you are inticed to write a greiner with the changes mentioned in the paper write one which can handle multiple contours together.
ReplyDeleteGPC (The island version) is not a version to be compared with...It has far too many subtle bugs and it is so slow...
Both clipper and debugged GPC are so fast that it is doubtful if you can get any algorithm to be significantly faster.
Vatti like implementations have a inherent problem in the output polygons generated.Though in theory they are simple and disjoint ,
it may not be so in the output if American numbers (IEEE precision)are used for computations.
I have written my own .NET 2D polygon library that does boolean operations (subtract, intersect, union). It copes with polygons with holes; handles bezier curves, does buffering (polygon inflation and deflation) and triangulation. I'd be interested in testing it out against the test data sets.
ReplyDeleteWith the exception of the "Classic" benchmark, all the data sets are created at run-time, every time.
DeleteHi, i had a quick question, i've searched everywhere for a function that does polygon clipping with cgal, but there seems to be none
ReplyDeleteFinding intersections between a plane and other 2d objects seems to be the only way to go about it, which i think cgal can do.
Is that right? or have i skipped over something? Thanks!
Master gupta,
DeleteCan you describe your problem?
Then I can point you to a proper forum.
Clipper(available with full source code, but no explanations) is ruling the roost as of today.
Gpc from univericity of manchester has a wonderful fault in its triangular clipper.It generates the strips(usually correct)but then when creating the triangle strips it just eats up some triangles if the left and right arms are not of same length. users take care..
ReplyDeleteI am going to implement clipping algorithm as my work is efficient polygon overlay on spatial Hadoop. Kindly suggest me.
ReplyDeleteif you are refering to bool clipping (union,intersection,or,XOR) then the best current one is Angus clipper.He even has a prototype on his site for a further revised one.His routines are for big big integers but they can be easily modified for a real numbers(single/double precision..).
DeleteThey are based on a half complete ACM artice of Balu vatti.
There is a wonderful writeup on a particulr implementation of vattis (the gpc library) which is resident with the university of manchester.Look for general polygon clipper.
They were so overwhelmed with requests that they just stopped the distribution of working code
Delete