---
tags: Geometry
title: Convex Hull
---

# 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 $\angle p_is_1s_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;
}