Banish the overlap (was:Re: drawmap.pl

in reply to drawmap.pl - Spot The Monk!
After burning my mouth by giving incomplete intersection hints in the chatterbox and on my home node, I reworked the great program by jcwren (idea) and OeufMayo (realization) to reduce the overlap.
There are some small glitches which I haven't yet worked out (for example, Tortue vs. Elgon), but the overlap has been reduced greatly. What would be interesting now would be some nice optimization to locate each monk as close as possible to the map marker, but I guess that's quite out of scope for a weekend hack :)
Test images

Update:
Sorted the code a bit better, now everything gets drawn when it got calculated
Reject monks earlier when they are off-map

#!/usr/bin/perl -w
#
# drawmap - spot the monk!
# Briac 'OeufMayo' Pilpré
# 2001/06/15

# Great earth maps available from http://apollo.spaceports.com/~jhasti
+ng/earth.html

# A jcwren's monkmap compliant map can be found at
# http://www.pilpre.com/briac/small_earth.jpg

#drawmap.pl -i=northam10k.jpg  -o=monkmap_northam.jpg -x=-1280 -y=-896
+ -m ./monks.xml -d cross.png -w 10800 -h 5400
#drawmap.pl -i=europe10k.jpg   -o=monkmap_europe.jpg  -x=-4880 -y=-695
+ -m ./monks.xml -d cross.png -w 10800 -h 5400
#drawmap.pl -i=small_earth.jpg -o=monkmap_world.jpg   -x=-25   -y=-3  
+ -m ./monks.xml -d cross.png -C

use strict;
use lib 'lib/';
use vars qw($VERSION); $VERSION = 0.03;
use XML::Simple;
use Getopt::Mixed 'nextOption';
use GD;

