#include <iostream>
#include <ctime>
#include <GL/glut.h>
#include <math.h>
#include <vector>

using namespace std;

struct Pos
{
    int x;
    int y;
};

struct Edge
{
    int x1, x2;
    int y1, y2;
    int vx;
    int vy;
    int a, b, c;
};

struct Poly
{
    // 點(diǎn)集
    int xx[100];
    int yy[100];

    // 邊集
    Edge Edges[100];

    int plotNums = 0; //點(diǎn)數(shù)量
    int edgeNums = 0; //邊數(shù)量

    // 記錄凹點(diǎn)
    int conv = 0;
};

Poly poly;


// 求交點(diǎn)坐標(biāo)
Pos CrossPos(int p1,int p2){
    Pos res;
    int A1 = poly.Edges[p1].a;
    int B1 = poly.Edges[p1].b;
    int A2 = poly.Edges[p2].a;
    int B2 = poly.Edges[p2].b;
    int C1 = poly.Edges[p1].c;
    int C2 = poly.Edges[p2].c;

    int m = A1 * B2 - A2 * B1;
    if (m == 0)
        cout <<"第"<<p1<<"邊和第"<<p2<<"邊"<< "無(wú)交點(diǎn)" << endl;
    else
    {
        res.x = (C2*B1 - C1 * B2) / m;
        res.y = (C1*A2 - C2 * A1) / m;
    }
    return res;

}

// 判斷點(diǎn)是否在線段內(nèi)
bool JudgeInLine(Pos pos,Edge edge)
{
    int maxX = edge.x1 >= edge.x2 ? edge.x1 : edge.x2;
    int minX = edge.x1 <= edge.x2 ? edge.x1 : edge.x2;
    int maxY = edge.y1 >= edge.y2 ? edge.y1 : edge.y2;
    int minY = edge.y1 <= edge.y2 ? edge.y1 : edge.y2;
    if (pos.x<=maxX && pos.x>=minX && pos.y<=maxY && pos.y>=minY)
    {
        return true;
    }
    return false;
}

// 求叉積 返回正負(fù)值
int CrossProduct(int n)
{
    n = n % poly.edgeNums;
    int np = (n + 1) % poly.edgeNums;
    return (poly.Edges[n].vx*poly.Edges[np].vy - poly.Edges[np].vx*poly.Edges[n].vy) >= 0 ? 1 : -1;
}

// 切割凹多邊形
void ChangePoly() {
    int convP = poly.conv; //凹點(diǎn)的下一個(gè)點(diǎn)
    Pos interPos;


    for (int i = 0; i < poly.edgeNums; i++)
    {
        if (i<convP-1 || i>convP+1)
        {
            interPos = CrossPos(convP, i);
        }
    }

    glClearColor(0.0, 0.0, 0.0, 0.0);
    glClear(GL_COLOR_BUFFER_BIT);
    glBegin(GL_POLYGON);
    glColor3f(1.0f, 0.0f, 0.0f);
    for (int i = 0; i <= convP; i++)
    {
        glVertex2f(poly.xx[i], poly.yy[i]);
    }
    glVertex2f(interPos.x, interPos.y);
    glEnd();

    glBegin(GL_POLYGON);
    glColor3f(0.0f, 1.0f, 1.0f);
    glVertex2f(interPos.x, interPos.y);
    for (int i=convP+1;i<poly.plotNums;i++)
    {
        glVertex2f(poly.xx[i], poly.yy[i]);
    }
    glEnd();

    glFlush();
}

