// (c) MIT 2003.  All rights reserved.

////////////////////////////////////////////////////////////////////////////////
//
// FILE:	GPolygon.java
//
// AUTHOR:	Manoj D. Muzumdar
//		archon@ai.mit.edu
//
// DATE:	07-XX-98
//
// COPYRIGHT:	Massachusetts Institute of Technology
//		All rights reserved.
//
// PURPOSE:	Geometric modeling
//
// HISTORY:     11-15-98 archon
//              Made mutable
//
////////////////////////////////////////////////////////////////////////////////

package rec.geo;

import java.awt.*;
import java.util.*;
import rec.util.*;

/**
 * GPolygon is the base class for all polygons.
 */
public class GPolygon extends GShape
{
  public GPolygon( GPoint[] arrPoints )
  {
    Assert.check( arrPoints != null && arrPoints.length >= 3,
		  "polygons must have at least 3 sides" );

    initialize( arrPoints );
  }

  public GPolygon( GPolygon gp )
  {
    initialize( gp.m_Points );
  }

  /////////////////////////////////////////////////////////////////////////////

  private void initialize( GPoint[] arrPoints )
  {
    m_Points = new GPoint[arrPoints.length];

    for( int i = 0; i < arrPoints.length; ++i )
      m_Points[i] = new GPoint( arrPoints[i] );
  }

  ////////////////////////////////////////////////////////////////////////////

  public GShape copy()
  {
    return( new GPolygon( this ) );
  }

  public void reflect()
  {
    for( int i = 0; i < m_Points.length; ++i )
      m_Points[i].reflect();
  }

  public void translate( double dx, double dy )
  {
    for( int i = 0; i < m_Points.length; ++i )
      m_Points[i].translate( dx, dy );
  }

  public void rotate( GPoint gp, double radians )
  {
    for( int i = 0; i < m_Points.length; ++i )
      m_Points[i].rotate( gp, radians );
  }

  //////////////////////////////////////////////////////////////////////////////

  public double size()
  {
    // Averages the lengths of all the segments in the polygon.
    double total = 0.0;

    for( int i = 0; i < m_Points.length - 1; ++i )
      total += Geometry.distance( m_Points[i], m_Points[i + 1] );

    total += Geometry.distance( m_Points[m_Points.length - 1], m_Points[0] );

    return( total / m_Points.length );
  }

  public void resize( double scaleFactor )
  {
    // ada: implemented scaling
    // scale around the center of the bounding box
    
    // get the center point
    Rectangle bounds = getBounds();
    double centerX = (bounds.getX() + (bounds.getWidth() / 2.0));
    double centerY = (bounds.getY() + (bounds.getHeight() / 2.0));

    // resize each point
    for( int i = 0; i < m_Points.length; ++i ) {
      double oldX = m_Points[i].getX();
      double oldY = m_Points[i].getY();
      double newX = ((oldX - centerX) * scaleFactor) + centerX;
      double newY = ((oldY - centerY) * scaleFactor) + centerY;
      GPoint newPt = new GPoint(newX, newY);
      m_Points[i] = newPt;
    }
  }

  //////////////////////////////////////////////////////////////////////////////

  public final Rectangle getBounds()
  {
    // Top left corner point.
    int tlx = m_Points[0].getIntX();
    int tly = m_Points[0].getIntY();

    // Bottom right corner point.
    int brx = m_Points[0].getIntX();
    int bry = m_Points[0].getIntY();

    for( int i = 1; i < m_Points.length; ++i ) {
      tlx = Math.min( tlx, m_Points[i].getIntX() );
      tly = Math.min( tly, m_Points[i].getIntY() );
      brx = Math.max( brx, m_Points[i].getIntX() );
      bry = Math.max( bry, m_Points[i].getIntY() );
    }

    return( new Rectangle( tlx - 1, tly - 1,
			   brx - tlx + 2, bry - tly + 2 ) );
  }

