Convex Hull

    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)

¡¡

The advantage of this algorithm is that the time complexity is O(nlg(n)). I asked professor whether the pre-

processing sorting is necessary. Professor's explanation is convincing. The average of time complexity of unsorted is still O(nlg(n)). And the worst case can be O(n^2).

Another advantage is that the numeric error won't create disconnected convex even though the error points may

be outside convex. However, practically it is acceptable.

¡¡

    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

    ¡¡