Apr 17, 2011

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

Classic polygon example

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.

Charts require a modern browser and Javascript enabled.

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

Known polygon example

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.

Charts require a modern browser and Javascript enabled.

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

Random polygon example

In this test the operands are polygons obtained subtracting random triangles from a square and Boost.Polygon is used to prepare those operands.

Charts require a modern browser and Javascript enabled.

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

Grid polygon example

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.

Charts require a modern browser and Javascript enabled.

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.
Charts require a modern browser and Javascript enabled.

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.

Charts require a modern browser and Javascript enabled.
Charts require a modern browser and Javascript enabled.

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.

Charts require a modern browser and Javascript enabled.
Charts require a modern browser and Javascript enabled.

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.

34 comments:

  1. 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
  2. @Ignorant
    What 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.

    ReplyDelete
  3. Hi Rogue Modron.
    Thanks for the very informative comparison.
    I look forward to more of your blogs :).
    Angus (author of Clipper)

    ReplyDelete
  4. @Rogue Modron
    I'd be also be very interested in how boost.geometry performs in these tests.

    ReplyDelete
  5. @Angus Johnson

    That 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.

    ReplyDelete
  6. Hi again Rogue.
    Firstly, 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.

    ReplyDelete
  7. Herewith my reply on this on the GGL-list.

    Thanks for the benchmark.

    ReplyDelete
  8. how about running a comparision using complex intersections rather than complex polygons.I am sure clipper will throw all the others away.
    GPC is probably delibrately slow so that others can write their journal papers on better! algorithms.

    ReplyDelete
  9. any other known gpc library other than manchester's?. That on is everones favorite thrashing polygon
    boolean manipulator. favorite of cpu vendors.

    ReplyDelete
  10. @Ignorant

    I have no more interest in this benchmark but the code is available (see link above) even for Vatti's followers :p

    ReplyDelete
  11. Err... where is the benchmark source.
    I 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..]

    ReplyDelete
  12. @Ignorant

    See "Downloads", click on "source code".

    ReplyDelete
  13. Hi Angus and Rogue Modron.
    I'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

    ReplyDelete
  14. @Mirko

    Hi 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.

    ReplyDelete
  15. Hi Rogue,
    many 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

    ReplyDelete
  16. I've written another C++ library for polygon clipping: http://wwwdi.ujaen.es/~fmartin/bool_op.html

    It would be great if you could add my libray to your comparison.
    Best regards,
    Francisco Martínez

    ReplyDelete
  17. Hi,

    I 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/

    ReplyDelete
    Replies
    1. 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.

      Delete
  18. Hi Mateusz,

    I 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.

    ReplyDelete
  19. Hi, Rogue,
    I 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

    ReplyDelete
    Replies
    1. Hi Xin,

      1. 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.

      再见

      Delete
  20. Hi, Rogue,
    Ha, 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

    ReplyDelete
    Replies
    1. 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

      Link on Greiner modification: http://arxiv.org/pdf/1211.3376v1.pdf

      Delete
  21. Clipper is a work of passion and much beyond vatti.It can handle winding number based clipping with several contours as subject/clip.

    GPC 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]...

    ReplyDelete
  22. If you are inticed to write a greiner with the changes mentioned in the paper write one which can handle multiple contours together.
    GPC (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.

    ReplyDelete
  23. 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.

    ReplyDelete
    Replies
    1. With the exception of the "Classic" benchmark, all the data sets are created at run-time, every time.

      Delete
  24. Hi, i had a quick question, i've searched everywhere for a function that does polygon clipping with cgal, but there seems to be none
    Finding 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!

    ReplyDelete
    Replies
    1. Master gupta,
      Can 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.

      Delete
  25. 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..

    ReplyDelete
  26. I am going to implement clipping algorithm as my work is efficient polygon overlay on spatial Hadoop. Kindly suggest me.

    ReplyDelete
    Replies
    1. if 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..).
      They 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.

      Delete
    2. They were so overwhelmed with requests that they just stopped the distribution of working code

      Delete

Note: Comments are moderated.