  /**
   * From graphic gems II, p5
   *
   * vertices are supposed to be in _counterclockwise_ order, but
   * I am not sure if they are.  The math.abs is a possible unthoughtout
   * hack to fix this problem.
   */
  public double area()
  {
    double tot = 0;
    
    int size = m_Points.length;
    for ( int i = 0; i < size; i++ )
      {
	tot += m_Points[i].x * m_Points[(i+1)%size].y;
	tot -= m_Points[(i+1)%size].x * m_Points[i].y;
      }

    return Math.abs( tot / 2 );
  }

  /////////////////////////////////////////////////////////////////////////////

  public final void display( Graphics g )
  {
    for( int i = 1; i < m_Points.length; ++i ) {
      g.drawLine( m_Points[i - 1].getIntX(), m_Points[i - 1].getIntY(),
		  m_Points[i].getIntX(), m_Points[i].getIntY() );
    }

    g.drawLine( m_Points[m_Points.length - 1].getIntX(),
		m_Points[m_Points.length - 1].getIntY(),
		m_Points[0].getIntX(), m_Points[0].getIntY() );
  }

  //////////////////////////////////////////////////////////////////////////////

  public final boolean includes( GPoint gp )
  {
    for( int i = 1; i < m_Points.length; ++i ) {
      if( (new GSegment( m_Points[i - 1], m_Points[i] ))
	  .includes( gp ) )
	return( true );
    }

    return( (new GSegment( m_Points[m_Points.length - 1],
			   m_Points[0] )).includes( gp ) );
  }

  public final boolean includes( GPoint gp, double offset )
  {
    Assert.check( offset >= 0.0, "offset cannot be negative" );

    for( int i = 1; i < m_Points.length; ++i ) {
      if( (new GSegment( m_Points[i - 1], m_Points[i] ))
	  .includes( gp, offset ) )
	return( true );
    }

    return( (new GSegment( m_Points[m_Points.length - 1],
			   m_Points[0] )).includes( gp, offset ) );
  }


  /**
   * @return true if l is on _BORDER_ of polygon, false otherwise.
   */
  public boolean includes( GSegment l, double offset )
  {
    // had to pull out segmentcontaining code since the offset could
    // allow the wrong segments to be selected by the algorithm.
    // Even the double-ended check can fail since _each_ point could
    // return the wrong segment.
    Assert.check( offset >= 0.0, "offset cannot be negative" );

    GPoint gp = l.getHeadPoint();
    GPoint gp2 = l.getTailPoint();

    GSegment ret = null;
    for( int i = 0; i < m_Points.length; ++i ) {
      ret = new GSegment( m_Points[i], m_Points[(i+1)%m_Points.length] );
      if( ret.includes( gp, offset ) && ret.includes( gp2, offset ) )
	return true;    
    }

    return false;
  }

  /////////////////////////////////////////////////////////////////////////////

  public final GSegment getSegmentContaining( GPoint gp )
  {
    GSegment ret = null;

    for( int i = 1; i < m_Points.length; ++i ) {
      ret = new GSegment( m_Points[i - 1], m_Points[i] );
      if( ret.includes( gp ) )
	return( ret );
    }

    ret = new GSegment( m_Points[m_Points.length - 1],
			m_Points[0] );
    if( ret.includes( gp ) )
      return( ret );

    return( null );
  }

  public final GSegment getSegmentContaining( GPoint gp, double offset )
  {
    Assert.check( offset >= 0.0, "offset cannot be negative" );

    GSegment ret = null;

    for( int i = 1; i < m_Points.length; ++i ) {
      ret = new GSegment( m_Points[i - 1], m_Points[i] );
      if( ret.includes( gp, offset ) )
	return( ret );
    }

    ret = new GSegment( m_Points[m_Points.length - 1],
			m_Points[0] );
    if( ret.includes( gp, offset ) )
      return( ret );

    return( null );
  }

  //////////////////////////////////////////////////////////////////////////////

  public final int getNumberOfPoints()
  {
    return( m_Points.length );
  }

