728x90

볼록 다각형(convex polygon)에서 한 방향으로(예를 들면 y-축방향) 가장 멀리 떨어진 두 꼭지점(antipodal points) 통과하는 평행한 두 직선을 생각해보자. 평행 직선의 방향은 이 경우에는 x-축(y-축과 수직)과 나란해야 한다 . 이제 두 평행 직선의 방향을 각각의 꼭지점을 축으로 해서 조금씩 회전시키면, 둘 중 하나는 볼록 다각형에 먼저 접하게 된다. 이 접하는 변을 기준으로 다시 antipodal point을  찾아 (당연히 접하지 않는 평행직선이 통과하는 꼭지점이 된다) 새로운 평행 직선을 구성한 후 동일한 과정을 반복한다. 이 과정을 N회 반복하면 볼록 다각형의 모든 변에 대해서 변을 공유하는 직선과 그 직선의 antipodal point를 찾을 수 있다. 

이 rotating calipers를 이용하면 convex hull의 bounding box, convex hull의 diameter, convex polygon 사이 거리 등의 계산에 응용할 수 있다.

double COS(CPoint A, CPoint B) {             // directional cosine;
    double norm2A = A.x * A.x + A.y * A.y;
    double norm2B = B.x * B.x + B.y * B.y;
    return (A.x * B.x + A.y * B.y) / sqrt(norm2A * norm2B);
}
int ccw(CPoint A, CPoint B, CPoint C) {     // cross(AB, BC); 반시계방향 > 0;
    return (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x) ;
}
// find antipodal points along y-direction;
bool initCalipers(std::vector<CPoint> &Q, 
                 int &minid, double &minCos,
                 int &maxid, double &maxCos) {
    int N = Q.size();
    // ccw check (중복 // 일직선을 고려);
    int orient = 0;
    for (int i = 0; i < N; i++) {
        orient = ccw(Q[(i - 1 + N) % N], Q[i], Q[(i + 1) % N]);
        if (orient != 0) break;
    }
    if (orient == 0) return false;

    minid = maxid = 0;
    for (int i = 1; i < N; i++) {
        if (Q[i].y < Q[minid].y) minid = i;
        if (Q[i].y > Q[maxid].y) maxid = i;
    }

    CPoint n0 = CPoint(1, 0);
    if (orient < 0) n0 = -n0;  // convex hull이 CW인 경우;
    CPoint dir0 = Q[(minid + 1) % N] - Q[minid];
    CPoint dir1 = Q[(maxid + 1) % N] - Q[maxid];
    minCos = COS(dir0, n0);
    maxCos = COS(dir1, -n0);
    return true;
}
int rotatingCalipers(std::vector<CPoint> &Q,
                    int &i0, double &dirCos0,
                    int &i1, double &dirCos1) {
    int N = Q.size();
    int i0next = (i0 + 1) % N ;
    int i1next = (i1 + 1) % N ;
    CPoint dir0 = Q[i0next] - Q[i0];
    CPoint dir1 = Q[i1next] - Q[i1];
    if (dirCos0 > dirCos1) {          // i0을 포함하는 평행선이 다음 edge와 이루는 각이 작음;
        CPoint ndir0 = Q[(i0next + 1) % N] - Q[i0next]; // 각을 재는 기준선은 현재 다다음 edge;
        dirCos0 = COS(ndir0, dir0);    
        dirCos1 = COS(dir1, -dir0);    
        i0 = i0next;                  // i0는 다음 꼭지점으로 이동; i1 = antipodal point;
        return 0;
    } else {                          // i1을 포함하는 평행선이 다음 edge와 이루는 각이 작음
        CPoint ndir1 = Q[(i1next + 1) % N] - Q[i1next];
        dirCos1 = COS(ndir1, dir1);   
        dirCos0 = COS(dir0, -dir1);   
        i1 = i1next;                  // i1은 다음 꼭지점으로 이동; i0 = antipodal point;
        return 1;
    }
}
void runCalipers(std::vector<CPoint> &Q) {
    int i0, i1;
    double dirCos0, dirCos1;
    bool done = false;
    if (!initCalipers(Q, i0, dirCos0, i1, dirCos1)) return ;  // fails
    while (!done) {
    	int i0old = i0, i1old = i1;
        if (rotatingCalipers(Q, i0, dirCos0, i1, dirCos1) == 0) {
            // Q[i1] = antipodal point;
            // do something useful...
        } else {
            // Q[i0] = antipodal point;
            // do something useful...
        }
    }
};

'Computational Geometry' 카테고리의 다른 글

Bezier Curve Approximation of a Circle  (0) 2021.04.10
Bresenham's Line Algorithm  (0) 2021.04.07
Rotating Calipers  (3) 2021.03.31
Convex Hull Peeling  (0) 2021.03.29
Graham Scan  (0) 2021.03.28
Jarvis March  (0) 2021.03.26
Posted by helloktk

댓글을 달아 주세요

  1. hgmhc 2021.04.04 11:56 신고  댓글주소  수정/삭제  댓글쓰기

    혹시 로테이팅 캘리퍼스의 정당성 증명 자료가 있으신가요?