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

////////////////////////////////////////////////////////////////////////////////
//
// FILE:	GPolySegment.java
//
// AUTHOR:	Manoj D. Muzumdar
//		archon@ai.mit.edu
//
// DATE:	06-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.util.*;
import java.awt.*;
import rec.util.*;
import rec.meche.Estimator;

/**
 * A GPolySegment is an immutable representation of a multi-point
 *     segment.
 */
public class GPolySegment extends GShape
{
  public GPolySegment( GSegment gs )
  {
    m_Vector = new Vector();
    m_Vector.addElement( new GPoint( gs.getHeadPoint() ) );
    m_Vector.addElement( new GPoint( gs.getTailPoint() ) );
  }

  public GPolySegment( GPolySegment gps )
  {
    this( gps.m_Vector );
  }

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

  public GPolySegment( Vector v )
  {
    Assert.check( v.size() > 1,
		  "a poly segment must have at least two points" );

    Iterator e = v.iterator();

    m_Vector = new Vector();

    while( e.hasNext() ) {
      m_Vector.addElement( new GPoint( (GPoint)e.next() ) );
    }
  }

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

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

  /** Reverse the order of the elements in the vector. **/
  public void reverse()
  {
    int n = m_Vector.size();
    Vector v = new Vector( n, 10 );
    
    for( int i = n-1; i >= 0; i-- ) {
      v.add( m_Vector.get( i ) );
    }
    m_Vector = v;
  }

  public void reflect()
  {
    for( int i = 0; i < m_Vector.size(); ++i )
      ((GPoint)m_Vector.elementAt( i )).reflect();
  }

  public void translate( double dx, double dy )
  {
    for( int i = 0; i < m_Vector.size(); ++i )
      ((GPoint)m_Vector.elementAt( i )).translate( dx, dy );
  }

  public void rotate( GPoint gp, double radians )
  {
    for( int i = 0; i < m_Vector.size(); ++i )
      ((GPoint)m_Vector.elementAt( i )).rotate( gp, radians );
  }

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

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

    for( int i = 0; i < m_Vector.size() - 1; ++i )
      total += Geometry.distance( (GPoint)m_Vector.elementAt( i ),
				  (GPoint)m_Vector.elementAt( i + 1 ) );

