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[0])); // 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.

Well thank you CodeSmuggler!

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

orient2dexact takes 3 points. It returns value greater than zero if points occurs in counter clockwise order, value Check out implementation of this function on this site: http://www.cs.cmu.edu/~quake/robust.html in "software" paragraph.

You have to compute the determinant of the square matrix 3×3 and return it.