A. First Edition

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

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.

E.Further improvement

F.File listing

1. ConvexHull.h

2. ConvexHull.cpp

file name: convex.h

#include <vector>

using namespace std;

const int MaxIntegerValue=100;



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(int pointNumber);
	void display();

	

	void convexHull(TPointSet& pointSet);
};

file name: convex.cpp

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

using namespace std;

TPoint* Convex::ptrArray=NULL;

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

//randomly generating points
Convex::Convex(int pointNumber)
{
	number=pointNumber;
	ptrArray=new TPoint[number];
	for (int i=0; i<number; i++)
	{
		ptrArray[i].x=generateRandomValue();
		ptrArray[i].y=generateRandomValue();
	}
}

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


int main()
{
	Convex convex(10);
	TPointSet pointSet;

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

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

	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