Convex hull

helloktk의 블로그 | ㅇ
http://blog.naver.com/helloktk/80025507906 평면상의 영역이 convex하다는 의미는 그 영역에 속하는 임의의 두점을 연결하는 선분상의 모든 점들 또한 해당영역에 속하는 경우을 의미한다.
점들의 모임에서 convex hull을 찾는 것은 점들을 잇는 선분자체가 포함되는 다각형을 찾는 것을 의미한다.
간단하게 생각할 수 있는 방법은 최외각의 한점을 기준으로해서(점들을 감싸는 최소 사각형상의 한점) 그 자신을 뺀 모든 점들이 왼편이나 일직선상에 놓일수 있는 점을 찾는다.
다시 이 찾은 점을 기준으로 나머지점들에 대해서 동일한 조건을 만족하는 점들을 차례로 찾으면, 주어진 점들을 감싸는 최소의 점들의 모임을 구할 수 있고, 이것이 convex hull을 구성한다(Gift Wrap).
이 알고리즘은 n개의 점들에 대해서 각각 O(n)정도의 찾기를 시도하므로 전체적으로 O(n^2)정도의 스텝이 필요한 알고리즘이다.
여기서 찾는 과정을 좀더 빠르게 할 수 있다면 전반적인 알고리즘의 복잡도도 감소한다.
 따라서 점들은 우선 일정한 순서대로 정열을 하고난 후에 순차적으로 들어오는 점들이 왼편에 있는가만 판별하면 되는 과정으로 줄일 수 있다.

---

이제 conex hull을 구하는 알고리즘중에서 잘알려진 Graham Scan 알고리즘을 살펴보도록 하자.
이 알고리즘은 앞에서 설명한 과정을 그대로 따라 진행이 되는데, 우선 점들을 맨 바깥쪽에 있는 한점
(점들을 감싸는 최소 사각형상의 임의의 한점이면 충분하다. 보통은 최저의 y값을 갖는 점들중에 최대의 x값을 갖는 점으로 기준점으로  잡는다)을
기준으로 해서 각도의 크기로 점들을 정열을 해 둔상태에서 진행이 된다.
정열방법은 기준점을 각도를 계산하여 정열을 할 수 있으나, 각도수치계산의 부정확성과 복잡한 삼각함수 연산에 의존하는 것보다는 기하학적인 배치를 고려하면 된다.
i=2인점이 기준점(i=0)과 i=1인 점이 이루는 직선의 오른쪽에 놓이면 i=1과 바꾸는 식으로 하면 정열이 쉽게된다
(두 점이 기준점을 지나는 일직선상에 놓인 경우에는 기준점에서 먼 점만 넣으면 된다. 

반시계방향(counterclockwise)으로 정열된 주어진 점들의 집합을 ${P[i], i=0, 1, 2, ..., N-1}$ 이라고 할 때, Graham Scan 알고리즘의 pseudo code는 

Push P[0] and P[1] onto a stack;

	i=2;
    while(i<N){
        Let PT1=the top point on stack ;
        Let PT2=the second top point on stack ;
        if (P[i] is strictly left of the line PT2 to PT1) {
            Push P[i] onto stack ;
            i++;    //increment (i);
        }else{
            Pop the top point PT1 off the stack ;
        }
    }

/*c-source*/

//각도를 기준으로 CCW로 정열하는 루틴으로 배열의 처음점은 y-값이 가장 작아야하며,
//x값은 가장 큰것으로 swap해야 한다.
int angular_sort(POINT P[], int N, POINT Q[])
{
    //P[0]==lowest and rightmost point;

    //Q[] = 정렬된 점들을 담는 배열로, 크기는 N이어야 한다.
    int i, j, k;
    Q[0]=P[0]; Q[1]=P[1];
    k=2;
    for(i=2; i<N; i++){
        int ccw=LEFTSIDE(Q[0],Q[k-1],P[i]);
        if(ccw>0){//LEFT ;
            Q[k]=P[i];k++; //push;
        }else if(ccw==0) {//on the line;
            //일직선상에 있는 경우에는 가까운 점은 제거하고, 먼점만 선택;
             if(DIST2(Q[0],P[i])>DIST2(Q[0],Q[k-1])){
                Q[k-1]=P[i];
             } 
             //만약에 일직선상에 있는 점들을 모두 보전하고자 하면, Q[0]에서 거리 순서대로
             //정렬을 하고, Scan과정에서 ccw==0인 경우를 넣어야 한다.
        }else if(ccw<0){
            for(j=k-2; j>0; j--){
                ccw=LEFT(Q[0],Q[j], P[i]);
                if (ccw>0) {//LEFT
                     INSERT(Q, j+1, P[i]); //Q(j+1)에 P[i]를 넣고,상위 Q는 이동,                      
                     k++;  break;
                }else if(ccw==0){ //ON THE LINE; 먼점만 선택
                     if(DIST2(Q[0],P[i])>DIST2(Q[0],Q[j])){
                          Q[j]=P[i]; break;
                     }
                }
            }
            if(j==0 && ccw<0){
                INSERT(Q,1,P[i]);//P[i]을 Q의 1번째에 넣고,상위Q는 이동;/
                k++;
            }
       }
   }

   return (k); //일직선상에 있는 점들을 제거하였으므로 k<=N;
}
 
int  graham_scan(POINT P[], int N, POINT Stack[])
{
   //P[]는 반시계방향으로 정렬이 된 상태의 배열이어야하고, statck의 크기는 N만큼 되어야 한다.

    int i=0, k=0;
    Stack[0]=P[0];
    Stack[1]=P[1];
    i=k=2;
   while(i<N) {
       POINT PT1=Stack[k-1]; //최상위 ;
       POINT PT2=Stack[k-2];  //차상위;
      if ( LEFTSIDE(PT2,PT1,P[i]) > 0 ) {
           Stack[k]=P[i]; k++ ;      //push P[i];
           i++ ;
      }else{
          k--;                                   //pop PT1;
      }
   }
   return (k); //number of convex hull points;
}

첨부한 화일은 위에서 설명한 알고리즘의 과정을 MFC를 써서 구현하였습니다.(첨부한 소스를 사용시 반드시 출처를 남겨주기바랍니다.)