Computational Geometry

Srippa

Libraries for Boolean operations on polygons, mainly in C++

I needed a good C++ library for Boolean operations on polygons so I investigated several libraries in search for a library that fit my needs: Computing Boolean intersection and difference for large sets of polygons. I also needed the ability to efficiently compute the union of large set of polygons at once, a property called unary cascade  union.  In this post I present the libraries which I found useful for my needs. The interested reader is encouraged to also consider this benchmark from 2011 and this newer benchmark from 2013. The later benchmark, however, seems to be biased towards VLSI applications operating on large collections of rectangular shapes.

Libraries with functions to compute Boolean operations on polygons:

  • Boost.Polygon is a library developed in Intel in 1997 by the name of GTL and was accepted to Boost in 2008. The core philosophy of Boost.Polygon is to give prime consideration to the correctness and geometrical robustness of their algorithms. A byproduct of this focus was the decision to allow only polygons with vertices at integral coordinates. In our tests Boost.Polygon always produced correct results. This library can compute unary/cascade union. Cascade union efficiently generate the union of a set of, possibly overlapping, polygons by one command. This is far more efficient than accumulating the union by adding polygons in a sequential manner (see here for a more complete discussion). Note  that Unary union can also be performed by other libraries such as GEOS or clipper. However GEOS was considerably slower than Boost.Polygon and clipper produced incorrect results for some tests. I am quite happy working with Boost.Polygon but it is a little bit worrying that the library does not seem to be actively maintained . Perhaps it is because it just works. The algorithm used for Boolean operations is based on Vatti .
  • Boost.Geometry is a library developed from 2006 by the name GGL and accepted to Boost in 2010. The library tries to closely follow the Simple Feature Access (SFA) data model that is widely used by the Geographic Information System community for describing two dimensional geometries. The library allows coordinates to be defined both by integral or by floating types. Thus it is more flexible than Boost.Polygon but also seems to be less robust (see, for example this discussion). The library is actively developed and have an helpful mailing list. By the information in this post, it seems that Boost.Geometry implements an adapted of Weiler-Atherton algorithm for Boolean operations.
  • Another library that closely follows the SFA model is GEOS which is heavily used for GIS applications. GEOS has a C interface and was considerably slower than Boost.Geometry in my experiments with Boolean operations. On the other hand, GEOS does have a unary-unify procedure.
  • Clipper is library developed in 2010 that uses the  Vatti Clipping Algorithms to perform Boolean operations. It is very fast and allows defining the rule for polygon filling . In the same spirit as Boost.Polygons, the Clipper library supports only points with integral coordinates for reasons of numerical robustness. Clipper can properly handle unary union and is very straightforward to use (no fancy template meta-programming tricks) but I found several cases where it did not perform correctly  some of my tests and thus I did not continue exploring the library any further. My tests were made at the end of 2013 so it might be that the above conclusions are no longer valid because of fixes in the algorithm.
  • Other libraries that do Boolean operations in C/C++ which did not have the time to test: CGAL, GPC. PolyBoolean, QISLib,GEOS.

In addition to C++, I also worked quite extensively with the  shapely library which is a Python package based on GEOS. This library is a joy to use for small experimental projects but its performance does not seem to scale well for large data sets.