Convex Hull

Convex Hull ของ set of points คือ convex polygon ที่เล็กที่สุดที่ครอบคลุมทุกจุด

Andrew’s Monotone Chain Algorithm

$O(n \log n)$ - ง่ายต่อการ implement

vector<Point> convexHull(vector<Point> points) {
    int n = points.size();
    if (n < 3) return points;
    
    sort(points.begin(), points.end());
    
    vector<Point> hull;
    
    // Build lower hull
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2 && 
               (hull[hull.size()-1] - hull[hull.size()-2]).cross(
                points[i] - hull[hull.size()-2]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }
    
    // Build upper hull
    int lower_size = hull.size();
    for (int i = n - 2; i >= 0; i--) {
        while (hull.size() > lower_size && 
               (hull[hull.size()-1] - hull[hull.size()-2]).cross(
                points[i] - hull[hull.size()-2]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }
    
    hull.pop_back();  // Remove last point (duplicate of first)
    return hull;
}

Graham Scan Algorithm

$O(n \log n)$ - classic algorithm

Point pivot;

bool compare(const Point& a, const Point& b) {
    int o = orientation(pivot, a, b);
    if (o == 0) {
        // Collinear: closer point first
        return dist(pivot, a) < dist(pivot, b);
    }
    return o > 0;  // counter-clockwise
}

vector<Point> grahamScan(vector<Point> points) {
    int n = points.size();
    if (n < 3) return points;
    
    // Find bottom-most (or left-most if tie)
    int minIdx = 0;
    for (int i = 1; i < n; i++) {
        if (points[i].y < points[minIdx].y ||
            (points[i].y == points[minIdx].y && points[i].x < points[minIdx].x)) {
            minIdx = i;
        }
    }
    swap(points[0], points[minIdx]);
    pivot = points[0];
    
    // Sort by polar angle
    sort(points.begin() + 1, points.end(), compare);
    
    // Build hull
    vector<Point> hull;
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2 && 
               orientation(hull[hull.size()-2], hull[hull.size()-1], points[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }
    
    return hull;
}

Applications

1. Perimeter of Convex Hull

double hullPerimeter(vector<Point>& hull) {
    double perimeter = 0;
    int n = hull.size();
    
    for (int i = 0; i < n; i++) {
        perimeter += dist(hull[i], hull[(i + 1) % n]);
    }
    
    return perimeter;
}

2. Diameter (Rotating Calipers)

หาคู่จุดที่ห่างกันมากที่สุด

double diameter(vector<Point>& hull) {
    int n = hull.size();
    if (n == 1) return 0;
    if (n == 2) return dist(hull[0], hull[1]);
    
    double maxDist = 0;
    int j = 1;
    
    for (int i = 0; i < n; i++) {
        // Find farthest point from edge (i, i+1)
        while (true) {
            int next = (j + 1) % n;
            double curr = (hull[(i+1)%n] - hull[i]).cross(hull[j] - hull[i]);
            double nextVal = (hull[(i+1)%n] - hull[i]).cross(hull[next] - hull[i]);
            
            if (nextVal > curr) {
                j = next;
            } else {
                break;
            }
        }
        
        maxDist = max(maxDist, dist(hull[i], hull[j]));
        maxDist = max(maxDist, dist(hull[(i+1)%n], hull[j]));
    }
    
    return maxDist;
}

3. Width (Minimum Distance between Parallel Lines)

double width(vector<Point>& hull) {
    int n = hull.size();
    if (n <= 2) return 0;
    
    double minWidth = 1e18;
    int j = 1;
    
    for (int i = 0; i < n; i++) {
        // Find farthest point from edge
        Point edge = hull[(i+1)%n] - hull[i];
        
        while (true) {
            int next = (j + 1) % n;
            if (edge.cross(hull[next] - hull[j]) > 0) {
                j = next;
            } else {
                break;
            }
        }
        
        // Distance from j to line (i, i+1)
        double d = abs(edge.cross(hull[j] - hull[i])) / edge.norm();
        minWidth = min(minWidth, d);
    }
    
    return minWidth;
}

4. Smallest Enclosing Rectangle

tuple<double, Point, Point, Point, Point> minAreaRect(vector<Point>& hull) {
    int n = hull.size();
    if (n <= 2) return {0, {}, {}, {}, {}};
    
    double minArea = 1e18;
    // ... (rotating calipers with 4 pointers)
    
    return {minArea, /*corners*/};
}

5. Point in Convex Polygon (Binary Search)

$O(\log n)$ check if point is inside convex polygon

bool pointInConvexHull(Point p, vector<Point>& hull) {
    int n = hull.size();
    
    // Check if on the correct side of first and last edges
    if (orientation(hull[0], hull[1], p) < 0) return false;
    if (orientation(hull[0], hull[n-1], p) > 0) return false;
    
    // Binary search
    int lo = 1, hi = n - 1;
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        if (orientation(hull[0], hull[mid], p) >= 0) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    
    return orientation(hull[lo], hull[hi], p) >= 0;
}

6. Convex Hull Union

// Merge two convex hulls
vector<Point> mergeHulls(vector<Point>& h1, vector<Point>& h2) {
    vector<Point> all;
    for (auto& p : h1) all.push_back(p);
    for (auto& p : h2) all.push_back(p);
    return convexHull(all);
}

7. Online Convex Hull

class OnlineConvexHull {
    set<Point, function<bool(const Point&, const Point&)>> upper, lower;
    
    // ... (maintain upper and lower hulls separately)
    
public:
    void insert(Point p);
    bool inside(Point p);
};

Complexity

Algorithm	Time	Space
Andrew’s Monotone Chain	$O(n \log n)$	$O(n)$
Graham Scan	$O(n \log n)$	$O(n)$
Jarvis March (Gift Wrapping)	$O(nh)$	$O(h)$
Chan’s Algorithm	$O(n \log h)$	$O(n)$

โดยที่ $h$ = จำนวนจุดบน hull

Tips

1. Collinear points - ตัดสินใจว่าจะรวมหรือไม่ (เปลี่ยน <= เป็น <)
2. Integer coordinates - ใช้ integer cross product เพื่อหลีกเลี่ยง floating point errors
3. Duplicate points - remove duplicates ก่อนถ้าจำเป็น
4. Rotating calipers - ใช้แก้ปัญหาหลายอย่างบน convex hull ใน linear time