// 判斷是什么多邊形
bool Judge()
{
    /*輸出邊信息*/
    for (int i = 0; i < poly.edgeNums; i++)
    {
        cout << "Vx：" << poly.Edges[i].vx << "  " << "Vy：" << poly.Edges[i].vy << "  " << "A：" << poly.Edges[i].a<< "  " << "B：" << poly.Edges[i].b << "  " << "C：" << poly.Edges[i].c <<endl;
    }

    /*判斷自交*/
    Pos interPos;
    if (poly.edgeNums > 3)
        for (int i = 0; i < poly.edgeNums; i++)
        {
            interPos = CrossPos(i, (i + 2) % poly.edgeNums);
            if (JudgeInLine(interPos, poly.Edges[i]) && JudgeInLine(interPos, poly.Edges[(i + 2) % poly.edgeNums]))
            {
                cout << "該多邊形為自相交多邊形" << endl;
                return false;
            }
        }

    /*判斷凹凸*/
    // 判斷向量叉積 是否為同一正負(fù)
    int judge;
    if (CrossProduct(0) >= 0)
        judge = 1;
    else
        judge = -1;
    //判斷每一個(gè)角，兩邊向量乘積是否同符號(hào)
    for (int i = 1; i <= poly.edgeNums; i++)
    {
        if (judge*CrossProduct(i) < 0)
        {
            poly.conv = i;
            ChangePoly();
            cout << "該多邊形為凹多邊形" << endl;
            return false;
        }
    }
    cout << "該多邊形為凸多邊形" << endl;
    return true;
}

void init(void)
{
    glClearColor(0.0, 0.0, 0.0, 0.0);

    glMatrixMode(GL_PROJECTION);//設(shè)置投影矩陣
    gluOrtho2D(0.0, 400.0, 0.0, 300.0);//二維視景區(qū)域

    glColor3f(1.0, 0.0, 0.0);
    glPointSize(3.0);//點(diǎn)的大小
}

void plotpoint(GLint x, GLint y)
{
    glBegin(GL_POINTS);
    glVertex2i(x, y);
    glEnd();
}

void displayFcn(void)
{
    glClearColor(0.0, 0.0, 0.0, 0.0);
    glClear(GL_COLOR_BUFFER_BIT);
    for (int i = 0; i < poly.plotNums; i++)
    {
        plotpoint(poly.xx[i], poly.yy[i]);
    }
    glBegin(GL_POLYGON);
    for (int i = 0; i < poly.edgeNums; i++)
    {
        glVertex2f(poly.xx[i], poly.yy[i]);
    }
    glEnd();

    glFlush();
}

void mouse(GLint button, GLint action, GLint x, GLint y)
{
    if (button == GLUT_LEFT_BUTTON && action == GLUT_DOWN)
    {
        poly.xx[poly.plotNums] = x;
        poly.yy[poly.plotNums] = 300 - y;
        cout << "x：" << x << "  " << "y：" << 300 - y << endl;
        poly.plotNums++;
        glutPostRedisplay();//重繪窗口
    }
    if (button == GLUT_RIGHT_BUTTON && action == GLUT_DOWN)
    {
        poly.edgeNums = poly.plotNums;
        if (poly.plotNums > 2)
        {
            for (int i = 1; i <= poly.plotNums; i++)
            {
                poly.Edges[i - 1].x1 = poly.xx[i - 1];
                poly.Edges[i - 1].y1 = poly.yy[i - 1];
                poly.Edges[i - 1].x2 = poly.xx[i%poly.plotNums];
                poly.Edges[i - 1].y2 = poly.yy[i%poly.plotNums];
                poly.Edges[i - 1].vx = poly.Edges[i - 1].x2 - poly.Edges[i - 1].x1;
                poly.Edges[i - 1].vy = poly.Edges[i - 1].y2 - poly.Edges[i - 1].y1;
                poly.Edges[i - 1].a = poly.Edges[i - 1].vy;
                poly.Edges[i - 1].b = -poly.Edges[i - 1].vx;
                poly.Edges[i - 1].c = poly.Edges[i - 1].x2 * poly.Edges[i - 1].y1 - poly.Edges[i - 1].x1 * poly.Edges[i - 1].y2;
            }
            if (Judge())
                glutPostRedisplay();//重繪窗口
        }
    }
}

int main(int argc, char** argv)
{
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
    glutInitWindowPosition(50, 100);
    glutInitWindowSize(400, 300);
    glutCreateWindow("mouse");

    init();
    glutDisplayFunc(displayFcn);

    glutMouseFunc(mouse);

    glutMainLoop();

}