# [complex-hull.pm] 31.01.1999 R.Scholz <Voland@Jena.Thur.de>
#
# Time-stamp: <31.01.1999, 22:01:07, mrz@isun24>
#
# This modul calculates the complex hull of a data file
#
# It implements the wrap-algorithm you find in the book from Sedgewick



sub theta {
  my($rp1, $rp2)=@_;
  my($dx,$dy,$ax,$ay,$t, %p1,%p2);

  %p1=%$rp1; %p2=%$rp2;

  $dx=$p2{x} - $p1{x};  $ax=abs($dx);
  $dy=$p2{y} - $p1{y};  $ay=abs($dy);
  if($dx==0 && $dy==0)  { $t=0; }
  else                  { $t=$dy/($ax+$ay);}

  if($dx<0) { $t=2-$t; } elsif($dy<0) { $t+=4; }
  return($t*90.0);
}




sub wrap {
  my($max, @points)=@_;
  my($i, $min, $M, $minangle, $tp);
  $min=0; $tp={};

  for($i=1; $i<=$max; $i++)
    {
      $min=$i if( ($points[$i]{y}) < ($points[$min]{y}) );
    }
  
  $points[$max+1]{x}=$points[$min]{x};
  $points[$max+1]{y}=$points[$min]{y};
  $minangle=0.0;
  $M=-1;
  
  do 
    {
      $M++;
      $tp->{x}=$points[$M]{x};
      $tp->{y}=$points[$M]{y};
      $tp->{D}=$points[$M]{D};
      $points[$M]{x}=$points[$min]{x};
      $points[$M]{y}=$points[$min]{y};
      $points[$M]{D}=$points[$min]{D};
      $points[$min]{x}=$tp->{x};
      $points[$min]{y}=$tp->{y};
      $points[$min]{D}=$tp->{D};
      $min=$max+1;
      
      $v=$minangle;
      $minangle=360.0;
      for($i=$M+1; $i<=$max+1; $i++)
	{
	  if(&theta($points[$M], $points[$i]) > $v)
	    {
	      if(&theta($points[$M], $points[$i]) < $minangle)
		{
		  $min=$i;
		  $minangle=&theta($points[$M], $points[$min]);
		}
	    }
	}
    }
  until($min == ($max+1) );

  return($M); # last point of the complex hull
}




# read data (aka: GNUPLOT-Data) 
# x and y are the first two with whitespace seperated
# numbers of the line
sub read_data {
  my(@points)=@_;
  my $point;
  
  while(<>)
    {
      next if(/^\s*\#|^\s*$/);
      s/^\s+//;
      /(\S+)\s+(\S+)/;
      $point={};
      $point->{x}=$1;
      $point->{y}=$2;
      $point->{D}=$_;
      
      push(@points, $point)
    }
  return(@points);
}


# write all data lines of the convex hull to stdio:
sub write_konvexhull_data {
  my($last, @points)=@_;
  my($i);

  foreach $i (0..$last)  { print $points[$i]{D}; }
}


# END
1;