  /**
   * @return  Array of points in the order of the initialization
   *               points going around the polygon.
   */
  public final GPoint[] getPoints()
  {
    return( m_Points );
  }

  //////////////////////////////////////////////////////////////////////////////  }

  public final int getNumberOfSides()
  {
    return( m_Points.length );
  }

  /**
   * @return  Array of segments in the order of the initialization
   *               points going around the polygon.  Last segment
   *               goes from last point in list to first point.  (So
   *               points corrispond to the array from getPoints()).
   */
  public final GSegment[] getSides()
  {
    GSegment[] ret = new GSegment[m_Points.length];

    for( int i = 1; i < m_Points.length; ++i ) {
      ret[i - 1] = new GSegment( m_Points[i - 1], m_Points[i] );
    }

    ret[m_Points.length - 1]
      = new GSegment( m_Points[m_Points.length - 1],
		      m_Points[0] );

    return( ret );
  }

  //////////////////////////////////////////////////////////////////////////////

  public final int getNumberOfAngles()
  {
    return( m_Points.length );
  }

  /**
   * @return  Array of angles in the order of the initialization
   *               points going around the polygon.
   */
  public final GAngle[] getAngles()
  {
    GAngle[] ret = new GAngle[m_Points.length];

    GPoint prev = m_Points[0];

    ret[0] = new GAngle( m_Points[m_Points.length - 1],
			 m_Points[0],
			 m_Points[1] );

    for( int i = 1; i < m_Points.length - 1; ++i ) {
      ret[i] = new GAngle( m_Points[i - 1],
			   m_Points[i],
			   m_Points[i + 1]  );
    }

    ret[m_Points.length - 1]
      = new GAngle( m_Points[m_Points.length - 2],
		    m_Points[m_Points.length - 1],
		    m_Points[0] );

    return( ret );
  }

  /**
   * @return true if p is within the loop specified by this polygon.  
   *      Behaviour undefined for self-intersecting polygons.
   */
  public boolean contains( GPoint p )
  {
    GPoint cur = m_Points[ m_Points.length - 1 ];
    boolean up = cur.y > p.y;
    boolean offsides = cur.x < p.x;
    boolean curoff;

    int cross = 0;

    //    System.err.println( "p = " + p );

    int s = m_Points.length;
    for( int i = 0; i < s; i++ ) {

      cur = m_Points[i];

      //      System.err.println( "cur = " + cur );

      curoff = cur.x < p.x;
	
      if( up ) {
	if( cur.y <= p.y ) {
	  //	  System.err.println( "down" );
	  if ( !curoff && !offsides )
	    cross++;
	  else if ( !curoff || !offsides )
	    cross += checkX( p, cur, m_Points[(i-1+s)%s] );
	  up = false;
	}
      }
      else {
	if( cur.y > p.y ) {
	  //	  System.err.println( "up" );
	  if ( !curoff && !offsides )
	    cross++;
	  else if ( !curoff || !offsides )
	    cross += checkX( p, cur, m_Points[(i-1+s)%s] );
	  up = true;
	}
      }

      offsides = curoff;
    }

    //    System.err.println( "contains() found " + cross + " crosses" );

    return(( cross % 2 ) == 1 );
  }

  /**
   * Return 1 if A left of p1-p2 segment, 0 otherwise.  p1.x != p2.x
   * 
   * This function is derived by plugging in the 2-point line equation,
   * solving for A.y and then seeing if the resultant x is to the left or
   * right of A.x.
   */
  public int checkX( GPoint A, GPoint p1, GPoint p2 )
  {
    double tx = ( A.y - p2.y ) * ( p1.x - p2.x ) / ( p1.y - p2.y ) + p2.x;
    return ( tx > A.x ) ? 1 : 0;
  }

  public boolean contains( GPoint p, double slack )
  {
    if ( contains( p ) )
      return true;

    // if not entirely inside, then check the perimeter.
    return includes( p, slack );
  }

