Skip to content

Instantly share code, notes, and snippets.

@Gro-Tsen
Created December 23, 2023 12:07
Show Gist options
  • Save Gro-Tsen/b6d1af6bb0d187287d09bc78bbb6a8ab to your computer and use it in GitHub Desktop.
Save Gro-Tsen/b6d1af6bb0d187287d09bc78bbb6a8ab to your computer and use it in GitHub Desktop.
Draw the Stern-Brocot or dyadic tree
#! /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");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment