This single-file C library implements a grab bag of functions related to enclosing disks. Perhaps the most interesting function is the hierarchical packer:
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:
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:
It also provides a picking function, which is again crazy fast:
One more demo, this time for a couple lower-level functions that the library implements:
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.
The library implements the algorithms described in the following papers.