Andrew's Monotone Chain Algorithm
From CodeCodex
This is a C++ implementation of Andrew's Monotone Chain algorithm to find the convex hull if 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;
}
}
}
}
}

