/*
 * MAE574 Homework #2
 * Written by Tom Oldani
 * Some code used from the GLUT shapes demo
 */

#include <GL/glut.h>
#include <stdlib.h>
#include <math.h>
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

// polygon, limited to 30 vertices/edges
typedef struct
{
    float inputx[30];
    float inputy[30];
    int edge[30];
    int n;
}polygon;

polygon poly[20];

// for drawing the polygon
float scale = 5;
float offsetx = 20;
float offsety = 40;
float crossProduct[4];
float normalLength[4];

int k = 0; // index of the current polygon
int totalPolys = 2; // technically, the index of the last polygon in the set
int convex = 0; // true if in polygon creation mode

float testx[20];
float testy[20];

// Writes text on the screen
void writetext( int x, int y, char text[])
{
    for(int i=0; text[i] != '\0'; i++)
    {
        glRasterPos2i( i*9+x, y );
        glutBitmapCharacter(GLUT_BITMAP_9_BY_15, text[i]);
    }
}

// check if point is inside polygon, return 0 for false and 1 for true
int isInside( polygon p, float x, float y )
{
    // use the raycasting method, with a ray parallel to the x-axis
    int edges = 0;
    double crossx, x1, y1, x2, y2;

    for( int i=1; i <= p.n; i++ )
    {
        // store edge so first point has the lower y value.  this makes
        // operations easier, and takes care of cases where the ray intersects
        // one or more vertices.
        if( p.inputy[p.edge[i] - 1] < p.inputy[p.edge[i+1] - 1] )
        {
            x1 = p.inputx[p.edge[i] - 1];
            y1 = p.inputy[p.edge[i] - 1];
            x2 = p.inputx[p.edge[i+1] - 1];
            y2 = p.inputy[p.edge[i+1] - 1];
        }
        else
        {
            x1 = p.inputx[p.edge[i+1] - 1];
            y1 = p.inputy[p.edge[i+1] - 1];
            x2 = p.inputx[p.edge[i] - 1];
            y2 = p.inputy[p.edge[i] - 1];
        }

        // check if the horizontal ray (pointing toward 0) crosses the edge
        if( y1 < y && y2 >= y )
        {
            crossx = (y-y1) / (y2-y1) * (x2-x1) + x1;
            if( crossx < x )
                edges++;
        }
    }

    return edges %2;
}

// performs a cross product and stores the results in crossProduct[] and normalLength[]
void cross( float x1, float y1, float z1, float x2, float y2, float z2 )
{
    float length;
    crossProduct[1] = y1*z2 - z1*y2;
    crossProduct[2] = z1*x2 - x1*z2;
    crossProduct[3] = x1*y2 - y1*x2;

    length = sqrtf( pow(crossProduct[1], 2) + pow(crossProduct[2], 2) + pow(crossProduct[3], 2) );

    normalLength[1] = crossProduct[1] / length;
    normalLength[2] = crossProduct[2] / length;
    normalLength[3] = crossProduct[3] / length;
}

// calculates an angle, given 3 sets of points.  the first point is the vertex
float angle( float x1, float y1, float x2, float y2, float x3, float y3 )
{
    float a1;
    a1 = atan2f( ((x3-x1)*(y2-y1)) - ((x2-x1)*(y3-y1)), ((x3-x1)*(x2-x1)) + ((y2-y1)*(y3-y1)) );
    if( a1 < 0 )
        a1 += (2 * M_PI);
    return a1;
}