  /**
   * If entire passed polygon is inside, return true. 
   */
  public boolean contains( GPolygon gp, double slack )
  {
    for ( int i = 0; i < gp.m_Points.length; i++ )
      {
	// are we flat out inside the durn thing?
	if ( !contains( gp.m_Points[i] ) )
	  {
	    // do the slack test.
	    if ( ( slack <= 0 ) || !includes( gp.m_Points[i], slack ) )
	      return false;
	  }
      }

    return true;
  }



  /**
   * @return Vector of all points which are members of segments which exit
   *     this polygon or are outside of polygon.
   *     Any segments completely inside polygon are ditched.
   */
  public Vector getRemainder_old( GPolygon gp, double slack )
  {
    Vector pts = new Vector();
    boolean cross = false;
    GSegment[] segs = gp.getSides();

    int size = m_Points.length;
    for ( int i = 0; i < m_Points.length; i++ )
      {
	boolean in1 = gp.contains(m_Points[i], slack );
	boolean in2 = gp.contains(m_Points[(i+1)%size], slack );

	if ( !in1 )
	  {
	    Console.writeln( "Adding " + m_Points[i] );
	    pts.addElement( m_Points[i] );
	  }

	// check for crossover
	if ( (in1 && !in2) || (!in1 && in2) )
	  {
	    Console.writeln( "Crossing!" );
	    GSegment xer = new GSegment( m_Points[i],
					 m_Points[(i+1)%size] );
	    double xer_angle = xer.getAngle();
	    GPoint out = null;
	    if ( in1 )
	      out = m_Points[(i+1)%size];
	    else
	      out = m_Points[i];
	    double dist = 100000; // Double.INFINITY;
	    GPoint best = null;

	    // find the closest intersection point to the outside point
	    // and add that to the polygon as a boundary point.
	    boolean done = false;
	    for ( int j = 0; !done && (j < segs.length); j++ )
	      {
		// make sure these are not ||-ish segments
		// this is a hack for dealing with the big rectangle-
		// little rectangle issue where the top edge of the
		// little rectangle is the intersection line, giving the
		// intersection point of one of its corners

		// this gets difference in radians
		double d = segs[j].getAngle() - xer_angle;
		Console.writeln( "seg = " + segs[j] );
		Console.writeln( " ang = " + segs[j].getAngle()
				 + ", d = " + d );
		if ( Math.abs( d ) < 0.3 ) // roughly 15 deg.
		  continue;

		GPoint x = segs[j].getIntersection( xer );
		if ( ( x != null ) && (( xer.includes( x, slack ) )
					|| segs[j].includes(x,slack) ))
		  {
		    double nd = Geometry.distance( out, x );
		    if ( (best == null) || ( nd < dist ) )
		      {
			best = x;
			dist = nd;
		      }
		    //		    pts.addElement( x );
		    //		    done = true;
		  }
	      }
	    Console.writeln( "making and adding " + best );
	    pts.addElement( best );		
	  }
      }

    return pts;
  }




