Circle Packing Animation in GNU Emacs

 

Here's an implementation of circle packing algorithm by Wang et. el. in Elisp. Front chain is the set of circles on the periphery. These are shown as connected by red line in the animation.

(require 'graph-pack)

(defstruct point x y r)

 

;; Define a point

(setq p (make-point :x 17 :y 0 :r 16))

 

;; Define a list of points

(setq points (list p1 p2))

 

;; Image is an SVG image. This is used for drawing the animation (optional). The return value is the front chain. This can be further used to generate a circumscribing circle.

(graph-pack points image) 

;; Get circumscribing circle

(setq p (graph-enclose (graph-pack children)))

 

Bubble Graph

 

You can pass a hierarchical tree of points to generate a bubble graph. Only radii of leaf nodes are mandatory. title and fill parameters are used if provided.

;; For drawing additional point attributes are required. Hence this definition is different from above. Properties old-x and old-y are used internally.

(defstruct point x y r old-x old-y fill title)

 

;; Image is an SVG image.

(graph-pack-tree root image)

 

Background

I don't have access to the research paper. The link to paper in D3js documentation wasn't very helpful either. Hence the code didn't make much sense to me. It only struck me when I saw the following image.

Important: My implementation doesn't use scores at each step. On the surface, that doesn't seem to be a drawback though.

Code

1. https://github.com/atamariya/tumblesocks/blob/dev/graph-pack.el
2. https://github.com/atamariya/tumblesocks/blob/dev/graph-enclose.el
3. https://github.com/atamariya/tumblesocks/blob/dev/graph-draw.el
   

 

References

1. Visualization of large hierarchical data by circle packing (Research paper) 
2. D3.js implementation
3. Python implementation
4. Useful circle packing application ideas  
   

 

https://t.ly/E9Ene