//=====================================================================//
// Program by Anna Shleyfman
// CS 8803e -- geomorph 
// Project 1
//=====================================================================//

import java.io.*;
import javax.vecmath.*;

import LineSegment;
import Geomorph;

//======================================================================
//                          Delaunay triangluation
//======================================================================

public class Delaunay 
{

    //======================================================================
    //                         Declarations 
    //======================================================================

    protected int _t[] = null;           // temp array of triangles (corner)
                                         // used in geomorph to build _vindex[]
    protected int num_t = 0;             // current num of tri in _t[]
    private Geomorph geo;

    //======================================================================
    //                         Constructors
    //======================================================================

    public Delaunay( Geomorph g ){
	geo = g;
   }

    //======================================================================
    //                 Delaunay triangluation methods
    //======================================================================
    /**
     * creates vector from 2 (x, y) points
     * @return resulting Vector2d;
     */
    protected Vector2d createVector( Point3d a, Point3d b )
    {
	Vector2d ab = new Vector2d( b.x - a.x, b.y - a.y );
	return ab;
    }

    //======================================================================

    /**
     * @return vector, perpendicular to the passed in vector v
     */
    protected Vector2d getNormal( Vector2d v )
    {
	return (new Vector2d( -v.y, v.x ));
    }

    //======================================================================

    /**
     * returns 0 if point with coordinates p is not found inside triangle abc
     * returns 1 if point was found inside of triangle,
     * returns 2 if point is on the edge of triangle,
      */
    private int isInside( Point3d a, Point3d b, Point3d c, Point3d p )
    {
	double d1, d2, d3;  //results of dot product

	Vector2d abn = getNormal( createVector( a, b ) );
	Vector2d bcn = getNormal( createVector( b, c ) );
	Vector2d can = getNormal( createVector( c, a ) );

	d1 = abn.dot( createVector( p, a ) );
	d2 = bcn.dot( createVector( p, b ) );
	d3 = can.dot( createVector( p, c ) );

     	//inside
	if( (d1>0 && d2>0 && d3>0) || (d1<0 && d2<0 && d3<0) ){
	    return 1;
	}       

	// on the border
	if( d1==0 && ((d2>=0 && d3>=0) || (d2<=0 && d3<=0)) )
	    return 21;        // incident on ab

	if( d2==0 && ((d1>=0 && d3>=0) || (d1<=0 && d3<=0)) )
	    return 22;        // incident on bc

	if( d3==0 && ((d1>=0 && d2>=0) || (d1<=0 && d2<=0)) ) 
	    return 23;        // incident on ca

	// outside of triangle
	return 0;
		
    }// isInside

    //======================================================================

    /**
     * Writes the id's of the the vertices into the _t[] 
     * in the tri_num position
     */
    private void insert_tri( int tri_num, int v1_id, int v2_id, int v3_id )
    {
	int c = (tri_num - 1) * 3;       //find corner position

	_t[ c ] = v1_id;
	_t[ c+1 ] = v2_id;
	_t[ c+2 ] = v3_id;

    }//insert_tri

    //======================================================================

    /**
     * Given the triange and the edge, finds the opposite vertex of the 
     * adjacent triangle and returns array containing vertex id and 
     * triangle id.
     */
    private int[] findAdjacentVtx( int a_id, int b_id, int tri_num )
    {
	int v, x, y, z;  // temp looping variables

	for( int t=0; t<num_t; t++){
	    if( t != tri_num - 1 ){
		v = t*3;                  // find the beginning of triangle
		x= _t[ v ];               // get vertices' ids of tri to split
		y= _t[ v+1 ];             
		z= _t[ v+2 ];	    

		if( ((x == a_id) && (y == b_id)) ||
		    ((y == a_id) && (x == b_id)) ){
		    return (new int[] {z, t+1} );  //return vtx and tri ids
		}
		if( ((y == a_id) && (z == b_id)) ||
		    ((z == a_id) && (y == b_id)) ){
		    return (new int[] {x, t+1} );  //return vtx and tri ids
		}
		if( ((x == a_id) && (z == b_id)) ||
		    ((z == a_id) && (x == b_id)) ){
		    return (new int[] {y, t+1} );  //return vtx and tri ids
		}
	    }//if not triangle found
	}// for

	// border edge -- no adjacent triangle
	return (new int[] {-4, -4});   // error -- shouldn't happen
    }//findAdjacentVtx

