Brute Force Convex Hull Algorithm

Convex hull은 집합으로 주어진 점이나 영역을 포함하는 가장 작은 볼록 집합이다. 알려진 알고리즘으로는 

1. Jarvis March (Gift Wrap)

2. Graham scan

3. Quick hull (Chain hull)

4. Monotone chain

5.......

여기서는 소개하는 convex hull 알고리즘은 가장 기초적인 알고리즘이다. 두 점에 의해서 만들어지는 선분이 convex hull의 일부이면 나머지 점들은 항상 왼편(설정에 따라 오른편으로 해도 된다)에 있게 된다는 사실을 이용한다. N개의 점이 있을 떄 가능한 선분의 수는 N(N-1) (방향까지 고려함)이고, 나머지 점에 대해서 테스트를 해야 하므로 총 비교 횟수는 N(N-1)(N-2) ~ O(N^3) 정도이다. 알고리즘의 구현이 간단하고, 단순 비교연산이므로 매우 robust해서 점집합의 크기가 작을 때 효과적이다.

 

static int ccw(CPoint A, CPoint B, CPoint P) ; // cross(AB, AP) > 0 if <ABP> is ccw;

static int ccw(CPoint A, CPoint B, CPoint P) { //cross(AB, AP) > 0 if <ABP> is ccw;
    return ((B.x - A.x) * (P.y - A.y) - (B.y - A.y) * (P.x - A.x));
}

std::vector<CPoint> BruteForceConvexHull(const std::vector<CPoint>& pts) {
    // O(n^3) ;
    if (pts.size() < 3) return std::vector<CPoint> (); //null_vector;
    std::vector<std::pair<int,int>> edges;
    for (int i = 0; i < pts.size(); i++) {
        for (int j = 0; j < pts.size(); j++) {
            if (pts[j] == pts[i]) continue;     //에지는 중복점이 아닌 경우만(점을 비교해야 함)
            bool onHull = true;
            for (int k = 0; k < pts.size(); k++) {
                if (pts[k] == pts[i] || pts[k] == pts[j]) continue;
                if (ccw(pts[i], pts[j], pts[k]) < 0) {  // cw;
                    onHull = false;                     // (i,j) is not an edge;
                    break ;
                }
            }
            if (onHull)  //(i->j) edge is on the hull;
                edges.push_back(std::make_pair(i, j));
        }
    }
    if (edges.size() < 1) return std::vector<CPoint> ();
    // hull을 구성하는 에지정보에서 단순폴리곤 만들기(bug 수정);
    std::vector<CPoint> hull; hull.reserve(edges.size());
    int currIdx = 0;
    hull.push_back(pts[edges[currIdx].first]);
    hull.push_back(pts[edges[currIdx].second]);
    while (edges[currIdx].second != edges[0].first) {
        for (int j = edges.size(); j-->0;) 
            if (edges[j].first == edges[currIdx].second) {
                currIdx = j;
                hull.push_back(pts[edges[currIdx].second]);
                break;
            }
        if (hull.size()==edges.size()) break; //마지막==처음 중복을 피하기 위해
    }
    return hull;
};

convex hull의 edge가 중간에 (collinear) 점을 포함하지 않도록 하기 위해서는, ccw == 0일 때 ABC가 접혀있는지를 체크하면 된다.