Draw the Stern-Brocot or dyadic tree

draw-binary-tree.pl

#! /usr/local/bin/perl -w

# Generate a graphical representation of either the Stern-Brocot or
# (with option -d) the dyadic tree on the interval [0,1].
# -- David A. Madore <http://www.madore.org/~david/> 2023-12-23
# Public Domain

use strict;
use warnings;

use Getopt::Std;

use Cairo;

# Option -s requests SVG output
# Option -d requests the dyadic (rather than Stern-Brocot) tree
# Option -l <levels> specifies the number of levels to draw (default 10)
my %opts;
getopts('sdl:', \%opts);
my $dosvg = $opts{s};
my $dodyadic = $opts{d};

my $maxlevel = defined($opts{l}) ? $opts{l}+0 : 10;

my $fullwidth = 1920;    # Total output image width
my $fullheight = 1080;   # Total output image height
my $margin = 20;
my $width = $fullwidth-2*$margin;
my $height = $fullheight-2*$margin;

my $surface;
if ( $dosvg ) {
    $surface = Cairo::SvgSurface->create ("binary-tree.svg", $fullwidth, $fullheight);
} else {
    $surface = Cairo::ImageSurface->create ("argb32", $fullwidth, $fullheight);
}
my $cr = Cairo::Context->create ($surface);
if ( 1 ) {
    $cr->set_source_rgb (1., 1., 1.);
    $cr->rectangle(0,0, $fullwidth, $fullheight);
    $cr->fill;
}
$cr->translate($margin, $margin);

$cr->set_source_rgb (0., 0., 0.);
$cr->set_line_cap("round");
$cr->set_line_join("round");
$cr->set_line_width (2);

sub hpos { my $v = shift;  return $v*$width; }
sub vpos { my $l = shift;  return ($l/($l+$maxlevel))*$height*2; }

sub recursor {
    # Parameters to this function are, in order:
    # $level -> the recursion level (starts at 0)
    # $left_ances_numer, ..._denom -> rational value of closest left ancestor
    # $right_ances_numer, ..._denom -> rational value of closest right ancestor
    # $parent_numer, $parent_denom -> rational value of parent
    # (parent is either left or right ancestor, undefined for top node)
    # $lastdir -> undefined for top node, 0 for a left child, 1 for right
    my $level = shift;
    my $left_ances_numer = shift;
    my $left_ances_denom = shift;
    my $right_ances_numer = shift;
    my $right_ances_denom = shift;
    my $parent_numer = shift;
    my $parent_denom = shift;
    my $lastdir = shift;
    my ($my_numer, $my_denom);
    if ( $dodyadic ) {
	die "this is impossible" unless $left_ances_denom == $right_ances_denom;
	$my_numer = ($left_ances_numer + $right_ances_numer);
	$my_denom = ($left_ances_denom + $right_ances_denom);
	$left_ances_numer *= 2;
	$left_ances_denom *= 2;
	$right_ances_numer *= 2;
	$right_ances_denom *= 2;
    } else {
	$my_numer = ($left_ances_numer + $right_ances_numer);
	$my_denom = ($left_ances_denom + $right_ances_denom);
    }
    if ( $level < $maxlevel ) {
	recursor ($level+1, $left_ances_numer, $left_ances_denom, $my_numer, $my_denom, $my_numer, $my_denom, 0);
	recursor ($level+1, $my_numer, $my_denom, $right_ances_numer, $right_ances_denom, $my_numer, $my_denom, 1);
    }
    my $my_x = hpos($my_numer/$my_denom);
    my $my_y = vpos($level);
    if ( defined($parent_numer) && defined($parent_denom) ) {
	# Draw the edge to parent
	my $parent_x = hpos($parent_numer/$parent_denom);
	my $parent_y = vpos($level-1);
	$cr->move_to ($parent_x, $parent_y);
	$cr->line_to ($my_x, $my_y);
	$cr->stroke;
    }
    if ( 1 ) {
	# Draw the text label
	my $avail;  # Compute space available to us
	if ( ! defined($lastdir) ) {
	    $avail = $width;
	} elsif ( $lastdir == 1 ) {
	    $avail = hpos($right_ances_numer/$right_ances_denom) - $my_x;
	} else {
	    $avail = $my_x - hpos($left_ances_numer/$left_ances_denom);
	}
	$avail *= 0.85;
	# Compute "normal" size at this level
	$cr->select_font_face("sans", "normal", "normal");
	my $fct = $maxlevel/($level+$maxlevel);
	my $fontsize = 20*$fct*$fct;
	$cr->set_font_size($fontsize);
	my $text = sprintf("%d/%d", $my_numer, $my_denom);
	my $extents = $cr->text_extents($text);
	if ( $avail < $extents->{"width"} * 0.4 || $avail < 5 ) {
	    # It's really too cramped: forget it
	    goto out;
	} elsif ( $avail < $extents->{"width"} ) {
	    # Scale down text to fit in available space
	    my $sc = $avail / $extents->{"width"};
	    $fontsize *= $sc;
	    $cr->set_font_size($fontsize);
	    $extents = $cr->text_extents($text);
	}
	# Actually draw the text
	$cr->save;
	$cr->set_source_rgb (0., 0., 0.8);
	if ( ! defined($lastdir) ) {
	    $cr->move_to ($my_x - $extents->{"x_bearing"} - $extents->{"width"}/2,
			  $my_y - $extents->{"y_bearing"} + $fontsize);
	} elsif ( $lastdir == 1 ) {
	    $cr->move_to ($my_x - $extents->{"x_bearing"},
			  $my_y - $extents->{"y_bearing"} - $fontsize);
	} else {
	    $cr->move_to ($my_x - $extents->{"x_bearing"} - $extents->{"width"},
			  $my_y - $extents->{"y_bearing"} - $fontsize);
	}
	$cr->show_text ($text);
	$cr->restore;
    }
  out:
}

recursor 0, 0, 1, 1, 1;

$cr->show_page;
if ( $dosvg ) {
    ;
} else {
    $surface->write_to_png("binary-tree.png");
}