Polyglot Code Offline Layout

TODO: this page is largely a placeholder, it needs more content

This is a quite hacky script to calculate weighted Voronoi Treemap layouts for JSON files produced by the polyglot-code-scanner program.

The source code is available at https://github.com/kornysietsma/polyglot-code-offline-layout

What is a weighted voronoi treemap?

A treemap is generally a way of representing a hierarchy of data in a recursive way so that each node has area proportional to it's value - in our case, to the lines of code.

Traditional D3 treemaps are typically rectangular: https://observablehq.com/@d3/treemap - this is where I started out. But rectangular maps get quite hard to understand visually - edges line up in ugly ways, and you can't really see what is a parent and what is a child.

Instead, I'm using a tree based on Weighted Voronoi Diagrams - which also have the property that each area shown is proportional to the value, but are much more organic.

TODO: insert pretty pictures which will make this clearer

Why offline?

There are two big problems with the libraries I am using:

  1. They are slow for big diagrams - sometimes quite painfully slow
  2. They are buggy! Sometimes they go into infinite loops. Sometimes they never reach a good solution.

I didn't have time or brain space to re-implement them - good Voronoi power diagram algorithms are beautiful and elegant, but quite complex. So instead, I decided to cheat. I run the layout algorithm in a loop - every time I start the loop, it uses different random starting points, so I keep going until I get a good enough solution - or if I have looped too many times, I give up and just choose the best solution I've seen so far.

This of course is even slower, so it's much easier to run it offline.

What are the downsides?

Sometimes, the result still isn't very accurate. Roughly speaking, areas of my diagrams are proportional to lines of code - but it's not always quite right. That's why I still have a visualisation that highlights file size, so you don't have to trust your eyes.

Also the layout can't change in the UI. You can't exclude files and re-draw the layout, or go back in time and re-draw the layout - whatever you got from this tool, you are stuck with.

Which libraries am I using?

I'm using the generally quite nice libraries by LeBeau Franck - d3-voronoi-treemap, d3-voronoi-map and d3-weighted-voronoi - it's possible he'll fix the problems I've seen at some stage, and then I might ditch the offline processing. Or someone else will produce a fast Voronoi implementation I can use. Or I'll write one myself.

What about circle packing?

If you specify the -c parameter to the layout script, the top level diagram is drawn with circle packing - this is a very pretty layout, but leaves a lot of wasted space between circles. It's nice for a top-level layout, I don't like it for a treemap though as the maps can be huge - also parent circles don't have the area of the sum of their children, because of all the extra space.

Have you considered other algorithms?

I tried rectangular treemaps first - I don't like them much.

I'd love to try a Gosper treemap just because I love fractals. If I find the time. It might also solve the speed problem - but it's not as easy on the eyes for a deeply nested tree as the Voronoi layout, I tend to think.

TODO: this page desperately needs sample pictures!

Edit this page on GitHub