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.

Introduction

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.

Features

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.

Usage

Include tourtre.h 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.

Download

The latest version is v14. Download it here.

There is an API change from v8 (which is still available here. ) A comparison callback is no longer required, the total order suffices.

It does not currently fail gracefully if you pass it bad input. It will just do something stupid like "assert(false);" I will add some nice error message facility in the future.