// recursively fills a polygon, based on the ear cropping algorithm
void fillPoly( polygon p )
{
    int canDraw=0;
    float x1, y1, x2, y2, x3, y3, temp=0, ang = 0;

    for( int i = 1; i <= p.n; i++ )
    {
        // three vertices to test to see if a triangle can be drawn inside
        x1 = p.inputx[p.edge[i] - 1];
        y1 = p.inputy[p.edge[i] - 1];
        x2 = p.inputx[p.edge[i-1] - 1];
        y2 = p.inputy[p.edge[i-1] - 1];
        x3 = p.inputx[p.edge[i+1] - 1];
        y3 = p.inputy[p.edge[i+1] - 1];

        ang = angle( x1, y1, x2, y2, x3, y3 );

        if( ang < M_PI )
        {
            for(int q=0; q < p.n; q++)
            {
                // checking all points in the polygon besides those that make up this triangle
                if( (q+1 != p.edge[i]) && (q+1 != p.edge[i+1]) && (q+1 != p.edge[i-1]) )
                {
                    // if the angles add to pi, the point is in the triangle
                    temp = atan2f( x1 - p.inputx[q], y1 - p.inputy[q] );
                    temp += atan2f( x2 - p.inputx[q], y2 - p.inputy[q] );
                    temp += atan2f( x3 - p.inputx[q], y3 - p.inputy[q] );

                    if( abs(temp - M_PI) > 0.0001 )
                    {
                        canDraw = i;
                        goto drawIt;
                    }
                }
            }
        }
    }
    drawIt:

    glColor3f( 0, (p.n - 1)/5., 0 );

    glBegin( GL_TRIANGLES );
        glVertex2f( x1 * scale + offsetx, y1 * scale + offsety );
        glVertex2f( x2 * scale + offsetx, y2 * scale + offsety );
        glVertex2f( x3 * scale + offsetx, y3 * scale + offsety );
        glEnd();

    for(int i=canDraw; i<=p.n; i++)
        p.edge[i] = p.edge[i+1];

    p.n--;
    p.edge[p.n+1] = p.edge[1];
    p.edge[0] = p.edge[p.n];

    for(int i=1; i<=p.n; i++)
    {
        // gets rid of any points that may be connected to only one other point
        if(p.edge[i+1] == p.edge[i-1])
        {
            for(int q=i; q<=p.n; q++)
                p.edge[q] = p.edge[q+2];
            p.n -= 2;
            p.edge[p.n+1] = p.edge[1];
            p.edge[0] = p.edge[p.n];
        }
    }

    if( p.n > 2 )
        fillPoly(p);
}

void makeConvex( polygon p )
{
    for(int i=1; i<p.n; i++)
    {
        glBegin( GL_TRIANGLE_FAN );
            if( p.inputx[i] > 0 )
            glVertex2f( p.inputx[i] * scale + offsetx, p.inputy[i] * scale + offsety );

            for(int q=0; q<p.n; q++)
            {
                if( q != i && p.inputx[q] > 0)
                glVertex2f( p.inputx[q] * scale + offsetx, p.inputy[q] * scale + offsety);
            }
            glEnd();
    }
}

// tests to see if a given polygon is convex.
int isConvex( polygon p )
{
    float ang;

    for(int i = 1; i <= p.n; i++)
    {
        ang = angle( p.inputx[p.edge[i] - 1], p.inputy[p.edge[i] - 1], p.inputx[p.edge[i-1] - 1], p.inputy[p.edge[i-1] - 1], p.inputx[p.edge[i+1] - 1], p.inputy[p.edge[i+1] - 1] );

        if( ang > M_PI )
            return 0;
    }
    return 1;
}

static void reshape(int width, int height)
{

}

static void display(void)
{
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

    if( convex )
        makeConvex( poly[k] );
    else
        fillPoly( poly[k] );

    glColor3f( 1., 0., 0. );

    // draw the test point (it's red, and a little hard to see)
    glBegin( GL_POINTS );
        glVertex2f( testx[k] * scale + offsetx, testy[k] * scale + offsety );
        glEnd();

    glColor3f( 0., 1., 0. );

    char message1[80], message2[80];

    strcpy(message1, "The test point is ");
    if( !isInside( poly[k], testx[k], testy[k] ) )
        strcat(message1, "not ");
    strcat(message1, "inside the polygon.  The polygon is ");
    if( !isConvex( poly[k] ) )
        strcat(message1, "not ");
    strcat(message1, "convex.");

    float x1, x2, x3, y1, y2, y3;

    x1 = poly[k].inputx[poly[k].edge[0] - 1];
    y1 = poly[k].inputy[poly[k].edge[0] - 1];
    x2 = poly[k].inputx[poly[k].edge[1] - 1];
    y2 = poly[k].inputy[poly[k].edge[1] - 1];
    x3 = poly[k].inputx[poly[k].edge[2] - 1];
    y3 = poly[k].inputy[poly[k].edge[2] - 1];

    // does the cross product, assumes z = 0
    cross( x2-x1, y2-y1, 0, x3-x1, y3-y1, 0 );

    sprintf(message2, "The normal vector is %4.3fi + %4.3fj + %4.3fk.", normalLength[1], normalLength[2], normalLength[3] );

    writetext( 30, 390, "+ Zoom in" );
    writetext( 30, 410, "- Zoom out" );
    writetext( 30, 430, "n Next polygon" );
    writetext( 30, 450, "c Show convex hull" );
    writetext( 30, 470, "Clicking will change the test point" );

    writetext( 10, 20, message1 );
    writetext( 10, 40, message2 );

    glutSwapBuffers();
}

