Special case: 2-Dimensional space

Graham's Scan

• First choose a trivial point
  $p_0$ that it must be in convex hull (leftmost and lowest).
• sort all the other points in polar angle order, getting
  $\{p_1,\dots ,p_n\}$.
• let
  $s=\{p_0,p_1\}=\{s_2,s_1\}$(reversed order).
• let
  $i=2$.
• while
  $i<n$ do the following:
  If
  $|s|<2$ or
  $\mathrm{\angle }{p}_i{s}_1{s}_2$ is convex, then let
  $s=s\cup \{p_i\}$, and
  $i=i+1$.
  If not,
  $s=s\setminus \{s_1\}$.
• then
  $s$ is a convex hull

Implementation Issue:

Polar angle sort may cause dividing by

$0$, or two points with the same tangent.

Optimizing: Monotone Chain

Divide the question into upper convex hull and lower convex hull,
and there are points at infinitely low and infinitely high respectively.
Then we don't really need to do polar angle sort, what we need is just sort by coordinate.

Implementation

vector<point> ConvexHull(vector<point>& pts) {
    int n = pts.size();
    
    // lower monotone chain
    sort(pts.begin(), pts.end(), [](const point& a, const point& b){
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    });
    vector<point> chain(1, pts[0]);
    for (int i = 1; i < n;) {
        int bk = chain.size() - 1;
        
        if (bk == 0 || (chain[bk] - chain[bk - 1]) ^ (pts[i] - chain[bk]) > 0)
            chain.push_back(pts[i++]);
        else chain.pop_back();
    }
    
    // upper monotone chain
    vector<point> chain2(1, pts.back());
    for (int i = n - 2; i >= 0;) {
        int bk = chain2.size() - 1;
        
        if (bk == 0 || (chain2[bk] - chain2[bk - 1]) ^ (pts[i] - chain2[bk]) > 0)
            chain2.push_back(pts[i--]);
        else chain2.pop_back();
    }
    
    // remove duplicate points
    chain.pop_back();
    chain2.pop_back();
    
    // combine lower chain and upper chain to convex hull
    chain.insert(chain.end(), chain2.begin(), chain2.end());
    
    return chain;
}