#! /usr/bin/perl -w
use strict;
use Image::Magick;

# this program ought to be written in C

# read data in.  format is "NAME X Y".
our %x = ();
our %y = ();
our @names = ();
while(<>) {
  my @s = split(/\s+/, $_);
  push(@names, $s[0]);
  $x{$s[0]} = int($s[1]) + 32;
  $y{$s[0]} = int($s[2]) + 32;
}
our %nx = %x;
our %ny = %y;
my $e;
our $width = 768;
our $height = 640;
our $xpadding = 3;
our $ypadding = 2;
our $image = Image::Magick->new(size => "${width}x${height}");
$image->Read('xc:white');

# find out how big all the text is
my %w = ();
my %h = ();
get_font_metrics($image);

# rearrange things to have less overlap
for my $n (1 .. 30) {
  print STDERR "iteration $n ";
  my $improvement = 0;
  for my $name (@names) {
    $improvement += reduce_overlap($name);
  }
  print STDERR "...improved by $improvement\n";
  last if $improvement < 1;
}

# construct the image
draw($image);

# display it
$e = $image->Display();
die "$e" if "$e";

########################################################################

sub min {
  my ($x, $y) = @_;
  return $x < $y ? $x : $y;
}

sub max {
  my ($x, $y) = @_;
  return $x > $y ? $x : $y;
}

# find out how heavily N would be overlapped if it were at (X, Y)
# pixels that fall outside the canvass are counted as overlapped
sub find_overlap {
  my ($n, $x, $y) = @_;
  my $o = 0;

  my $xt = $x + $w{$n};
  my $yt = $y + $h{$n};
  # how much falls outside the image
  $o += $h{$n} * -$x if $x < 0;
  $o += $w{$n} * -$y if $y < 0;
  $o += $h{$n} * ($xt - $width) if $xt > $width;
  $o += $w{$n} * ($yt - $height) if $yt > $height;
  for my $m (@names) {
    next if $n eq $m;		# skip self
    my $nxt = $nx{$m} + $w{$m};
    my $nyt = $ny{$m} + $h{$m};
    next if($x >= $nxt
	    || $y >= $nyt
	    || $xt <= $nx{$m}
	    || $yt <= $ny{$m});	# skip non-overlapping things
    my $ix = max($x, $nx{$m});
    my $iy = max($y, $ny{$m});
    my $ixt = min($xt, $nxt);
    my $iyt = min($yt, $nyt);
    $o += ($ixt - $ix) * ($iyt - $iy);
  }
  return $o;
}

# move NAME in whichever of the 8 compass points reduces its overlap
# with other names, and return how many pixels of overlap were saved.
sub reduce_overlap {
  my $name = shift;
  my $best_offset = [0,0];
  my $current_overlap = find_overlap($name,
				     $nx{$name},
				     $ny{$name});
  my $best_overlap = $current_overlap;
  # up and right are favoured as we're less likely to overlap the
  # connecting line that way.  explicitly counting the pixels overlapping
  # with it would be better but just setting the ordering is much
  # cheaper.
  for my $offset (
		  [1,-1],	# up right
		  [1,0],	# right
		  [0,-1],	# up
		  [-1,-1],	# up left
		  [1,1],	# down right
		  [0,1],	# down
		  [-1,0],	# left
		  [-1,1],	# down left
		 ) {
    my $overlap = find_overlap($name,
			       $nx{$name} + $offset->[0],
			       $ny{$name} + $offset->[1]);
    if($overlap < $best_overlap) {
      $best_offset = $offset;
      $best_overlap = $overlap;
    }
  }
  $nx{$name} += $best_offset->[0];
  $ny{$name} += $best_offset->[1];
  return $current_overlap - $best_overlap;
}

# collect text size
sub get_font_metrics {
  my $image = shift;
  for my $name (@names) {
    my ($x_ppem, $y_ppem, $ascender, $descender, $width, $height, $max_advance)
      = $image->QueryFontMetrics(text => $name,
				 font => 'Generic.ttf',
				 pointsize => 10);
    $w{$name} = $width + 2 * $xpadding;
    $h{$name} = $height + 2 * $ypadding;
  }
}

# draw the image
sub draw {
  my $image = shift;
  my $e;

  for my $name (@names) {
    my $x = $x{$name};
    my $y = $y{$name};
    my $nx = $nx{$name} + $xpadding;
    my $ny = $ny{$name} + $ypadding;
    $e = $image->Draw(primitive => 'line',
		      points => "$x,$y $nx,$ny",
		      strokewidth => 1,
		      stroke => 'black');
    die "$e" if "$e";
    my $xx = $x + 1;
    $e = $image->Draw(primitive => 'circle',
		      points => "$x,$y $xx,$y",
		      stroke => 'red',
		      fill => 'red');
    die "$e" if "$e";
    $e = $image->Annotate(text => $name,
			  fill => 'black',
			  font => 'Generic.ttf',
			  geometry => "+$nx+$ny",
			  pointsize => 10);
    die "$e" if "$e";
  }
}