I love binary trees

NoC with binary memory tree

A few years ago I was very proud of myself for managing to translate the original Pascal of the Reingold-Tilford algorithm into C/C++ and every since then I have had a fascination for drawing binary trees.

NoC with binary memory tree


The one drawn here was actually done “by hand” in Metapost – I realised only as I finished it that I could have or maybe should used an algorithmic approach and not a heuristic (“does it look ok?”), though Metapost is a pretty inflexible programming tool (though as this book shows can produce some beautiful results) and I reckon a decent tree drawing algorithm in that ought to be worth at least an MSc.

Why I love Metapost

I am writing some stuff about Conway’s Game of Life (and Scratch) – thinking about whether it is possible to explain to adults the basics of programming a computer using the Scratch Life script an an example: Life is more suitable for adults than say the Code Club fish chasing game and anyway it gives me an opportunity to indulge my fascination with the game.

To write the text I need to draw diagrams that explain how the rules work and I tried in both Xfig and Dia to do this. But it was a nightmare.

In contrast I could manage it very quickly in Metapost, even though the natural inclination is to steer clear of that and stick with the “point and drool” GUI based alternatives.


for i=0 upto 4:
draw (0, i*20 + 10) — (100, i*20 + 10);
draw (10 + i*20, 0) — (10 + i*20, 100);
draw (200, i*20 + 10) — (300, i*20 + 10);
draw (210 + i*20, 0) — (210 + i*20, 100);

pickup pencircle scaled 12;
draw (140, 40) — (150, 50)–(140, 60) withcolor red;

path a, b, c, d, e, f, g, h, j, k, l, m;
a = fullcircle scaled 10 shifted (40,40);
draw a;
fill a withcolor green;
b = fullcircle scaled 10 shifted (40,60);
draw b;
fill b withcolor green;
c = fullcircle scaled 10 shifted (60,60);
draw c;
fill c withcolor green;
h = fullcircle scaled 10 shifted (60,40);
draw h;
fill h withcolor green;
j = fullcircle scaled 10 shifted (40,20);
draw j;
fill j withcolor green;
k = fullcircle scaled 10 shifted (60,20);
draw k;
fill k withcolor green;

d = fullcircle scaled 10 shifted (220,40);
draw d;
fill d withcolor green;
e = fullcircle scaled 10 shifted (240,60);
draw e;
fill e withcolor green;
f = fullcircle scaled 10 shifted (260,60);
draw f;
fill f withcolor green;
g = fullcircle scaled 10 shifted (280,40);
draw g;
fill g withcolor green;
l = fullcircle scaled 10 shifted (240,20);
draw l;
fill l withcolor green;
m = fullcircle scaled 10 shifted (260,20);
draw m;
fill m withcolor green;

Gives me this: (actually the original EPS is better as it is a vector format and the PNG won’t scale in the same way)

Conway's Game of Life patternMetapost is not widely known and under-appreciated.

Renamed my project Postmeta

MetaPost logo as icon - from Wikipedia
MetaPost logo as icon – from Wikipedia

As Steven Kelly pointed out to me there was a trade marked product called MetaEdit+ I renamed my project to build a editor/viewer of MetaPost files Postmeta: I don’t think that is taken.

I also worked out why I could not see the mplib.h header for the MetaPost library – or indeed many of the source files: I had to download the code from the MetaPost SVN repo – here – and then build the code. I think the fact it took me a day/a question on tex.stackexchange.com to get that answer shows how sadly neglected the excellent MetaPost package is.

New coding project – metaedit – started

Image representing GitHub as depicted in Crunc...
Image via CrunchBase

I have started writing a MetaPost editor – metaeditpostmeta – which is on Github.

I am not sure how much time and effort I will be able to devote to it, but hopefully I will produce something somebody (even if it is just me) can use.

Yesterday I discovered someone had written a DSL with Haskell to generate MetaPost output – and so maybe I could do something similar using Groovy, but to commit myself to that would be a step too far for now.

Still, it is good to be writing some code again.

A GUI for Metapost?

English: Three examples of metapost output
English: Three examples of metapost output (Photo credit: Wikipedia)

I have sort-of abandoned my Apple Air Book for serious work this last week – going back to a 2008/9 Toshiba laptop (another Morgan Computers purchase) running Linux.

The Apple is a lovely device to travel with and is beautiful, if extremely expensive, device with which to browse the web, but a decade of conditioning to Linux and its command-line power and orthogonal tool set means I am much happier even with a slower machine when it comes to doing things like drawing figures with Metapost.

