#!/usr/bin/perl
use strict;
my @state_polys;

my $debug = $ENV{DEBUG};
sub qprint{return if ($ENV{QUIET});     print STDERR @_;}
sub qprintf{return if ($ENV{QUIET});     printf STDERR @_;}
sub dprint{return if (!$debug);     print STDERR @_;}
sub dprint1{return if ($debug < 1); print STDERR @_;}
sub dprint2{return if ($debug < 2); print STDERR @_;}
sub dprint3{return if ($debug < 3); print STDERR @_;}
sub dprint4{return if ($debug < 4); print STDERR @_;}
sub dprint5{return if ($debug < 5); print STDERR @_;}

sub dprintf{return if (!$debug); printf STDERR @_;}
sub dprintf1{return if ($debug < 1); printf STDERR @_;}
sub dprintf2{return if ($debug < 2); printf STDERR @_;}
sub dprintf3{return if ($debug < 3); printf STDERR @_;}
sub dprintf4{return if ($debug < 4); printf STDERR @_;}
sub dprintf5{return if ($debug < 5); printf STDERR @_;}

my $poly;
my @names = ();

my $in = shift(@ARGV);

sub cstr
{
	my $c = shift;
	return sprintf("(%6.2f, %6.2f)", $c->{lon}, $c->{lat});
}

sub str_to_coord
{
        my $str = shift;
        #printf1 "coord line: '$str'\n";
        my ($lon, $lat) = split(",", $str, 2);
	$lon =~ s/\s//g;
	$lat =~ s/\s//g;
        die "bad lat: '$lat' '$str'" if !$lat;
        die "bad lon: '$lon' '$str'" if !$lon;
        my $ret;
        $ret->{lon} = $lon;
        $ret->{lat} = $lat;
        return $ret;
}

sub cat_file_into_array
{
        my $filename = shift;;
        my $nr_lines = shift;
        my @contents;
        my $line;
        open FILE, "< $filename";
        while ($line = <FILE>) {
                chomp $line;
                push @contents, $line;
                last if defined $nr_lines && --$nr_lines <= 0;
        }
        close FILE;
        return @contents;
}


sub poly_contains_coord
{
	my $poly = shift;
	my $c = shift;
	my $ret = undef;
	my $nr = 0;
	my $contains = poly_contains_coord($poly, $c);
	if ($contains) {
		$ret = $poly;
		dprintf2("$c: contained in '%s': %d\n", $poly->{name}, $contains);
	}
	return $ret;
}
#oregon
#1
#    -1.2358194E+002    4.622078E+001
#    -1.2358194E+002    4.624029E+001
#    -1.2354859E+002    4.624029E+001
#    -1.2354859E+002    4.622078E+001
#    -1.2358194E+002    4.622078E+001
#END
#2

sub cindex
{
	my $coord = shift;
	my $index = shift;
	my @parts = split(/ +/, $coord);
	return $parts[$index] + 0.0;
}

sub cmin
{
	my $poly = shift;
	my $ll = shift;
	my $ret = 9999;
	my $key = "min.".$ll;
	return $poly->{$key} if defined $poly->{$key};
	for my $coord (@{$poly->{coords}}) {
		my $l = $coord->{$ll};
		#rintf("cmin l: '$l'\n");
		$ret = $l if ($l < $ret);
	}
	$ret += 0.0;
	$poly->{$key} = $ret;
	return $ret;
}

sub cmax
{
	my $poly = shift;
	my $ll = shift;
	my $ret = -9999;
	my $key = "max.".$ll;
	return $poly->{$key} if defined $poly->{$key};
	for my $coord (@{$poly->{coords}}) {
		my $l = $coord->{$ll};
		$ret = $l if ($l > $ret);
	}
	$ret += 0.0;
	$poly->{$key} = $ret;
	return $ret;
}

sub poly_contains_coord
{
	my $poly = shift;
	my $coord = shift;
	my $min_lat = cmin($poly, "lat");
	my $lat = $coord->{lat};
	my $lon = $coord->{lon};
	return 0 if ($lat < $min_lat);
	my $min_lon = cmin($poly, "lon");
	dprintf3 "1\n";
	return 0 if ($lon < $min_lon);
	my $max_lat = cmax($poly, "lat");
	dprintf2("lat: '%s' min/max: '%s' '%d' '%s' '%d'\n", $lat, $min_lat, ($lat < $min_lat), $max_lat, ($lat > $max_lat));
	return 0 if ($lat > $max_lat);
	my $max_lon = cmax($poly, "lon");
	dprintf3 "3\n";
	return 0 if ($lon > $max_lon);
	dprintf1("lon min/max: '%s' '%d' '%s' '%d'\n", $min_lon, ($lon < $min_lon), $max_lon, ($lon > $max_lon));
	return 1;
}

