Creating Simple Polygons

기하 알고리즘, 특히 폴리곤 관련 알고리즘을 테스트하려면 먼저 다양한 형태의 폴리곤 데이터를 생성해야 한다. 여기서는 2차원 점집합으로부터 간단하게 simple polygon을 생성하는 방법을 소개한다.

Simple polygon을 생성하기 위해서는 먼저 점들을 일정한 순서로 정렬해야 한다. 가장 간단한 방법은 각 점을 $x\,$축에 정사영하여 $x\,$좌표의 오름차순으로 정렬하는 것이다. 동일한 $x\,$좌표를 갖는 점은 $y\,$좌표의 오름차순으로 정렬한다. 이렇게 정렬된 점들을 차례대로 연결하면 하나의 polyline을 얻을 수 있다. 그러나 polyline의 양 끝점을 단순히 연결한다고 해서 항상 simple polygon이 만들어지는 것은 아니다. 경우에 따라서는 변들이 서로 교차하는 자기 교차 다각형(self-intersecting polygon)이 생성될 수 있다.

이를 방지하기 위해 가장 작은 $x\,$좌표를 갖는 점과 가장 큰 $x\,$좌표를 갖는 점을 연결하는 직선을 기준선으로 사용한다. 각 점을 이 직선의 위쪽과 아래쪽으로 분류한 뒤, 위쪽에 있는 점들은 $x\,$좌표가 큰 순서로, 아래쪽에 있는 점들은 $x\,$좌표가 작은 순서로 정렬한다. 마지막으로 아래쪽 점들을 차례대로 연결한 후 위쪽 점들을 역순으로 연결하면, 모든 점을 한 번씩 지나는 simple polygon을 얻을 수 있다.

이 방법은 구현이 간단하고 계산량도 작기 때문에 기하 알고리즘을 시험하기 위한 테스트 데이터를 생성하는 데 널리 사용된다.

// cross(CB, AB)
// A->B-C: 반시계(C가 AB 왼편: > 0), 시계(C가 AB오른편: < 0), 일직선(0);
int CCW(const CPoint& A, const CPoint& B, const CPoint& C) {
    const CPoint CB = C - B, AB = A - B;
    return CB.x * AB.y - CB.y * AB.x;
}
// x가 커지는(같으면 y가 커지는) 순서로 정렬;
bool compare(const CPoint &a, const CPoint& b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
std::vector<CPoint> makeSimplePolygon(const std::vector<CPoint>& pts) {
    if (pts.size() < 1) return std::vector<CPoint> (); //null_vector;
    int rightId = 0, leftId = 0;
    for (int i = pts.size(); i-->1;) {
        if (pts[i].x > pts[rightId].x) rightId = i;
        if (pts[i].x < pts[leftId].x) leftId = i;
    }
    std::vector<CPoint> LP, RP;
    for (int i = 0; i < pts.size(); i++) {
        if (i == rightId || i == leftId) continue;
        // 기준선의 왼편(LP)/오른편(RP)에 놓인 점 분리;
        if (CCW(pts[leftId], pts[rightId], pts[i]) >= 0) LP.push_back(pts[i]); 
        else RP.push_back(pts[i]);
    }
    if (LP.size() > 0) std::sort(LP.begin(), LP.end(), compare);
    if (RP.size() > 0) std::sort(RP.begin(), RP.end(), compare);
	
    std::vector<CPoint> sploy;
    spoly.reserve(LP.size()+RP.size()+2);
    spoly.push_back(pts[leftId]);
    for (int i = 0; i < LP.size(); i++) spoly.push_back(LP[i]);
    spoly.push_back(pts[rightId]);
    for (int i = RP.size(); i-->0;) spoly.push_back(RP[i]);
    // spoly = clockwise simple polygon;
    return spoly;
};

또 다른 방법은 앞에서 사용한 기준선을 그대로 이용하는 것이다. 먼저 기준선 아래쪽에 있는 점들로 convex hull을 구성한 뒤, 기준선 위쪽에 있는 나머지 점들은 앞에서 설명한 방법과 같이 정렬하여 두 경계를 연결하면 simple polygon을 얻을 수 있다.

보다 간단한 방법도 있다. 먼저 기준점 하나를 선택한 후, 나머지 점들을 그 점에 대한 극각(polar angle)의 증가 순으로 정렬한다. 기준점으로는 가장 아래쪽에 있는 점을 선택하고, 같은 $y\,$좌표를 갖는 점이 여러 개이면 그중 가장 오른쪽에 있는 점을 사용하는 것이 편리하다. 이렇게 정렬된 점들을 차례대로 연결한 뒤 마지막 점을 기준점과 연결하면 simple polygon을 얻을 수 있다.

 

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

**네이버 블로그에서 이전;