static void key(unsigned char key, int x, int y)
{
    switch (key)
    {
        case 27 :
        case 'q':
            exit(0);
            break;

        case '+':
            scale++;
            break;

        case '-':
            if( scale > 1 )
                scale--;
            break;

        case 'n':
            k++;
            if(k > totalPolys) k = 0;
            break;

        case 'c':
            if( convex )
                convex = 0;
            else
                convex = 1;
            break;
    }

    glutPostRedisplay();
}

static void mouse( int button, int state, int x, int y )
{
    if(state == GLUT_DOWN && button == GLUT_LEFT_BUTTON)
    {
        testx[k] = (x - offsetx) / scale;
        testy[k] = (y - offsety) / scale;
    }

    glutPostRedisplay();
}

static void idle(void)
{
    glutPostRedisplay();
}

int main(int argc, char *argv[])
{
	glutInit( &argc, argv );
	glutInitDisplayMode( GLUT_DOUBLE | GLUT_RGB );
	glutInitWindowPosition( 50, 50 );
	glutInitWindowSize( 640, 480 );
	glutCreateWindow( "Homework 1" );

	glClearColor( 0., 0., 0. , 1. );
	glMatrixMode( GL_PROJECTION );
	glLoadIdentity( );
	gluOrtho2D( 0, 640, 480, 0 );

	testx[0] = 100;
	testx[1] = 10;
	testx[2] = 3;

	testy[0] = 5;
	testy[1] = 5.8;
	testy[2] = 5.5;

// first test case (there has got to be a better way to do this!)
	poly[0].inputx[0] = 1;
	poly[0].inputx[1] = 100;
	poly[0].inputx[2] = 101;
	poly[0].inputx[3] = 2;

	poly[0].inputy[0] = 1;
	poly[0].inputy[1] = 5;
	poly[0].inputy[2] = 6;
	poly[0].inputy[3] = 5.4;

	poly[0].edge[0] = 4;
	poly[0].edge[1] = 1;
	poly[0].edge[2] = 2;
	poly[0].edge[3] = 3;
	poly[0].edge[4] = 4;
	poly[0].edge[5] = 1;

	poly[0].n = 4;

// second test case
    poly[1].inputx[0] = 1;
	poly[1].inputx[1] = 10;
	poly[1].inputx[2] = 20;
	poly[1].inputx[3] = 15;
	poly[1].inputx[4] = 3;

	poly[1].inputy[0] = 1;
	poly[1].inputy[1] = 5;
	poly[1].inputy[2] = 3;
	poly[1].inputy[3] = 7;
	poly[1].inputy[4] = 8;

	poly[1].edge[0] = 5;
	poly[1].edge[1] = 1;
	poly[1].edge[2] = 2;
	poly[1].edge[3] = 3;
	poly[1].edge[4] = 4;
	poly[1].edge[5] = 2;
	poly[1].edge[6] = 5;
	poly[1].edge[7] = 1;

	poly[1].n = 6;

// third test case
    poly[2].inputx[0] = 1;
	poly[2].inputx[1] = 5;
	poly[2].inputx[2] = 10;
	poly[2].inputx[3] = 10;
	poly[2].inputx[4] = 5;
	poly[2].inputx[5] = 1;

	poly[2].inputy[0] = 1;
	poly[2].inputy[1] = 5;
	poly[2].inputy[2] = 1;
	poly[2].inputy[3] = 10;
	poly[2].inputy[4] = 7;
	poly[2].inputy[5] = 10;

	poly[2].edge[0] = 6;
	poly[2].edge[1] = 1;
	poly[2].edge[2] = 2;
	poly[2].edge[3] = 3;
	poly[2].edge[4] = 4;
	poly[2].edge[5] = 5;
	poly[2].edge[6] = 6;
	poly[2].edge[7] = 1;

	poly[2].n = 6;

	glutDisplayFunc( display );
	glutReshapeFunc( reshape );
	glutKeyboardFunc( key );
    glutMouseFunc( mouse );
    glutIdleFunc( idle );
	glutMainLoop( );

	return 0;
}