libtourtre: A Contour Tree Library
libtourtre is a library for contourtrees. Tourtre is the French name
for a bird. Here is a picture of said bird on a tree.
This library implements the contour tree construction algorithm outlined in the paper "Computing Contour Trees in All Dimensions" [link]
by Carr, Snoeyink and Axen, and variant of another algorithm described in "Multi-Resolution computation and presentation of Contour Trees" [link]
by Pascucci, Cole-McLaughlin and Scorzelli, which computes the so-called "branch decomposition." The algorithms are separate, but the latter depends on the former. The library contains three data structures (Arc, Node and Branch) that are convenient for representing the tree and its branch decomposition.
A contour tree can be extracted from any scalar function defined on a domain which satisfies certain properties. These properties are described in Hamish Carr's
dissertation (if not elsewhere), but it suffices to say that it it works on simplicial complexes of genus zero. If your simplicial complex has holes, then you're looking for a Reeb graph, which is another algorithm. With some preprocessing, it can also be used for bilinearly and trilinearly interpolated images. For general image data, your best (easiest) bet is to impose a simplicial domain over the image.
A feature of this library is that it produces a mapping from vertices of the domain to arcs (branches) of the contour tree (branch decomposition), which can be very handy.
The algorithms in the library are serial, but the library is reentrant, should you need to compute another contour tree in one of the callbacks ... or something.
in your program. Call ct_init()
to create a ctContext, then call ct_sweepAndMerge()
to create the contour tree and (optionally) ct_decompose()
to transform it into a branch decomposition.
The contour tree is made up of nodes and arcs , which form an acyclic graph. The branch decomposition is composed of branches which form a rooted tree.
The code is hosted at github: http://github.com/sedillard/libtourtre