    //======================================================================

    /**
     * returns the center of circle formed by points p1, p2, and p3
     */
    private Point3d findCenterCircle( Point3d p13, Point3d p23, Point3d p33)
    {
	Point2d p1 = new Point2d( p13.x, p13.y );
	Point2d p2 = new Point2d( p23.x, p23.y );
	Point2d p3 = new Point2d( p33.x, p33.y );

	LineSegment N1, N2;                    //normals to p1 p2, and p2, p3
	LineSegment l1 = new LineSegment();
	l1.initSegment( p1, p2 ); 

	LineSegment l2 = new LineSegment();
	l2.initSegment( p2, p3 ); 

	N1 = l1.buildPerpThruCentr();
	N2 = l2.buildPerpThruCentr();

	Point2d o = N1.findIntersection( N2 ); //point of normals' intersection
	return (new Point3d( o.x, o.y, 0 ));

    }//findCenterCircle

    //======================================================================

    /** 
     * checks if edge is legal: returns true if yes, false if now
     */
    private boolean isLegal( int a, int b, int p, int d)
    {
	Point3d A, B, P, D;
	A = geo.g_vert(a);
	B = geo.g_vert(b);
	P = geo.g_vert(p);
	D = geo.g_vert(d);

	// regular case: a>=0 && b>=0 && d>=0
	Point3d o = findCenterCircle( A, B, P );
	double radius = A.distance( o );
	if( radius < B.distance( o ) )  // don't want to loose precision 
	    radius = B.distance( o );   //of last three digits
	if( radius < P.distance( o ) )  // don't want to loose precision 
	    radius = P.distance( o );   //of last three digits

	if( o.distance( D ) < radius ){  //edge is illegal
	    return false;
	}

	return true;                     // d is outside the circle
	
    }// isLegal

    //======================================================================

    /**
     * ab is the edge that needs to be checked for being legal
     * if the edge isn't legal, legalizeEdge flips it in _t[]
     */
    private void legalizeEdge( int inserted, int a, int b, int tri_num )
    {
	//vertex id and triangle id.
	int d[] = findAdjacentVtx( a, b, tri_num );

	if( d[0] == -4 ){
	    return;
	}

	boolean test = isLegal( a, b, inserted, d[0] );
       //System.out.println( "test: " + a + " " +b+" "+ inserted + "=" +test );

	//flip
	if( false == test ){
	    insert_tri( tri_num, inserted, a, d[0] );
	    insert_tri( d[1], inserted, d[0], b );
	    legalizeEdge( inserted, a, d[0], tri_num );
	    legalizeEdge( inserted, d[0], b, d[1]);
	}
	return;
    }// legalizeEdge

    //======================================================================

