A. First Edition

This is simple practicing of computational geometry. The algorithm is a fast convex hull generating algorithm.

This is just a little add-on on previous convex hull so that it displays processes in OpenGL window. And in 

purpose of keeping version, I posted it here.

B.The problem

　

The definition of convex hull of a set of points P is that you need to find a subset of P such that the polygon consisted of this subset of points is the smallest convex which contains set P.

　

C.The idea of program

　

Graham’s Scan-type Algorithm (p. 6 of CGAA)

Algorithm CONVEXHULL(P)

Input. A set P of points in the plane.

Output. A list L containing the vertices of C H (P) in clockwise order.

1. Sort the points by x-coordinate, resulting in a sequence p1, . . . , pn.

2. Put the points p1 and p2 in a list Lupper, with p1 as the first point.

3. for i 3 to n

4. do Append pi to Lupper.

5. while Lupper contains more than two points and the last

three points in Lupper do not make a right turn

6. do Delete the middle of the last three points from Lupper.

7. Similar for Llower (except right to left). (And you need to remove the first and last to avoid duplicate points)

　

D.The major functions

The "qsort" needs a callback function and the callback needs to access point array of Convex class. So, I have 

to make the Point array of Convex static data member. 

To merge the upper and lower part, remove the first and last of lower part to avoid duplicated points.

There is nothing special about this implementation because it is just a mechanic coding according to pseudo code

in text book. However, I am a bit satisfied with my coding speed which is about one and half hour. It proves

I am alive cause I can do the coding.

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

F.File listing

1. ConvexHull.h

2. ConvexHull.cpp

file name: convex.h

#include <vector>

using namespace std;

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

const int MaxIntegerValue=winSize_width/2-1;


struct TPoint
{
	float x;
	float y;
	void display();	
};

float direction(const TPoint& p, const TPoint& q, const TPoint& r);

class TPointSet
{
public:
	~TPointSet();
	TPointSet();
	int number;
	TPoint* ptrArray;
	void setArray(TPoint* inputArray, int inputNumber);

	void display();

	
};

class Convex
{
private:
	int number;
	float generateRandomValue();
	int* indexArray;
	void sortPoint();
	vector<int> upVector;
	vector<int> downVector;
	void collectVertex(vector<int>& intVector, bool upper);
	void addPoint(vector<int>& intVector, int rIndex);
public:
	static TPoint* ptrArray;

	Convex();
	void generatePoint(int pointNumber);
	void display();
	void convexHull(TPointSet& pointSet);
};

file name: convex.cpp

#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;
}

running result:

before convex hull
[x=-40.806694,y=0.479873]
[x=78.822838,y=-63.141056]
[x=-80.696007,y=-90.635551]
[x=27.988525,y=4.004669]
[x=92.531662,y=16.607166]
[x=47.450790,y=-37.392315]
[x=-66.480118,y=-93.273323]
[x=-21.460646,y=-63.764671]
[x=53.779655,y=44.999695]
[x=-36.733788,y=-40.976257]

after convex hull

[x=-80.696007,y=-90.635551]
[x=-40.806694,y=0.479873]
[x=53.779655,y=44.999695]
[x=92.531662,y=16.607166]
[x=78.822838,y=-63.141056]
[x=-66.480118,y=-93.273323]
Press any key to continue