convex.cpp

#include <iostream>
#include <vector>
#include <stack>
#include <stdlib.h>
#include <algorithm>
#include <cfloat>
using namespace std;

struct Point {
  Point():x(0), y(0){}
  Point(float x, float y):x(x), y(y){}
  float x, y;
};

vector<int> convexhull(const vector<Point> &pts) {
  int n = pts.size();
  if( n < 3 ) return vector<int>();

  float minX = FLT_MAX, minY = FLT_MAX;
  for(auto &pt : pts ) {
    minX = min(pt.x, minX);
    minY = min(pt.y, minY);
  }
  
  Point origin(minX, minY);
  vector<pair<Point, int>> p(n);
  for(int i=0;i<n;++i) {
    p[i] = make_pair(pts[i], i);
  }
  
  std::sort(p.begin(), p.end(), [=](const pair<Point, int>& a, const pair<Point, int> &b){
    float dya = a.first.y - origin.y, dxa = a.first.x - origin.x;
    float dyb = b.first.y - origin.y, dxb = b.first.x - origin.x;
    float thetaA = atan2(dya, dxa);
    float thetaB = atan2(dyb, dxb);
    if( thetaA < thetaB ) return true;
    else if( thetaA == thetaB ) return dxa < dxb;
    else return false;
  });
  
  vector<int> S;
  S.push_back(0); S.push_back(1);
  int nxt = 2;
  while( nxt <= n ) {
    int cur = S.back(); S.pop_back();
    int pre = S.back();

    const Point& pcur = p[cur].first;
    const Point& ppre = p[pre].first;
    const Point& pnxt = p[nxt%n].first;
    
    float v1x = pcur.x - ppre.x, v1y = pcur.y - ppre.y;
    float v2x = pnxt.x - pcur.x, v2y = pnxt.y - pcur.y;

    float dotproduct = v1x * v2x + v1y * v2y;
    float crossproduct = v1x * v2y - v2x * v1y;
    
    if( crossproduct > 0 || crossproduct == 0 &&  dotproduct > 0 ) {
      S.push_back(cur);
      if( nxt == n ) break;
      S.push_back(nxt);
      ++nxt;
    }
  }
  
  vector<int> res;
  for(int i=0;i<S.size();++i) {
    res.push_back(p[S[i]].second);
  }
  return res;
}

int main(int argc, char **argv) {
  vector<Point> v;
  v.push_back(Point(0, 0));
  v.push_back(Point(1, 0));
  v.push_back(Point(2, 1));
  v.push_back(Point(2, 0));
  v.push_back(Point(1, 2));
  v.push_back(Point(1, 1));
  v.push_back(Point(0, 2));
  v.push_back(Point(2, 2));
  
  vector<int> res = convexhull(v);
  for(auto idx : res) {
    cout << v[idx].x << ", " << v[idx].y << endl;
  }
  return 0;
}