    /**
     * finds the correct triangle in _t[] and inserts the point into it
     * assume that the triangles in the _t should contain the point --
     * don't check for error
     */
    private void findTri( int point_id )
    {
	Point3d pos = geo.g_vert( point_id ); //store point coordinates
	int v=0;                          // temp vertex # 
	int a, b, c;                      // vertices of triangle to split
	int result = 0;                   // temp var to store isInside result
	int d[] = null;                   // stores [vertex id, triangle id]

	for( int i=0; i<num_t; i++ ){     // "i" is the temp triangle number
	    v = i*3;                      // find the beginning of triangle
	    a= _t[ v ];                   // get vertices' ids of tri to split
	    b= _t[ v+1 ];             
	    c= _t[ v+2 ];

	    //test if the current triangle is the one to split
	    result = isInside( geo.g_vert(a), geo.g_vert(b), 
			       geo.g_vert(c), pos ); 

	    switch( result ){
	    case 1:                        // insert point inside of triangle
		insert_tri( i+1, a, b, point_id );
		insert_tri( ++num_t, b, c, point_id );
		insert_tri( ++num_t, c, a, point_id );

		legalizeEdge( point_id, a, b, i+1 );
		legalizeEdge( point_id, b, c, num_t-1 );
		legalizeEdge( point_id, c, a, num_t );
		return;
	    case 21:                       // insert on the triangle edge ab
		insert_tri( i+1, c, a, point_id );
		insert_tri( ++num_t, c, point_id, b );
		System.out.println("Splitting on Edge ");

		legalizeEdge( point_id, b, c, num_t-1 );
		legalizeEdge( point_id, c, a, i+1 );

		// find adjacent triangle and split it in two
		d = findAdjacentVtx( a, b, i+1 ); // get v and t ids
		if( d[0] != -4 ){
		    insert_tri( d[1], a, d[0], point_id );
		    insert_tri( ++num_t, d[0], b, point_id );
		    System.out.println("Splitting on Edge opposite");

		    legalizeEdge( point_id, a, d[0], d[1] );
		    legalizeEdge( point_id, d[0], b, num_t );
		}
		return;
	    case 22:                       // insert on the triangle edge bc
		insert_tri( i+1, a, b, point_id );
		insert_tri( ++num_t, a, point_id, c );
		System.out.println("Splitting on Edge");

		legalizeEdge( point_id, c, a, num_t-1 );
		legalizeEdge( point_id, a, b, i+1 );

		// find adjacent triangle and split it in two
		d = findAdjacentVtx( b, c, i+1 ); // get v and t ids
		if( d[0] != -4 ){
		    insert_tri( d[1], point_id, b, d[0] );
		    insert_tri( ++num_t, c, point_id, d[0] );
		    System.out.println("Splitting on Edge opposite");
		    
		    legalizeEdge( point_id, b, d[0], d[1] );
		    legalizeEdge( point_id, d[0], c, num_t );
		}
		return;
	    case 23:                       // insert on the triangle edge ca
		insert_tri( i+1, b, point_id, a );
		insert_tri( ++num_t, b, c, point_id );
		System.out.println("Splitting on Edge");

		legalizeEdge( point_id, a, b, i+1 );
		legalizeEdge( point_id, b, c, num_t-1 );

		// find adjacent triangle and split it in two
		d = findAdjacentVtx( c, a, i+1 ); // get v and t ids
		if( d[0] != -4 ){
		    insert_tri( d[1], d[0], a, point_id );
		    insert_tri( ++num_t, c, d[0], point_id );
		    System.out.println("Splitting on Edge opposite");		    
		    legalizeEdge( point_id, c, d[0], num_t );
		    legalizeEdge( point_id, d[0], a, d[1] );
		}
		return;
	    default:                       // continue to loop
		break;
	    }// if edge
	}//for
	System.out.println( "Error: this point is outside of the "+
			    "bounding triangle." );

    }// findTri

    //======================================================================

    /**
     * prints out _t[] for testing purposes
     */
    public void print_t()
    {
	System.out.println( "num_t: " + num_t + "printing _t: ");
	for( int i=0; i<num_t*3; i++)
	    System.out.println( _t[i] );
    }

    //======================================================================
    /**
     * Given the triange and the edge, finds the opposite corner of the 
     * adjacent triangle and returns array containing vertex id and 
     * triangle id.
     */
    private int findOpposite( int a_id, int b_id, int tri_num )
    {
	int v, x, y, z;  // temp looping variables

	for( int t=0; t<geo.num_t; t++){
	    if( t != tri_num - 1 ){
		v = t*3;                  // find the beginning of triangle
		x= geo._vindex[ v ];      // get vertices' ids of tri to split
		y= geo._vindex[ v+1 ];             
		z= geo._vindex[ v+2 ];	    

		if( ((x == a_id) && (y == b_id)) ||
		    ((y == a_id) && (x == b_id)) ){
		    return v+2;                        //return corner
		}
		if( ((y == a_id) && (z == b_id)) ||
		    ((z == a_id) && (y == b_id)) ){
		    return v;                          //return corner
		}
		if( ((x == a_id) && (z == b_id)) ||
		    ((z == a_id) && (x == b_id)) ){
		    return v+1;                       //return corner
		}
	    }//if not triangle found
	}// for

	return -7;     	// border edge -- no adjacent triangle found
    }//findAdjacentVtx

