TrianGO

A game of GO on triangles

    A. First Edition

    This is my project of comp6711 and it is an interesting little game of triangles which simulates some feature

    of game GO.

    B.The problem

To best understand the game, you may need to download a demo slides from here.

¡¡

¡¡

C.The idea of program
¡¡

¡¡

    D.The major functions

    In order to run in OpenGL, you need download "glut32.dll" and "glu32.dll" in your system folder.

    i.e. c:\windows\system32

    And to compile the code, you need to link with "openGL32.lib, glut32.lib, glu32.lib" in your vc6++.

    ¡¡

    ¡¡

    E.Further improvement

Compilation:

a) This project only uses common glu and glut as library.

b) In case when system is not installed with these library, copy glu32.lib, glut32.lib to library path of Visual C++ 6.0. For example, the path may look like this:

C:\Program Files\Microsoft Visual Studio\VC98\Lib

c) My code will automatically add libs into project by macros, so you don¡¯t have to add these libs into your Visual6.0 project file setting by hand.

Running:

a) In system where glu or glut library are not installed, as long as you keep glu32.dll and glut32.dll in same directory with executable file ¡°TrianGO.exe¡± it should be able to run correctly.

Operation:

a) create random points: by right click mouse or press ¡®n¡¯;

b) create nested convex hull: by press ¡®n¡¯.

c) create triangulation: press ¡®t¡¯.

d) start playing: left click triangles in chess board.

restart: press ¡®a¡¯ to clear everything.

To show menu: press ¡®m¡¯

