# [C++] Convex hull – Graham algorithm

In this article I will concentrate on Graham algorithm – method of computing convex hull. The complexity of this algorithm is equal to O(nlogn). Assuming that you already know the Graham algorithm, let’s move to the implementation ;)

1. Declare class for computing convex hull:

```/*
* GrahamImplementation.h
*
*  Created on: 2010-10-25
*      Author: codesmuggler
*      Website: http://codesmuggler.com
*/

#ifndef GRAHAMIMPLEMENTATION_H_
#define GRAHAMIMPLEMENTATION_H_

#include "Point.h"
#include
#include

class GrahamImplementation {
public:
GrahamImplementation() {};
// this method does the job -
// given vector of points return convex hull
std::stack compute(std::vector points);
private:
// conve hull points
std::stack cstack;
std::vector points;
// orient point taking 2 points from the top of the points cstack
double orient(Point p);
};

#endif /* GRAHAMIMPLEMENTATION_H_ */
```

2. The Graham algorithm implementation:

```/*
* GrahamImplementation.cpp
*
*  Created on: 2010-10-25
*      Author: codesmuggler
*      Website: http://codesmuggler.com
*/

#include "GrahamImplementation.h"
#include "GeomLib.h"
#include "Utils.h"
#include
#include
#include
#include
#include
using namespace std;

// return true if an angle between
// point A, central point and line
// parallel to the axis OX passing through central point
// is smaller than point B angle
class GrahamAngleComparator {
public:
GrahamAngleComparator(Point c) : central(c) {};
bool operator() (Point a, Point b) {
return getAngle(a)  GrahamImplementation::compute(vector points) {
vector::iterator it = min_element(points.begin(),
points.end(), minComparator);
swap(*it,*points.begin());
sort(points.begin()+1, points.end(),
GrahamAngleComparator(points));

// first 3 points
for(int i=0; i  0) {
cstack.pop();
}
cstack.push(points[i]);
}
return cstack;
}
```

As you see, come functions are cut off of this code snip, but whole algorithm is implemented. I’m leaving missing functions as an exercise for readers ;) I hope implementing Graham algorithm will be an easy task for you after reading this article.

This entry was posted in algorithms, c++, coding and tagged convex hull, graham, . Bookmark the permalink.

### 2 Responses to [C++] Convex hull – Graham algorithm

1. Shirin says:

Well thank you CodeSmuggler!
But I don’t understand the part with member function “orient” I mean what does orient2dexact(Point, stack, Point); return??