Getopt::Mixed::init('C:i i=s o=s d=s w=i h=i x:i y:i m=s xml>m dot>d w
+idth>w height>h input>i output>o offsetx>x offsety>y nocaption>C');

die "Uhoh" unless rectangles_intersect(589,573,645,586, 598,572,640,58
+5);
die "Uhoh" unless rectangles_intersect(598,572,640,585, 589,573,645,58
+6);

# Fetch the command line parameters
my ($input, $output, $offsetx, $offsety, $dot, $xml, $width, $height, 
+$nocaption);
while (my ($option, $value, $pretty) = nextOption()) {
        $input   = $value if $option eq 'i';
        $output  = $value if $option eq 'o';
        $offsetx = $value if $option eq 'x';
        $offsety = $value if $option eq 'y';
        $xml         = $value if $option eq 'm';
        $dot         = $value if $option eq 'd';
        $width         = $value if $option eq 'w';
        $height         = $value if $option eq 'h';
        $nocaption = 1 if $option eq 'C';
}
Getopt::Mixed::cleanup();
&usage unless ($input && $output);

$offsetx ||= 0;
$offsety ||= 0;

my %monks;

# Parse the monks coordinates XML file I fetched from jcwren's stats s
+ite.
# ( code to fetch & create the XML is available on request )
my $xs  =  new XML::Simple();
my $ref = $xs->XMLin($xml);

# Fill the monks hash with their respective locations
foreach (keys %{$ref->{monk}}){
        push (@{$monks{$_}}, (
                                $ref->{monk}->{$_}->{location}->{latit
+ude},
                                $ref->{monk}->{$_}->{location}->{longi
+tude},
        ));
}

# Load the pictures we need.
my $map    = GD::Image->newFromJpeg($input);
my $flag   = GD::Image->newFromPng($dot);
my $white  = $map->colorResolve(255,255,255);
my $black  = $map->colorResolve(0,0,0);

unless ($width && $height){
        ($width, $height) = $map->getBounds();
}

my %points;        #keep track of the points for managing monks densit
+y
my %boxes;        #keep track of the caption bounding boxes

# First, lets filter out all monks not on the map :
my ($img_width,$img_height) = $map->getBounds();
my @monks_off_map = grep {
                          my ($x,$y) = coord2pix($monks{$_}->[0],$monk
+s{$_}->[1],
                                                 $width, $height);

                          # Tweak the x/y to fit the picture
                          $x += $offsetx;
                          $y += $offsety;

                          # We want only the off-map monks :
                             ! (between(0,$width-$offsetx, $x) && betw
+een(0,$height-$offsety,$y))
                          || ! (between(0,$img_width, $x) && between(0
+,$img_height,$y));
                        } keys %monks;

foreach (@monks_off_map) {
  #print "Goodbye, $_\n";
  delete $monks{$_}
};

# Now, we want to place all position markers :
my $f = 6;        # "closeness" factor

foreach (keys %monks){

        # Convert the lat/long to x/y
        my ($x,$y) = coord2pix($monks{$_}->[0],$monks{$_}->[1],
                                                         $width, $heig
+ht);

        # Tweak the x/y to fit the picture
        $x += $offsetx;
        $y += $offsety;

        $points{$_}    = [$x-$f, $y-$f, $x+$f, $y+$f]; # store the cur
+rent pos
        $boxes{"__$_"} = [$x-$f, $y-$f, $x+$f, $y+$f]; # store the cur
+rent pos of the bbox

        # Pinpoints the monk location on the map
        $map->copy($flag, $x, $y, 0,0,7,7);
};

foreach (keys %monks){

        # Convert the lat/long to x/y
        my ($x,$y) = coord2pix($monks{$_}->[0],$monks{$_}->[1],
                                                         $width, $heig
+ht);
        # Tweak the x/y to fit the picture
        $x += $offsetx;
        $y += $offsety;

        # Let's find if we have a monk close to the current one
        unless ($nocaption){
                my ($x1,$y1);
                my ($radius, $angle) = (10,0);
                my $textl = 7 * length($_);        #length of the capt
+ion

                # Create a box for the label
                my @box = (int($x-$textl/2), $y-17, int($x+$textl/2), 
+$y-18+13);

                if (find_density(\%points, $_, $x,$y) ||      # If tru
+e the monk is too close
                    find_intersect(\%boxes, $_, @box)         # or the
+ place has been taken already
                   )
                {
                  CLOSE :{
                    $radius += 5;
                    $angle  += 10 % 360;

                    # Find a point on a circle.
                    # provided by CheeseLord: (x+r cos a, y+r sin a)
                    ($x1,$y1)=(int($x + ($radius * cos $angle)), int($
+y+($radius * sin $angle)));

                    # Move the label
                    @box = (int($x1-$textl/2), $y1, int($x1+$textl/2),
+ $y1+13);

                    # Check to see if it intersects with a previous ca
+ption
                    redo CLOSE if find_intersect(\%boxes, $_, @box);

                    $map->line($x+4, $y+4, $x1+4, $y1+4, $white);
                    $map->string(gdMediumBoldFont, $x1 - $textl/2 + 2,
+ $y1, $_, $black);
                    $map->string(gdMediumBoldFont, $x1 - $textl/2 + 3,
+ $y1, $_, $white);
                  }
                }
                else {
                    $map->string(gdMediumBoldFont, int($x - $textl/2)+
+1, $y-17, $_, $black);
                    $map->string(gdMediumBoldFont, int($x - $textl/2),
+   $y-18, $_, $white);
                }
                $boxes{$_} = [@box];
        }

}

# We now save our masterpiece on a storage device
open        JPGOUT, ">  $output" or die $!;
binmode JPGOUT;
print         JPGOUT $map->jpeg(75);

sub between {
  my ($a1,$a2,$b) = @_;
  return ($a1 <= $b) && ($b <= $a2);
};

sub point_in_rectangle {
  my ($left,$top,$right,$bottom,$x,$y) = @_;
  return between($left,$right,$x) && between($top,$bottom,$y)
};

sub rectangles_intersect {
  my ($a_lft,$a_top,$a_rgt,$a_btm,$b_lft,$b_top,$b_rgt,$b_btm) = @_;
  return (
                        # One of the four corners within the other rec
+tangle
                        point_in_rectangle($a_lft,$a_top,$a_rgt,$a_btm
+,$b_lft,$b_top) ||
                        point_in_rectangle($a_lft,$a_top,$a_rgt,$a_btm
+,$b_rgt,$b_top) ||
                        point_in_rectangle($a_lft,$a_top,$a_rgt,$a_btm
+,$b_lft,$b_btm) ||
                        point_in_rectangle($a_lft,$a_top,$a_rgt,$a_btm
+,$b_rgt,$b_btm) ||
                        point_in_rectangle($b_lft,$b_top,$b_rgt,$b_btm
+,$a_lft,$a_top) ||
                        point_in_rectangle($b_lft,$b_top,$b_rgt,$b_btm
+,$a_rgt,$a_top) ||
                        point_in_rectangle($b_lft,$b_top,$b_rgt,$b_btm
+,$a_lft,$a_btm) ||
                        point_in_rectangle($b_lft,$b_top,$b_rgt,$b_btm
+,$a_rgt,$a_btm) ||
                        # Or an intersection where no corner is within
+ the other rectangle
                        (
                            between( $a_lft, $a_rgt, $b_lft )
                         && between( $a_lft, $a_rgt, $b_rgt )
                         && between( $b_top, $b_btm, $a_top )
                         && between( $b_top, $b_btm, $a_btm )
                        ) ||
                        (
                            between( $b_lft, $b_rgt, $a_lft )
                         && between( $b_lft, $b_rgt, $a_rgt )
                         && between( $a_top, $a_btm, $b_top )
                         && between( $a_top, $a_btm, $b_btm )
                        )
                );
};

sub find_intersect {
        my $boxes   = shift;
        my $current = shift;
        my ($a_lft,$a_top, $a_rgt, $a_btm) = @_;

        my $overlap;

        foreach (keys %{$boxes}){
                next if $_ eq $current;
                next if $_ eq "__$current";                 # The own 
+location marker is never "too close"

                my ($b_lft,$b_top, $b_rgt, $b_btm) = @{$boxes->{$_}};

                # Collison tests provided by Corion. I probably left s
+ome out.
                if (rectangles_intersect($a_lft,$a_top,$a_rgt,$a_btm,$
+b_lft,$b_top,$b_rgt,$b_btm)){
                        $overlap++;
                        last;
                }
        }
        return $overlap;
}

sub find_density {
        my $dens    = shift;
        my $current = shift;
        my ($x,$y)  = @_;

        my $too_close;

        foreach (keys %{$dens}){
                next if $_ eq $current;
                my ($x1,$y1,$x2,$y2) = @{$dens->{$_}};
                if (point_in_rectangle($x1,$y1,$x2,$y2, $x,$y)){
                        $too_close++;
                        last;
                }
        }
        return $too_close;
}

sub coord2pix {
        # Convert the lat/long to their actual coordinates in the
        # picture (thanks to jcwren for the tips!)
        my ($lat, $long, $width, $height) = @_;
        my $x =  $width / 2 + ($long / 360 * $width);
        my $y = $height / 2 - ($lat  / 180 * $height);
        return ( int $x, int $y );
}

sub usage {
        print STDERR <<"__USAGE__";
drawmap - v.$VERSION
 perl drawmap.pl -i inputfile.jpg -o outputfile.jpg -m ./locat.xml -d 
+dot.png

 Required arguments:
 -i --input   : Name of the map base.
 -o --output  : Name of the output file created by drawmap

 -d --dot     : Location of the png used as location marker
 -m --xml     : Location of the xml coordinates file

 Optional arguments:
 -x --offsetx : Offset of the x axis
 -y --offsety : Offset of the y axis

 -C --nocaption : Does not draw the caption above the marker

 -w --width   : Width of the original whole earth map (useful when zoo
+ming)
 -h --height  : Height of the original whole earth map
__USAGE__

         die "\n";
}

__DATA__
<!-- monks.xml DTD -->
<!ELEMENT monkmap (monk+)>
<!ELEMENT monk (name, location)>
        <!ATTLIST monk id CDATA #REQUIRED>
<!ELEMENT name (#PCDATA)>
<!ELEMENT location (latitude, longitude)>
        <!ELEMENT latitude (#PCDATA)>
        <!ELEMENT longitude (#PCDATA)>
[download]
In Section Cool Uses for Perl