Andrew's Monotone Chain Algorithm

From CodeCodex

This is a C++ implementation of Andrew's Monotone Chain algorithm to find the convex hull, given a set of points.

Input Format:
Number of points in set (int)
3 4
6 20
...
#include <vector>
#include <iostream>
using namespace std;

// Global Vars and Structs
struct Point {
	int x;
	int y;
    };
int MaxPts;

// Function prototypes
int CrossProd(const Point Orig, const Point A, const Point B);
vector<Point> convexHull(vector<Point> P);
void Sort (Point P[]);

int main()
{
    // Input Data
    cin >> MaxPts;
    Point PointArray[MaxPts];
    for (int i = 0; i < MaxPts; i++) {
        cin >> PointArray[i].x;
        cin >> PointArray[i].y;
        }

    // Sort
    Sort(PointArray);

    // Convert to Vector
    vector<Point> PointVect(PointArray, PointArray+MaxPts);

    // Calculate Hull
    vector<Point> OutVect = convexHull(PointVect);

    // Output
    cout << endl << endl << "The points of the convex hull are:" << endl;
    for (vector<Point>::iterator iter = OutVect.begin(); iter != OutVect.end();iter++) {
        cout << "(" << iter->x << ", " << iter->y << ")" << endl;
        }
}

vector<Point> convexHull(const vector<Point> &P)
{
    // Init Vars
    int W = P.size(), Z = 0;
    vector<Point> H(MaxPts * 2);

    // Build lower hull
    for (int i = 0; i < W; i++) {
        while (Z >= 2 && CrossProd(H[Z-2], H[Z-1], P[i]) <= 0)
            Z--;
        H[Z++] = P[i];
        }

    // Build upper hull
    for (int i = W-2, t = Z+1; i >= 0; i--) {
        while (Z >= t && CrossProd(H[Z-2], H[Z-1], P[i]) <= 0)
            Z--;
        H[Z++] = P[i];
        }

    H.resize(Z);
    H.erase(H.begin());
    return H;
}

int CrossProd(const Point &Orig, const Point &A, const Point &B)
{
	return (A.x - Orig.x) * (B.y - Orig.y) - (A.y - Orig.y) * (B.x - Orig.x);
}

void Sort (Point P[])
{
    for( int i=0; i<MaxPts-1; i++ ) {
        for( int j=1; j<MaxPts; j++) {

            if( P[j].x < P[j-1].x ) {
                temp=P[j];
                P[j]=P[j-1];
                P[j-1]=temp;
                }

            else if( P[j].x == P[j-1].x ) {
                if( P[j].y < P[j-1].y ) {
                    temp=P[j];
                    P[j]=P[j-1];
                    P[j-1]=temp;
                    }
                }
            }
        }
}