/*-------------------------------------------------------------------*/
/*  BruteForceEarCut.java                                            */
/*      This file contains the class needed for the implementation   */
/*      of ear cutting for a simple polygon.                         */
/*                                                                   */
/*- Modification History---------------------------------------------*/
/*  When:       Who:          Comments:                              */
/*                                                                   */
/*  97.12.09    Ian Garton    Final Implementation                   */
/*-------------------------------------------------------------------*/


import java.awt.*;
import java.applet.Applet;


public class BruteForceEarCut extends Applet
implements CanvasController
{
    private PolygonCanvas canvas;

    private static boolean runsInBrowser = true;
    private Button quitButton, clearButton, cutEarButton;

    private int npoints;
    private int earCounter;
    private int concaveCount;
    private double xpoints[], ypoints[];
    private double xpointsTemp[], ypointsTemp[];
    private int ptType[];
    private Polygon transformedPoly;
    private Polygon earPoly[];

    
    public void init()
    {
	setLayout(new BorderLayout());

	canvas = new PolygonCanvas();
	canvas.setFinishNotify(this);
	add("Center", canvas);	

	Panel p = new Panel();

	if (!runsInBrowser)
	    p.add(quitButton = new Button("Quit"));

	p.add(clearButton = new Button("Clear"));
	p.add(cutEarButton = new Button("Cut an Ear!"));
	cutEarButton.disable();
	
	add("South", p);

	resize (400,400);
        validate();
    }


    /*
     * main:  This is to run outside of Netscape, using AppletFrame.
     */
    public static void main (String args[])
    {
	runsInBrowser = false;
	AppletFrame.startApplet("BruteForceEarCut",
				"Brute Force Ear Cutting",
				args);
    }


    /* finishNotify:  When user enters final point, variables are
     *                initialized and the Cut Ear button is made
     *                active.
     */
    public void finishNotify(Canvas c)
    {
	PolygonCanvas pc = (PolygonCanvas)c;
	npoints = pc.inputPolygon.npoints;
	earCounter = 0;
	xpoints = new double[npoints];
	ypoints = new double[npoints];
	earPoly = new Polygon[npoints-2];
	for (int i = 0; i < npoints - 2; i++)
	    earPoly[i] = new Polygon();
	
	for (int i = 0; i < npoints; i++)
	{
	    xpoints[i] = pc.inputPolygon.xpoints[i];
	    ypoints[i] = pc.inputPolygon.ypoints[i];
	}
	for (int i = 0; i < npoints-2; i++)
	    earPoly[i] = null;
	transformedPoly = null;
	if (npoints > 4) 
	    cutEarButton.enable();
    }


    /* action:  Performs actions according to button user activates.
     */	
    public boolean action(Event e, Object arg)
    {
	if (e.target == quitButton) {
	    System.exit (0);
	} else if (e.target == clearButton) {
	    cutEarButton.disable();
	    for (int i = 0; i < npoints - 2; i++)
	        earPoly[i] = null;
	    transformedPoly = null;
	    earCounter = 0;
	    canvas.reset();
	} else if (e.target == cutEarButton) {
	    if (npoints > 3) {
	        classifyPoints();
	        doCutEar();
	        canvas.repaint();
	    }
	    if (npoints <= 3) {
		cutEarButton.disable();
	    }
	} else
	    return false;
	return true;
    }


    /* paint:  Displays modified polygon
     */
    public void paint(Canvas caller, Graphics g)
    {
	if (transformedPoly == null) return;

	for (int i = 0; i < earCounter; i++) {
	    g.setColor(Color.yellow);
	    g.fillPolygon(earPoly[i]);
	    g.setColor(Color.pink);
	    g.drawPolygon(earPoly[i]);
	}

	if (npoints > 3) {
	    g.setColor(Color.black);
	    g.drawPolygon(transformedPoly);
        }
    }


    /* polygonClockwise:  Returns true if user inputted polygon in 
     *                    clockwise order, false if counterclockwise.  
     *                    The Law of Cosines is used to determine the
     *                    angle.
     */
    boolean polygonClockwise()
    {
	double aa, bb, cc, b, c, theta;
	double convex_turn;
	double convex_sum = 0;

	for (int i = 0; i < npoints - 2; i++) {
	    aa = ((xpoints[i+2] - xpoints[i]) * (xpoints[i+2] - xpoints[i])) +
	         ((-ypoints[i+2] + ypoints[i]) * (-ypoints[i+2] + ypoints[i]));
	    
	    bb = ((xpoints[i+1] - xpoints[i]) * (xpoints[i+1] - xpoints[i])) +
	         ((-ypoints[i+1] + ypoints[i]) * (-ypoints[i+1] + ypoints[i]));
	    
	    cc = ((xpoints[i+2] - xpoints[i+1]) * 
		  (xpoints[i+2] - xpoints[i+1])) +
		 ((-ypoints[i+2] + ypoints[i+1]) *
		  (-ypoints[i+2] + ypoints[i+1]));
	
	    b = Math.sqrt(bb);
	    c = Math.sqrt(cc);
	    theta = Math.acos((bb + cc - aa) / (2 * b * c));

	    if (convex(xpoints[i], ypoints[i],
                       xpoints[i+1], ypoints[i+1],
                       xpoints[i+2], ypoints[i+2])) {
		convex_turn = Math.PI - theta;
		convex_sum += convex_turn;
	    }
	    else {
		convex_sum -= Math.PI - theta;
	    }
	}
	aa = ((xpoints[1] - xpoints[npoints-2]) * 
	      (xpoints[1] - xpoints[npoints-2])) +
	     ((-ypoints[1] + ypoints[npoints-2]) * 
	      (-ypoints[1] + ypoints[npoints-2]));
	    
	bb = ((xpoints[0] - xpoints[npoints-2]) * 
	      (xpoints[0] - xpoints[npoints-2])) +
	     ((-ypoints[0] + ypoints[npoints-2]) * 
	      (-ypoints[0] + ypoints[npoints-2]));
	    
	cc = ((xpoints[1] - xpoints[0]) * (xpoints[1] - xpoints[0])) +
	     ((-ypoints[1] + ypoints[0]) * (-ypoints[1] + ypoints[0]));
	
	b = Math.sqrt(bb);
	c = Math.sqrt(cc);
	theta = Math.acos((bb + cc - aa) / (2 * b * c));
	
	if (convex(xpoints[npoints-2], ypoints[npoints-2],
                   xpoints[0], ypoints[0],
                   xpoints[1], ypoints[1])) {
	    convex_turn = Math.PI - theta;
	    convex_sum += convex_turn;
	}
	else { 
	    convex_sum -= Math.PI - theta;
	}

	if (convex_sum >= (2 * 3.14159))
	    return true;
	else
	    return false;
    }


    /* classifyPoints:  Classifies points as "convex" or "concave".  
     *                  Convex points are represented as a "1" in the
     *                  ptType array; concave points are represented as a
     *                  "-1" in the array.
     */
    void classifyPoints()
    {
	ptType = new int[npoints];
	xpointsTemp = new double[npoints];
	ypointsTemp = new double[npoints];
	concaveCount = 0;


	/* Before cutting any ears, we must determine if the polygon was
         * inputted in clockwise order or not, since the algorithm for
         * cutting ears assumes that the polygon's points are in clockwise
         * order.  If the points are in counterclockwise order, they are
         * simply reversed in the array.
         */
	if (earCounter == 0) {
	    if (!polygonClockwise()) {
	        for (int i = 0; i < npoints; i++) {
		    xpointsTemp[i] = xpoints[npoints-1 - i];
		    ypointsTemp[i] = ypoints[npoints-1 - i];
	        }
	        for (int i = 0; i < npoints - 1; i++) {
		    xpoints[i] = xpointsTemp[i];
		    ypoints[i] = ypointsTemp[i];
		}
	    }
	}

        for (int i = 0; i < npoints - 1; i++) {
	    if (i == 0) {
		if (convex(xpoints[npoints-2], ypoints[npoints-2],
                           xpoints[i], ypoints[i],
                           xpoints[i+1], ypoints[i+1])) {
		    ptType[i] = 1;	/* point is convex */
		}
		else {
		    ptType[i] = -1;	/* point is concave */
		    concaveCount++;
	        }
	    }
	    else {    /* i > 0 */
		if (convex(xpoints[i-1], ypoints[i-1],
                           xpoints[i], ypoints[i],
                           xpoints[i+1], ypoints[i+1])) {
		    ptType[i] = 1;	/* point is convex */
                }
		else {
		    ptType[i] = -1;	/* point is concave */		    
		    concaveCount++;
		}
	    }
	}
    }


    /* convex:  returns true if point (x2, y2) is convex
     */
    boolean convex(double x1, double y1, double x2, double y2, 
		   double x3, double y3)
    {
	if (area(x1, y1, x2, y2, x3, y3) < 0)
	    return true;
	else
	    return false;
    }


    /* area:  determines area of triangle formed by three points
     */
    double area(double x1, double y1, double x2, double y2,
		double x3, double y3)
    {
	double areaSum = 0;

	areaSum += x1 * (y3 - y2);
	areaSum += x2 * (y1 - y3);
	areaSum += x3 * (y2 - y1);

	/* for actual area, we need to multiple areaSum * 0.5, but we are
         * only interested in the sign of the area (+/-)
         */

	return areaSum;
    }


    /* triangleContainsPoints:  returns true if the triangle formed by
     *                          three points contains another point
     */
    boolean triangleContainsPoint(double x1, double y1, double x2,
				  double y2, double x3, double y3)
    {
	int i = 0;
	double area1, area2, area3;
	boolean noPointInTriangle = true;

	while ((i < npoints - 1) && (noPointInTriangle)) {
	    if ((ptType[i] == -1)   /* point is concave */  &&
                (((xpoints[i] != x1) && (ypoints[i] != y1)) ||
		 ((xpoints[i] != x2) && (ypoints[i] != y2)) ||
		 ((xpoints[i] != x3) && (ypoints[i] != y3)))) {

		area1 = area(x1, y1, x2, y2, xpoints[i], ypoints[i]);
		area2 = area(x2, y2, x3, y3, xpoints[i], ypoints[i]);
		area3 = area(x3, y3, x1, y1, xpoints[i], ypoints[i]);

		if (area1 > 0)
		    if ((area2 > 0) && (area3 > 0))
			noPointInTriangle = false;
		if (area1 < 0)
		    if ((area2 < 0) && (area3 < 0))
			noPointInTriangle = false;
	    }
	    i++;
	}
	return !noPointInTriangle;
    }


    /* ear:  returns true if the point (x2, y2) is an ear, false
     *       otherwise
     */
    boolean ear(double x1, double y1, double x2, double y2, 
                double x3, double y3)
    {
	if (concaveCount != 0)
	    if (triangleContainsPoint(x1, y1, x2, y2, x3, y3))
		return false;
	    else 
		return true;
	else
	    return true;
    }


    /* cutEar:  creates triangle that represents ear for graphics purposes
     */
    void cutEar(int index)
    {
	Polygon p = new Polygon();
	int new_i = 0;
	int i = 0;

	double ex[], ey[];
	ex = new double[4];
	ey = new double[4];

	if (index == 0) {
	    ex[0] = xpoints[npoints-2];
	    ey[0] = ypoints[npoints-2];
	    ex[1] = xpoints[index];
	    ey[1] = ypoints[index];
	    ex[2] = xpoints[index+1];
	    ey[2] = ypoints[index+1];
	}
	else if ((index > 0) && (index < npoints-2)) {
	    ex[0] = xpoints[index-1];
	    ey[0] = ypoints[index-1];
	    ex[1] = xpoints[index];
	    ey[1] = ypoints[index];
	    ex[2] = xpoints[index+1];
	    ey[2] = ypoints[index+1];
	}
	else if (index == npoints-2) {
	    ex[0] = xpoints[index-1];
	    ey[0] = ypoints[index-1];
	    ex[1] = xpoints[index];
	    ey[1] = ypoints[index];
	    ex[2] = xpoints[0];
	    ey[2] = ypoints[0];
	}
	for (i = 0; i < 3; ++i)
	    p.addPoint((int) ex[i], (int) ey[i]);
	ex[3] = ex[0];
	ey[3] = ey[0];
	p.addPoint((int) ex[0], (int) ey[0]);
	earPoly[earCounter] = p;
	earCounter++;
    }


    /* updatePolygon:  creates new polygon without the ear that was
     *                 cut
     */
    void updatePolygon(int index)
    {
	Polygon p = new Polygon();
	int new_i = 0;
	int i = 0;

	if (index == 0)
	    i++;
	while (i < npoints - 1) {
	    if (i == index)
		i++;
	    if (i < npoints - 1) {
		xpoints[new_i] = xpoints[i];
		ypoints[new_i] = ypoints[i];
		p.addPoint((int) xpoints[new_i], (int) ypoints[new_i]);
		new_i++;
		i++;
	    }
	}
	xpoints[npoints-2] = xpoints[0];
	ypoints[npoints-2] = ypoints[0];
	p.addPoint((int) xpoints[0], (int) ypoints[0]);
	npoints--;
	transformedPoly = p;
    }


    /* doCutEar:  Performs all the functions needed to find and cut an
     *            ear.
     */
    void doCutEar()
    {
	boolean earHasBeenCut = false;
	int i = 0;

	while ((i < npoints - 1) && (!earHasBeenCut)) {
	    if (ptType[i] == 1) {  /* point is convex */
		if (i == 0) {
		    if (ear(xpoints[npoints-2], ypoints[npoints-2],
			    xpoints[i], ypoints[i],
                            xpoints[i+1], ypoints[i+1])) {
			cutEar(i);
			updatePolygon(i);
			earHasBeenCut = true;
		    }
		}
		else {    /* i > 0 */
		    if (ear(xpoints[i-1], ypoints[i-1],
			    xpoints[i], ypoints[i],
                            xpoints[i+1], ypoints[i+1])) {
			cutEar(i);
			updatePolygon(i);
			earHasBeenCut = true;
		    }
		}
	    }
	    i++;
	}
    }
}