#!/usr/local/bin/perl
# Borrowed from the article: http://www.linuxjournal.com/article/1103 
# Things to add:
# * Read and parse the gpslog file for long and lat coords
# * Cutdown commands, check 3 times before firing, only fire 3 times
# * Survive if coords are 0.0,0.0
# * Shift polygon coord to a config file.
 
sub hypot # (x, y) returns sqrt(x * x + y * y)
{
sqrt $_[0] * $_[0] + $_[1] * $_[1];
}
 
$epsilon = 1.0e-10;
sub point_on_line #(point, line) returns 0 or 1
{ # if on - sum of distance to ends should be distance between ends
local($point, $line) = @_;
local($p_x, $p_y) = split(",", $point);
local($l_b, $l_e) = split(":", $line);
local($l_b_x, $l_b_y) = split(",", $l_b);
local($l_e_x, $l_e_y) = split(",", $l_e);
&fabs(&hypot($p_x - $l_b_x, $p_y - $l_b_y) +
      &hypot($p_x - $l_e_x, $p_y - $l_e_y) -
      &hypot($l_e_x - $l_b_x, $l_e_y - $l_b_y)) < $epsilon;
}
 
sub fabs # (x) returns absolute value of x
{
local($rv) = @_;
$rv = -$rv if $rv < 0.0;
$rv;
}
 
sub ccw # (three points) return -1, 0, or 1
{
local(@points) = @_;
local($rv) = 0;
local($dx1, $dx2, $dy1, $dy2, $p0x, $p0y, $p1x, $p1y, $p2x, $p2y);
($p0x, $p0y) = split(",", $points[0]);
($p1x, $p1y) = split(",", $points[1]);
($p2x, $p2y) = split(",", $points[2]);
$dx1 = $p1x - $p0x;
$dy1 = $p1y - $p0y;
$dx2 = $p2x - $p0x;
$dy2 = $p2y - $p0y;
switch:
   {
   $rv =  1, last if $dx1 * $dy2 > $dy1 * $dx2;
   $rv = -1, last if $dx1 * $dy2 < $dy1 * $dx2;
   $rv = -1, last if ($dx1 * $dx2 < 0.0) || ($dy1 * $dy2 < 0.0);
   $rv =  1, last if ($dx1 * $dx1 + $dy1 * $dy1) < ($dx2 * $dx2 + $dy2 * $dy2);
   }
$rv;
}
 
sub intersect # (two lines) returns 0 or 1
{
local($l1, $l2) = @_;
local($l1_b, $l1_e) = split(":", $l1);
local($l2_b, $l2_e) = split(":", $l2);
&ccw($l1_b, $l1_e, $l2_b) * &ccw($l1_b, $l1_e, $l2_e) <= 0 &&
&ccw($l2_b, $l2_e, $l1_b) * &ccw($l2_b, $l2_e, $l1_e) <= 0;
}
 
$big_float = 1.0e7;
sub lower_left_index # (polygon) returns index of lower left corner
{
local($polygon) = @_;
local($index) = 0;
local(@vertices) = split(":", $polygon);
local($x_min, $y_min) = split(",", $vertices[0]);
local($i, $x, $y);
for($i = 1; $i <= $#vertices; $i++)
   {
   ($x, $y) = split(",", $vertices[$i]);
   if(($y < $y_min) || (($y == $y_min) && ($x < $x_min)))
      {
      $x_min = $x;
      $y_min = $y;
      $index = $i;
      }
   }
$index;
}
sub inside # (point, polygon) returns 0 or 1
{
local($point, $polygon) = @_;
local(@vertices) = split(":", $polygon);
local($index) = &lower_left_index($polygon);
local($last_index) = $index ? $index - 1 : $#vertices;
local($count, $holding_point) = (0, 0);
local($i, $lp, $lt, $vertex, $x, $y, $big_x_point);
local($check_index) = $index; # true if index is not zero
OUTER: for(;;)
   { # one pass loop
   for($i = 0, $vertex = $vertices[$#vertices]; $i <= $#vertices; $i++)
      {
      $lp = join(":", $vertex, $vertices[$i]);
      $vertex = $vertices[$i];
      if(&point_on_line($point, $lp))
         {
         $count = 1;
         print "Point on boundary\n" if defined $verbose;
         last OUTER;
         }
      }
   ($x, $y) = split(",", $point);
   $big_x_point = join(",", $big_float, $y);
   $lt = join(":", $point, $big_x_point);
   for($i = 0; $i <= $#vertices; $i++)
      {
      if(&point_on_line($vertices[$index], $lt))
         {
         $holding_point = 1;
         }
      else
         {
         if(!$holding_point)
            {
            $lp = join(":", $vertices[$last_index], $vertices[$index]);
            $count++ if &intersect($lp, $lt);
            }
         elsif($holding_point &&
               (&ccw($point, $big_x_point, $vertices[$index]) !=
                &ccw($point, $big_x_point, $vertices[$last_index])))
            {
            $count++;
            }
         $last_index = $index;
         $holding_point = 0;
         }
      $index++;
      if($check_index && ($index == @vertices))
         {
         $check_index = 0;
         $index = 0;
         }
      }
   last;
   } # one pass "loop"
$count & 1;
}
 
while(<DATA>)
   {
   chop;
   $polygon .= $_ . ":";
   }
chop $polygon;
for(;;)
   {
   print "Enter x and y separated by a comma (q to quit): ";
   chop($point = <STDIN>);
   last if $point =~ /^[qQ]/;
   print("No comma!  Try again.\n"), redo if $point !~ /,/;
   $point =~ s/ +//g;
   print "Checking point: $point\n";
   printf "%s\n", &inside($point, $polygon) ? "inside" : "outside therefore CUTDOWN";
   }
__END__
 
# Polygon coordinates
0.0,0.0
5.0,0.0
0.0,5.0
5.0,5.0