Boost Polygon Library: Main Page

The Boost.Polygon library provides algorithms focused on manipulating planar polygon geometry data. Specific algorithms provided are the polygon set operations (intersection, union, difference, disjoint-union) and related algorithms such as polygon connectivity graph extraction, offsetting and map-overlay. An example of the disjoint-union (XOR) of figure a and figure b is shown below in figure c. These so-called Boolean algorithms are of significant interest in GIS (Geospatial Information Systems), VLSI CAD as well all other fields of CAD, and many more application areas, and providing them is the primary focus of this library. The Boost.Polygon library is not intended to cover all of computational geometry in its scope, and provides a set of capabilities for working with coordinates, points, intervals and rectangles that are needed to support implementing and interacting with polygon data structures and algorithms.

One of the important features of the library is the implementation of the generic sweepline algorithm to construct Voronoi diagrams of points and linear segments in 2D (developed as part of the GSoC 2010 program). Voronoi diagram data structure has applications in image segmentation, optical character recognition, nearest neighbor queries execution. It is closely related with the other computational geometry concepts: Delaunay triangulation, medial axis, straight skeleton, the largest empty circle. The Boost.Polygon library provides interface to construct Voronoi diagram of points figure a and line segments figure b (the last could be used to discretize any two-dimensional curve). Figure c contains the example of the medial axis of the non-convex polygon. The implementation outperforms most of the known commercial and non-commercial libraries in both efficiency and numerical robustness aspects. You may find more details on the topic at the Voronoi main page.

The coordinate data type is a template parameter of all data types and algorithms provided by the library, and is expected to be integral. Floating point coordinate data types are not supported by the algorithms implemented in the library due to the fact that the achieving floating point robustness implies a different set of algorithms and generally platform specific assumptions about floating point representations. For additional detailed discussion of the library and its implementation including benchmark comparisons with other open source alternatives please see the paper and presentation from boostcon 2009 as well as a detailed analysis of the runtime complexity of the library's core algorithms.

The design philosophy behind the polygon library was to create an API for invoking the library algorithms it provides on user geometry data types that is maximally intuitive, minimally error-prone and easy to integrate into pre-existing applications. C++-concepts based template meta-programming combined with generic operator overloading meets these design goals without sacrificing the runtime or memory efficiency of the underlying algorithms. The API is intended to demonstrate what could be achieved with ease by a C++-concepts based library interface, but is implemented based on current language features. This API makes the following code snippet that operates on non-library geometry types possible:

void foo(list<CPolygon>& result, const list<CPolygon>& a,
const list<CPolygon>& b, int deflateValue) {

CBoundingBox domainExtent;

using namespace boost::polygon::operators;

boost::polygon::extents(domainExtent, a);

result += (b & domainExtent) ^ (a - deflateValue);

}

In the code snippet above the hypothetical polygon type CPolygon has been mapped to the library polygon concept and is used with library APIs to clip polygon list b against the bounding box of polygon list a and apply the disjoint-union of that with polygon list a deflated by some integer amount. The end result is accumulated into a list of polygons with a union operation. It is considerably more typing to describe this usage of the API than to code it, and the description is not much clearer than the code itself. A picture is worth a thousand words.

In Boost.Polygon operations such as those shown above are free functions named for what they do, or are overloads of C++ operators that make it easy to infer from reading the code what to expect. Operators are contained in the namespace boost::polygon::operators so that they can be used outside the boost::polygon namespace without bringing in the entire boost::polygon namespace. Following the principle of least astonishment, the inferred behavior should generally match the actual behavior. Conventions such as argument ordering (output arguments come first) and consistently applying the same semantics across different functions (accumulate) reduces the learning curve for new users while reducing the need to memorize semantics and argument ordering of many different functions for advanced users.

While the internal library code that implements this API is usually complex and cryptic due to heavy use of template meta-programming, the application of the library API in user code is usually simple and clear because it is free of any extraneous syntax. The one exception to this is the mapping of user types to library concepts, which necessitates that the user perform some simple template programming and understand some of the internals of how the library concept type system works. The examples below should aid the user in performing these programming tasks.

We would like to thank: Thomas Klimpel, Frank Mori Hess, Barend Gehrels, Andreas Fabri, Jeffrey Hellrung, Tim Keitt, Markus Werle, Paul A. Bristow, Robert Stewart, Mathias Gaunard, Michael Fawcett, Steven Watanabe, Joachim Faulhaber, John Bytheway, Sebastian Redl, Mika Heiskanen, John Phillips, Kai Benndorf, Hartmut Kaiser, Arash Partow, Maurizio Vitale, Brandon Kohn, David Abrahams, Gordon Woodhull, Daniel James, John Maddock, Tom Brinkman, Bo Persson, Mateusz Loskot, Christian Henning, Jean-Sebastien Stoezel, for providing feedback and or formal review of the library as part of the boost submission process and Fernando Cacciola for graciously serving as review manager.

Contents

Other Resources

Polygon Sponsor

THE BOOST.POLYGON LIBRARY