par_bubbles.h

This single-file C library implements a grab bag of functions related to enclosing disks. Perhaps the most interesting function is the hierarchical packer:

// Consume a hierarchy defined by a list of integers.  Each integer is an index
// to its parent. The root node is its own parent, and it must be the first node
// in the list. Clients do not have control over individual radiuses, only the
// radius of the outermost enclosing disk.
par_bubbles_t* par_bubbles_hpack_circle(int* nodes, int nnodes, double radius);

This implements Visualization of Large Hierarchical Data by Circle Packing by Wang et al (2006).

The API is pretty simple: it consumes the topological description of a tree (without any actual data in the tree) and produces a list of disks, where each disk is represented with a 3-tuple (x, y, radius). For example, to specify a perfect binary tree, you’d give it a list that looks like:

int nodes[] = {0, 0, 0, 1, 1, 2, 2};

Next we have an emscripten demo of the hierarchical packer. Try clicking the 20K button a few times. This performs layout on a random tree of 20,000 nodes every time you click it.

Small nodes are culled at run time. Click a circle to zoom in, or scroll around in the canvas like you would with Google Maps. If you get lost, refresh the page.

If you click the 2M button, you might need a wait a few seconds during layout. However, the rendering should still be quite smooth (~60 fps on my mid-range MacBook). Frustum culling is ridiculously fast since the scene is the spatial bounding hierarchy! The library provides a cull function for this:

// Clip the bubble diagram to the given AABB (4-tuple of left,bottom,right,top)
// and return the result.  Circles smaller than the given world-space
// "minradius" are removed.  Optionally, an existing diagram (dst) can be passed
// in to receive the culled dataset, which reduces the number of memory allocs
// when calling this function frequently.  Pass null to "dst" to create a new
// culled diagram.
par_bubbles_t* par_bubbles_cull(par_bubbles_t const* src,
    double const* aabb, double minradius, par_bubbles_t* dst);

It also provides a picking function, which is again crazy fast:

// Find the node at the given position.  Children are on top of their parents.
// If the result is -1, there is no node at the given pick coordinate.
int par_bubbles_pick(par_bubbles_t const*, double x, double y);

One more demo, this time for a couple lower-level functions that the library implements:

// Read an array of (x,y) coordinates, write a single 3-tuple (x,y,radius).
void par_bubbles_enclose_points(double const* xy, int npts, double* result);

// Read an array of 3-tuples (x,y,radius), write a 3-tuple (x,y,radius).
void par_bubbles_enclose_disks(double const* xyr, int ndisks, double* result);

These functions implement Emo Welzl’s Smallest enclosing disks algorithm (1991), which is quite beautiful, considering that it can be implemented in a single screenful of C code.

In the following demo, you can click in an empty area to create disk, or click an existing disk to delete it. Move disks by dragging their center, or resize them by dragging their border. You can also drag / scroll in the canvas as you would with Google Maps.

Here are links to the library and the github repo that it lives in.

• par_bubbles.h
• prideout/par

The library implements the algorithms described in the following papers.

• Visualization of Large Hierarchical Data by Circle Packing
• Smallest enclosing disks