[공유] simple polygon 만들기

helloktk의 블로그 | 드라곤
원문 https://blog.naver.com/helloktk/80028346861
기하 알고리즘을 특히 폴리곤알고리즘을 테스트하기 위해서는 폴리곤 데이터를 만들어야 한다. 여기서 2차원의 점들을 이용하여 간단히 simple polygon을 만드는 방법을 살펴본다.

단순폴리곤을 만들기 위해서는 점들을 정렬을 해야한다.
각각의 점들을 X축에 프로젝션을 시키면 x축에 대해서 정렬이 된다(같은 x값인경우에는 의 크기대로 정렬).
따라서 x값으로 정렬된 점들을 쭉 이어나가면 하나늬 폴리라인(poly-line)을 만들 수 있다.
그러나 원하는 폴리곤은 아니다.
이를 해결하기위해서는 점들을 직선으로 두부분으로 나누고, 직선의 윗부분은 x값이 큰순서대로 정렬을 하고, 아래 부분은 x값이 작은 순서대로 정열을 하면 폴리라인이 아닌 폴리곤을 얻을 수 있다.
직선은 어떻게 잡을까? 이것은 가장작은 x값을 갖는 점과 가장 큰 x값을 같는 점을 잇는 직선을 생각하면 편리하다.

int CCW(CPoint A, CPoint B, CPoint C) {
    C -= B;                              //점B에서 C로 향하는 선분의 왼편인가, 아니면 오른편인가;
    A -= B;
    return C.x*A.y-C.y*A.x;
}
int comp(const void*A, const void *B) {//x->y의 크기순서대로 정렬용;
    int a=((POINT *)A)->x - ((POINT *)B)->x ;
    if(a>0) return 1 ;
    else if(a<0) return -1;
    a=((POINT *)A)->y - ((POINT *)B)->y ;
    if(a>0) return 1;
    else if(a<0) return -1;
    return 0;
}
void MakeSimplePolygon(POINT P[], int N, POINT Q[]) {

    int maxx=P[0].x, minx=P[0].x;
    int maxid=0, minid=0;
    for(int i=1;i<N; i++){
        if(P[i].x>maxx) { maxx=P[i].x ; maxid=i;}
        if(P[i].x<minx) { minx=P[i].x ; minid=i ;}
    }
    POINT B=P[maxid], A=P[minid];
    int lcnt,rcnt;
    POINT *LP=new POINT [N];
    POINT *RP=new POINT [N];
    for(i=0,rcnt=0,lcnt=0; i<N; i++){
        if(i==maxid||i==minid) continue;
        int ccw=CCW(P[i],A, B) ;
        if(ccw>=0) LP[lcnt++]=P[i];      //기준선의 왼편과 오른편에 놓인 점들을 분리함;
        else RP[rcnt++]=P[i];
    }
    qsort(LP, lcnt, sizeof(POINT), comp);
    qsort(RP, rcnt, sizeof(POINT), comp);

    int k=0;

    Q[k++]=P[minid];
    for(i=0; i<lcnt; i++) Q[k++]=LP[i];
    Q[k++]=P[maxid];
    for(i=rcnt-1; i>=0; i--) Q[k++]=RP[i];

    delete[] LP;
    delete[] RP;

}

다른 방법으로는 위와 같은 직선을 만들고, 아래부분의 점들의 convex hull을 구성하고, 나머지 점들을 마찬가지의 방법으로 정렬을 하여 폴리곤을 만들거나,
아니면 한 점을 잡아서(맨 아래 오른쪽) 그점을 기준으로 해서 나머지 점들을 각도에 대해서 정렬을 한다음 그 정렬된 순서대로 폴리곤을 구성하면 된다.

기준점에 대한 각도를 정렬하여 만든 예(동일한 각도가 생기는 경우에는 기준점에서의 거리로 비교)