To exit: press ¡®esc¡¯

    ¡¡

    F.File listing

    1. common.h

    2. common.cpp

    3. ConvexHull.h

    4. ConvexHull.cpp

    5. main.cpp

    ¡¡

    file name: common.h

    #ifndef COMMON_H
    #define COMMON_H
    #include <set>
    #include <vector>
    #include <deque>

    using namespace std;

    #pragma comment(lib, "opengl32.lib")
    #pragma comment(lib, "glu32.lib")
    #pragma comment(lib, "glut32.lib")

    const int winPos_x=0, winPos_y=0;
    const int winSize_width=600, winSize_height=600;
    static const char* windowTitle="Convex Hull Demo";

    const int MaxIntegerValue=winSize_width/2-30;

    typedef float TColor[3];

    typedef float TVector2[2];

    static TColor red={1,0,0}, green={0,1,0}, blue={0,0,1}, yellow={0,1,1}, beige={1,1,0};

    typedef float TPlayerColors[2][3];

    static float playerColor[3][3]={{1,0,0}, {0,0,1}, {0,1,1}};
    struct TTriangle;

    enum FaceStatus
    {
    	Red=0, Blue=1, Empty=2
    };

    struct TPoint
    {
    	float x;
    	float y;
    	const TPoint& operator=(const TPoint& other)
    	{
    		x=other.x;
    		y=other.y;
    		return *this;
    	}
    	TPoint(){;}
    	TPoint(float theX, float theY)
    	{
    		x=theX;
    		y=theY;
    	}
    	void display() const;
    	void display();
    };

    struct PrevPoint
    {
    	bool operator()(const TPoint& first, const TPoint& second)
    	{
    		if (first.x==second.x)
    		{
    			return first.y>second.y;
    		}
    		else
    		{
    			return first.x<second.x;
    		}
    	}
    	bool operator()(const TPoint& first, const TPoint& second) const
    	{
    		if (first.x==second.x)
    		{
    			return first.y>second.y;
    		}
    		else
    		{
    			return first.x<second.x;
    		}
    	}
    };

    static PrevPoint prevPoint;

    struct TPointContext
    {
    	TPoint point;
    	TColor pointColor;
    };

    int compPoint(const void* elem1, const void* elem2);
    float direction(TPoint* p, TPoint* q, TPoint* r);
    float generateRandomValue();
    void generatePoint(int pointNumber, TPoint*& ptrArray);

    typedef TPoint TTriPoint[3];

    typedef set<TPoint, PrevPoint> TPointSet;
    typedef vector<TPoint> TPointVector;
    typedef deque<TPoint> TPointQueue;
    typedef deque<TTriangle> TTriangleQueue;

    const TPointSet& setCopy(TPointSet& dest, const TPointSet& source);
    void generateRandomPoint(int pointNumber, TPointSet& pointSet);

    struct TTriangle
    {
    	TTriPoint triangle;
    	void assign(TPoint p1, TPoint p2, TPoint p3);

    	bool pointInside(TPoint& point);
    	void display();
    	void draw();
    	TTriangle& operator=(TTriangle& other)
    	{
    		for (int i=0; i<3; i++)
    		{
    			triangle[i]=other.triangle[i];
    		}
    		return *this;
    	}
    };

    struct TEdge;
    struct TFace;
    typedef TEdge* TTripleEdgePtr[3];
    typedef TPoint TPairPoint[2];

    //undirected edge
    struct TEdge
    {
    	TPairPoint pairPoint;
    	TColor color;
    	TFace* faces[2];
    	void display();
    	void draw();
    };

    struct PrevEdge
    {
    	//assume the point in edge is sorted when constructed.
    	//that is, pointPair[0]<pointPair[1]
    	bool operator()(TEdge* first, TEdge* second)
    	{
    		for (int i=0; i<2; i++)
    		{
    			if (prevPoint(first->pairPoint[i], second->pairPoint[i]))
    			{
    				return true;
    			}
    			if (prevPoint(second->pairPoint[i], first->pairPoint[i]))
    			{
    				return false;
    			}
    		}
    		//equal edge
    		return false;
    	}
    	bool operator()(TEdge* first, TEdge* second) const
    	{
    		for (int i=0; i<2; i++)
    		{
    			if (prevPoint(first->pairPoint[i], second->pairPoint[i]))
    			{
    				return true;
    			}
    			if (prevPoint(second->pairPoint[i], first->pairPoint[i]))
    			{
    				return false;
    			}
    		}
    		//equal edge
    		return false;
    	}
    };

    static PrevEdge prevEdge;

    typedef set<TEdge*, PrevEdge> TEdgePtrSet;

    struct TFace
    {
    	TTripleEdgePtr edges;
    	TColor color;
    	FaceStatus status;
    	bool pointInside(TPoint& point);
    	void display();
    	void draw();

    };

    struct PrevFace
    {
    	//assume three edges are sorted in TFace
    	bool operator()(TFace* first, TFace* second)
    	{
    		for (int i=0; i<3; i++)
    		{
    			if (prevEdge(first->edges[i], second->edges[i]))
    			{
    				return true;
    			}
    			if (prevEdge(second->edges[i], first->edges[i]))
    			{
    				return false;
    			}
    		}
    		//if both equal
    		return false;
    	}
    	bool operator()(TFace* first, TFace* second) const
    	{
    		for (int i=0; i<3; i++)
    		{
    			if (prevEdge(first->edges[i], second->edges[i]))
    			{
    				return true;
    			}
    			if (prevEdge(second->edges[i], first->edges[i]))
    			{
    				return false;
    			}
    		}
    		//if both equal
    		return false;
    	}
    };

    typedef set<TFace*, PrevFace> TFacePtrSet;
    typedef set<TFace*> TFacePointerSet;
    typedef vector<TFace*> TFacePtrVector;

    #endif

    ¡¡

    ¡¡

    file name: common.cpp

    #include "common.h"
    #include <GL/glut.h>
    #include <iostream>

    using namespace std;

    float direction(TPoint* p, TPoint* q, TPoint* r)
    {
    	return q->x*r->y +p->x*q->y+p->y*r->x - p->y*q->x - q->y*r->x -p->x*r->y;
    }

    int compPoint(const void* elem1, const void* elem2)
    {
    	TPoint* ptr1, *ptr2;
    	ptr1=(TPoint*)elem1;
    	ptr2=(TPoint*)elem2;
    	return ptr1->x-ptr2->x;
    }

    void generateRandomPoint(int pointNumber, TPointSet& pointSet)
    {
    	TPoint point;
    	pointSet.clear();
    	for (int i=0; i<pointNumber; i++)
    	{
    		point.x=generateRandomValue();
    		point.y=generateRandomValue();
    		pointSet.insert(point);
    	}
    }

    void TTriangle::draw()
    {
    	glBegin(GL_POLYGON);
    	for (int i=0; i<3; i++)
    	{
    		glColor3fv(red);
    		glVertex2f(triangle[i].x, triangle[i].y);
    	}
    	glEnd();
    }

    void TTriangle::display()
    {
    	for (int i=0; i<3; i++)
    	{
    		triangle[i].display();
    	}
    }

    void TPoint::display() const
    {
    	printf("[x=%f,y=%f]\n", x, y);
    }

    void TPoint::display()
    {
    	printf("[x=%f,y=%f]\n", x, y);
    }

    /*
    void TMyPointSet::display()
    {
    	for (TPointSet::const_iterator it=pointSet.begin(); it!=pointSet.end(); it++)
    	{
    		it->display();
    	}
    }

    void TMyPointSet::generatePoint(int pointNumber)
    {
    	TPoint point;
    	pointSet.clear();
    	for (int i=0; i<pointNumber; i++)
    	{
    		point.x=generateRandomValue();
    		point.y=generateRandomValue();
    		pointSet.insert(point);
    	}
    }
    */

    const TPointSet& setCopy(TPointSet& dest, const TPointSet& source)
    {
    	dest.clear();
    	TPointSet::const_iterator it;
    	for (it=source.begin(); it!=source.end(); it++)
    	{
    		dest.insert(*it);
    	}
    	return dest;
    }

    void TTriangle::assign(TPoint p1, TPoint p2, TPoint p3)
    {
    	triangle[0]=p1;
    	triangle[1]=p2;
    	triangle[2]=p3;
    }

    bool TTriangle::pointInside(TPoint& point)
    {
    	float result[3];

    	for (int i=0; i<3; i++)
    	{
    		result[i]=direction(triangle+i, triangle+(i+1)%3, &point);
    	}

    	return result[0]*result[1]>=0&&result[0]*result[2]>=0&&result[1]*result[2]>=0;
    }

    bool TFace::pointInside(TPoint& point)
    {
    	float result[3];
    	TPoint points[3];
    	points[0]=edges[0]->pairPoint[0];
    	points[1]=edges[0]->pairPoint[1];
    	points[2]=edges[2]->pairPoint[1];
    	for (int i=0; i<3; i++)
    	{
    		result[i]=direction(points+i, points+(i+1)%3, &point);
    	}

    	return result[0]*result[1]>=0&&result[0]*result[2]>=0&&result[1]*result[2]>=0;
    }

    void TEdge::draw()
    {
    	glLineWidth(1);
    	glBegin(GL_LINES);
    	for (int i=0; i<2; i++)
    	{
    		glColor3fv(color);
    		glVertex2f(pairPoint[i].x, pairPoint[i].y);
    	}
    	glEnd();
    }

    void TEdge::display()
    {
    	printf("display edge\n");
    	for (int i=0; i<2; i++)
    	{
    		pairPoint[i].display();
    	}
    }

    void TFace::display()
    {
    	printf("\n***************display face***********************\n");
    	for (int i=0; i<3; i++)
    	{
    		edges[i]->display();
    	}
    }

    //why is that sequence? because first edge must have the no.1, no2 vertex
    //the last edge or 3rd edge's second vertex must be last one
    void TFace::draw()
    {
    	glBegin(GL_POLYGON);
    		glColor3fv(color);
    		glVertex2f(edges[0]->pairPoint[0].x, edges[0]->pairPoint[0].y);
    		glColor3fv(color);
    		glVertex2f(edges[0]->pairPoint[1].x, edges[0]->pairPoint[1].y);

    		glColor3fv(color);
    		glVertex2f(edges[2]->pairPoint[1].x, edges[2]->pairPoint[1].y);
    	glEnd();
    	for (int i=0; i<3; i++)
    	{
    		edges[i]->draw();
    	}
    }

    /*
    void TMyPointSet::setArray(TPoint* inputArray, int inputNumber)
    {
    	pointSet.clear();

    	pointSet.insert(inputArray, inputArray+inputNumber);
    }
    */

    float generateRandomValue()
    {
    	float intPart, floatPart;
    	intPart=rand()%MaxIntegerValue * (rand()%2==0?1 : (-1));
    	floatPart=(float)rand()/(float)RAND_MAX;
    	return intPart+floatPart;
    }

    ¡¡

    file name: convex.h

    #ifndef CONVEXHULL_H
    #define CONVEXHULL_H

    #include <vector>
    //#include "DCEL.h"
    #include <utility>
    #include <GL/glut.h>
    #include "common.h"

    using namespace std;

    struct TConvex;
    struct TBoard;

    typedef vector<TPointQueue> TPointQueueVector;
    typedef pair<TPoint, TPoint> TPointPair;
    typedef vector<TPointPair> TPointPairVector;

    struct TConvex
    {
    	TPointSet pointSet;
    	void collectVertexUp(TPointQueue&);
    	void collectVertexDown(TPointQueue&);
    	void addPoint(TPointQueue&, TPoint*);
    	int number;
    	void generatePoint(int pointNumber);
    	void display();
    	void convexHull(const TPointSet& inputSet, TPointQueue& pointqueue);
    };

    struct TNestConvex
    {
    	static void nestConvex(const TPointSet& pointSet, TPointQueueVector& convexQueue);
    	static void triangulate(TPointQueueVector& convexQueue, TPointPairVector& pointPairVector);
    	//static void triangulate(TPointQueueVector& convexQueue, TTriangleQueue& triangleQueue);

    	static bool triangulate(TPointQueueVector& convexQueue, TBoard& board);
    };

    struct TBoard
    {
    	TEdgePtrSet edgePtrSet;
    	TFacePtrSet facePtrSet;

    	int controlCounter[3];

    	void makeEdge(TPoint& p1, TPoint& p2, TEdge& result);
    	void makeFace(TPoint& p1, TPoint& p2, TPoint& p3, TFace& result);
    	void makeBoard(TTriangleQueue& triangleQueue);
    	bool insertFace(TPoint& p1, TPoint& p2, TPoint& p3);
    	void clear();
    	void draw();
    	void drawEdge();
    	void drawFace();
    	void display();
    	void displayFace();
    	TFace* linearSearch(TPoint& point);
    	//TFace* binarySearch(TPoint& point);
    	bool validMove(TFace* face, FaceStatus player, bool justTest=false);

    	//bool hasSpace(TFace* face, bool player);

    	bool sameColor(TFace* him, FaceStatus player);

    	bool isSurrounded(TFace* face, bool player);

    	void getNeighbour(TFace* face, TFace* neighbours[3]);

    	bool doSearchSpace(TFace* start, FaceStatus player, TFacePointerSet& path);

    	void removeEnemy(TFace* face, FaceStatus enemy);

    	int countTriangle();
    	bool controlBy(TFace* face, FaceStatus& status, TFacePointerSet& path);

    };

    class TPolygon
    {
    private:
    	int number;
    	TPoint* leftMost;
    	TPoint* rightMost;

    public:
    	TPoint* ptrArray;
    	//TPolygon();
    	void createPolygon(int pointNumber, TPointQueue& pointQueue);

    };

    #endif

    ¡¡

    file name: convex.cpp

    #include <iostream>
    #include <cmath>
    #include <vector>
    #include "common.h"
    #include "ConvexHull.h"

    using namespace std;

    //GLenum drawingMode = GL_POINTS;

    vector<TPointContext> separateVector;
    vector<TPointContext> connectVector;

    vector<TPointContext> polygonVector;
    TPolygon polygon;

    TConvex convex;

    void TPolygon::createPolygon(int pointNumber, TPointQueue& pointQueue)
    {
    	TPointContext pointContext;
    	number=pointNumber;
    	::generatePoint(pointNumber, ptrArray);
    	qsort(ptrArray, number, sizeof(TPoint), compPoint);
    	leftMost=ptrArray;
    	rightMost=ptrArray+number-1;

    	for (int i=0; i<number; i++)
    	{
    		if (direction(leftMost, rightMost, ptrArray+i)<=0)
    		{
    			pointQueue.push_back(ptrArray[i]);
    		}
    		else
    		{
    			pointQueue.push_front(ptrArray[i]);
    		}
    	}
    }

    /*
    TPolygon::TPolygon()
    {
    	createPolygon();
    }
    */

    void TConvex::generatePoint(int pointNumber)
    {
    	number=pointNumber;
    	TPoint point;
    	for (int i=0; i<number; i++)
    	{
    		point.x=generateRandomValue();
    		point.y=generateRandomValue();
    		pointSet.insert(point);
    	}
    }

    void generatePoint(int pointNumber, TPoint*& ptrArray)
    {
    	TPointContext pointContext;
    	ptrArray=new TPoint[pointNumber];
    	for (int i=0; i<pointNumber; i++)
    	{
    		ptrArray[i].x=generateRandomValue();
    		ptrArray[i].y=generateRandomValue();
    		pointContext.point=ptrArray[i];
    		memcpy(pointContext.pointColor, red, sizeof(TColor));
    		separateVector.push_back(pointContext);
    		//glutPostRedisplay();
    		glutSwapBuffers();
    	}
    	//glutPostRedisplay();
    }

    void TConvex::addPoint(TPointQueue& pointQueue, TPoint* pointPtr)
    {
    	TPointQueue::reverse_iterator start, last;
    	while (pointQueue.size()>=2)
    	{
    		start=pointQueue.rbegin();
    		last=start;
    		start++;

    		if (direction(&(*start), &(*last), pointPtr)>=0)
    		{
    			pointQueue.pop_back();
    		}
    		else
    		{
    			break;
    		}
    	}
    	pointQueue.push_back(*pointPtr);
    }

    void TConvex::collectVertexUp(TPointQueue& pointQueue)
    {
    	TPointSet::iterator it, stop;

    	it=pointSet.begin();
    	stop=pointSet.end();

    	pointQueue.push_back(*it);
    	it++;
    	pointQueue.push_back(*it);
    	it++;

    	while (it!=stop)
    	{
    		addPoint(pointQueue, &(*it));
    		it++;
    	}
    }

    void printQueue(TPointQueue& pointQueue)
    {
    	for (TPointQueue::iterator it=pointQueue.begin(); it!=pointQueue.end(); it++)
    	{
    		it->display();
    	}
    }

    void TConvex::collectVertexDown(TPointQueue& pointQueue)
    {
    	TPointSet::reverse_iterator it, stop;

    	it=pointSet.rbegin();
    	stop=pointSet.rend();

    	pointQueue.push_back(*it);
    	it++;
    	pointQueue.push_back(*it);
    	it++;

    	while (it!=stop)
    	{
    		addPoint(pointQueue, &(*it));
    		it++;
    	}
    }

    void TConvex::display()
    {
    	for (TPointSet::iterator it=pointSet.begin(); it!=pointSet.end(); it++)
    	{
    		it->display();
    	}
    }

    void TConvex::convexHull(const TPointSet& inputSet, TPointQueue& pointQueue)
    {
    	int upSize, downSize;
    	TPointQueue upQueue, downQueue;
    	TPointQueue::iterator it;
    	TPointSet::const_iterator setIt;
    	pointSet.clear();
    	pointQueue.clear();

    	for (setIt=inputSet.begin(); setIt!=inputSet.end(); setIt++)
    	{
    		pointSet.insert(*setIt);
    	}

    	if (pointSet.size()<3)
    	{
    		for (TPointSet::iterator it=pointSet.begin(); it!=pointSet.end(); it++)
    		{
    			pointQueue.push_back(*it);
    		}
    	}
    	else
    	{
    		collectVertexUp(upQueue);
    		collectVertexDown(downQueue);
    		for (it=upQueue.begin(); it!=upQueue.end(); it++)
    		{
    			pointQueue.push_back(*it);
    		}

    		pointQueue.pop_back();//remove last

    		for (it=downQueue.begin(); it!=downQueue.end(); it++)
    		{
    			pointQueue.push_back(*it);
    		}
    		pointQueue.pop_back();//remove last

    	}

    }

    void TNestConvex::nestConvex(const TPointSet& pointSet, TPointQueueVector& convexQueue)
    {
    	TConvex convex;
    	TPointQueue pointQueue;
    	TPointSet inputSet;
    	TPointQueue::iterator qIt;

    	setCopy(inputSet, pointSet);

    	while (!inputSet.empty())
    	{
    		convex.convexHull(inputSet, pointQueue);
    		//printf("get a convex\n");
    		//printQueue(pointQueue);
    		convexQueue.push_back(pointQueue);
    		for (qIt=pointQueue.begin(); qIt!=pointQueue.end(); qIt++)
    		{
    			inputSet.erase(*qIt);
    		}
    	}
    }

    bool TNestConvex::triangulate(TPointQueueVector& convexQueue, TBoard& board)
    {
    	TPointQueue outside, inside;
    	TTriangle triangle;
    	int i, j, k;
    	int counter;
    	int inCounter, outCounter;
    	TPoint outPoint, inPoint, nextIn, p1, p2, p3;
    	float result;

    	if (convexQueue.size()==0)
    	{
    		return false;
    	}
    	for (i=0; i<convexQueue.size()-1; i++)
    	{
    		outside=convexQueue[i];
    		inside=convexQueue[i+1];

    		j=k=0;
    		printf("\n");

    		outCounter=outside.size();
    		if (inside.size()==1)
    		{
    			inCounter=0;
    		}
    		else
    		{
    			inCounter=inside.size();
    		}
    		while (true)
    		{
    			outPoint=outside[j];
    			inPoint=inside[k];

    			nextIn=inside[(k+1)%inside.size()];

    			result=direction(&inPoint, &nextIn, &outPoint);

    			//here for the case the inside has only ONE vertex, the result is always 0
    			//so, we move outside when result is zero
    			if (result>0&&inCounter>0)
    			{
    				p1=outPoint;
    				p2=inPoint;
    				k=(k+1)%inside.size();
    				p3=inside[k];
    				inCounter--;
    			}
    			else
    			{
    				p1=outPoint;
    				p2=inPoint;
    				j=(j+1)%outside.size();
    				p3=outside[j];
    				outCounter--;
    			}

    			//triangle.display();
    			///////////////////////////
    			if (!board.insertFace(p1, p2, p3))
    			{
    				///////////////////////////////////////////////////
    				printf("what? and inside convex is*******************\n\n", result);
    				printQueue(inside);
    				printf("\n***********outside convex is:*********************\n");
    				printQueue(outside);
    				printf("\n********************************\n");
    				return false;
    			}

    			if (inCounter==0&&outCounter==0)
    			{
    				break;
    			}
    		}
    	}
    	outside=convexQueue.back();

    	outPoint=outside[0];
    	for (i=2; i<outside.size(); i++)
    	{
    		p1=outside[0];
    		p2=outside[i-1];
    		p3=outside[i];
    		if (!board.insertFace(p1, p2, p3))
    		{
    			printf("what????*****and the convex is::::\n");
    			printQueue(outside);
    			printf("\n**********immediately convex******************\n");
    			printQueue(convexQueue[convexQueue.size()-2]);
    			printf("\n**********immediately convex******************\n");
    			return false;
    		}
    		//pointPairVector.push_back(make_pair(outPoint, inPoint));
    	}
    	return true;
    }

    void TNestConvex::triangulate(TPointQueueVector& convexQueue, TPointPairVector& pointPairVector)
    {
    	TPointQueue outside, inside;
    	int i, j, k;
    	int counter;
    	bool inDone, outDone;
    	TPoint outPoint, inPoint, nextIn, nextOut;
    	float result;
    	if (convexQueue.size()<=1)
    	{
    		return;
    	}
    	for (i=0; i<convexQueue.size()-1; i++)
    	{
    		outside=convexQueue[i];
    		inside=convexQueue[i+1];
    		//printf("outside queue:\n");
    		//printQueue(outside);

    		//printf("inside queue:\n");
    		//printQueue(inside);

    		j=k=0;
    		printf("\n");
    		if (inside.size()>1)
    		{
    			counter=inside.size()+outside.size();
    		}
    		else
    		{
    			counter=outside.size();
    		}

    		//initially both the leftmost point pair will be stored

    		while (true)
    		{
    			outPoint=outside[j];
    			inPoint=inside[k];
    			//printf("outside[%f,%f],inside[%f,%f]\n", outPoint.x, outPoint.y, inPoint.x, inPoint.y);
    			pointPairVector.push_back(make_pair(outPoint, inPoint));
    			counter--;
    			if (counter==0)
    			{
    				break;
    			}

    			nextIn=inside[(k+1)%inside.size()];

    			result=direction(&inPoint, &nextIn, &outPoint);

    			//here for the case the inside has only ONE vertex, the result is always 0
    			//so, we move outside when result is zero
    			if (result>0)
    			{
    				//move outside
    				k=(k+1)%inside.size();

    			}
    			else
    			{
    				j=(j+1)%outside.size();
    			}

    		}

    	}

    	outside=convexQueue.back();

    	outPoint=outside[0];
    	for (i=2; i<outside.size(); i++)
    	{
    		inPoint=outside[i];
    		//printf("outside[%f,%f],inside[%f,%f]\n", outPoint.x, outPoint.y, inPoint.x, inPoint.y);
    		pointPairVector.push_back(make_pair(outPoint, inPoint));
    	}

    }

    void TBoard::makeEdge(TPoint& first, TPoint& second, TEdge& result)
    {
    	if (prevPoint(first, second))
    	{
    		result.pairPoint[0]=first;
    		result.pairPoint[1]=second;
    	}
    	else
    	{
    		result.pairPoint[0]=second;
    		result.pairPoint[1]=first;
    	}
    }

    void TBoard::makeFace(TPoint& p1, TPoint& p2, TPoint& p3, TFace& result)
    {
    	TEdge* swap;
    	makeEdge(p1, p2, *result.edges[0]);
    	makeEdge(p1, p3, *result.edges[1]);
    	makeEdge(p2, p3, *result.edges[2]);

    	//find the smallest edge
    	//bubble sorting??
    	for (int i=0; i<2; i++)
    	{
    		for (int j=i+1; j<3; j++)
    		{
    			if (!prevEdge(result.edges[i], result.edges[j]))
    			{
    				swap=result.edges[i];
    				result.edges[i]=result.edges[j];
    				result.edges[j]=swap;
    			}
    		}
    	}
    }

    void TBoard::clear()
    {
    	TEdgePtrSet::iterator eit;
    	TFacePtrSet::iterator fit;
    	for (eit=edgePtrSet.begin(); eit!=edgePtrSet.end(); eit++)
    	{
    		delete *eit;
    	}
    	edgePtrSet.clear();
    	for (fit=facePtrSet.begin(); fit!=facePtrSet.end(); fit++)
    	{
    		delete *fit;
    	}
    	facePtrSet.clear();
    }

    void TBoard::drawEdge()
    {
    	TEdgePtrSet::iterator eit;
    	for (eit=edgePtrSet.begin(); eit!=edgePtrSet.end(); eit++)
    	{
    		(*eit)->draw();
    	}
    }

    void TBoard::drawFace()
    {
    	TFacePtrSet::iterator fit;

    	for (fit=facePtrSet.begin(); fit!=facePtrSet.end(); fit++)
    	{
    		(*fit)->draw();
    	}
    }

    void TBoard::draw()
    {
    	TEdgePtrSet::iterator eit;
    	TFacePtrSet::iterator fit;

    	for (fit=facePtrSet.begin(); fit!=facePtrSet.end(); fit++)
    	{
    		(*fit)->draw();
    	}
    	for (eit=edgePtrSet.begin(); eit!=edgePtrSet.end(); eit++)
    	{
    		(*eit)->draw();
    	}

    }

    TFace* TBoard::linearSearch(TPoint& point)
    {
    	TFacePtrSet::iterator it, stop;
    	for (it=facePtrSet.begin(); it!=facePtrSet.end(); it++)
    	{
    		if ((*it)->pointInside(point))
    		{
    			return *it;
    		}
    	}
    	return NULL;
    }

    void TBoard::displayFace()
    {
    	TFacePtrSet::iterator fit;
    	printf("display face set\n");
    	for (fit=facePtrSet.begin(); fit!=facePtrSet.end(); fit++)
    	{
    		(*fit)->display();
    	}
    }

    void TBoard::display()
    {
    	TEdgePtrSet::iterator eit;
    	TFacePtrSet::iterator fit;
    	printf("\n\n*********************************\ndisplay edge set\n");
    	for (eit=edgePtrSet.begin(); eit!=edgePtrSet.end(); eit++)
    	{
    		(*eit)->display();
    	}

    	printf("display face set\n");
    	for (fit=facePtrSet.begin(); fit!=facePtrSet.end(); fit++)
    	{
    		(*fit)->display();
    	}
    }

    bool TBoard::sameColor(TFace* him, FaceStatus player)
    {
    	return him->status==player;

    }

    //assume they are same color
    bool TBoard::doSearchSpace(TFace* face, FaceStatus player, TFacePointerSet& path)
    {
    	TFace* neighbour[3];
    	//TFacePointerSet tempPath;
    	TFacePointerSet::iterator it;
    	if (path.find(face)!=path.end())
    	{
    		return false;
    	}
    	if (face->status==Empty)
    	{
    		return true;
    	}
    	//enemy
    	if (face->status!=player)
    	{
    		return false;
    	}
    	//before that, let' place face into path

    	path.insert(face);
    	//otherwise it must be friend and we search recursively
    	//find three neighbours
    	getNeighbour(face, neighbour);

    	for (int i=0; i<3; i++)
    	{
    		if (neighbour[i]!=NULL)
    		{
    			if (path.find(neighbour[i])==path.end())
    			{
    				//new path
    				if (neighbour[i]->status==Empty)
    				{
    					return true;
    				}

    				if (neighbour[i]->status==player)
    				{
    					//avoid infinite loop, we check path at beginning, so don't add it here
    					//and each sub-path search is independant, so, we give separate path
    					/*
    					tempPath.clear();
    					for (it=path.begin(); it!=path.end(); it++)
    					{
    						tempPath.insert(*it);
    					}
    					if (doSearchSpace(neighbour[i], player, tempPath))
    					{
    						return true;
    					}
    					*/
    					if (doSearchSpace(neighbour[i], player, path))
    					{
    						return true;
    					}

    				}
    			}
    			//else nothing
    		}
    	}
    	//after all,
    	return false;//no chance to survive
    }

    void TBoard::getNeighbour(TFace* face, TFace* neighbour[3])
    {
    	for (int i=0; i<3; i++)
    	{
    		if (face->edges[i]->faces[0]==face)
    		{
    			//doing little testing here
    			if (face->edges[i]->faces[1]==face)
    			{
    				printf("data corrupted! two neighbour are the same!\n");
    				exit(8);
    			}
    			neighbour[i]=face->edges[i]->faces[1];
    		}
    		else
    		{
    			//doing little testing here
    			if (face->edges[i]->faces[1]!=face)
    			{
    				printf("data corrupted! face itself is not the neighbour!\n");
    				exit(8);
    			}
    			neighbour[i]=face->edges[i]->faces[0];
    		}
    	}
    }

    bool TBoard::controlBy(TFace* face, FaceStatus& status, TFacePointerSet& path)
    {
    	/*
    	TFace* neighbours[3];

    	FaceStatus tempStatus;

    	bool color[2];

    	if (!path.insert(face).second)
    	{
    		return false;
    	}

    	color[0]=color[1]=false;

    	getNeighbour(*it, neighbours);
    	for (int i=0; i<3; i++)
    	{
    		if (neighbours[i]!=NULL)
    		{
    			if (neighbours[i]->status==Empty)
    			{
    				if (controlBy(neighbours[i], tempStatus, path))
    				{

    			color[neighbours[i]->status]=true;
    		}
    	}
    	if (color[Empty]||(color[Red]&&color[Blue]))
    	{
    		mutualCount++;
    	}
    	else
    	{
    		if (color[Red])
    		{
    */
    	return true;
    }

    /*
    TFace* TBoard::binarySearch(TPoint& point)
    {
    	TFace face;
    	TEdge edges[3];
    	int i;
    	TFacePtrSet::iterator it;

    	for (i=0; i<3; i++)
    	{
    		face.edges[i]=edges+i;
    	}
    	makeFace(point, point, point, face);

    	it=facePtrSet.upper_bound(&face);

    	while (it!=facePtrSet.end())
    	{
    		if ((*it)->pointInside(point))
    		{
    			return *it;
    		}
    		it++;
    	}

    	return NULL;
    }
    */

    int TBoard::countTriangle()
    {
    	TFacePointerSet path;
    	FaceStatus status;
    	TFacePtrSet::iterator it;
    	for (int i=0; i<3; i++)
    	{
    		controlCounter[i]=0;
    	}
    	for (it=facePtrSet.begin(); it!=facePtrSet.end(); it++)
    	{
    		if ((*it)->status!=Empty)
    		{
    			controlCounter[(*it)->status]++;
    		}
    		else
    		{
    			path.clear();
    			if (controlBy(*it, status, path))
    			{
    				controlCounter[status]++;
    			}
    			else
    			{
    				printf("unknown error\n");
    				exit(8);
    			}
    		}
    	}
    	return -1;
    }

    bool TBoard::validMove(TFace* face, FaceStatus player, bool justTest)
    {
    	TFace* neighbour[3];
    	TFacePointerSet path;
    	FaceStatus enemy;
    	int i;
    	bool canKill=false;
    	bool isValid=false;

    	//if non-empty, no good move
    	if (face->status==Red || face->status==Blue)
    	{
    		return false;
    	}

    	getNeighbour(face, neighbour);
    	//so here, but if we do place our
    	//chess piece, can we kill enemy? So, we need to test enemy's life
    	//first temparorily change the status of face

    	face->status=player;
    	//now test if enemy will survive
    	enemy=(player==Red)?Blue:Red;

    	for (i=0; i<3; i++)
    	{
    		if (neighbour[i]!=NULL)
    		{
    			if (neighbour[i]->status==Empty)
    			{
    				isValid=true;
    				break;
    			}

    			if (neighbour[i]->status==player)
    			{
    				//avoid infinite loop, we check path at beginning, so don't add it here
    				//and each sub-path search is independant, so, we give separate path
    				path.clear();
    				path.insert(face);

    				if (doSearchSpace(neighbour[i], player, path))
    				{
    					isValid=true;
    					break;
    				}
    			}
    			//else nothing we ignore
    		}
    	}

    	canKill=false;

    	for (i=0; i<3; i++)
    	{
    		if (neighbour[i]!=NULL)
    		{
    			if (neighbour[i]->status==enemy)
    			{
    				//avoid infinite loop, we check path at beginning, so don't add it here
    				//and each sub-path search is independant, so, we give separate path
    				path.clear();

    				if (!doSearchSpace(neighbour[i], enemy, path))
    				{
    					canKill=true;
    					if (!justTest)
    					{
    						removeEnemy(neighbour[i], enemy);
    					}
    				}
    			}
    			//else nothing we ignore
    		}
    	}
    	//always reset original status, because we may just do testing
    	face->status=Empty;
    	if (canKill)
    	{
    		return true;//
    	}
    	else
    	{
    		//we need to change status back
    		return isValid;
    	}
    }

    void TBoard::removeEnemy(TFace* face, FaceStatus enemy)
    {
    	TFace* neighbour[3];
    	getNeighbour(face, neighbour);

    	face->status=Empty;
    	memcpy(face->color, playerColor[Empty], sizeof(TColor));
    	for (int i=0; i<3; i++)
    	{
    		if (neighbour[i]!=NULL)
    		{
    			if (neighbour[i]->status==enemy)
    			{
    				neighbour[i]->status=Empty;
    				removeEnemy(neighbour[i], enemy);//recursive
    			}
    		}
    	}
    }

    bool TBoard::insertFace(TPoint& p1, TPoint& p2, TPoint& p3)
    {
    	TFace* face;
    	TEdge edges[3];
    	TEdge* edge;
    	int i;
    	TColor color;
    	TEdgePtrSet::iterator it;

    	face=new TFace;
    	face->status=Empty;
    	for (i=0; i<3; i++)
    	{
    		//temporary assign these edges
    		face->edges[i]=edges+i;
    		//color[i]=((edgePtrSet.size()*rand()%10+3)*2)/40.0;
    	}

    	makeFace(p1, p2, p3, *face);

    	for (i=0; i<3; i++)
    	{
    		it=edgePtrSet.find(face->edges[i]);

    		if (it==edgePtrSet.end())
    		{
    			//now replace real allocated edge with those temp edges
    			edge=new TEdge;

    			edge->faces[0]=face;
    			edge->faces[1]=NULL;//assume unknown
    			memcpy(edge->pairPoint, face->edges[i]->pairPoint, sizeof(TPairPoint));
    			memcpy(edge->color, green, sizeof(TColor));
    			edgePtrSet.insert(it, edge);
    			face->edges[i]=edge;
    		}
    		else
    		{
    			face->edges[i]=*it;
    			//doing a little testing here
    			if (face->edges[i]->faces[0]==NULL)
    			{
    				printf("data corrupted, dangling edge found\n");
    				exit(8);
    			}
    			if (face->edges[i]->faces[1]!=NULL)
    			{
    				printf("\n******************************************\n");
    				printf("\n\n**********\ndata corrupted, one edge attached with three faces\n");
    				printf("\nand here is the repeat edge\n");
    				face->edges[i]->display();

    				printf("\n************show us the face problem***************\n");
    				face->display();

    				printf("\n*****************and all faces are**********************\n");
    				displayFace();
    				return false;
    				//exit(5);
    			}
    			face->edges[i]->faces[1]=face;
    		}

    		//face->edges[j]=new TEdge;
    	}
    	//now add the new face into face set
    	memcpy(face->color, beige, sizeof(TColor));
    	facePtrSet.insert(face);
    	return true;
    	//printf("now display the board\n");
    	//displayFace();
    }

    void TBoard::makeBoard(TTriangleQueue& triangleQueue)
    {
    	TFace* face;
    	TEdge edges[3];
    	TEdge* edge;
    	int i, j;
    	TColor color;
    	TEdgePtrSet::iterator it;
    	for (i=0; i<triangleQueue.size(); i++)
    	{
    		face=new TFace;
    		for (j=0; j<3; j++)
    		{
    			//temporary assign these edges
    			face->edges[j]=edges+j;
    			//color[j]=i*30+j*40;
    		}

    		makeFace(triangleQueue[i].triangle[0], triangleQueue[i].triangle[1],
    			triangleQueue[i].triangle[2], *face);

    		for (j=0; j<3; j++)
    		{
    			it=edgePtrSet.find(face->edges[j]);

    			if (it==edgePtrSet.end())
    			{
    				//now replace real allocated edge with those temp edges
    				edge=new TEdge;

    				edge->faces[0]=face;
    				edge->faces[1]=NULL;//assume unknown
    				memcpy(edge->pairPoint, face->edges[j]->pairPoint, sizeof(TPairPoint));
    				memcpy(edge->color, green, sizeof(TColor));
    				edgePtrSet.insert(it, edge);
    				face->edges[j]=edge;
    			}
    			else
    			{
    				face->edges[j]=*it;
    				//doing a little testing here
    				if (face->edges[j]->faces[0]==NULL)
    				{
    					printf("data corrupted, dangling edge found\n");
    					exit(8);
    				}
    				if (face->edges[j]->faces[1]!=NULL)
    				{
    					printf("\n******************************************\n");
    					printf("\n\n**********\ndata corrupted, one edge attached with three faces\n");
    					printf("\nand here is the repeat edge\n");
    					face->edges[j]->display();

    					printf("\n************show us the face problem***************\n");
    					face->display();

    					printf("\n*****************and all faces are**********************\n");
    					displayFace();
    					continue;
    					//exit(5);
    				}
    				face->edges[j]->faces[1]=face;
    			}

    			//face->edges[j]=new TEdge;
    		}
    		//now add the new face into face set
    		memcpy(face->color, color, sizeof(TColor));
    		facePtrSet.insert(face);
    		//printf("now display the board\n");
    		//displayFace();
    	}
    }

    file name: main.cpp

    /*********************************************************
    nest convex:
    1000: 1.3sec
    5000: 5sec
    10000: 16sec

    triangulation:
    1000: 0.3sec
    5000: 1.3sec
    10000: 1.6sec

    *********************************************************/

    #include "common.h"
    #include "ConvexHull.h"
    //#include <windows.h>

    #include <GL/glut.h>
    #include <vector>
    #include <deque>
    #include <utility>
    #include <ctime>

    using namespace std;

    extern vector<TPointContext> separateVector;
    extern vector<TPointContext> connectVector;
    TPointPairVector pairVector;

    TTriangleQueue triangleQueue;
    extern TConvex convex;
    extern TPolygon polygon;

    bool gameEnd=false;

    FaceStatus player=Red;

    TPointQueue pointQueue;
    TPointQueueVector convexQueueVector;
    TPointSet pointSet;
    TPointPairVector pointPairVector;

    TFacePtrVector facePtrVector;

    TBoard board;

    bool showBoard=true;

    TFacePtrSet::iterator fit;

    void outputMessage();
    void output(int x, int y, char *str);

    void drawAxis()
    {
    	glLineWidth(1);
    	glBegin(GL_LINES);
    	glColor3fv(beige);
    	glVertex2f(MaxIntegerValue,0);
    	glColor3fv(red);
    	glVertex2f(-MaxIntegerValue, 0);
    	glEnd();

    	glBegin(GL_LINES);
    	glColor3fv(beige);
    	glVertex2f(0, -MaxIntegerValue);
    	glColor3fv(red);
    	glVertex2f(0, MaxIntegerValue);
    	glEnd();

    }

    void clearAll()
    {
    	separateVector.clear();
    	connectVector.clear();
    	pairVector.clear();
    	convexQueueVector.clear();
    	pointPairVector.clear();
    	pairVector.clear();
    	triangleQueue.clear();
    	player=Red;
    	gameEnd=false;
    }

    int index=0;

    void displayMenu()
    {
    	printf("\n***********************************************\n");
    	printf("<<<<<<<<<<<<<Welcome To TrianGO>>>>>>>>>>>>>>>>>>\n");
    	printf("<<<<<<<<<<<<<A Game of GO on Triangle>>>>>>>>>>>>\n");
    	printf("Operation:\n\
    a)	create random points: by right click mouse or press 'n'; \n\
    b)	create nested convex hull:  by press 'n'. \n\
    c)	create triangulation: press 't'. \n\
    d)	start playing: left click triangles in chess board. \n\
    	restart: press 'a' to clear everything. \n\
    	show menu: press 'm' \n\
    	exit: press 'esc'\n");

    	printf("\n***********************************************\n");
    }

    void displayCallback()
    {
    	int separateNumber, connectNumber, pairNumber, i, j;
    	glClearColor(1,1,0,1);
    	glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);

    	//separateNumber=separateVector.size();
    	separateNumber=separateVector.size();
    	connectNumber=connectVector.size();
    	pairNumber=pairVector.size();

    	//connectNumber=0;

    	glPointSize(5.0);
    	glLineWidth(5);

    	if (connectNumber>0)
    	{

    		glBegin(GL_LINE_LOOP);
    		for (i=0; i<connectNumber; i++)
    		{
    			glColor3fv(connectVector[i].pointColor);
    			glVertex2f(connectVector[i].point.x, connectVector[i].point.y);
    			//printf("x=%f, y=%f\n", connectVector[i].pointPtr->x,
    			//	connectVector[i].pointPtr->y);

    		}
    		glEnd();

    		glBegin(GL_POINTS);
    		for (i=0; i<connectNumber; i++)
    		{
    			glColor3fv(connectVector[i].pointColor);
    			glVertex2f(connectVector[i].point.x, connectVector[i].point.y);

    			//printf("x=%f, y=%f\n", separateVector[i].pointPtr->x, separateVector[i].pointPtr->y);
    		}
    		glEnd();

    	}
    	if (separateNumber>0)
    	{
    		glBegin(GL_POINTS);
    		for (i=0; i<separateNumber; i++)
    		{
    			glColor3fv(separateVector[i].pointColor);
    			glVertex2f(separateVector[i].point.x, separateVector[i].point.y);

    			//printf("x=%f, y=%f\n", separateVector[i].pointPtr->x, separateVector[i].pointPtr->y);
    		}
    		glEnd();
    	}
    	if (pairNumber>0)
    	{
    		for (i=0; i<pairNumber; i++)
    		{
    			glBegin(GL_LINES);
    			glColor3fv(blue);
    			glVertex2f(pairVector[i].first.x, pairVector[i].first.y);
    			glColor3fv(blue);
    			glVertex2f(pairVector[i].second.x, pairVector[i].second.y);

    			glEnd();
    		}
    	}

    	for (i=0; i<convexQueueVector.size(); i++)
    	{
    		glBegin(GL_LINE_LOOP);
    		for (j=0; j<convexQueueVector[i].size(); j++)
    		{
    			glColor3fv(red);

    			glVertex2f(convexQueueVector[i][j].x, convexQueueVector[i][j].y);
    		}
    		glEnd();
    	}

    	if (triangleQueue.size()>0)
    	{
    		triangleQueue[index].draw();
    	}

    	//board.draw();
    	if (showBoard)
    	{
    		/*
    		for (i=0; i<facePtrVector.size(); i++)
    		{
    			facePtrVector[i]->draw();
    		}
    		*/
    		board.drawFace();

    	}

    	//board.drawEdge();

    	//drawAxis();

    	outputMessage();

    	glutSwapBuffers();
    	//glutPostRedisplay();
    }

    void outputMessage()
    {
    	TFacePtrSet::iterator it;
    	const int CharHeight=15;
    	char msg[20];
    	int winner;
    	int counter[3]={0};
    	static char* playerName[4]={"RED", "BLUE", "EMPTY", "NOBODY"};
    	int currentx, currenty;

    	for (it=board.facePtrSet.begin(); it!=board.facePtrSet.end(); it++)
    	{
    		counter[(*it)->status]++;
    	}

    	currentx=-winSize_width/2+2;
    	currenty=winSize_height/2-CharHeight;

    	sprintf(msg, "[PLAYER] %s", playerName[player]);
    	output(currentx, currenty, msg);
    	currenty-=CharHeight;

    	for (int i=0; i<3; i++)
    	{
    		sprintf(msg, "[%s] %d", playerName[i], counter[i]);
    		output(currentx, currenty, msg);
    		currenty-=CharHeight;
    	}
    	if (gameEnd)
    	{
    		if (counter[Red]>counter[Blue])
    		{
    			winner=Red;
    		}
    		else
    		{
    			if (counter[Red]<counter[Blue])
    			{
    				winner=Blue;
    			}
    			else
    			{
    				winner=3;
    			}
    		}
    		sprintf(msg, "[WINNER] %s!", playerName[winner]);
    		output(currentx, currenty, msg);
    	}
    }

    void output(int x, int y, char *str)
    {
    	int len, i;
    	glColor3fv(red);
    	glRasterPos2f(x, y);
    	len = (int) strlen(str);
    	for (i = 0; i < len; i++)
    	{
    		glutBitmapCharacter(GLUT_BITMAP_8_BY_13 , str[i]);
    	}
    }

    void keyboardCallback(unsigned char key, int x, int y)
    {
    	//int i;
    	//bool noProblem=false;
    	TPointContext pointContext;
    	unsigned long int startSec;

    	TPointPair pointPair;
    	TPointQueue::iterator it;
    	TPointSet::iterator setIt;
    	TFacePtrSet::iterator fit;
    	//float coord[4];
    	switch (key)
    	{
    	case 27:
    		exit(0);
    		break;
    	case 's':
    		//convex.generatePoint(10);
    		generateRandomPoint(10, pointSet);
    		for (setIt=pointSet.begin(); setIt!=pointSet.end(); setIt++)
    		{
    			pointContext.point=*setIt;
    			memcpy(pointContext.pointColor, red, sizeof(TColor));

    			separateVector.push_back(pointContext);

    		}
    		/*
    		for (setIt=convex.pointSet.begin(); setIt!=convex.pointSet.end(); setIt++)
    		{
    			memcpy(pointContext.pointColor, red, sizeof(TColor));
    			pointContext.point=*setIt;
    			separateVector.push_back(pointContext);
    		}
    		*/
    		break;
    	case 'm':
    		displayMenu();
    		break;
    	case 'c':
    		convex.convexHull(pointSet, pointQueue);
    		for (it=pointQueue.begin(); it!=pointQueue.end(); it++)
    		{
    			memcpy(pointContext.pointColor, green, sizeof(TColor));
    			pointContext.point=*it;
    			connectVector.push_back(pointContext);

    		}
    		break;

    	case 'p':
    		pointQueue.clear();
    		polygon.createPolygon(11, pointQueue);
    		for (it=pointQueue.begin(); it!=pointQueue.end(); it++)
    		{
    			memcpy(pointContext.pointColor, blue, sizeof(TColor));
    			pointContext.point=*it;
    			connectVector.push_back(pointContext);
    			//glutPostRedisplay();
    		}
    		break;
    	case 'e':
    		separateVector.clear();
    		connectVector.clear();
    		break;
    	case 'n':
    		if (pointSet.size()==0)
    		{
    			generateRandomPoint(8, pointSet);
    		}
    		convexQueueVector.clear();
    		startSec=glutGet(GLUT_ELAPSED_TIME);
    		TNestConvex::nestConvex(pointSet, convexQueueVector);
    		startSec=glutGet(GLUT_ELAPSED_TIME)-startSec;
    		//printf("nest convex time takes %d milli seconds\n", startSec);

    		//TNestConvex::triangulate(convexQueueVector, pointPairVector);

    		//pairVector.insert(pairVector.end(), pointPairVector.begin(), pointPairVector.end());

    		break;
    	case 'r':
    		startSec=glutGet(GLUT_ELAPSED_TIME);
    		TNestConvex::triangulate(convexQueueVector, pointPairVector);
    		startSec=glutGet(GLUT_ELAPSED_TIME)-startSec;
    		//printf("triangulation time takes %d milli seconds\n", startSec);
    		pairVector.insert(pairVector.end(), pointPairVector.begin(), pointPairVector.end());
    		break;
    	case 'a':
    		separateVector.clear();
    		connectVector.clear();
    		pairVector.clear();
    		convexQueueVector.clear();
    		pointPairVector.clear();
    		pointSet.clear();
    		triangleQueue.clear();
    		board.clear();
    		displayMenu();
    		break;

    	case 't':
    		//triangleQueue.clear();
    		startSec=glutGet(GLUT_ELAPSED_TIME);
    		showBoard=TNestConvex::triangulate(convexQueueVector, board);

    		startSec=glutGet(GLUT_ELAPSED_TIME)-startSec;
    		//printf("triangulation time takes %d milli seconds\n", startSec);
    		/*
    		for (i=0; i<triangleQueue.size(); i++)
    		{
    			printf("triangle retrieved\n");
    			triangleQueue[i].display();
    		}
    		*/
    		if (showBoard)
    		{
    			//board.makeBoard(triangleQueue);

    			clearAll();
    		}

    		break;

    	case 'g':
    		index=(index+1)%triangleQueue.size();
    		break;

    	}
    	glutPostRedisplay();
    }

    void reshapeCallback(int width, int height)
    {
    	glutPostRedisplay();
    }

    void init()
    {
    	displayMenu();
    	glShadeModel(GL_FLAT);
    	//glShadeModel(GL_SMOOTH);
    	gluOrtho2D((float)winSize_width/-2.0, (float)winSize_width/2.0,
    		(float)winSize_height/-2.0, (float)winSize_height/2.0);
    }

    void mouseCallback(int button, int state, int x, int y)
    {
    	TPoint point;
    	TFacePtrSet::iterator it;
    	TFace* face;
    	FaceStatus enemy;
    	//printf("coord[x=%d,y=%d]\n", x, y);
    	point.x=x-winSize_width/2;
    	point.y=winSize_height/2-y;
    	TPointContext pointContext;

    	if (button==GLUT_LEFT_BUTTON &&state==GLUT_DOWN)
    	{
    		face=board.linearSearch(point);
    		if (face!=NULL)
    		{
    			//showBoard=false;
    			//board.checkColor(face, redPlayer);
    			if (board.validMove(face, player))
    			{
    				memcpy(face->color, playerColor[player], sizeof(TColor));
    				face->status=player;
    				enemy=(player==Red)?Blue:Red;

    				//but before that, let's see if it is end of game.
    				gameEnd=true;

    				for (it=board.facePtrSet.begin(); it!=board.facePtrSet.end(); it++)
    				{
    					if (board.validMove(*it, enemy, true))
    					{
    						gameEnd=false;
    						break;
    					}
    				}
    				player=(player==Red)?Blue:Red;
    				glutPostRedisplay();
    			}
    		}

    	}
    	if (button==GLUT_RIGHT_BUTTON &&state==GLUT_DOWN)
    	{
    		pointSet.insert(point);
    		pointContext.point=point;
    		memcpy(pointContext.pointColor, red, sizeof(TColor));
    		separateVector.push_back(pointContext);
    		glutPostRedisplay();
    	}
    }

    int main(int argc, char** argv)
    {
    	srand(time(0));
    	glutInit(&argc, argv);
    	glutInitWindowPosition(winPos_x, winPos_y);
    	glutInitWindowSize(winSize_width, winSize_height);
    	glutInitDisplayMode(GLUT_RGBA|GLUT_ALPHA|GLUT_DOUBLE);
    	glutCreateWindow(windowTitle);

    	glutMouseFunc(mouseCallback);
    	glutDisplayFunc(displayCallback);
    	glutKeyboardFunc(keyboardCallback);
    	glutReshapeFunc(reshapeCallback);

    	init();

    	//printf("before convex hull\n");
    	//convex.display();

    	//convex.convexHull(pointSet);
    	//printf("after convex hull\n");
    	//pointSet.display();
    	//glutPostRedisplay();
    	//glutShowWindow();

    	glutMainLoop();

    	return 0;
    }