알고리즘 : ConvexHull (Graham's Scan)

외곽선 찾기(ConvexHull) 알고리즘

1. 개요

2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 나머지 모든 점을 내부에 포함하는 다각형을 만든다. 이를 볼록 껍질(CONVEX HULL) 이라 한다.

아래 그림은 N=10인 경우의 한 예.

2. 알고리즘 : Graham's Scan 사용

(1) P0을 선택합니다.

  - P0은 y축 가장 아래에 위치한 점을 선택합니다.

  - 가장 아래 위치한 점이 여러 개 존재 시 x축 가장 좌측을 선택합니다.

(2) P0을 기준으로 모든 점들에 대한 각도를 구한다.

(3) 구한 점들의 각도 중 가장 낮은 각을 가진 점을 순서대로 P1, P2 선택

(4) 다음 점 Pn을 선택하여, 점을 추가 할 것인지 교체 할 것인지 정한다.

  - 이전 두 점에 대해 조건 검색을 하여, 조건에 만족하지 않으면 해당 점을 Pn과 교체하며, 만족하면 Pn을 추가한다.

   - 조건 : 선택된 점[Pn]이 선[Pn-2Pn-1(->)]에서 왼쪽(반시계 방향)에 위치하면 Pn을 추가,

             오른쪽(시계방향)에 위치하면 점[Pn]을 점[Pn-1]과 교체한다.

  * 이 때 선의 방향을 유의하자. 선은 Pn-2 -> Pn-1.

(5) 모든 점에 대한 (4)의 탐색이 끝나면 선택된 점을 연결한다.

3. 소스설명

** 사용된 자료구조

//점의 정보를 담을 구조체

struct  Point

{

int x, y

float angle

};

std::vector <Point> PointLocate //생성한 모든 점은 벡터를 통해 관리

std::stack <Point> ConvexPoint //선정된 점은 스택에 Push

가. P0 구하기

- 벡터[0]에 P0을 위치시킨다.

void FirstPoint(std::vector <Point> &PointLocate)

{

FOR 1 TO Vector Size

IF Vector[0].y < Vector[i].y

SWAP

ELSE IF (Vector.y == Vector.y)

IF Vector.x > Vector.x

SWAP

}

나. P0와 점들의 각도 구하기

  - atan2()를 이용해 두 점의 각을 구하고 Degree로 변환

void PointAngle(std::vector<Point> &PointLocate)

{

for (unsigned int i = 1; i < PointLocate.size(); i++)

{

//P2.x - P1.x, P2.y - P1.y

cx = (float)Vector[i].x - (float)Vector[0].x;

cy = (float)Vector[i].y - (float)Vector[0].y;

angle = atan2(cy, cx); //각도 구함.

angle = angle * 180 / (float)PI; //Degree로 표현

Vector[i].angle = fabs(angle); //각에 대한 절대값

}

}

다. 구해진 각에 대해 정렬 후 P0, P1, P2로 선택

  - Vector[0] = P0, 이후 크기 순으로 오름차순 정렬

  - Sort 함수 사용

bool Comp(Point &angle, Point &angle2)

{

return angle.angle < angle2.angle

}

void PointSort(std::vector<Point> &PointLocate, std::stack<Point> &ConvexPoint)

{

int nSize = Vector.size();

sort(Vector.begin(), Vector.end(), Comp); //오름차순 정렬

Stack.push(Vector[0]); //P0

Stack.push(Vector[1]); //P1

Stack.push(Vector[2]); //P2

}

라. 나머지 점들에 대해 ConvexPoint 조건 판단 후 선택 및 교체

void PointSearch(std::vector<Point> &PointLocate, std::stack<Point> &ConvexPoint)

{

FOR 3 TO Vector SIze

WHILE ccw(P1, P2, Vector[i]) <= 0) //시계 방향이면 POP Stack.pop();

Stack.push(Vector[i]);

}

int ccw(Point p1, Point p2, Point p3)

{

//선[Pn-2Pn-1]에 대한 점[Pn]의 위치 판단

return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);

}

4. 실행결과

5. 기타

  - MFC GDI를 사용해 표현

  - 점을 원으로 표현하였기 때문에 외곽으로 원의 일부가 삐져나올 수 있으나, 좌표 상으로는 선 내부에 포함됨.

  - 5000개 이상 생성 시 정신건강에 해로움

6. 소스파일 및 실행파일 첨부

HnS17_ConvexHull.zip