[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[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.