hye0.log hye0.log

그라함 스캔 알고리즘

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

  Computer Science/Algorithm 2021. 12. 15. 12:28

  그라함 스캔 알고리즘 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 점이 가장 작은 점을 선택한 후, 그 점에서 부터 가장 작은 각도를 만드는 순서대로 번호를 매겨줍니다. 처음 ..

  Read More