convex.cpp

cnvex hull with algorith graham

#include "ConvexHull.h"
#include <GL/glut.h>
//#include <GL/glu.h>
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

TPoint* Convex::ptrArray=NULL;

//GLenum drawingMode = GL_POINTS;

typedef GLfloat TColor[3];

TColor red={1,0,0}, green={0,1,0}, blue={0,0,1};

struct TPointContext
{
	TPoint* pointPtr;
	TColor pointColor;
};

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

Convex convex;
TPointSet pointSet;


int pointComp(const void* elem1, const void* elem2)
{
	TPoint *ptr1, *ptr2;
	float result;

	ptr1=Convex::ptrArray + *(const int*)(elem1);
	ptr2=Convex::ptrArray + *(const int*)(elem2);
	result= ptr1->x-ptr2->x;
	if (result>0)
	{
		return 1;
	}
	else
	{
		if (result<0)
		{
			return -1;
		}
		else
		{
			return 0;
		}
	}
}

float direction(const TPoint* p, const TPoint* q, const 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;
}

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

TPointSet::TPointSet()
{
	number=0;
	ptrArray=NULL;
}

void TPointSet::display()
{
	for (int i=0; i<number; i++)
	{
		ptrArray[i].display();
	}
}


TPointSet::~TPointSet()
{
	if (number!=0)
	{
		delete[]ptrArray;
	}
}

void TPointSet::setArray(TPoint* inputArray, int inputNumber)
{
	number=inputNumber;
	ptrArray=new TPoint[number];
	memcpy(ptrArray, inputArray, sizeof(TPoint)*number);
}

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

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

//randomly generating points
Convex::Convex()
{
	number=0;
	ptrArray=NULL;	
}

void Convex::sortPoint()
{
	indexArray=new int[number];
	for (int i=0; i<number; i++)
	{
		indexArray[i]=i;
	}
	qsort(indexArray, number, sizeof(int), pointComp);
}

void Convex::addPoint(vector<int>& intVector, int rIndex)
{
	int currentSize;
	int pIndex, qIndex;
	while (intVector.size()>=2)
	{
		currentSize=intVector.size();
		pIndex=intVector[currentSize-2];
		qIndex=intVector[currentSize-1];

		if (direction(ptrArray+pIndex, ptrArray+qIndex, ptrArray+rIndex)>=0)
		{
			intVector.pop_back();
		}
		else
		{			
			break;
		}
	}
	intVector.push_back(rIndex);
}


void Convex::collectVertex(vector<int>& intVector, bool upper)
{
	int index, offset, counter=number-2;

	intVector.clear();
	if (upper)
	{
		index=0;
		offset=1;
	}
	else
	{
		index=number-1;
		offset=-1;
	}

	intVector.push_back(indexArray[index]);
	index+=offset;
	intVector.push_back(indexArray[index]);
	
	while (counter>0)
	{
		index+=offset;

		addPoint(intVector, indexArray[index]);
		counter--;
	}
}


void Convex::display()
{
	for (int i=0; i<number; i++)
	{
		ptrArray[i].display();
	}
}

void Convex::convexHull(TPointSet& pointSet)
{
	int i;
	int upSize, downSize;
	if (number<3)
	{
		pointSet.setArray(ptrArray, number);
	}
	else
	{
		sortPoint();
		collectVertex(upVector, true);
		collectVertex(downVector, false);
		upSize=upVector.size();
		//we need to remove the first and last
		downSize=downVector.size()-2;
		pointSet.number=upSize+downSize;
		pointSet.ptrArray=new TPoint[pointSet.number];
		for (i=0; i<pointSet.number; i++)
		{
			if (i<upSize)
			{
				pointSet.ptrArray[i]=ptrArray[upVector[i]];
			}
			else
			{
				//starting from second, so add 1
				pointSet.ptrArray[i]=ptrArray[downVector[i-upSize+1]];
			}
		}
	}
}





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

	separateNumber=separateVector.size();
	connectNumber=connectVector.size();

	glPointSize(10.0);
	if (separateNumber>0)
	{
		glBegin(GL_POINTS);
		for (i=0; i<separateNumber; i++)
		{
			glVertex2f(separateVector[i].pointPtr->x, separateVector[i].pointPtr->y);
			glColor3fv(separateVector[i].pointColor);
		}
		glEnd();
	}
	if (connectNumber>0)
	{
		glBegin(GL_LINE_LOOP);
		for (i=0; i<connectNumber; i++)
		{
			glVertex2f(connectVector[i].pointPtr->x, connectVector[i].pointPtr->y);
			glColor3fv(connectVector[i].pointColor);
		}
		glEnd();
	}


	glutSwapBuffers();
	//glutPostRedisplay();
}

void keyboardCallback(unsigned char key, int x, int y)
{
	int i;
	TPointContext pointContext;
	switch (key)
	{
	case 27:
		exit(0);
		break;
	case 's':
		convex.generatePoint(10);
		break;
	case 'c':
		convex.convexHull(pointSet);
		for (i=0; i<pointSet.number; i++)
		{
			memcpy(pointContext.pointColor, green, sizeof(TColor));
			pointContext.pointPtr=pointSet.ptrArray+i;
			connectVector.push_back(pointContext);
			glutPostRedisplay();
		}
		break;
	}
	glutPostRedisplay();
}

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


void init()
{
	gluOrtho2D((float)winSize_width/2.0, (float)winSize_width/-2.0, 
		(float)winSize_height/-2.0, (float)winSize_height/2.0);
}


int main(int argc, char** argv)
{
	glutInit(&argc, argv);
	glutInitWindowPosition(winPos_x, winPos_y);
	glutInitWindowSize(winSize_width, winSize_height);	
	glutInitDisplayMode(GLUT_RGBA|GLUT_ALPHA|GLUT_DOUBLE);
	glutCreateWindow(windowTitle);
	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;
}