Applying BGL to Computational Geometry

Ablavsky, V.

C/C++ Users Journal (August 2002)

The Boost libraries ( extend the C++ Standard library by providing new functionality (e.g., threads and smart pointers) and establishing an extensive set of language idioms. Not surprisingly, Boost will have an impact on the emerging C++ Library Extensions Technical Report (Herb Sutter’s discussion at C++ Experts Forum). Among Boost’s several dozen libraries, the BGL (Boost Graph Library) stands as a prime example of modern C++ design applied to advanced algorithmic concepts. You do not need to be doing scientific computing for a living to appreciate graph-theoretic concepts. For instance, your build system analyzes the directed (and, hopefully, acyclic!) graph of file dependencies to control compilation. Many network routing problems are solved in the graph framework. In this article, I apply BGL to the domain of computational geometry (see sidebar). First, I formulate a concrete problem in graph terms. Second, I develop a way to transform the output of an existing algorithm into an appropriate BGL data structure. Finally, I implement two new algorithms for my BGL graph. The first algorithm gets the job done, but could have been written in any programming language. The second algorithm, however, shows the power of BGL’s generic programming approach.

For More Information

To learn more or request a copy of a paper (if available), contact

(Please include your name, address, organization, and the paper reference. Requests without this information will not be honored.)