[알고리즘] 그라함 스캔 알고리즘

그라함 스캔 알고리즘

• 1972년 로날드 그라함에 의해 개발된 알고리즘
• 주어진 점 집합으로부터 단순 폐쇄 다각형을 만든 다음, y좌표 값이 가장 작은 점부터 시작해 다각형의 꼭지점들을 순서대로 방문하면서 볼록 껍질에 포함될지 여부를 검사하는 것이다.
• 볼록 껍질에 포함되는지 검사 방법
  • p[1], p[2], ..., p[M]이 부분 볼록 껍질이라 하고 새로운 점 p[i]를 추가하고자 할 때, ccw(p[M], p[M-1], p[i])≥ 0 이면 p[M]을 제거
  • p[M-1], p[M], p[i]가 우회전이면, p[M]을 제거하고, 좌회전이면 p[i]를 포함한다.

 

그라함 스캔 알고리즘 동작 과정

먼저 y 점이 가장 작은 점을 선택한 후, 그 점에서 부터 가장 작은 각도를 만드는 순서대로 번호를 매겨줍니다.

처음 3개의 점을 stack에 넣어줍니다.

stack의 위에 두 점(1, 2) 선분에서 그 다음 점으로 갈 때, 시계 방향이라면 stack 맨 위의 값을 pop합니다.

0,1 선분이 그 다음 점 3으로 갈땐, 반시계 방향이므로 stack에 push 해줍니다.

1, 3 선분이 4로 가는 것은 반시계 방향이므로 push 해줍니다

3, 4 선분이 그 다음 점, 5로 가기 위해선 시계방향으로 움직이므로 맨 위에 점인 4를 pop해줍니다.

1,3 선분에서 5로 가는 것은 반시계 방향이므로 push 해줍니다.

3, 5 선분에서 6으로 가는 것은 반시계 방향이므로 push 해줍니다.

5, 6 선분에서 7로 가는 것은 시계 방향이므로 맨 위의 값 6을 pop해줍니다.

3, 5 선분에서 7로 가는 것은 반시계방향이므로 push를 해줍니다. 

5, 7 선분에서 8로 가는 것은 반시계 방향이므로 push해줍니다. 

7, 8 선분에서 9로 가는 것은 시계방향이므로 stack의 맨 위의 값 8을 pop해줍니다.

5, 7 선분에서 9로 가는것도 시계방향이므로 stack의 맨 위의 값 7을 pop 해줍니다.

3, 5 선분에서 9로 가는 것은 반시계방향이므로 push해줍니다. 

5, 9선분에서 10으로 가는 것은 반시계방향이므로 push해줍니다. 

9, 10선분에서 11로 가는 것은 반시계방향이므로 push해줍니다. 

10, 11선분에서 12로 가는것은 시계방향이므로 stack의 맨 위의 값 11을 pop 해줍니다.

 

9, 10선분에서 12로 가는 것은 반시계방향이므로 push해줍니다. 

10, 12선분에서 13로 가는것은 시계방향이므로 stack의 맨 위의 값 12을 pop 해줍니다.

9, 10선분에서 13로 가는것은 시계방향이므로 stack의 맨 위의 값 10을 pop 해줍니다.

5, 9선분에서 13으로 가는 것은 반시계방향이므로 push해줍니다. 

9, 13선분에서 14로 가는 것은 반시계방향이므로 push해줍니다. 

13, 14선분에서 15로 가는 것은 반시계방향이므로 push해줍니다. 

 

스택에 있는 모든 숫자들을 점으로 이어주면 알고리즘 동작과정이 끝난다. 

 

 

 

궁금한 점이 있거나, 틀린 점이 있다면 댓글로 남겨주세요

감사합니다 !