Geometry & Recognition

static 
int ccw(const CPoint& A, const CPoint& B, const CPoint& C) {
    // cross (C-A, B-A) >= 0 이면 AB의 오른쪽에 C가 놓임;
    int cax = C.x - A.x;
    int cay = C.y - A.y;
    int bax = B.x - A.x;
    int bay = B.y - A.y;
    return (cax * bay - cay * bax) >= 0; 
}

// lower-hull은 x-증가: y-감소로 정렬;
static int cmpl(const void *a, const void *b) {
    int v = ((CPoint *)a)->x - ((CPoint *)b)->x;       
    if (v > 0) return  1; 
    if (v < 0) return -1;
    v = ((CPoint *)b)->y - ((CPoint *)a)->y;
    if (v > 0) return 1; 
    if (v < 0) return -1;
    return 0;
}
// upper-hull은 x-감소: y-증가로 정렬;
static int cmph(const void *a, const void *b) {
    return cmpl(b, a);
}

static 
int makeChain(CPoint *V, int n, int (*cmp)(const void*, const void*)) {
    qsort(V, n, sizeof(CPoint), cmp);
    // 점 i (>j))가 현재까지 생성된 hull(s까지)의 에지보다도 더 오른쪽에 있으면, 
    // 왼쪽에 위치할 때까지 기존 hull을 줄이고. (i)를 hull에 추가.
    int s = 1;
    for (int i = 2; i < n; i++) {
        int j = s;
        while(j >= 1 && ccw(V[j-1], V[j], V[i])) j--;
        // ccw의 =때문에 일직선상의 마지막점만 들어감;
        s = j + 1; // j = last index of hull;
        // (j+1)에 새 hull-point을 추가:
        CPoint t = V[i]; V[i] = V[s]; V[s] = t;
    }
    return s;
}
std::vector<CPoint> chainHull2(const std::vector<CPoint>& P) {
    if (P.size() < 3) return std::vector<CPoint> (); //null_vector;
    // copy to working array;
    std::vector<CPoint> chull(P.size()+1);
    for (int i = P.size(); i-->0;) chull[i] = P[i];
    /* make lower hull;*/
    int u = makeChain(&chull[0], P.size(), cmpl);      
    /* make upper hull;*/   
    chull.back()= chull.front();
    u += makeChain(&chull[u], P.size() - u + 1, cmph); 
    chull.resize(u);
    return chull;
}