But having extolled the power of the command line I am wondering whether I should build a GUI for Metapost – essentially an editor panel coupled with a EPS display panel.

Metapost users seem thin on the ground – though maybe that is because a GUI tool doesn’t exist – but anyone who does use it care to comment?

How to use textpath with Metapost

It took me more than a few hours to get this working and as the manual is not at all fully clear on what you need to do (or rather, it assumes more knowledge of LaTeX than I had), I thought it would be useful to set this out.

Textpath allows one to draw text on a path (i.e., not just on a straight line). Here’s an example I prepared earlier:

Hardware Virtualisation

Decus et tutamen as the coins say.

But using it is not as simple as I hoped it would be and even the very fine The LATEX Graphics Companion does not cover it – this is despite textpath being in the standard free TeX distributions and the alternative they describe – TXP – requiring a manual install.

Here are the key steps you need to get it to work.

Firstly, you have to configure your metapost file as a full LaTeX file and not just a piece of Metapost.

So at the top:

input latexmp;
input textpath;
filenametemplate "%j-%c.mps";

And then you need to create your LaTeX preamble – i.e. the file I have called “mypreamble.tex” here but you can call it anything.

Here is mine:


This is what constrains your file as LaTeX.

This also means you have to end your file with an end after the endfig of the Metapost.

If you get some of this wrong you may find that you get an output but the strings (labels) are messed up – it is quite sensitive.

Here’s the file that generated the above graphic:

input latexmp;
input textpath;
filenametemplate "%j-%c.mps";

%some colours
color lightgrey;
lightgrey:=(4/5, 4/5, 4/5);
color midgrey;
midgrey:=(3/5, 3/5, 3/5);
color darkgrey;
darkgrey=(2/5, 2/5, 2/5);
color gloom;
gloom=(1/5, 1/5, 1/5);

color azure;
azure:=(12/13, 1, 1);
color baby;
baby:=(12/13, 24/25, 1);
color lavender;
lavender=(23/26, 23/26, 49/50);
color ultra;
ultra=(8/13, 23/26, 12/13);
color ukraine;
ukraine=(66/255, 173/255, 222/255);
color turquoise;
turquoise=(0, 191/255, 1);

path hardware, virtlayer, kernel, user;
path hardwareL, virtlayerL, kernelL, userL;

hardware = fullcircle scaled 100;
virtlayer = fullcircle scaled 150;
kernel = fullcircle scaled 250;
user = fullcircle scaled 350;

hardwareL := reverse fullcircle scaled 75 rotated 180;
virtlayerL := reverse fullcircle scaled 125 rotated 180;
kernelL := reverse fullcircle scaled 225 rotated 160;
userL := reverse fullcircle scaled 325 rotated 160;

fill virtlayer withcolor lavender;
draw user;
fill user withcolor midgrey;
draw kernel;
fill kernel withcolor lightgrey;
draw virtlayer;
fill virtlayer withcolor lavender;
draw hardware;
fill hardware withcolor white;
draw textpath("Virtualisation", virtlayerL, 0);
draw textpath("Hardware", hardwareL, 0);
draw textpath("Kernel", kernelL, 0);

label.urt(btex Hardware virtualisation etex, (-200,-200));


There are lots of tricks to get the text looking the right way – e.g., inside or outside the path, left to right and so on. But they are described in the manual and I will leave them to readers to work out – getting the output at all is the most fundamental task!

The evolution of the astroid pattern on the spirograph

Here is a MetaPost generated picture of the first 14% or so movements of an inner circle one quarter of the size of the outer circle (as might be found on a spirograph). This eventually generates the astroid pattern. The red arrows follow the movement of a fixed point on the smaller circle – as you can see it moves clockwise while the smaller circle moves anticlockwise relative to the centre of the larger circle.

Evolution of a spirograph pattern

The maths of the spirograph

I wrote this on Saturday >> I have been reading some more of Wheels, Life and Other Mathematical Amusements: in fact I just read the rest of the first chapter on

Spirograph (Photo credit: Wikipedia)

wheels. And so now I know about the maths of the spirograph.


<< Since then I have been fitfully working out how to draw some of the shapes needed to illustrate this article. But spending more time reading and writing stuff for my PhD literature review presentation, which really ought to be a greater priority.


But I cannot let this hang around for ever, so I am going to have a serious attempt at drawing the spirograph pictures (with MetaPost) this evening and


hopefully post about it!


A search on Amazon.co.uk – Spirograph – suggests that the original toy may be all but extinct … so maybe nobody under-35 has a clue what this is about.