#!/usr/bin/perl -w

# tkil@scrye.com 1999-12-01

=pod

Problem: given a set of points on a 2-d plane which define a polygon
(not necessarily convex), test additional points to see if they are
within the convex hull of the set.

My first solution: take the first point, and then form a triangle with
each of the other points, in sequence.  if the point is within any of
those triangles, then the point is within the convex hull.  (because
convex hulls can be simply triangulated in this manner.)

too bad it breaks.

try 2: take our test point 't' and draw a vector from it to the first
point in the set.  this will be both a min and a max vector.  for each
point after the first, compare against the min vectcor to see if the
new vector (from t to current point) is further "clockwise" (negative
cross product) than the current min vector.  if not, see if it is
further "counter-clockwise" (positive cross product) than the current
max vector.  if either vector has changed, compare the vectors against
each other; if min cross max has a negative cross product, then the
test point is in the hull.

=cut

use strict;

my $DEBUG = 0;

sub pv
{
    local $" = ',';
    return "(@{$_[0]})";
}

sub cross
{
    my ($a, $b) = @_;
    my $rv = $a->[0] * $b->[1] - $a->[1] * $b->[0];
    if ($DEBUG)
    {
        my $as = pv($a);
        my $bs = pv($b);
        print "cross( $as, $bs ) = $rv\n";
    }
    return $rv;
}

sub diff
{
    my ($a, $b) = @_;
    my $rv = [ $b->[0] - $a->[0], $b->[1] - $a->[1] ];
    if ($DEBUG)
    {
        my $as = pv($a);
        my $bs = pv($b);
        my $rvs = pv($rv);
        print "diff( $as, $bs ) = $rvs\n";
    }
    return $rv;
}

sub dup
{
    return [ @{ $_[0] } ];
}

sub equal
{
    my ($a, $b) = @_;
    my $rv = ( $a->[0] == $b->[0] && $a->[1] == $b->[1] ) ? 1 : 0;
    if ($DEBUG)
    {
        my $as = pv($a);
        my $bs = pv($b);
        print "equal( $as, $bs ) = $rv\n";
    }
    return $rv;
}

sub point_in_set
{
    my $t = shift;
    my $verts = shift;

    # get initial min and max vectors.
    my $p = $verts->[0];
    return 1 if equal($t, $p);

    my $min = diff($t, $p);
    my $max = dup($min);

    for $p ( @{ $verts }[1 .. $#$verts] )
    {
        return 1 if equal($t, $p);

        my $v = diff($t, $p);

        my $changed = 0;
        if (cross($min, $v) < 0)
        {
            $min = dup($v);
            $changed = 1;
            print "  setting min=", pv($min), "\n" if $DEBUG;
        }
        elsif (cross($max, $v) > 0)
        {
            $max = dup($v);
            $changed = 1;
            print "  setting max=", pv($max), "\n" if $DEBUG;
        }

        if ($changed && cross($min, $max) < 0)
        {
            return 1;
        }
    }

    print "not in set, min=", pv($min), ", max=", pv($max), "\n\n"
      if $DEBUG;

    return 0;
}

# ============================================================

my @points =
  (
   [  4,  1 ],
   [  0, -2 ],
   [  3,  3 ],
   [  0,  0 ],
   [ -4, -1 ],
   [ -1,  5 ],
  );

my @test_points =
  (
   [ -2, 2 ],                   # should be in the set
   [ -3,  3 ],                  # shouldn't be in the set.
  );

foreach my $t (@test_points)
{
    my $rc = point_in_set($t, \@points);
    my $rc_s = $rc ? "is in" : "is not in";

    my $t_s = '(' . join(", ", @$t) . ')';

    print "$t_s $rc_s the set.\n";
    print "\n" if $DEBUG;
}

exit 0;