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.

20 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

Note: Comments are moderated.