  /**
   * @return Vector of all points which are members of segments which exit
   *     this polygon or are outside of polygon.
   *     Any segments completely inside polygon are ditched.
   */
  public Vector getRemainder( GPolygon gp, double slack )
  {
    Vector pts = new Vector();
    boolean cross = false;
    GSegment[] segs = gp.getSides();
    int size = m_Points.length;
    int start = -1, stop = -1;

    // find the out -> in crossing point
    // and the in -> out crossing point
    // start = last point before going in
    // stop = last point before going out
    boolean done1 = false, done2 = false;
    for ( int i = 0; ( !done1 || !done2 ) && ( i < size );  i++ )
      {
	boolean in1 = gp.contains(m_Points[i], slack );
	boolean in2 = gp.contains(m_Points[(i+1)%size], slack );
	
	if ( !in1 && in2 )
	  {
	    start = i;
	    done1 = true;
	  }

	if ( in1 && !in2 )
	  {
	    stop = i;
	    done2 = true;
	  }
      }

    for ( int q = 0; q < size; q++ )
      Console.writeln( "---> " + m_Points[q] );
    for ( int q = 0; q < gp.m_Points.length; q++ )
      Console.writeln( "-2-> " + gp.m_Points[q] );


    int enter_x = -1, exit_x = -1;

    // single cutting line -- HACK HACK HACK!
    if ( ( start == -1 ) || ( stop == -1 ) )
      {
	int c;
	for ( c = 0;
	      (enter_x == -1) && (c < size);
	      c++ )
	  {
	    exit_x = enter_x = findCross( segs,
				 m_Points[(c+1) % size],
				 m_Points[c],
				 slack );
	  }

	if ( enter_x == -1 )
	  {
	    Console.writeln( "No line found" );
	    return null;
	  }

	start = stop = c - 1;
      }

    // entire poly inside!
    if ( ( start == -1 ) || ( stop == -1 ) )
      return null;

    Console.writeln( "start = " + start + ", enter_x = " + enter_x );
    // find entering & exiting cross point indices
    enter_x = findCross( segs,
			 m_Points[(start+1)%size],
			 m_Points[start],
			 slack );
    exit_x = findCross( segs,
			m_Points[stop],
			m_Points[(stop+1)%size],
			slack );

    Assert.check( enter_x != -1, "enter_x -1" );
    Assert.check( exit_x != -1, "exit_x -1" );

    // do entering cross
    GPoint x = segs[enter_x].getIntersection( new GSegment( m_Points[start],
					     m_Points[(start+1)%size] ) );
    Console.writeln( " x = " + x );
     x = segs[enter_x].getIntersection( new GSegment( 
					     m_Points[(start+1)%size],
					     m_Points[start] ) );
    pts.addElement( x );
    Console.writeln( "adding -x " + x );

    // do exiting cross
    x = segs[exit_x].getIntersection( new GSegment( m_Points[stop],
			     m_Points[(stop+1)%size] ) );
    Console.writeln( "saving -x " + x );

    // do interior border points
    if ( contains( segs[enter_x].getHeadPoint(), slack ) )
      {
	Console.writeln( "forward march!" );

	Assert.note( !contains( segs[enter_x].getTailPoint(), slack ),
		      "Non-cutting line." );

	//	exit_x = (exit_x + segs.length - 1) % segs.length;
	for ( int i = enter_x;
	      i != exit_x; 
	      i = (i + segs.length - 1)%segs.length )
	  {
	    pts.addElement( segs[i].getHeadPoint() );
	    Console.writeln( "adding #" + i + " " + segs[i].getHeadPoint() );
	  }
      }
    else
      {
	Console.writeln( "backward march!" );

	Assert.note( contains( segs[enter_x].getTailPoint(), slack ),
		      "Non-cutting line (all out)." );

	exit_x = (exit_x + 1) % segs.length;
	for ( int i = (enter_x + 1) % segs.length;
	      i != exit_x;
	      i = (i + 1) % segs.length )
	  {
	    pts.addElement( segs[i].getHeadPoint() );
	    Console.writeln( "adding #" + i + " " + segs[i].getHeadPoint() );
	  }
      }

    Console.writeln( "now adding -x " + x );
    pts.addElement( x );

    
    // now add the original polygon border starting at point just after
    // the first crossing point.
    size = m_Points.length;
    Console.writeln( "start at " + start + ", stop at " + stop );
    start = (start + 1) % size;
    boolean fig = true;
    for ( int i = ( stop + 1 ) % size;
	  fig || (i != start);
	  i = (i + 1) % size )
      {
	fig = false;

	pts.addElement( m_Points[ i ] );
	Console.writeln( "adding " + m_Points[ i ] );
      }

    return pts;
  }