    //======================================================================

    /**
     * If the opposited corner of corner v is found it is set in _o[].
     * @param v      -- corner number
     * @param v1, v2 -- vertex_ids of the other corners in triangle
     * @param tnum   -- triangle number
     */
    private void set_o_corner( int v, int v1, int v2, int tnum )
    {
	int ov; // opposite corner

	if( geo._o[ v ] == -1 ){  // check that _o of this corner isn't set
	    ov = findOpposite( v1, v2, tnum );

	    if( ov != -7 ){
		geo._o[ v ] = ov;
		geo._o[ ov ] = v;
	    }
	}//if _o[v] isn't set

    }// set opposite corner

    //======================================================================
    /**
    *    Create opposite table _o
    **/    
    private void set_opposite()
    {
	int ov, ov1, ov2; // opposite
	int v0, v1, v2;   // corner id

	// allocate space for _vindex table
	geo._o = new int[ geo._vindex.length ];  

	for( int i=0; i<geo._o.length; i++ ){  //initialize
	    geo._o[i] = -1; 
	}//for

	for( int t=0; t < geo.num_t; t++ ){  //initialize
	    int v = t*3;
	    v0 = geo._vindex[ v ];      // get vertices' ids of tri to split
	    v1 = geo._vindex[ v+1 ];             
	    v2 = geo._vindex[ v+2 ];

	    set_o_corner( v, v1, v2, t+1 );   //set _o[v]
	    set_o_corner( v+1, v2, v0, t+1 ); //set _o[v+1]
	    set_o_corner( v+2, v0, v1, t+1 ); //set _o[v+2]
	}//for

    }// set_opposite

    //======================================================================

    /**
     * Counts all of the triangles in _t that contain nonnegtive edges
     */
    private int compute_numtri_of_vidnex()
    {
	int v, x, y, z;  // temp looping variables
	int num_tri = 0;

	for( int t=0; t<num_t; t++){
	    v = t*3;                   // find the beginning of triangle
	    x= _t[ v ];                // get ids of vertices
	    y= _t[ v+1 ];             
	    z= _t[ v+2 ];	    

	    if( ((x > -1) && (y > -1)) && (z > -1) ){
		num_tri++;
	    }
	}//for

	return num_tri;
    }//compute_numtri_of_vidnex()
    
    //======================================================================
    /**
     * discard all triangles with negative edges
     * set _vindex table
     */
    private void set_vindex()
    {
	int v, v2, x, y, z;  // temp looping variables

	geo.num_t = compute_numtri_of_vidnex();
	int remtri=0;

	// allocate space for _vindex table
	geo._vindex = new int[ 3 * geo.num_t ];  

	for( int t=0, t2=0; t < num_t; t++){
	    v = t*3;                  // find the beginning of triangle
	    x = _t[ v ];              // get vertices' ids 
	    y = _t[ v+1 ];             
	    z = _t[ v+2 ];	    

	    if( ((x > -1) && (y > -1)) && (z > -1) ){
		v2 = 3 * t2++;
		geo._vindex[ v2 ] = x;
		geo._vindex[ v2+1 ] = y;
		geo._vindex[ v2+2 ] = z;
	    }//if
	    else{
		remtri++;
	    }
	}//for	    

	//System.out.println( "remtri = " + remtri ); //debug
    }//set_videx

    //======================================================================

    /**
     * Creates delaunay triangle mesh using the _vertices table
     * Sets _vertices and _o tables
     */
    public void delaunay()
    {	
	_t = new int [ 10 * geo.num_vert ];  // temp array of triangles
	num_t = 1;                           // current num of tri in _t 

	// init first triangle
	insert_tri( num_t, -1, -2, -3 );

	// find triangle that contains the vertex, and insert vertex into it
	for( int i=0; i < geo.num_vert; i++ ){
	    findTri( i );
	}

	// discard all triangles with negative edges
	// set _vindex table
	set_vindex();
	set_opposite();

    }//delaunay

}// end of class Delaunay

//======================================================================
//                           End of Class Delaunay
//======================================================================