    return( total / (double)(m_Vector.size() - 1) );
  }

  public void resize( double scaleFactor )
  {
    // archon: Does nothing right now!
  }

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

  public Rectangle getBounds()
  {
    Point min = getHeadPoint().getPoint();
    Point max = getHeadPoint().getPoint();

    for( int i = 0; i < getNumberOfPoints(); ++i ) {

      int x = getPointAt( i ).getIntX();
      int y = getPointAt( i ).getIntY();

      // x
      min.x = Math.min( x, min.x );
      max.x = Math.max( x, max.x );

      // y
      min.y = Math.min( y, min.y );
      max.y = Math.max( y, max.y );
    }

    return( new Rectangle( min.x - 1,
			   min.y - 1,
			   max.x - min.x + 2,
			   max.y - min.y + 2 ) );
  }

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

  public void display( Graphics g )
  {
    Iterator e = m_Vector.iterator();

    GPoint prev = (GPoint)e.next();

    while( e.hasNext() ) {
      GPoint curr = (GPoint)e.next();
      g.drawLine( prev.getIntX(), prev.getIntY(),
		  curr.getIntX(), curr.getIntY() );
      prev = curr;
    }
  }

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

  /**
   * @param gp  The point to be contained in the polysegment.
   */
  public boolean includes( GPoint gp )
  {
    Iterator e = m_Vector.iterator();

    GPoint prev = (GPoint)e.next();

    while( e.hasNext() ) {
      GPoint curr = (GPoint)e.next();
      if( (new GSegment( prev, curr )).includes( gp ) )
	return( true );
      prev = curr;
    }

    return( false );
  }

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

    Iterator e = m_Vector.iterator();

    GPoint prev = (GPoint)e.next();

    while( e.hasNext() ) {
      GPoint curr = (GPoint)e.next();
      if( (new GSegment( prev, curr )).includes( gp, offset ) )
	return( true );
      prev = curr;
    }

    return( false );
  }

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

  public void addSegment( GSegment gs )
  {
    // We want to keep all head endpoints pointing towards the head
    //     of the polysegment.

    if( gs.getHeadPoint().equals( getHeadPoint() ) )
      addPointToHead( gs.getTailPoint() );

    if( gs.getHeadPoint().equals( getTailPoint() ) )
      addPointToTail( gs.getTailPoint() );

    if( gs.getTailPoint().equals( getHeadPoint() ) )
      addPointToHead( gs.getHeadPoint() );

    if( gs.getTailPoint().equals( getTailPoint() ) )
      addPointToTail( gs.getHeadPoint() );

    Assert.error( "segment does not connect to the polysegment" );
  }

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

  public void addPointToHead( GPoint gp )
  {
    addPointBefore( 0, gp );
  }

  public void addPointToTail( GPoint gp )
  {
    addPointAfter( m_Vector.size() - 1, gp );
  }

  public void removeHeadPoint()
  {
    removePointAt( 0 );
  }

  public void removeTailPoint()
  {
    removePointAt( m_Vector.size() - 1 );
  }

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

  public void addPointBefore( int index, GPoint gp )
  {
    validateIndex( index );

    m_Vector.insertElementAt( gp, index );
  }

  public void addPointAfter( int index, GPoint gp )
  {
    validateIndex( index );

    if( index == m_Vector.size() - 1 ) {
      m_Vector.addElement( gp );
      return;
    }

    m_Vector.insertElementAt( gp, index + 1 );
  }

  public void removePointAt( int index )
  {
    validateRemove( index );

    m_Vector.removeElementAt( index );
  }

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

  public int getNumberOfPoints()
  {
    return( m_Vector.size() );
  }

  /**
   * @return the n'th point from the head of the polysegment.
   * i.e. getPointFromHead( 0 ) returns the head point.
   **/
  public GPoint getPointFromHead( int n ) 
  {
    return getPointAt( n );
  }

  /**
   * @return the n'th point from the tail of the polysegment.
   * i.e. getPointFromTail( 0 ) returns the tail point.
   **/
  public GPoint getPointFromTail( int n ) 
  {
    return getPointAt( m_Vector.size() - n - 1 );
  }


  public GPoint getPointAt( int index )
  {
    validateIndex( index );

    return( (GPoint)m_Vector.elementAt( index ) );
  }

  public GPoint getHeadPoint()
  {
    return( getPointAt( 0 ) );
  }

  public GPoint getTailPoint()
  {
    return( getPointAt( m_Vector.size() - 1 ) );
  }

  public GPolySegment getHeadSub( int last )
  {
    return( getMiddleSub( 0, last ) );
  }

  public GPolySegment getTailSub( int first )
  {
    return( getMiddleSub( first, m_Vector.size() - 1 ) );
  }

  public GPolySegment getMiddleSub( int first, int last )
  {
    validateIndex( first );
    validateIndex( last );

    Assert.check( first <= last,
      "first point index is greater than last point index" );

    Vector tmp = new Vector();

    int i = 0;
    for( i = first; i < last + 1; ++i )
      tmp.addElement( m_Vector.elementAt( i ) );

    return( new GPolySegment( tmp ) );
  }

  private GSegment getSegment( int n ) 
  {
    Assert.check( n < m_Vector.size() - 1,
		  "There are not that many segments" );

    return new GSegment( getPointAt( n ), getPointAt( n+1 ) );
  }
  

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

  public double getLength()
  {
    double ret = 0.0;

    Iterator e = m_Vector.iterator();

    GPoint prev = (GPoint)e.next();

    while( e.hasNext() ) {
      GPoint curr = (GPoint)e.next();
      ret += (new GSegment( prev, curr )).getLength();
      prev = curr;
    }

    return( ret );
  }

  /**
   * @param gp  The point to be contained in the polysegment.
   *
   * @return  The segment that contains gp;
   *     null is there is no segment that contains gp.
   */
  public GSegment getSegmentContaining( GPoint gp )
  {
    Iterator e = m_Vector.iterator();

    GPoint prev = (GPoint)e.next();

    while( e.hasNext() ) {
      GPoint curr = (GPoint)e.next();
      GSegment gs = new GSegment( prev, curr );
      if( gs.includes( gp ) )
	return( gs );
      prev = curr;
    }

    return( null );
  }


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

    Iterator e = m_Vector.iterator();

    GPoint prev = (GPoint)e.next();

    while( e.hasNext() ) {
      GPoint curr = (GPoint)e.next();
      GSegment gs = new GSegment( prev, curr );
      if( gs.includes( gp, offset ) )
	return( gs );
      prev = curr;
    }

    return( null );
  }

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

  private void validateRemove( int index )
  {
    validateIndex( index );

    Assert.check( getNumberOfPoints() != 2,
		  "polysegment only has two points" );
  }

  private void validateIndex( int index )
  {
    Assert.check( index >= 0 && index < m_Vector.size(),
		  "index out of bounds" );
  }

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

  /**
   * @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 = (GPoint) m_Vector.lastElement();
    boolean up = cur.y > p.y;
    boolean offsides = cur.x < p.x;
    boolean curoff;

    int cross = 0;

    int s = m_Vector.size();
    for( int i = 0; i < s; i++ ) {

      cur = (GPoint)m_Vector.elementAt( i );

      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,
			     (GPoint)m_Vector.elementAt((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,
			     (GPoint)m_Vector.elementAt((i-1+s)%s) );

	  up = true;
	}
      }

      offsides = curoff;
    }

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

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

  public boolean intersects( Rectangle bounds ) 
  {
    for( int i = 0; i < m_Vector.size() - 1; i++ ) {
      if( Geometry.intersects( getSegment( i ), bounds ) )
	return true;
    }
    return false;
  }

  public boolean isNear( GShape shape, double tolerance )
  {
    for( int i = 0; i < m_Vector.size() - 1; i++ ) {
      if( Estimator.isNear( shape, getSegment( i ), tolerance ) ) {
	return true;
      }
    }
    return false;
  }
  

  /**
   * 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;
  }

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

  private Vector m_Vector;
}

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