  private int findCross( GSegment[] segs,
			 GPoint in, GPoint out, double slack )
  {
    GSegment xer = new GSegment( out, in );
    double xer_angle = xer.getAngle();
    double dist = 100000; // Double.INFINITY;
    int best = -1;

    for ( int j = 0; j < segs.length; j++ )
      {
	// make sure these are not ||-ish segments
	// this is a hack for dealing with the big rectangle-
	// little rectangle issue where the top edge of the
	// little rectangle is the intersection line, giving the
	// intersection point of one of its corners
	double d = segs[j].getAngle() - xer_angle;
	if ( Math.abs( d ) < 0.3 ) // roughly 15 deg.
	  continue;
	
	GPoint x = segs[j].getIntersection( xer );
	if ( ( x != null ) && (( xer.includes( x, slack ) )
			       && segs[j].includes(x,slack) ))
	  {
	    double nd = Geometry.distance( out, x );
	    if ( (best == -1) || ( nd < dist ) )
	      {
		Console.writeln( "found " + j + " = " + x + " to be good" );
		best = j;
		dist = nd;
	      }
	  }
      }

    //    Assert.check( best != -1, "Did not find crossing line in findCross" );
    Console.writeln( "making and adding " + best );
    return best;
  }


  /**
   * @return Vector of all points which are members of segments which enter
   *     this polygon or are inside of polygon.
   *     Any segments completely outside polygon are ditched.
   */
  public Vector getOverlap( GPolygon gp, double slack )
  {
    Vector pts = new Vector();
    boolean cross = false;
    GSegment[] segs = gp.getSides();

    int size = m_Points.length;
    for ( int i = 0; i < m_Points.length; i++ )
      {
	boolean in1 = gp.contains(m_Points[i], slack );
	boolean in2 = gp.contains(m_Points[(i+1)%size], slack );

	if ( in1 )
	  {
	    Console.writeln( "Adding " + m_Points[i] );
	    pts.addElement( m_Points[i] );
	  }

	// check for crossover
	if ( (in1 && !in2) || (!in1 && in2) )
	  {
	    Console.writeln( "Crossing!" );
	    GSegment xer = new GSegment( m_Points[i],
					 m_Points[(i+1)%size] );
	    double xer_angle = xer.getAngle();
	    GPoint out = null;
	    if ( in1 )
	      out = m_Points[(i+1)%size];
	    else
	      out = m_Points[i];
	    double dist = 100000; // Double.INFINITY;
	    GPoint best = null;

	    // find the closest intersection point to the outside point
	    // and add that to the polygon as a boundary point.
	    boolean done = false;
	    for ( int j = 0; !done && (j < segs.length); j++ )
	      {
		// make sure these are not ||-ish segments
		// this is a hack for dealing with the big rectangle-
		// little rectangle issue where the top edge of the
		// little rectangle is the intersection line, giving the
		// intersection point of one of its corners

		// this gets difference in radians
		double d = segs[j].getAngle() - xer_angle;
		Console.writeln( "seg = " + segs[j] );
		Console.writeln( " ang = " + segs[j].getAngle()
				 + ", d = " + d );
		if ( Math.abs( d ) < 0.3 ) // roughly 15 deg.
		  continue;

		GPoint x = segs[j].getIntersection( xer );
		if ( ( x != null ) && (( xer.includes( x, slack ) )
					|| segs[j].includes(x,slack) ))
		  {
		    double nd = Geometry.distance( out, x );
		    if ( (best == null) || ( nd < dist ) )
		      {
			best = x;
			dist = nd;
		      }
		    //		    pts.addElement( x );
		    //		    done = true;
		  }
	      }
	    Console.writeln( "making and adding " + best );
	    pts.addElement( best );		
	  }
      }

    return pts;
  } // end getOverlap


  /**
   * Return list of points for the overlap, or null if none.
   */
  public boolean overlaps( GPolygon p )
  {
    Rectangle b1 = getBounds(), b2 = p.getBounds();

    // do quick bounds check
    if ( ! b1.intersects( b2 ) )
      return false;

    Vector res = getOverlap( p, 0 );
    if ( res.size() < 3 )
      return false;
    
    return true;
  }

  ///////////////////////////////////////////////////////////////////////////

  private GPoint[] m_Points;
}

////////////////////////////////////////////////////////////////////////////