while (my $line = <>) {
	$line =~ s/\s$//g;
	chomp $line;
	next if ! length($line);
	if ($line =~ /END/) {
		if (defined $poly) {
	       		my $fullname = join("-", @names);
			$poly->{name} = $fullname;
			push @state_polys, $poly;
			#rintf("ended: '$line' name: '$fullname' total polygons: %d\n", scalar(@polys));
			$poly = undef;
		}
		my $popped = pop @names;
		#rintf "names now after pop of '$popped': '%s' len: %d\n", join(",", @names), scalar(@names);
	} elsif ($line =~ /\s+([-\.\d\+e]+)\s+([-\.\d\+e]+).*/i) {
		my $lon = $1;
		my $lat = $2;
		my @empty = ();
		my $coords_ref = $poly->{coords};
		if (! defined $coords_ref) {
			$poly->{coords} = \@empty;
			$coords_ref = $poly->{coords};
		}
		push @{$coords_ref}, str_to_coord("$lon,$lat");
		#rintf("coord: '$line' '%s' '%s' len: %d\n", $lon, $lat, scalar(@{$coords_ref}));
	} else {
		push @names, $line;
		#rintf("pushed name[%d]: '$line'\n", scalar(@names));
	}
}
dprintf1("read %d state polygons\n", scalar(@state_polys));
my @coords = ();

#unlink("america.php.txt");
#system("wget -q -O america.php.txt http://garmin.na1400.info/america.php");
my @americas = cat_file_into_array($in);
dprintf "read %d lines from '%s'\n", scalar(@americas), $in;
my $name = undef;

my $middles;
my $orig_size = scalar @americas;
my $dienow = 0;
my $debugtile = "";#73240190";
my @area_polys;
while (scalar @americas) {
	#if (scalar(@americas) % 20 == 0) {
	#	printf("\r%4.2f done", (100.0*($orig_size - scalar @americas)/$orig_size));
	#}
        my $line = shift @americas;
        chomp $line;
        if ($line =~ /<name>/) {
                $name = $line;
                $name =~ s/<[\/]?[a-z]+>//ig;
                $name =~ s/\s*//;
		dprintf1("looking for '$name'\n");
		die "died" if $dienow;
		#$dienow = 1 if $name eq $debugtile;
        }
        if ($line =~ /<coordinates>/
            && defined $name) {
                my @coords = (str_to_coord(shift(@americas)),
                              str_to_coord(shift(@americas)),
                              str_to_coord(shift(@americas)),
                              str_to_coord(shift(@americas)));
		my $area_poly;
		$area_poly->{name} = $name;
		$area_poly->{coords} = \@coords;
		push @area_polys, $area_poly;
	}
}

sub __poly_intersect
{
	my $p1 = shift;
	my $p2 = shift;
	# swap if one is shorter

	foreach my $c (@{$p1->{coords}}) {
		if (poly_contains_coord($p2, $c)) {
			return 1;
		}
		#dprintf1("c: '%s' poly: $poly\n", cstr($c)) if $name eq $debugtile;
		#	next if ! $poly;
		#	dprintf1("poly_containing_coord($name,$c): '%s'\n", $poly->{name});
		#	printf "$name\n";
        }
	return undef;
}

sub poly_intersect
{
	my $p1 = shift;
	my $p2 = shift;
	return __poly_intersect($p1, $p2) || __poly_intersect($p2, $p1);
}

sub sprint_poly
{
	my $p = shift;
	my $ret = "";
	$ret .= sprintf "name: '%s'\n", $p->{name};
	foreach my $coord (@{$p->{coords}}) {
		$ret .= sprintf "\t%s\n", cstr($coord);
	}
	return $ret;
}

# this is O(n^2)... O(n^3) if you include the polygon dimensions...
# It sucks.  So sue me.
foreach my $area_poly (@area_polys) {
	foreach my $state_poly (@state_polys) {
		next if ! poly_intersect($area_poly, $state_poly);
		dprintf1 sprint_poly($state_poly);
		dprintf1 sprint_poly($area_poly);
		dprintf1 "intersects with state poly: '%s' ", $state_poly->{name};
		print $area_poly->{name}."\n";
		last;
	}
}